Baillie-PSW primality test

From Wikipedia, the free encyclopedia

In number theory, the Baillie-PSW primality test is a probabilistic primality testing heuristic: it determines if a number is composite or a probable prime. The authors of the test offered $30 for the discovery of a composite number that passed this test. As of today, the value was raised to $620 (Guy 1994, p. 28) and no pseudoprime was found up to 10¹⁵, consequently this can be considered a sound primality test on numbers below that upper bound.

A primality testing implementation (PRIMO) uses this algorithm to check for probable primes, and no certification of this test has yet failed. The author, Marcel Martin, estimates by those results that the test is accurate for numbers below 10000 digits. There is a heuristic argument (Pomerance 1984) suggesting that there may be infinitely many counterexamples.

[edit] The test

Perform a base 2 strong pseudoprimality test. If it fails; n is composite. If it doesn't, find the first a in the sequence 5, -7, 9, -11... for which the Jacobi symbol . Then, perform a Lucas pseudoprimality test with discriminant a on n. If this test does not fail, n is likely a prime.

Optionally, one can first perform trial division to check if the number isn't a multiple of a small prime number.

[edit] Notes

1. ^{^}  Pomerance, C. (1984). “Are There Counterexamples to the Baillie-PSW Primality Test?”.
2. ^{^}  Guy, R. (1994). “Pseudoprimes. Euler Pseudoprimes. Strong Pseudoprimes.” $A12 in Unsolved Problems in Number Theory. 2nd ed., New York: Springer-Verlag. ISBN 0-387-20860-7.
3. Thomas R. Nicely. “The Baillie-PSW primality test.”
4. Eric W. Weisstein, Baillie-PSW Primality Test at MathWorld.

v • d • e Number-theoretic algorithms Primality tests AKS · APR · Ballie-PSW · ECPP · Fermat · Lucas–Lehmer · Lucas–Lehmer (Mersenne numbers) · Lucas–Lehmer–Riesel · Proth's theorem · Pépin's · Solovay-Strassen · Miller-Rabin · Trial division Sieving algorithms Sieve of Atkin · Sieve of Eratosthenes · Sieve of Sundaram · Wheel factorization Integer factorization algorithms CFRAC · Dixon's · ECM · Euler's · Pollard's rho · P - 1 · P + 1 · QS · GNFS · SNFS · rational sieve · Fermat's · Shanks' square forms · Trial division · Shor's algorithm Other algorithms Ancient Egyptian multiplication · Aryabhata · Binary GCD · Chakravala · Euclidean · Extended Euclidean · integer relation algorithm · integer square root · Modular exponentiation · Shanks-Tonelli Italics indicate that algorithm is for numbers of special forms; bold indicates deterministic algorithm for primality tests.