Editing Prime number (section)

== Computational methods ==
[[File:Gears large.jpg|thumb|The small gear in this piece of farm equipment has 13 teeth, a prime number, and the middle gear has 21, relatively prime to 13.]]
For a long time, number theory in general, and the study of prime numbers in particular, was seen as the canonical example of pure mathematics, with no applications outside of mathematics{{efn|name="pure"}} other than the use of prime numbered gear teeth to distribute wear evenly.<ref>{{cite book|title=How Round is Your Circle?: Where Engineering and Mathematics Meet|title-link=How Round Is Your Circle|first1=John|last1=Bryant|first2=Christopher J.|last2=Sangwin|publisher=Princeton University Press|year=2008|isbn=978-0-691-13118-4|at=[https://books.google.com/books?id=iIN_2WjBH1cC&pg=PA178 p. 178]}}</ref> In particular, number theorists such as [[United Kingdom|British]] mathematician [[G. H. Hardy]] prided themselves on doing work that had absolutely no military significance.<ref>{{cite book|title=A Mathematician's Apology|last1=Hardy|first1=Godfrey Harold|publisher=Cambridge University Press|year=2012|isbn=978-0-521-42706-7|page=[https://books.google.com/books?id=EkY2im6xkVkC&pg=PA140 140]|oclc=922010634|quote=No one has yet discovered any warlike purpose to be served by the theory of numbers or relativity, and it seems unlikely that anyone will do so for many years.|author1-link=G. H. Hardy|orig-year=1940|title-link=A Mathematician's Apology}}</ref>

This vision of the purity of number theory was shattered in the 1970s, when it was publicly announced that prime numbers could be used as the basis for the creation of [[public-key cryptography]] algorithms.<ref name="ent-7"/>
These applications have led to significant study of [[algorithm]]s for computing with prime numbers, and in particular of [[primality test]]ing, methods for determining whether a given number is prime. The most basic primality testing routine, trial division, is too slow to be useful for large numbers. One group of modern primality tests is applicable to arbitrary numbers, while more efficient tests are available for numbers of special types. Most primality tests only tell whether their argument is prime or not. Routines that also provide a prime factor of composite arguments (or all of its prime factors) are called [[integer factorization|factorization]] algorithms. Prime numbers are also used in computing for [[checksum]]s, [[hash table]]s, and [[pseudorandom number generator]]s.

=== Trial division ===
{{main|Trial division}}
The most basic method of checking the primality of a given integer {{tmath|n}} is called ''[[trial division]]''. This method divides {{tmath|n}} by each integer from 2 up to the [[square root]] of {{tmath|n}}. Any such integer dividing {{tmath|n}} evenly establishes {{tmath|n}} as composite; otherwise it is prime. Integers larger than the square root do not need to be checked because, whenever {{tmath|1= n = a\cdot b }}, one of the two factors {{tmath|a}} and {{tmath|b}} is less than or equal to the [[square root]] of {{tmath|n}}. Another optimization is to check only primes as factors in this range.<ref>{{cite book|title=Primes and Programming|first=Peter|last=Giblin|author-link=Peter Giblin|publisher=Cambridge University Press|year=1993|isbn=978-0-521-40988-9|page=[https://archive.org/details/primesprogrammin0000gibl/page/39 39]|url=https://archive.org/details/primesprogrammin0000gibl|url-access=registration}}</ref> For instance, to check whether 37 is prime, this method divides it by the primes in the range from 2 to {{tmath|\sqrt{37} }}, which are 2, 3, and 5. Each division produces a nonzero remainder, so 37 is indeed prime.

Although this method is simple to describe, it is impractical for testing the primality of large integers, because the number of tests that it performs [[exponential growth|grows exponentially]] as a function of the number of digits of these integers.<ref>{{harvnb|Giblin|1993}}, [https://archive.org/details/primesprogrammin0000gibl/page/54 p.&nbsp;54]</ref> However, trial division is still used, with a smaller limit than the square root on the divisor size, to quickly discover composite numbers with small factors, before using more complicated methods on the numbers that pass this filter.<ref name="p. 220">{{harvnb|Riesel|1994}}, [https://books.google.com/books?id=ITvaBwAAQBAJ&pg=PA220 p.&nbsp;220].</ref>

=== Sieves ===
[[File:Sieve of Eratosthenes animation.gif|frame|The [[sieve of Eratosthenes]] starts with all numbers unmarked (gray). It repeatedly finds the first unmarked number, marks it as prime (dark colors) and marks its square and all later multiples as composite (lighter colors). After marking the multiples of 2 (red), 3 (green), 5 (blue), and 7 (yellow), all primes up to the square root of the table size have been processed, and all remaining unmarked numbers (11, 13, etc.) are marked as primes (magenta).|alt=Animation of the sieve of Eratosthenes]]

{{main|Sieve of Eratosthenes}}
Before computers, [[mathematical table]]s listing all of the primes or prime factorizations up to a given limit were commonly printed.<ref>{{cite journal| first=Maarten |last=Bullynck |title=A history of factor tables with notes on the birth of number theory 1657–1817 |journal=Revue d'Histoire des Mathématiques |year=2010 |pages=133–216 |volume=16 |issue=2 |url=https://hal-univ-paris8.archives-ouvertes.fr/hal-01103903/ }}</ref> The oldest known method for generating a list of primes is called the sieve of Eratosthenes.<ref>{{cite book |title=The Joy of Factoring |volume=68 |series=Student mathematical library |first=Samuel S. Jr. |last=Wagstaff |author-link=Samuel S. Wagstaff Jr. |publisher=American Mathematical Society |year=2013 |isbn=978-1-4704-1048-3 |page=191 |url=https://books.google.com/books?id=rowCAQAAQBAJ&pg=PA191 }}</ref> The animation shows an optimized variant of this method.<ref>{{cite book |title=Prime Numbers: A Computational Perspective |edition=2nd |first1=Richard |last1=Crandall |author1-link=Richard Crandall |first2=Carl |last2=Pomerance |author2-link=Carl Pomerance |publisher=Springer |year=2005 |isbn=978-0-387-25282-7 |page=121 |url=https://books.google.com/books?id=RbEz-_D7sAUC&pg=PA121 }}</ref> Another more asymptotically efficient sieving method for the same problem is the [[sieve of Atkin]].<ref>{{cite conference | last1 = Farach-Colton | first1 = Martín | author1-link = Martin Farach-Colton | last2 = Tsai | first2 = Meng-Tsung | editor1-last = Elbassioni | editor1-first = Khaled | editor2-last = Makino | editor2-first = Kazuhisa | arxiv = 1504.05240 | contribution = On the complexity of computing prime tables | doi = 10.1007/978-3-662-48971-0_57 | pages = 677–688 | publisher = Springer | series = Lecture Notes in Computer Science | title = Algorithms and Computation: 26th International Symposium, ISAAC 2015, Nagoya, Japan, December 9-11, 2015, Proceedings | volume = 9472 | year = 2015| isbn = 978-3-662-48970-3 }}</ref> In advanced mathematics, [[sieve theory]] applies similar methods to other problems.<ref>{{cite book|title=Sieves in Number Theory|volume=43|series=Ergebnisse der Mathematik und ihrer Grenzgebiete (3. Folge)|first=George|last=Greaves|publisher=Springer|year=2013|isbn=978-3-662-04658-6|page=1|url=https://books.google.com/books?id=G0TtCAAAQBAJ&pg=PA1}}</ref>

=== 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"/>
|}

=== Special-purpose algorithms and the largest known prime ===
{{Further|List of prime numbers}}
In addition to the aforementioned tests that apply to any natural number, some numbers of a special form can be tested for primality more quickly. For example, the [[Lucas–Lehmer primality test]] can determine whether a [[Mersenne number]] (one less than a [[power of two]]) is prime, deterministically, in the same time as a single iteration of the Miller–Rabin test.<ref>{{cite book | last = Tao | first = Terence | author-link = Terence Tao | contribution = 1.7 The Lucas–Lehmer test for Mersenne primes | contribution-url = https://terrytao.wordpress.com/2008/10/02/the-lucas-lehmer-test-for-mersenne-primes/ | isbn = 978-0-8218-4883-8 | location = Providence, RI | mr = 2523047 | pages = 36–41 | publisher = American Mathematical Society | title = Poincaré's legacies, pages from year two of a mathematical blog. Part I | year = 2009 }}</ref> This is why since 1992 ({{as of|2024|10|lc=y}}) the [[largest known prime|largest ''known'' prime]] has always been a Mersenne prime.<ref>{{harvnb|Kraft|Washington|2014}}, [https://books.google.com/books?id=4NAqBgAAQBAJ&pg=PA41 p.&nbsp;41].</ref> It is conjectured that there are infinitely many Mersenne primes.<ref>For instance see {{harvnb|Guy|2013}}, [https://books.google.com/books?id=1BnoBwAAQBAJ&pg=PA13 A3 Mersenne primes. Repunits. Fermat numbers. Primes of shape {{tmath| k\cdot 2^n+1 }}. pp. 13–21].</ref>

The following table gives the largest known primes of various types. Some of these primes have been found using [[distributed computing]]. In 2009, the [[Great Internet Mersenne Prime Search]] project was awarded a US$100,000 prize for first discovering a prime with at least 10 million digits.<ref>{{cite web | url= https://www.eff.org/press/archives/2009/10/14-0  | title= Record 12-Million-Digit Prime Number Nets $100,000 Prize | date= October 14, 2009 | publisher= Electronic Frontier Foundation | access-date= 2010-01-04 }}</ref> The [[Electronic Frontier Foundation]] also offers $150,000 and $250,000 for primes with at least 100 million digits and 1 billion digits, respectively.<ref>{{cite web  | url= https://www.eff.org/awards/coop | title= EFF Cooperative Computing Awards | date= 2008-02-29| publisher= Electronic Frontier Foundation | access-date= 2010-01-04 }}</ref>

{| class="wikitable"
|-
! Type
! Prime
! Number of decimal digits
! Date
! Found by
|-
| [[Mersenne prime]]
| 2<sup>136,279,841</sup> − 1
| style="text-align:right;"| 41,024,320
| October 21, 2024<ref name="GIMPS-2024"/>
| Luke Durant, [[Great Internet Mersenne Prime Search]]
|-
| [[Proth prime]]
| 10,223 × 2<sup>31,172,165</sup> + 1
| style="text-align:right;"| 9,383,761
| October 31, 2016<ref>{{cite web|url=https://www.primegrid.com/download/SOB-31172165.pdf|title=PrimeGrid's Seventeen or Bust Subproject|access-date=2017-01-03}}</ref>
| Péter Szabolcs, [[PrimeGrid]]<ref>{{cite web|first=Chris K.|last=Caldwell |url=http://primes.utm.edu/top20/page.php?id=3 |title=The Top Twenty: Largest Known Primes |website=[[Prime Pages|The Prime Pages]] |access-date=2017-01-03}}</ref>
|-
| [[factorial prime]]
| 208,003! − 1
| style="text-align:right;"| 1,015,843
| July 2016
| Sou Fukui<ref>{{cite web|first=Chris K.|last=Caldwell |url=http://primes.utm.edu/top20/page.php?id=30 |title=The Top Twenty: Factorial |website=[[Prime Pages|The Prime Pages]] |access-date=2017-01-03}}</ref>
|-
| [[primorial prime]]{{efn|The [[primorial]] function of {{tmath|n}}, denoted by {{tmath|n\#}}, yields the product of the prime numbers up to {{tmath|n}}, and a [[primorial prime]] is a prime of one of the forms {{tmath| n\#\pm 1 }}.<ref>{{harvnb|Ribenboim|2004}}, p. 4.</ref>}}
| 1,098,133# − 1
| style="text-align:right;"| 476,311
| March 2012
| James P. Burt, [[PrimeGrid]]<ref>{{cite web|first=Chris K.|last=Caldwell |url=http://primes.utm.edu/top20/page.php?id=5 |title=The Top Twenty: Primorial |website=[[Prime Pages|The Prime Pages]] |access-date=2017-01-03}}</ref>
|-
| [[twin prime]]s
| 2,996,863,034,895 × 2<sup>1,290,000</sup> ± 1
| style="text-align:right;"| 388,342
| September 2016
| Tom Greer, [[PrimeGrid]]<ref>{{cite web|first=Chris K.|last=Caldwell |url=http://primes.utm.edu/top20/page.php?id=1 |title=The Top Twenty: Twin Primes |website=[[Prime Pages|The Prime Pages]] |access-date=2017-01-03}}</ref>
|}

=== Integer factorization ===
{{main|Integer factorization}}
Given a composite integer {{tmath|n}}, the task of providing one (or all) prime factors is referred to as ''factorization'' of {{tmath|n}}. It is significantly more difficult than primality testing,<ref>{{harvnb|Kraft|Washington|2014}}, [https://books.google.com/books?id=4NAqBgAAQBAJ&pg=PA275 p.&nbsp;275].</ref> and although many factorization algorithms are known, they are slower than the fastest primality testing methods. Trial division and [[Pollard's rho algorithm]] can be used to find very small factors of {{tmath|n}},<ref name="p. 220"/> and [[elliptic curve factorization]] can be effective when {{tmath|n}} has factors of moderate size.<ref>{{cite book|title=An Introduction to Mathematical Cryptography|series=Undergraduate Texts in Mathematics|first1=Jeffrey|last1=Hoffstein|first2=Jill|last2=Pipher|author2-link=Jill Pipher|first3=Joseph H.|last3=Silverman|author3-link=Joseph H. Silverman|edition=2nd|publisher=Springer|year=2014|isbn=978-1-4939-1711-2|page=329|url=https://books.google.com/books?id=cbl_BAAAQBAJ&pg=PA329}}</ref> Methods suitable for arbitrary large numbers that do not depend on the size of its factors include the [[quadratic sieve]] and [[general number field sieve]]. As with primality testing, there are also factorization algorithms that require their input to have a special form, including the [[special number field sieve]].<ref>{{cite journal | last = Pomerance | first = Carl | author-link = Carl Pomerance | issue = 12 | journal = [[Notices of the American Mathematical Society]] | mr = 1416721 | pages = 1473–1485 | title = A tale of two sieves | volume = 43 | year = 1996}}</ref> {{as of|2019|12}} the [[Integer factorization records|largest number known to have been factored]] by a general-purpose algorithm is [[RSA-240]], which has 240 decimal digits (795 bits) and is the product of two large primes.<ref>{{cite web |first1=Emmanuel |last1=Thomé |url=https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;fd743373.1912 |title=795-bit factoring and discrete logarithms |date= December 2, 2019 |website=LISTSERV Archives }}</ref>

[[Shor's algorithm]] can factor any integer in a polynomial number of steps on a [[quantum computer]].<ref>{{cite book|title=Quantum Computing: A Gentle Introduction|first1=Eleanor G.|last1=Rieffel|author1-link=Eleanor Rieffel|first2=Wolfgang H.|last2=Polak|publisher=MIT Press|year=2011|isbn=978-0-262-01506-6|contribution=Chapter 8. Shor's Algorithm|pages=163–176|title-link= Quantum Computing: A Gentle Introduction |contribution-url=https://books.google.com/books?id=iYX6AQAAQBAJ&pg=PA163}}</ref> However, current technology can only run this algorithm for very small numbers. {{As of|2012|10}}, the largest number that has been factored by a quantum computer running Shor's algorithm is 21.<ref>{{cite journal |last1=Martín-López |first1=Enrique  |first2=Anthony|last2=Laing|first3=Thomas|last3=Lawson  |first4=Roberto|last4=Alvarez  |first5=Xiao-Qi|last5=Zhou  |first6=Jeremy L.|last6=O'Brien |title=Experimental realization of Shor's quantum factoring algorithm using qubit recycling |journal=Nature Photonics |volume=6  |issue=11  |pages=773–776  |date=12 October 2012 |doi=10.1038/nphoton.2012.259 |arxiv = 1111.4147  |bibcode = 2012NaPho...6..773M |s2cid=46546101 }}</ref>

=== Other computational applications ===
Several [[public-key cryptography]] algorithms, such as [[RSA (algorithm)|RSA]] and the [[Diffie–Hellman key exchange]], are based on large prime numbers (2048-[[bit]] primes are common).<ref>{{cite news|newspaper=[[The Register]]|url=https://www.theregister.co.uk/2016/10/09/crypto_needs_more_transparency_researchers_warn/|title=Crypto needs more transparency, researchers warn|first=Richard|last=Chirgwin|date=October 9, 2016}}</ref> RSA relies on the assumption that it is much easier (that is, more efficient) to perform the multiplication of two (large) numbers {{tmath|x}} and {{tmath|y}} than to calculate {{tmath|x}} and {{tmath|y}} (assumed [[coprime]]) if only the product <math>xy</math> is known.<ref name="ent-7"/> The Diffie–Hellman key exchange relies on the fact that there are efficient algorithms for [[modular exponentiation]] (computing {{tmath|a^b\bmod{c} }}), while the reverse operation (the [[discrete logarithm]]) is thought to be a hard problem.<ref>{{harvnb|Hoffstein|Pipher|Silverman|2014}}, Section 2.3, Diffie–Hellman key exchange, pp. 65–67.</ref>

Prime numbers are frequently used for [[hash table]]s. For instance the original method of Carter and Wegman for [[universal hashing]] was based on computing [[hash function]]s by choosing random [[linear function]]s modulo large prime numbers. Carter and Wegman generalized this method to [[k-independent hashing|{{tmath|k}}-independent hashing]] by using higher-degree polynomials, again modulo large primes.<ref>{{Introduction to Algorithms|edition=2|chapter=11.3 Universal hashing|pages=232–236}} For {{tmath|k}}-independent hashing see problem 11–4, p. 251. For the credit to Carter and Wegman, see the chapter notes, p. 252.</ref> As well as in the hash function, prime numbers are used for the hash table size in [[quadratic probing]] based hash tables to ensure that the probe sequence covers the whole table.<ref>{{cite book|title=Data Structures & Algorithms in Java|edition=4th|first1=Michael T.|last1=Goodrich|author1-link=Michael T. Goodrich|first2=Roberto|last2=Tamassia|author2-link=Roberto Tamassia|publisher=John Wiley & Sons|year=2006|isbn=978-0-471-73884-8}} See "Quadratic probing", p. 382, and exercise C–9.9, p. 415.</ref>

Some [[checksum]] methods are based on the mathematics of prime numbers. For instance the checksums used in [[International Standard Book Number]]s are defined by taking the rest of the number modulo 11, a prime number. Because 11 is prime this method can detect both single-digit errors and transpositions of adjacent digits.<ref>{{cite book|title=Identification Numbers and Check Digit Schemes|volume=18|series=Classroom Resource Materials|first=Joseph|last=Kirtland|author-link=Joseph Kirtland|publisher=Mathematical Association of America|year=2001|isbn=978-0-88385-720-5|pages=43–44|url=https://books.google.com/books?id=Z8eka35WUb8C&pg=PA43}}</ref> Another checksum method, [[Adler-32]], uses arithmetic modulo 65521, the largest prime number less than {{tmath|2^{16} }}.<ref>{{cite IETF |rfc=1950|title=ZLIB Compressed Data Format Specification version 3.3|last=Deutsch|first=P.|publisher=Network Working Group|date=May 1996}}</ref> Prime numbers are also used in [[pseudorandom number generator]]s including [[linear congruential generator]]s<ref>{{cite book|title=The Art of Computer Programming, Vol. 2: Seminumerical algorithms|edition=3rd|first=Donald E.|last=Knuth|author-link=Donald Knuth|publisher=Addison-Wesley|year=1998|contribution=3.2.1 The linear congruential model|pages=10–26|isbn=978-0-201-89684-8|title-link=The Art of Computer Programming}}</ref> and the [[Mersenne Twister]].<ref>{{cite journal | last1 = Matsumoto | first1 = Makoto | last2 = Nishimura | first2 = Takuji | doi = 10.1145/272991.272995 | issue = 1 | journal = ACM Transactions on Modeling and Computer Simulation | pages = 3–30 | title = Mersenne Twister: A 623-dimensionally equidistributed uniform pseudo-random number generator | volume = 8 | year = 1998| citeseerx = 10.1.1.215.1141 | s2cid = 3332028 }}</ref>