Baillie-PSW primality test
- Baillie-PSW primality test
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 ref_harvard|Guy|Guy 1994, p. 28|none and no pseudoprime was found up to , consequently this can be considered a sound primality test on numbers below that upper bound.
A primality testing implementation ( [http://www.ellipsa.net/primo/index.html 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 ref_harvard|Pomerance|Pomerance 1984|none suggesting that there may be infinitely many counterexamples.
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.
Notes
# Pomerance, C. (1984). [http://www.pseudoprime.com/dopo.pdf "“Are There Counterexamples to the Baillie-PSW Primality Test?”"] .
# 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.
# Thomas R. Nicely. [http://www.trnicely.net/misc/bpsw.html “The Baillie-PSW primality test.”]
#
Wikimedia Foundation.
2010.
Look at other dictionaries:
Primality test — A primality test is an algorithm for determining whether an input number is prime. Amongst other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating… … Wikipedia
AKS primality test — The AKS primality test (also known as Agrawal–Kayal–Saxena primality test and cyclotomic AKS test) is a deterministic primality proving algorithm created and published by three Indian Institute of Technology Kanpur computer scientists, Manindra… … Wikipedia
PSW — stand for any of the following:* Program status word, an element of a computer memory * Baillie PSW primality test, a mathematical deterministic primality testing heuristic * Polish Soviet War (February 1919 – March 1921) * Pacific South West, a… … Wikipedia
Miller–Rabin primality test — The Miller–Rabin primality test or Rabin–Miller primality test is a primality test: an algorithm which determines whether a given number is prime, similar to the Fermat primality test and the Solovay–Strassen primality test. Its original version … Wikipedia
Тест Агравала — В информатике тест Агравала Каяла Саксены (или тест AKS) это полиномиальный детерминированный тест простоты чисел, предложенный индийскими учёным Маниндрой Агравалом (англ.) и его двумя студентами Нираджем Каялом (англ … Википедия
List of mathematics articles (B) — NOTOC B B spline B* algebra B* search algorithm B,C,K,W system BA model Ba space Babuška Lax Milgram theorem Baby Monster group Baby step giant step Babylonian mathematics Babylonian numerals Bach tensor Bach s algorithm Bachmann–Howard ordinal… … Wikipedia
Тест простоты — Тест простоты алгоритм, который по заданному натуральному числу определяет, простое ли это число. Различают детерминированные и вероятностные тесты. Определение простоты заданного числа в общем случае не такая уж тривиальная задача. Только… … Википедия
Quadratic sieve — The quadratic sieve algorithm (QS) is a modern integer factorization algorithm and, in practice, the second fastest method known (after the general number field sieve). It is still the fastest for integers under 100 decimal digits or so, and is… … Wikipedia
