Editing Primality test (section)

== Probabilistic tests ==
[[randomized algorithm|Probabilistic tests]] are more rigorous than heuristics in that they provide provable bounds on the probability of being fooled by a composite number.
Multiple popular primality tests are probabilistic tests. These tests use, apart from the tested number ''n'', some other numbers ''a'' which are chosen at random from some [[sample space]]; the usual randomized primality tests never report a prime number as composite, but it is possible for a composite number to be reported as prime. The probability of error can be reduced by repeating the test with several independently chosen values of ''a''; for two commonly used tests, for ''any'' composite ''n'' at least half the ''a''{{'}}s detect ''n''{{'}}s compositeness, so ''k'' repetitions reduce the error probability to at most 2<sup>−''k''</sup>, which can be made arbitrarily small by increasing ''k''.

The basic structure of randomized primality tests is as follows:

#Randomly pick a number ''a''.
#Check equality (corresponding to the chosen test) involving ''a'' and the given number ''n''. If the equality fails to hold true, then ''n'' is a composite number and ''a'' is a ''witness'' for the compositeness, and the test stops.
#Get back to the step one until the required accuracy is reached.

After one or more iterations, if ''n'' is not found to be a composite number, then it can be declared [[Probable prime|probably prime]].

=== Fermat primality test ===
The simplest probabilistic primality test is the [[Fermat primality test]] (actually a compositeness test). It works as follows:

:Given an integer ''n'', choose some integer ''a'' coprime to ''n'' and calculate ''a<sup>n</sup>''<sup> − 1</sup> [[modular arithmetic|modulo]] ''n''. If the result is different from 1, then ''n'' is composite. If it is 1, then ''n'' may be prime.

If ''a<sup>n</sup>''<sup>−1</sup> (modulo ''n'') is 1 but ''n'' is not prime, then ''n'' is called a
[[pseudoprime]] to base ''a''. In practice, if
''a<sup>n</sup>''<sup>−1</sup> (modulo ''n'')
is 1, then ''n'' is usually prime. But here is a counterexample:
if ''n'' = 341 and ''a'' = 2, then
: <math>2^{340} \equiv 1\pmod{341}</math>
even though 341 = 11·31 is composite. In fact, 341 is the smallest pseudoprime base 2 (see Figure 1 of
<ref name="PSW">{{cite journal |last1=Pomerance |first1=Carl |author1-link=Carl Pomerance |last2=Selfridge |first2=John L. |author2-link=John Selfridge |last3=Wagstaff |first3=Samuel S. Jr. |author3-link=Samuel S. Wagstaff Jr. |date=July 1980 |title=The pseudoprimes to 25·10<sup>9</sup> |journal=Mathematics of Computation |volume=35 |issue=151 |pages=1003–1026 |url=https://www.math.dartmouth.edu/~carlp/PDF/paper25.pdf |doi=10.1090/S0025-5718-1980-0572872-7 |doi-access=free}}</ref>).

There are only 21853 pseudoprimes base 2 that are less than 2.5{{e|10}} (see page 1005 of <ref name="PSW"/>). This means that, for ''n'' up to 2.5{{e|10}}, if ''2<sup>n</sup>''<sup>−1</sup> (modulo ''n'') equals 1, then ''n'' is prime, unless ''n'' is one of these 21853 pseudoprimes.

Some composite numbers ([[Carmichael number]]s) have the property that ''a<sup>n</sup>''<sup> − 1</sup> is 1 (modulo ''n'') for every ''a'' that is coprime to ''n''. The smallest example is ''n'' = 561 = 3·11·17, for which ''a<sup>560</sup>'' is 1 (modulo 561) for all ''a'' coprime to 561. Nevertheless, the Fermat test is often used if a rapid screening of numbers is needed, for instance in the key generation phase of the [[RSA (algorithm)|RSA public key cryptographic algorithm]].

=== Miller–Rabin and Solovay–Strassen primality test===
The [[Miller–Rabin primality test]] and [[Solovay–Strassen primality test]] are more sophisticated variants, which detect all composites (once again, this means: for ''every'' composite number ''n'', at least 3/4 (Miller–Rabin) or 1/2 (Solovay–Strassen) of numbers ''a'' are witnesses of compositeness of ''n''). These are also compositeness tests.

The Miller–Rabin primality test works as follows:
Given an integer ''n'', choose some positive integer ''a''&nbsp;<&nbsp;''n''. Let 2<sup>''s''</sup>''d'' = ''n''&nbsp;−&nbsp;1, where ''d'' is odd. If

:<math>
a^{d} \not\equiv \pm 1\pmod{n}
</math>
and
:<math>
a^{2^rd} \not\equiv -1\pmod{n}</math> for all <math>0 \le r \le s - 1,
</math>

then ''n'' is composite and ''a'' is a witness for the compositeness. Otherwise, ''n'' may or may not be prime.
The Miller–Rabin test is a [[strong pseudoprime|strong probable prime]] test (see PSW<ref name="PSW"/> page 1004).

The Solovay–Strassen primality test uses another equality: Given an odd number ''n'', choose some integer ''a''&nbsp;<&nbsp;''n'', if

:<math> a^{(n-1)/2} \not\equiv \left(\frac{a}{n}\right) \pmod n</math>, where <math>\left(\frac{a}{n}\right)</math> is the [[Jacobi symbol]],

then ''n'' is composite and ''a'' is a witness for the compositeness. Otherwise, ''n'' may or may not be prime.
The Solovay–Strassen test is an [[Euler pseudoprime|Euler probable prime]] test (see PSW<ref name="PSW"/> page 1003).

For each individual value of ''a'', the Solovay–Strassen test is weaker than the Miller–Rabin test. For example, if ''n'' = 1905 and ''a'' = 2, then the Miller-Rabin test shows that ''n'' is composite, but the Solovay–Strassen test does not. This is because 1905 is an Euler
pseudoprime base 2 but not a strong pseudoprime base 2 (this is illustrated in Figure 1 of PSW<ref name="PSW"/>).

=== Frobenius primality test ===
The Miller–Rabin and the Solovay–Strassen primality tests are simple and are much faster than other general primality tests. One method of improving efficiency further in some cases is the [[Frobenius pseudoprime|Frobenius pseudoprimality test]]; a round of this test takes about three times as long as a round of Miller–Rabin, but achieves a probability bound comparable to seven rounds of Miller–Rabin.

The Frobenius test is a generalization of the [[Lucas pseudoprime|Lucas probable prime]] test.

=== Baillie–PSW primality test ===
The [[Baillie–PSW primality test]] is a probabilistic primality test that combines a Fermat or Miller–Rabin test with a [[Lucas pseudoprime|Lucas probable prime]] test to get a primality test that has no known counterexamples. That is, there are no known composite ''n'' for which this test reports that ''n'' is probably prime.<ref name="lpsp">{{cite journal |last1=Baillie |first1=Robert |last2=Wagstaff |first2=Samuel S. Jr. |author2-link=Samuel S. Wagstaff Jr. |date=October 1980 |title=Lucas Pseudoprimes |journal=Mathematics of Computation |volume=35 |issue=152 |pages=1391–1417 |url=https://mpqs.free.fr/LucasPseudoprimes.pdf |mr=583518 |doi=10.1090/S0025-5718-1980-0583518-6 |doi-access=free}}</ref><ref name=bpsw2>{{cite journal |last1=Baillie |first1=Robert |last2=Fiori |first2=Andrew |last3=Wagstaff |first3=Samuel S. Jr. |author3-link=Samuel S. Wagstaff Jr. |date=July 2021 |title=Strengthening the Baillie-PSW Primality Test |journal=Mathematics of Computation |volume=90 |issue=330 |pages=1931–1955 |doi=10.1090/mcom/3616 |arxiv=2006.14425 |s2cid=220055722}}</ref> It has been shown that there are no counterexamples for ''n'' <math> < 2^{64}</math>.

=== Other tests ===
[[Leonard Adleman]] and Ming-Deh Huang presented an errorless (but expected polynomial-time) variant of the [[Elliptic curve primality proving|elliptic curve primality test]]. Unlike the other probabilistic tests, this algorithm produces a [[primality certificate]], and thus can be used to prove that a number is prime.<ref name=AH92>{{cite book |first1=Leonard M. |last1=Adleman |author1-link=Leonard Adleman |first2=Ming-Deh |last2=Huang |title=Primality testing and Abelian varieties over finite field |series=Lecture notes in mathematics |volume=1512 |year=1992 |isbn=3-540-55308-8 |publisher=[[Springer-Verlag]]}}</ref> The algorithm is prohibitively slow in practice.

If [[quantum computer]]s were available, primality could be tested [[Big O notation|asymptotically faster]] than by using classical computers. A combination of [[Shor's algorithm]], an integer factorization method, with the [[Pocklington primality test]] could solve the problem in <math>O((\log n)^3 (\log\log n)^2 \log\log\log n)</math>.<ref>{{cite arXiv |last1=Chau |first1=H. F. |last2=Lo |first2=H.-K. |year=1995 |eprint=quant-ph/9508005 |title=Primality Test Via Quantum Factorization}}</ref>