section_path: Computational methods/Other computational applications
section_name: Other computational applications
paragraph_text: Other computational applications
  
  Several public-key cryptography algorithms, such as RSA and the Diffie–Hellman key exchange, are based on large prime numbers (2048- bit primes are common). RSA relies on the assumption that it is much easier (that is, more efficient) to perform the multiplication of two (large) numbers x {\displaystyle x} and y {\displaystyle y} than to calculate x {\displaystyle x} and y {\displaystyle y} (assumed coprime) if only the product x y {\displaystyle xy} is known. The Diffie–Hellman key exchange relies on the fact that there are efficient algorithms for modular exponentiation (computing a b mod c {\displaystyle a^{b}{\bmod {c}}}), while the reverse operation (the discrete logarithm) is thought to be a hard problem.
  
  Prime numbers are frequently used for hash tables. For instance the original method of Carter and Wegman for universal hashing was based on computing hash functions by choosing random linear functions modulo large prime numbers. Carter and Wegman generalized this method to k {\displaystyle k} -independent hashing by using higher-degree polynomials, again modulo large primes. 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.
  
  Some checksum methods are based on the mathematics of prime numbers. For instance the checksums used in International Standard Book Numbers 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. Another checksum method, Adler-32, uses arithmetic modulo 65521, the largest prime number less than 2 16 {\displaystyle 2^{16}}. Prime numbers are also used in pseudorandom number generators including linear congruential generators and the Mersenne Twister.