Frobenius pseudoprime

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In number theory, a Frobenius pseudoprime is a pseudoprime that passes a three-step probable prime test set out by Jon Grantham in 1996.[1][2]

Example[edit]

Frobenius pseudoprimes with respect to polynomial x^2-x-1 form a sequence:

4181, 5777, 6721, 10877, 13201, 15251, 34561, 51841, 64079, ... (sequence A212424 in OEIS)

Properties[edit]

Although a single round of Frobenius is slower than a single round of most standard tests, it has the advantage of a much smaller worst-case per-round error bound of \tfrac{1}{7710},[1] which would require 7 rounds to achieve with the Miller–Rabin primality test according to best known bounds.

Strong Frobenius pseudoprimes[edit]

A strong Frobenius pseudoprime is a pseudoprime which obeys an additional restriction beyond that required for a Frobenius pseudoprime.[3]

See also[edit]

References[edit]

  1. ^ a b Weisstein, Eric W., "Frobenius pseudoprime", MathWorld.
  2. ^ Jon Grantham (2001). "Frobenius pseudoprimes". Mathematics of Computation 70 (234): 873–891. doi:10.1090/S0025-5718-00-01197-2. 
  3. ^ Weisstein, Eric W., "Strong Frobenius pseudoprime", MathWorld.
  • R. Crandall, C. B. Pomerance (2005). Prime Numbers: A Computational Perspective (2nd ed. ed.). Springer. p. 613. ISBN 9780387252827. 

External links[edit]