Universally Accessible Distributed Computing on Public, Heterogeneous Networks,
Applied to the Search for Mersenne Primes

Overview

Introduction

Approach

Model

Implementation

Results

Conclusions

Going Further

References

Acknowledgements

Appendix A: Active Jobs

Appendix B: Processing Resource Applet

Appendix C: Control Server Source Code

Appendix D: Processing Resource Source Code

Appendix E: Database Source Code

Model

Mersenne Primes

A Mersenne number is defined as follows:[6]

M_n = 2ⁿ - 1, where n ∈ {1, 2, 3, …}

A Mersenne prime is a Mersenne number which is also prime.

Mersenne primes have a number of properties that make them easier to identify than normal primes of comparable magnitude:

• If a Mersenne number is prime, then the seed exponent is also a prime number:[6]

  M_p is prime ⇒ p is prime.

  The reason that the seed (exponent) must be prime is that a Mersenne number with a composite seed can be expressed as the product of two integers, both greater than one. To see this, assume the following:

  n = ab, where a, b ∈ {2, 3, 4, ...}

  M_n = 2^ab - 1

  That is, M_n is a Mersenne number with a composite seed. However:

  2^ab - 1 = (2^a - 1)(2^a(b-1) + 2^a(b-2) + … + 2^2a + 2^a + 1)

  Each of the two parenthesized terms on the right-hand side of the equation is an integer greater than 1; thus, M_n is the product of two integers greater than 1, and is therefore composite.

  So, in order for a Mersenne number to be prime, the exponent must also be prime. The reverse isn't true – for example, M₁₁ has a prime exponent, but it isn't prime. Nonetheless, this gives us a way to generate Mersenne numbers that might be prime: just use a prime seed to generate the Mersenne number.

  Because these seeds are exponentially lower than the Mersenne numbers, they are easy to generate with traditional methods (e.g. using the Sieve of Eratosthenes).

• A specialized test exists for testing the primality of Mersenne numbers with prime exponents. The Lucas-Lehmer test of primality for Mersenne numbers is currently the best algorithm known for this purpose; it is far more efficient than general-purpose primality tests.

  In the Lucas-Lehmer test, the sequence s is generated as follows:

  s₀ = 4

  s_n = [(s_n-1)² - 2] mod M_p, for n = 1, 2, …, p - 2

  Where:

  p = seed prime

  M_p = 2^p - 1

  The final value of the sequence, s_p-2, is called the Lucas-Lehmer residue. This residue indicates the primality (or not) of M_p:

  If s_p-2 = 0, then M_p is prime;

  otherwise, M_p is composite.

• Any prime factors of a Mersenne number M_p, with a prime seed p, must be of the form:

  2k₁p + 1, where k₁ is a positive integer.

  That is, any prime factor of M_p must be one more than an integral multiple of 2p.

  Further, any prime factors of a Mersenne number with a prime exponent must also be of the form:

  8k₂ ± 1, where k₂ is a positive integer.

  That is, any prime factor of M_p must be one more or less than an integral multiple of 8.

  While Lucas-Lehmer is the most efficient test known for testing the primality of Mersenne numbers, the time required to test candidate Mersenne numbers increases very quickly as the seed prime increases. However, these properties of the prime factors of Mersenne numbers with prime exponents allow us to filter out some of the candidates by performing trial division with a comparatively small number of trial factors (following the above forms), reducing the number of Mersenne numbers that must be tested via Lucas-Lehmer.

The Sieve of Eratosthenes

Since the seed primes for Mersenne numbers are exponentially smaller than the Mersenne numbers themselves, they can be generated via simpler means, such as the Sieve of Eratosthenes. (In fact, the Sieve can easily generate seed primes that are much larger than the seed prime of the largest known Mersenne prime.) The Sieve of Eratosthenes is a very simple technique for enumerating prime numbers. It works on the principal that every prime number defines an infinite number of composites – namely, the integral multiples of the prime larger than itself. Realizing this, Eratosthenes invented a simple, but effective algorithm for finding all the primes up to u (some upper limit):[7]

1. Create an ordered list of consecutive integers, from 2 to u.

2. Set p, the sieving prime, to the first number in the list (i.e. 2).

3. Remove all integral multiples of p from the list, starting with p².

4. If any number greater than p and less than or equal to ⌊√u⌋ remains in the list, set p to the lowest such value, and return to step (3); otherwise, proceed to step (5).

5. All numbers still in the list are prime.

The basic Sieve can be extended, optimized for memory use or processing time, or simply tuned to fit within the practical constraints of a given platform. One modification used in this project is segmentation: instead of trying to enumerate the seed primes up to the maximum conceivable value needed in a single Sieve execution (since the largest known Mersenne prime is currently M_43112609, an upper limit of 100,000,00 would be sufficient for even the next few years of the GIMPS project), smaller ranges of numbers are processed as needed.

To perform the Sieve on a segment of numbers with a lower bound greater than 2, the classic sieve is modified slightly:

1. Create two ordered lists: one containing the integers from from 2 to ⌊√u⌋, and the second containing the integers from l to u, where l and u are the lower and upper bounds, respectively, of the segment to be sieved. (It's assumed that ⌊√u⌋ < l; if that isn't the case, then the Sieve should be performed in the usual manner, and all primes less than l should be discarded before returning the result.)

2. Perform the Sieve on the first list in the normal fashion, to enumerate a set of primes.

3. Process the second list as follows:

   1. Set p, the sieving prime, to the first number in the first list.

   2. Remove all integral multiples of p from the second list, starting with p² or l, whichever is greater.

   3. If the first list contains any numbers greater than p, set p to the lowest such value, and return to step (ii); otherwise, proceed to step (iv).

   4. The numbers remaining in the second list are the prime numbers in the range from l to u.