Frobenius pseudoprime

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

Example

Frobenius pseudoprimes with respect to polynomial $x^{2}-3x-1$ form a sequence:

649, 4187, 12871, 14041, 23479, 24769, 28421, 34997, 38503, 41441, 48577, 50545, 58081, 59081, 61447, 95761, 96139, 116821, 127937, 146329, 150281, 157693, 170039, 180517, 188501, 281017, 321441, 349441, 363091, 397927, 423721, 440833, 473801, 478401, 479119, 493697, ...

These numbers are also Lucas pseudoprime with both definition to (P, Q) = (3, -1). That is, if $U_{n}$ is the 3-Fibonacci number (sequence A006190 in the OEIS), $V_{n}$ is the 3-Lucas number (sequence A006497 in the OEIS), then $U_{n-({\frac {13}{n}})}$ = 0 (mod n) and $V_{n}$ = 3 (mod n) for all n in this sequence, where $({\frac {13}{n}})$ is the Jacobi symbol. However, a composite number which satisfy $U_{n-({\frac {13}{n}})}$ = 0 (mod n) and $V_{n}$ = 3 (mod n) not necessarily be a Frobenius pseudoprime to $x^{2}-3x-1$, a counterexample is 119.

Properties

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}}$. For example, there are only 17 Frobenius pseudoprime to the polynomial $x^{2}-3x-1$ less than 10⁵ (see above). Which would require 7 rounds to achieve with the Miller–Rabin primality test according to best known bounds.

Strong Frobenius pseudoprimes

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

See also

• Pseudoprime
• Lucas pseudoprime
• Ferdinand Georg Frobenius
• Quadratic Frobenius test

References

• R. Crandall, C. B. Pomerance (2005). Prime Numbers: A Computational Perspective (2nd ed. ed.). Springer. p. 613. ISBN 9780387252827. {{cite book}}: |edition= has extra text (help)

External links

• Symmetric Pseudoprimes, MathPages.