TOPICS
Search

Frobenius Pseudoprime


Let f(x) be a monic polynomial of degree d with discriminant Delta. Then an odd integer n with (n,f(0)Delta)=1 is called a Frobenius pseudoprime with respect to f(x) if it passes a certain algorithm given by Grantham (1996). A Frobenius pseudoprime with respect to a polynomial f(x) in Z[x] is then a composite Frobenius probably prime with respect to the polynomial x-a.

While 323 is the first Lucas pseudoprime with respect to the Fibonacci polynomial x^2-x-1, the first Frobenius pseudoprime is 5777. If f(x)=x^3-rx^2+sx-1, then any Frobenius pseudoprime n with respect to f(x) is also a Perrin pseudoprime. Grantham (1997) gives a test based on Frobenius pseudoprimes which is passed by composite numbers with probability at most 1/7710.


See also

Perrin Pseudoprime, Pseudoprime, Strong Frobenius Pseudoprime

Explore with Wolfram|Alpha

References

Grantham, J. "Frobenius Pseudoprimes." 1996. http://www.pseudoprime.com/pseudo1.ps.Grantham, J. "A Frobenius Probable Prime Test with High Confidence." 1997. http://www.pseudoprime.com/pseudo2.ps.Grantham, J. "Pseudoprimes/Probable Primes." http://www.pseudoprime.com/pseudo.html.

Referenced on Wolfram|Alpha

Frobenius Pseudoprime

Cite this as:

Weisstein, Eric W. "Frobenius Pseudoprime." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/FrobeniusPseudoprime.html

Subject classifications