Editing Primality test

{{Short description|Algorithm for determining whether a number is prime}}
A '''primality test''' is an [[algorithm]] for determining whether an input number is [[prime number|prime]]. Among other fields of [[mathematics]], it is used for [[cryptography]]. Unlike [[integer factorization]], primality tests do not generally give [[prime factor]]s, only stating whether the input number is prime or not. Factorization is thought to be a computationally difficult problem, whereas primality testing is comparatively easy (its [[Run-time complexity|running time]] is [[Polynomial time|polynomial]] in the size of the input). Some primality tests prove that a number is prime, while others like [[Miller–Rabin primality test|Miller–Rabin]] prove that a number is [[Composite number|composite]]. Therefore, the latter might more accurately be called ''compositeness tests'' instead of primality tests.

== Simple methods ==
The simplest primality test is ''[[trial division]]'':  given an input number, <math>n</math>, check whether it is [[divisibility|divisible]] by any [[prime number]] between 2 and <math>\sqrt n</math> (i.e., whether the division leaves no [[remainder]]). If so, then <math>n</math> is [[Composite number|composite]]. Otherwise, it is prime.<ref name="Riesel2-3">Riesel (1994) pp.2-3</ref> For any divisor <math>p \geq \sqrt n</math>, there must be another divisor <math>n/p \leq \sqrt n</math>, and a prime divisor <math>q</math> of <math>n/p</math>, and therefore looking for prime divisors at most <math>\sqrt n</math> is sufficient.

For example, consider the number 100, whose divisors are these numbers:

:1, 2, 4, 5, 10, 20, 25, 50, 100.

When all possible divisors up to <math>n</math> are tested, some divisors will be discovered ''twice''. To observe this, consider the list of divisor pairs of 100:

:<math>1 \times 100, \; 2 \times 50, \; 4 \times 25, \; 5 \times 20, \; 10 \times 10, \; 20 \times 5, \; 25 \times 4, \; 50 \times 2, \; 100 \times 1</math>.

Products past <math>10 \times 10</math> are the reverse of products that appeared earlier. For example, <math>5 \times 20</math> and <math>20 \times 5</math> are the reverse of each other. Further, that of the two divisors, <math>5 \leq \sqrt{100} = 10</math> and <math>20 \geq \sqrt{100} = 10</math>. This observation generalizes to all <math>n</math>: all divisor pairs of <math>n</math> contain a divisor less than or equal to <math>\sqrt{n}</math>, so the algorithm need only search for divisors less than or equal to <math>\sqrt{n}</math> to guarantee detection of all divisor pairs.<ref name="Riesel2-3"/>

Also, 2 is a prime dividing 100, which immediately proves that 100 is not prime. Every positive integer except 1 is divisible by at least one prime number by the [[Fundamental Theorem of Arithmetic]]. Therefore the algorithm need only search for ''prime'' divisors less than or equal to <math>\sqrt{n}</math>.

For another example, consider how this algorithm determines the primality of 17. One has <math>4 < \sqrt{17} < 5</math>, and the only primes <math>\leq \sqrt{17}</math> are 2 and 3. Neither divides 17, proving that 17 is prime. For a last example, consider 221. One has <math>14 < \sqrt{221} < 15</math>, and the primes <math>\leq \sqrt{221}</math> are 2, 3, 5, 7, 11, and 13. Upon checking each, one discovers that <math>221 / 13 = 17</math>, proving that 221 is not prime.

In cases where it is not feasible to compute the list of primes <math>\leq \sqrt{n}</math>, it is also possible to simply (and slowly) check all numbers between <math>2</math> and <math>\sqrt{n}</math> for divisors. A simple improvement is to test divisibility by 2 and by just the odd numbers between 3 and <math>\sqrt{n}</math>, since divisibility by an even number implies divisibility by 2.

This method can be improved further. Observe that all primes greater than 5 are of the form <math>6k + i</math> for a nonnegative integer <math>k</math> and <math>i \in \{1, 5\}</math>. Indeed, every integer is of the form <math>6k + i</math> for a positive integer <math>k</math> and <math>i \in \{0, 1, 2, 3, 4, 5\}</math>. Since 2 divides <math>6k, 6k + 2</math>, and <math>6k + 4</math>, and 3 divides <math>6k</math> and <math>6k + 3</math>, the only possible remainders mod 6 for a prime greater than 3 are 1 and 5. So, a more efficient primality test for <math>n</math> is to test whether <math>n</math> is divisible by 2 or 3, then to check through all numbers of the form <math>6k + 1</math> and <math>6k + 5</math> which are <math>\leq \sqrt{n}</math>. This is almost three times as fast as testing all numbers up to <math>\sqrt{n}</math>.

Generalizing further, all primes greater than <math>c\#</math> ([[Primorial#Definition for natural numbers|c primorial]]) are of the form <math>c\# \cdot k + i</math> for <math>i, k</math> positive integers, <math>0 \leq i < c\#</math>, and <math>i</math> [[coprime]] to <math>c\#</math>. For example, consider <math>6\# = 2 \cdot 3 \cdot 5 = 30</math>. All integers are of the form <math>30k + i</math> for <math>i, k</math> integers with <math>0 \leq i < 30</math>. Now, 2 divides <math>0, 2, 4, \dots, 28</math>, 3 divides <math>0, 3, 6, \dots, 27</math>, and 5 divides <math>0, 5, 10, \dots, 25</math>. Thus all prime numbers greater than 30 are of the form <math>30k + i</math> for <math>i \in \{1, 7, 11, 13, 17, 19, 23, 29\}</math>. Of course, not all numbers of the form <math>c\# \cdot k + i</math> with <math>i</math> coprime to <math>c\#</math> are prime. For example, <math>19 \cdot 23 = 437 = 210 \cdot 2 + 17 = 2 \cdot 7\# + 17</math> is not prime, even though 17 is coprime to <math>7\# = 2 \cdot 3 \cdot 5 \cdot 7</math>.

As <math>c</math> grows, the fraction of coprime remainders to remainders decreases, and so the time to test <math>n</math> decreases (though it still necessary to check for divisibility by all primes that are less than <math>c</math>). Observations analogous to the preceding can be applied [[recursion|recursively]], giving the [[Sieve of Eratosthenes]].

One way to speed up these methods (and all the others mentioned below) is to pre-compute and store a list of all primes up to a certain bound, such as all primes up to 200. (Such a list can be computed with the Sieve of Eratosthenes or by an algorithm that tests each incremental <math>m</math> against all known primes <math>\leq \sqrt m</math>). Then, before testing <math>n</math> for primality with a large-scale method, <math>n</math> can first be checked for divisibility by any prime from the list. If it is divisible by any of those numbers then it is composite, and any further tests can be skipped.

A simple but inefficient primality test uses [[Wilson's theorem]], which states that <math>p</math> is prime if and only if:

:<math>(p - 1)! \equiv -1 \pmod{p}</math>

Although this method requires about <math>p</math> modular multiplications,<ref>{{Cite book |date=2021-09-05 |chapter=Primality Tests |title=Elementary Number Theory |first1=Mike |last1=Barrus |first2=W. Edwin |last2=Clark |chapter-url=https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Elementary_Number_Theory_(Barrus_and_Clark)/01:_Chapters/1.25:_Primality_Tests |url=https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Elementary_Number_Theory_(Barrus_and_Clark) |access-date=2025-03-14 |publisher=Mathematics LibreTexts |language=en}}</ref> rendering it impractical, theorems about primes and modular residues form the basis of many more practical methods.

== Heuristic tests ==
These are tests that seem to work well in practice, but are unproven and therefore are not, technically speaking, algorithms at all.
The [[Fermat primality test]] and the Fibonacci test are simple examples, and they are effective when combined. [[John Selfridge]] has conjectured that if ''p'' is an odd number, and ''p'' ≡ ±2 (mod 5), then ''p'' will be prime if both of the following hold:
* 2<sup>''p''−1</sup> ≡ 1 (mod ''p''),
* ''f''<sub>''p''+1</sub> ≡ 0 (mod ''p''),
where ''f<sub>k</sub>'' is the ''k''-th [[Fibonacci number]]. The first condition is the Fermat primality test using base 2.

In general, if ''p'' ≡ a (mod ''x''<sup>2</sup>+4), where ''a'' is a quadratic non-residue (mod ''x''<sup>2</sup>+4) then ''p'' should be prime if the following conditions hold:

* 2<sup>''p''−1</sup> ≡ 1 (mod ''p''),
* ''f''(''1'')<sub>''p''+1</sub> ≡ 0 (mod ''p''),

''f''(''x'')<sub>''k''</sub> is the ''k''-th [[Fibonacci polynomial]] at ''x''.

Selfridge, [[Carl Pomerance]] and [[Samuel Wagstaff]] together offer $620 for a counterexample.<ref>[[John Selfridge#Selfridge's conjecture about primality testing]].</ref>

== 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>

== Fast deterministic tests ==
Near the beginning of the 20th century, it was shown that a corollary of [[Fermat's little theorem]] could be used to test for primality.<ref>{{cite journal |last=Pocklington |first=H. C. |year=1914 |title=The determination of the prime or composite nature of large numbers by Fermat's theorem |jfm=45.1250.02 |journal=Cambr. Phil. Soc. Proc. |volume=18 |pages=29–30}}</ref> This resulted in the [[Pocklington primality test]].<ref>{{MathWorld |urlname=PocklingtonsTheorem |title=Pocklington's Theorem}}</ref> However, as this test requires a partial [[factorization]] of ''n''&nbsp;−&nbsp;1 the running time was still quite slow in the worst case. The first [[deterministic algorithm|deterministic]] primality test significantly faster than the naive methods was the [[Adleman–Pomerance–Rumely primality test|cyclotomy test]]; its runtime can be proven to be [[Big O notation|O]]((log&nbsp;''n'')<sup>''c''&nbsp;log&nbsp;log&nbsp;log&nbsp;''n''</sup>), where ''n'' is the number to test for primality and ''c'' is a constant independent of ''n''. A number of further improvements were made, but none could be proven to have polynomial running time. (Running time is measured in terms of the size of the input, which in this case is ~ log&nbsp;''n'', that being the number of bits needed to represent the number ''n''.) The [[Elliptic curve primality proving|elliptic curve primality test]] can be proven to run in O((log&nbsp;''n'')<sup>6</sup>), if some conjectures on [[analytic number theory]] are true.{{Which|date=April 2010}} Similarly, under the [[generalized Riemann hypothesis]] (which Miller, confusingly, calls the "[[extended Riemann hypothesis]]"), the deterministic [[Miller–Rabin primality test#Deterministic variants|Miller's test]], which forms the basis of the probabilistic Miller–Rabin test, can be proved to run in [[big O notation#Extensions to the Bachmann–Landau notations|Õ]]((log&nbsp;''n'')<sup>4</sup>).<ref>{{cite journal |doi=10.1016/S0022-0000(76)80043-8 |author=[[Gary L. Miller (mathematician)|Gary L. Miller]] |title=Riemann's Hypothesis and Tests for Primality |journal=[[Journal of Computer and System Sciences]] |volume=13 |issue=3 |pages=300–317 |year=1976|doi-access=free}}</ref> In practice, this algorithm is slower than the other two for sizes of numbers that can be dealt with at all. Because the implementation of these two methods is rather difficult and creates a risk of programming errors, slower but simpler tests are often preferred.

In 2002, the first provably unconditional deterministic polynomial time test for primality was invented by [[Manindra Agrawal]], [[Neeraj Kayal]], and [[Nitin Saxena]]. The [[AKS primality test]] runs in Õ((log&nbsp;''n'')<sup>12</sup>) (improved to Õ((log&nbsp;''n'')<sup>7.5</sup>)<ref name=":0">{{Cite journal |last1=Agrawal |first1=Manindra |first2=Neeraj |last2=Kayal |last3=Saxena |first3=Nitin |year=2004 |url=http://annals.math.princeton.edu/wp-content/uploads/annals-v160-n2-p12.pdf |title=Primes is in P |journal=Annals of Mathematics |doi=10.4007/annals.2004.160.781 |volume=160 |issue=2 |pages=781–793 |doi-access=free}}</ref> in the published revision of their paper), which can be further reduced to Õ((log&nbsp;''n'')<sup>6</sup>) if the [[Sophie Germain prime|Sophie Germain conjecture]] is true.<ref name="AKS">{{cite journal |last1=Agrawal |first1=Manindra |last2=Kayal |first2=Neeraj |last3=Saxena |first3=Nitin |year=2004 |title=PRIMES is in P |url=http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf |journal=Annals of Mathematics |volume=160 |issue=2 |pages=781–793 |doi=10.4007/annals.2004.160.781 |doi-access=free}}</ref> Subsequently, Lenstra and Pomerance presented a version of the test which runs in time Õ((log&nbsp;''n'')<sup>6</sup>) unconditionally.<ref>{{cite web |author1=Carl Pomerance |author2=Hendrik W. Lenstra |name-list-style=amp |date=July 20, 2005 |url=http://www.math.dartmouth.edu/~carlp/PDF/complexity12.pdf |title=Primality testing with Gaussian periods}}</ref>

Agrawal, Kayal and Saxena suggest a variant of their algorithm which would run in  Õ((log&nbsp;''n'')<sup>3</sup>)  if [[Agrawal's conjecture]] is true; however, a heuristic argument by Hendrik Lenstra and Carl Pomerance suggests that it is probably false.<ref name=":0" /> A modified version of the Agrawal's conjecture, the Agrawal–Popovych conjecture,<ref>{{cite web |first=Roman |last=Popovych |date=December 30, 2008 |url=http://eprint.iacr.org/2009/008.pdf |title=A note on Agrawal conjecture}}</ref> may still be true.

== Complexity ==
In [[computational complexity theory]], the formal language corresponding to the prime numbers is denoted as PRIMES. It is easy to show that PRIMES is in '''[[Co-NP]]''': its complement COMPOSITES is in '''NP''' because one can decide compositeness by nondeterministically guessing a factor.

In 1975, [[Vaughan Pratt]] showed that there existed a certificate for primality that was checkable in polynomial time, and thus that PRIMES was in [[NP (complexity)|NP]], and therefore in {{tmath|\mathsf{NP \cap coNP} }}. See [[primality certificate]] for details.

The subsequent discovery of the Solovay–Strassen and Miller–Rabin algorithms put PRIMES in [[RP (complexity)|coRP]]. In 1992, the Adleman–Huang algorithm<ref name=AH92/> reduced the complexity to [[ZPP (complexity)|{{tmath|1=\mathsf{ {\color{Blue} ZPP} = RP \cap coRP} }}]], which superseded Pratt's result.

The [[Adleman–Pomerance–Rumely primality test]] from 1983 put PRIMES in '''QP''' ([[quasi-polynomial time]]), which is not known to be comparable with the classes mentioned above.

Because of its tractability in practice, polynomial-time algorithms assuming the Riemann hypothesis, and other similar evidence, it was long suspected but not proven that primality could be solved in polynomial time. The existence of the [[AKS primality test]] finally settled this long-standing question and placed PRIMES in '''[[P (complexity)|P]]'''. However, PRIMES is not known to be [[P-complete]], and it is not known whether it lies in classes lying inside '''P''' such as [[NC (complexity)|NC]] or [[L (complexity)|L]]. It is known that PRIMES is not in [[AC0|AC<sup>0</sup>]].<ref>{{cite journal | url=https://doi.org/10.1006/jcss.2000.1725 | doi=10.1006/jcss.2000.1725 | title=A Lower Bound for Primality | date=2001 | last1=Allender | first1=Eric | last2=Saks | first2=Michael | last3=Shparlinski | first3=Igor | journal=Journal of Computer and System Sciences | volume=62 | issue=2 | pages=356–366 }}</ref>

== Number-theoretic methods ==
Certain number-theoretic methods exist for testing whether a number is prime, such as the [[Lucas primality test|Lucas test]] and [[Proth's theorem|Proth's test]]. These tests typically require factorization of ''n''&nbsp;+&nbsp;1, ''n'' − 1, or a similar quantity, which means that they are not useful for general-purpose primality testing, but they are often quite powerful when the tested number ''n'' is known to have a special form.

The Lucas test relies on the fact that the [[multiplicative order]] of a number ''a'' modulo ''n'' is ''n'' − 1 for a prime ''n'' when ''a'' is a [[primitive root modulo n]]. If we can show ''a'' is primitive for ''n'', we can show ''n'' is prime.

== References ==
{{Reflist|2}}

== Sources ==
{{Refbegin}}
* {{cite book |last1=Crandall |first1=Richard |author1-link=Richard Crandall |last2=Pomerance |first2=Carl |author2-link=Carl Pomerance |year=2005 |title=Prime Numbers: A Computational Perspective |publisher=Springer |edition=2nd |isbn=0-387-25282-7}} Chapter 3: Recognizing Primes and Composites, pp.&nbsp;109–158. Chapter 4: Primality Proving, pp.&nbsp;159–190. Section 7.6: Elliptic curve primality proving (ECPP), pp.&nbsp;334–340.
* {{cite book |first=Donald |last=Knuth |author-link=Donald Knuth |title=[[The Art of Computer Programming]] |volume=2: ''Seminumerical Algorithms'' |edition=3rd |publisher=Addison–Wesley |year=1997 |isbn=0-201-89684-2 |pages=391–396 |chapter=section 4.5.4}}
* {{cite book |last1=Cormen |first1=Thomas H. |author1-link=Thomas H. Cormen |last2=Leiserson |first2=Charles E. |author2-link=Charles E. Leiserson |last3=Rivest |first3=Ronald L. |author3-link=Ron Rivest |last4=Stein |first4=Clifford |author4-link=Clifford Stein |year=2001 |title=[[Introduction to Algorithms]] |edition=Second |publisher=MIT Press, McGraw–Hill |isbn=0-262-03293-7 |chapter=Section 31.8: Primality testing |pages=887–896}}
* {{cite book |first=Christos H. |last=Papadimitriou |author-link=Christos Papadimitriou |year=1993 |title=Computational Complexity |url=https://archive.org/details/computationalcom00papa |url-access=limited |publisher=Addison Wesley |edition=1st |isbn=0-201-53082-1 |chapter=Section 10.2: Primality |zbl=0833.68049 |pages=[https://archive.org/details/computationalcom00papa/page/n230 222]–227}}
* {{cite book |first=Hans |last=Riesel |author-link=Hans Riesel |year=1994 |title=Prime Numbers and Computer Methods for Factorization |edition=second |publisher=Birkhäuser |isbn=0-8176-3743-5 |zbl=0821.11001 |series=Progress in Mathematics |volume=126 |location=Boston, Massachusetts}}
{{Refend}}

== External links ==
{{wikifunctions|Z12427}}
*{{webarchive |url=https://archive.today/20121220074426/http://computacion.cs.cinvestav.mx/~mruiz/cursos/maestria/csac.html |title=Solovay-Strassen (computacion.cs.cinvestav.mx) |date=2012-12-20}} – Implementation of the Solovay-Strassen primality test in Maple
*[http://cr.yp.to/primetests.html Distinguishing prime numbers from composite numbers, by D.J. Bernstein (cr.yp.to)]
*[http://primes.utm.edu/ The Prime Pages (primes.utm.edu)]
*{{webarchive |url=http://webarchive.loc.gov/all/20100806075947/http://mathpages.com/home/kmath473.htm |title=Lucas Primality Test with Factored ''N''&nbsp;−&nbsp;1 (MathPages.com) |date=2010-08-06}}
*[http://www.primaboinca.com/ PRIMABOINCA] is a research project that uses Internet-connected computers to search for a [[counterexample]] to some conjectures. The first conjecture ([[Agrawal's conjecture]]) was the basis for the formulation of the first deterministic prime test algorithm in polynomial time ([[AKS algorithm]]).

{{Number theoretic algorithms}}

{{DEFAULTSORT:Primality Test}}
[[Category:Primality tests|*]]
[[Category:Asymmetric-key algorithms]]
<!-- dummy edit, delete. -->