Editing Prime number (section)

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