Applications of Perfect Numbers

The Mersenne Twister [1] is a good pseudorandom number generator based on a Mersenne prime. Apparently other systems exist using Mersenne primes for pseudorandom number generation as well. [2]

In communication complexity, Mersenne primes enabled a major advance in private information retrieval schemes [3][4], with an asymptotic result dependent on their infinitude.

The number-theoretic transform, an alternative approach to fast Fourier transforms using modular arithmetic rather than floating-point numbers, is most efficient when using GF(p) where p is a Mersenne prime. [5]

The EFF is offering prizes for discovering large primes, and Mersenne primes have won the first two. They are also the likeliest candidate for the remaining two awards since they're easier to prove prime than other numbers of similar size.

The GIMPS software is often used to stress-test new computer configurations. In this capacity it uncovered a bug in the Skylake family of Intel processors. [6]

GPUs are similarly tested with Mersenne-prime methods. [7]

Solinas [8][9] showed how to use numbers near Mersenne primes to perform high-speed modular reductions, suitable for a fast cryptosystem. Granger & Moss [9] show an alternate generalization that enhances these benefits, especially for modular multiplication.

Harvey, van der Hoeven, & Lecerf [11] give a multiplication algorithm (an extension of Fürer's algorithm) which is the fastest known, and show that it can be further improved given "a slight weakening of the Lenstra-Pomerance-Wagstaff conjecture" on Mersenne prime distribution. Probably the algorithm is not practical for the sizes of numbers typically used but advances in multiplication are very important as they underlie many modern algorithms.


[1] M. Matsumoto and T. Nishimura, Mersenne Twister: A 623-dimensionally equidistributed uniform pseudorandom number generator, ACM Trans. on Modeling and Computer Simulation 8:1 (1998), pp. 3-30.

[2] Lih-Yuan Deng, Generalized Mersenne Prime Number and Its Application to Random Number Generation, Monte Carlo and Quasi-Monte Carlo Methods (2004), pp. 167-180.

[3] Sergey Yekhanin, New Locally Decodable Codes and Private Information Retrieval Schemes, Electronic Colloquium on Computational Complexity, Report No. 127 (2006)

[4] Kiran S. Kedlaya and Sergey Yekhanin, Locally Decodable Codes From Nice Subsets of Finite Fields and Prime Factors of Mersenne Numbers (2007)

[5] I. S. Reed and T. K. Truong, Fast algorithms for computing Mersenne-prime number-theoretic transforms, DSN Progress Report 42-41 (1977).

[6] TechTimes, Mathematicians Discover Bug That Causes Skylake Chips To Freeze In The Middle Of Complex Workloads (2016)

[7] Andrew Thall, Fast Mersenne Prime Testing on the GPU (2011)

[8] Jerome A. Solinas, Generalized Mersenne Primes (1999).

[9] Jerome A. Solinas, Pseudo-Mersenne Prime, Encyclopedia of Cryptography and Security, 2nd Ed. (2011), p. 992.

[10] Robert Granger and Andrew Moss, Generalised Mersenne numbers revisited (2011)

[11] David Harvey, Joris van der Hoeven, Grégoire Lecerf, Even faster integer multiplication (2014)