Editing Primality test (section)

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