Editing Prime number (section)

=== Primality testing versus primality proving ===
Some of the fastest modern tests for whether an arbitrary given number {{tmath|n}} is prime are [[probabilistic algorithm|probabilistic]] (or [[Monte Carlo algorithm|Monte Carlo]]) algorithms, meaning that they have a small random chance of producing an incorrect answer.<ref name="hromkovic">{{cite book | last = Hromkovič | first = Juraj | author-link = Juraj Hromkovič | contribution = 5.5 Bibliographic Remarks | contribution-url = https://books.google.com/books?id=nkeqCAAAQBAJ&pg=PA383 | doi = 10.1007/978-3-662-04616-6 | isbn = 978-3-540-66860-2 | mr = 1843669 | pages = 383–385 | publisher = Springer-Verlag, Berlin | series = Texts in Theoretical Computer Science. An EATCS Series | title = Algorithmics for Hard Problems | year = 2001| s2cid = 31159492 }}</ref> For instance the [[Solovay–Strassen primality test]] on a given number {{tmath|p}} chooses a number {{tmath|a}} randomly from 2 through <math>p-2</math> and uses [[modular exponentiation]] to check whether <math>a^{(p-1)/2}\pm 1</math> is divisible by {{tmath|p}}.{{efn|In this test, the <math>\pm 1</math> term is negative if {{tmath|a}} is a square modulo the given (supposed) prime {{tmath|p}}, and positive otherwise. More generally, for non-prime values of {{tmath|p}}, the <math>\pm 1</math> term is the (negated) [[Jacobi symbol]], which can be calculated using [[quadratic reciprocity]].}} If so, it answers yes and otherwise it answers no. If {{tmath|p}} really is prime, it will always answer yes, but if {{tmath|p}} is composite then it answers yes with probability at most 1/2 and no with probability at least 1/2.<ref name="koblitz"/> If this test is repeated {{tmath|n}} times on the same number, the probability that a composite number could pass the test every time is at most {{tmath|1/2^n}}. Because this decreases exponentially with the number of tests, it provides high confidence (although not certainty) that a number that passes the repeated test is prime. On the other hand, if the test ever fails, then the number is certainly composite.<ref>{{cite book | title = Fundamentals of Computer Security | first1 = Josef | last1 = Pieprzyk | first2 = Thomas | last2 = Hardjono | first3 = Jennifer | last3 = Seberry | author3-link =  Jennifer Seberry | publisher = Springer | year = 2013 | isbn = 978-3-662-07324-7 | contribution = 2.3.9 Probabilistic Computations | pages = 51–52 | contribution-url = https://books.google.com/books?id=BG2rCAAAQBAJ&pg=PA51}}</ref>
A composite number that passes such a test is called a [[pseudoprime]].<ref name="koblitz">{{cite book | last = Koblitz | first = Neal | author-link = Neal Koblitz | contribution = Chapter V. Primality and Factoring | doi = 10.1007/978-1-4684-0310-7_5 | isbn = 978-0-387-96576-5 | mr = 910297 | pages = 112–149 | publisher = Springer-Verlag, New York | series = Graduate Texts in Mathematics | title = A Course in Number Theory and Cryptography | volume = 114 | year = 1987}}</ref>

In contrast, some other algorithms guarantee that their answer will always be correct: primes will always be determined to be prime and composites will always be determined to be composite. For instance, this is true of trial division. The algorithms with guaranteed-correct output include both [[deterministic algorithm|deterministic]] (non-random) algorithms, such as the [[AKS primality test]],<ref name="tao-aks">{{cite book | last = Tao | first = Terence | author-link = Terence Tao | contribution = 1.11 The AKS primality test | contribution-url = https://terrytao.wordpress.com/2009/08/11/the-aks-primality-test/ | doi = 10.1090/gsm/117 | isbn = 978-0-8218-5280-4 | location = Providence, RI | mr = 2780010 | pages = 82–86 | publisher = American Mathematical Society | title = An epsilon of room, II: Pages from year three of a mathematical blog | volume = 117 | year = 2010| series = Graduate Studies in Mathematics }}</ref>
and randomized [[Las Vegas algorithm]]s where the random choices made by the algorithm do not affect its final answer, such as some variations of [[elliptic curve primality proving]].<ref name="hromkovic"/>
When the elliptic curve method concludes that a number is prime, it provides [[primality certificate]] that can be verified quickly.<ref name="atkin-morain" />
The elliptic curve primality test is the fastest in practice of the guaranteed-correct primality tests, but its runtime analysis is based on [[heuristic argument]]s rather than rigorous proofs. The [[AKS primality test]] has mathematically proven time complexity, but is slower than elliptic curve primality proving in practice.<ref name="morain"/> These methods can be used to generate large random prime numbers, by generating and testing random numbers until finding one that is prime; when doing this, a faster probabilistic test can quickly eliminate most composite numbers before a guaranteed-correct algorithm is used to verify that the remaining numbers are prime.{{efn|Indeed, much of the analysis of elliptic curve primality proving is based on the assumption that the input to the algorithm has already passed a probabilistic test.<ref name = "atkin-morain">{{cite journal | last1 = Atkin | first1 = A O.L. | author1-link = A. O. L. Atkin | last2 = Morain | first2 = F. | doi =  10.1090/s0025-5718-1993-1199989-x| issue = 203 | journal = [[Mathematics of Computation]] | mr = 1199989 | pages = 29–68 | title = Elliptic curves and primality proving | volume = 61 | year = 1993| jstor = 2152935 | bibcode = 1993MaCom..61...29A |url = https://www.ams.org/mcom/1993-61-203/S0025-5718-1993-1199989-X/S0025-5718-1993-1199989-X.pdf | doi-access = free }}</ref>}}

The following table lists some of these tests. Their running time is given in terms of {{tmath|n}}, the number to be tested and, for probabilistic algorithms, the number {{tmath|k}} of tests performed. Moreover, <math>\varepsilon</math> is an arbitrarily small positive number, and log is the [[logarithm]] to an unspecified base. The [[big O notation]] means that each time bound should be multiplied by a [[constant factor]] to convert it from dimensionless units to units of time; this factor depends on implementation details such as the type of computer used to run the algorithm, but not on the input parameters {{tmath|n}} and {{tmath|k}}.

{| class="wikitable sortable"
|-
! Test
! Developed in
! Type
! Running time
! Notes
! class=unsortable| References
|-
| [[AKS primality test]]
| 2002
| deterministic
| <math>O((\log n)^{6+\varepsilon})</math>
|
| <ref name="tao-aks"/><ref>{{cite journal|last1=Lenstra|first1=H. W. Jr.|author1-link=Hendrik Lenstra|last2=Pomerance|first2=Carl|author2-link=Carl Pomerance|doi=10.4171/JEMS/861|issue=4|journal=[[Journal of the European Mathematical Society]]|mr=3941463|pages=1229–1269|title=Primality testing with Gaussian periods|url=https://math.dartmouth.edu/~carlp/aks111216.pdf|volume=21|year=2019|hdl=21.11116/0000-0005-717D-0 |s2cid=127807021}}</ref>
|-
| [[Elliptic curve primality proving]]
| 1986
| Las Vegas
| <math>O((\log n)^{4+\varepsilon})</math> ''heuristically''
|
| <ref name="morain">{{cite journal | last = Morain | first = F. | doi = 10.1090/S0025-5718-06-01890-4 | issue = 257 | journal = [[Mathematics of Computation]] | mr = 2261033 | pages = 493–505 | title = Implementing the asymptotically fast version of the elliptic curve primality proving algorithm | volume = 76 | year = 2007| arxiv = math/0502097 | bibcode = 2007MaCom..76..493M | s2cid = 133193 }}</ref>
|-
| [[Baillie–PSW primality test]]
| 1980
| Monte Carlo
| <math>O((\log n)^{2+\varepsilon})</math>
|
| <ref name="PSW">{{cite journal |last1=Pomerance |first1=Carl |author-link1=Carl Pomerance |last2=Selfridge |first2=John L. |author-link2=John L. Selfridge |last3=Wagstaff, Jr. |first3=Samuel S. |author-link3=Samuel S. Wagstaff, Jr. |date=July 1980 |title=The pseudoprimes to 25·10<sup>9</sup> |url=http://math.dartmouth.edu/~carlp/PDF/paper25.pdf |journal=[[Mathematics of Computation]] |volume=35 |issue=151 |pages=1003–1026 |doi=10.1090/S0025-5718-1980-0572872-7 |jstor=2006210 |doi-access=free}}</ref><ref name="lpsp">{{cite journal |last1=Baillie |first1=Robert |last2=Wagstaff, Jr. |first2=Samuel S. |author-link2=Samuel S. Wagstaff, Jr. |date=October 1980 |title=Lucas Pseudoprimes |url=http://mpqs.free.fr/LucasPseudoprimes.pdf |journal=[[Mathematics of Computation]] |volume=35 |issue=152 |pages=1391–1417 |doi=10.1090/S0025-5718-1980-0583518-6 |jstor=2006406 |mr=583518 |doi-access=free}}</ref>
|-
| [[Miller–Rabin primality test]]
| 1980
| Monte Carlo
| <math>O(k(\log n)^{2+\varepsilon})</math>
| error probability <math>4^{-k}</math>
| <ref name="monier">{{cite journal | last = Monier | first = Louis | doi = 10.1016/0304-3975(80)90007-9 | issue = 1 | journal = [[Theoretical Computer Science (journal)|Theoretical Computer Science]] | mr = 582244 | pages = 97–108 | title = Evaluation and comparison of two efficient probabilistic primality testing algorithms | volume = 12 | year = 1980| doi-access = free }}</ref>
|-
| [[Solovay–Strassen primality test]]
| 1977
| Monte Carlo
| <math>O(k(\log n)^{2+\varepsilon})</math>
| error probability <math>2^{-k}</math>
| <ref name="monier"/>
|}