info prev up next book cdrom email home

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\Bbb{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


Grantham, J. ``Frobenius Pseudoprimes.'' 1996.

Grantham, J. ``A Frobenius Probable Prime Test with High Confidence.'' 1997.

Grantham, J. ``Pseudoprimes/Probable Primes.''

© 1996-9 Eric W. Weisstein