Mersenne prime numbers and Luke-Lemer test

Translation of the post by John McGee (John McGee) " Mersenne Primes and the Lucas – Lehmer Test ".
The code given in the article can be downloaded here .

I express my deep gratitude to Polina Sologub for assistance in translating and preparing the publication .

Content

- Introduction.
- The Euler and Mersenne multiplier theorem
- Luke and Lemer
- From

M_{13}

${M_ {13}}$ before

M_{20}

${M_ {20}}$
- perfect numbers
- 21st, 22nd and 23rd numbers of Mersenne
- 24th, 25th and 26th of Mersenne.
- 27th and 28th of Mersenne
- 29th number of Mersenne
- 30th and 31st of Mersenne
- Great online search for Mersenne numbers
- Factorization of Mersenne numbers
')

Introduction

Mersenne Prime Number - a Prime Number

M_{p} = 2^{p} - 1

${M_p} = {2 ^ p} - 1$ (the value of the degree of p should also be simple). These prime numbers got their name from the name of the French mathematician and religious scholar Mersenne , who made this list of prime numbers of this form in the first half of the seventeenth century. The first four of them have been known for a long time:

M_{2} = 3

${M_2} = 3$ ,

M_{3} = 7

${M_3} = 7$ ,

M_{5} = 31

${M_5} = 31$ and

M_{7} = 127

${M_7} = 127$ .

Mersenne argued that the value

2^{p} - 1

${2 ^ p} - 1$ will be simple for prime numbers

p l e q s l a n t $ 25

$p \ leqslant $ 25$ belonging to the set

p i n l e f t t e x t 2 t e x t, 3 t e x t, 5 t e x t, 7 t e x t, 13 t e x t, 17 t e x t, 19 t e x t, 31 t e x t, 67 t e x t, 127 t e x t, 257 r i g h t

$p \ in \ left \ {{{\ text {2}} {\ text {, 3}} {\ text {, 5}} {\ text {, 7}} {\ text {, 13}} {\ text {, 17}} {\ text {, 19}} {\ text {, 31}} {\ text {, 67}} {\ text {, 127}} {\ text {, 257}}} \ right \ }$ . Whether he was right in everything, you can check with the Wolfram Language - PrimeQ function , which uses modern methods of testing numbers for simplicity, which do not require searching for a specific multiplier to prove that the number is composite.

It is possible that his statement that

M_{67}

${M_ {67}}$ - a prime number, just a typo, and in fact he meant

M_{61}

${M_ {61}}$ . It is easy to understand that the test of simplicity was difficult for Mersenn during his life, because the test by division was one of the few tools available. For example, for

M_{257}

${M_ {257}}$ the smallest factor is a 15-digit number, so even with modern methods of factorization it is not so easy to find. The FactorInteger function uses the most advanced methods that allow you to apply the factorization method for large integers.

Euler and Mersenne multiplier theorem

The first important achievements in the field of simplicity testing belong to the great mathematician Leonard Euler , who, shortly before 1772, clarified that

M_{31}

${M_ {31}}$ is simple. He did this by demonstrating that any simple divisor

M_{31}

${M_ {31}}$ must be equal to 1 or 62 (mod 248).

Such a relatively short list, even in the times of Euler, could be checked using test division (manually). He belongs to the application of the theorem of Mersenne , which states that if

q

$q$ is a divider

M_{p}

${M_p}$ then

q e q u i v 1 v e e - 1 l e f t (b m o d 8 r i g h t)

$q \ equiv 1 \ vee - 1 \ left ({\ bmod 8} \ right)$ ,

q e q u i v 1 l e f t (b m o d p r i g h t)

$q \ equiv 1 \ left ({\ bmod p} \ right)$ and

q e q u i v 2 k p + 1

$q \ equiv 2kp + 1$ for some positive integer

k

$k$ . These facts significantly limit the number of possible dividers.

M_{p}

${M_p}$ . Using the functions presented below, the use of this theorem is demonstrated to provide a list of possible divisors.

M_{p}

${M_p}$ smaller than

s q r t 2^{p} - 1

$\ sqrt {{2 ^ p} - 1}$ .

We use these functions to quickly find a divider.

2^{41} - 1

${2 ^ {41}} - 1$ . note that

q

$q$ is a divider

2^{p} - 1

${2 ^ {p}} - 1$ then and only if

2^{p} e q u i v 1 l e f t (b m o d q r i g h t)

${2 ^ p} \ equiv 1 \ left ({\ bmod q} \ right)$ . This makes it possible to use the PowerMod function, which ensures effective exponentiation modulo.

The following is the number of Mersenne with 161649 characters :.

Luke and Lemer

The next important step was the discovery by Edward Luke of a method for checking the simplicity of the numbers of this form. He used his method in 1876 to check whether

M_{127}

${M_ {127}}$ (the largest number of Mersenne pre-computer era) simple. In the early twentieth century, when the basics of binary arithmetic and algebra became widely known, Derek Henry Lemer improved the method of Luke. The resulting simplicity test of Luc-Lemer provided an effective check if the number of this form was simple. The test was carried out using the comparison module:

It means that

k

$k$ identical to the number represented by its

p

$p$ bits of the lower order, plus - the numbers represented by the other bits. This relationship can be applied recursively as long as

k < 2^{p} - 1

$k <{2 ^ p} - 1$ .

Consider the following example. Here we show that

for

k = t e x t 1234567891

$k = {\ text {1234567891}}$ . note that

(23 lower order bits) and

- means that the remaining bits are shifted to the lowest position.

The function below sets this method to calculate

k b m o d l e f t (2^{p} - 1 r i g h t)

$k \ bmod \ left ({{2 ^ p} - 1} \ right)$ using only bit operations (no division). Note that

2^{n} - 1

${2 ^ n} - 1$ has binary form

111 . . . 111_{2}

${111 ... 111_2}$ , while there is no 0, and therefore it also serves as a mask for

p

$p$ lower order bits

k

$k$ .

The following function implements the Luke-Lemere simplicity test (LLT). Determine the sequence

s_{0} = 4

${s_0} = 4$ ,

s_{i} = s_{i - 1}^{2} - 2; i > 0

${s_i} = s_ {i - 1} ^ 2 - 2; i> 0$ . Then

M_{p} = 2^{p} - 1

${M_p} = {2 ^ p} - 1$ is simple if and only if

s_{p - 1} e q u i v 0 l e f t (b m o d M_{p} r i g h t)

${s_ {p - 1}} \ equiv 0 \ left ({\ bmod {M_p}} \ right)$ .

Experience shows that the main execution time of these functions is spent on integer arithmetic.

To check whether

2^{p} - 1

${2 ^ p} - 1$ simple, it is better to first check the simplicity on small prime dividers and perform other checks of simplicity. First, we use the Mersenne prime divisor theorem encoded in checkMPDivisors , and then the PrimeQ function. If this does not work, apply the Luke-Lemer test.

Here we present an extended version of PrimeQ , which applies the Luke- Lemere test for large numbers

2^{p} - 1

${2 ^ p} - 1$ .

From ${M_ {13}}$ before ${M_ {20}}$

The first prime number of Mersenne, discovered on a computer using the Luke-Lemer test, was

M_{521}

${M_ {521}}$ , found by Rafael Robinson on January 30, 1952 based on the SWAC (Standards Western Automatic Computer) tube computer. Below you see a block of memory of this computer, containing 256 words of 37 bits each.

The 20th Mersenne prime number was discovered by Alexander Hurwitz in November 1961 as a result of Luke-Lemer’s 50-minute test on the IBM 7090. Below we reproduce these results (this took about 151 seconds of computer time on a modern single-core laptop).

One of the features of the Wolfram Language that makes it suitable for this kind of work is its fast integer arithmetic. The search for Mersenne primes was a real challenge at the dawn of the era of computerized search. Researchers adapted fast Fourier transform methods to transform the problem of multiplying two large integers into a simple, element-wise product of transformed digits. Fast multiplication of integers is necessary for the squaring step in the Luc-Lemer test. The Wolfram Language uses the latest algorithms optimized to work with exact integers with billions of characters. For example, make sure that the last one, -

M_{4423} ​ ​

${M_ {4423}} $ , Is in fact a simple Mersenne number, and we will demonstrate all its numbers.

Perfect numbers

There is an interesting connection between prime Mersenne numbers and perfect numbers. A perfect number is a number equal to the sum of all its divisors (different from the number itself). Euclid assumed, and Euler proved that all even perfect numbers have the form

P = 2^{p - 1} l e f t (2^{p} - 1 r i g h t) = 2^{p - 1} M_{p}

$P = {2 ^ {p - 1}} \ left ({{2 ^ p} - 1} \ right) = {2 ^ {p - 1}} {M_p}$ . The Wolfram Language PerfectNumberQ function checks if the number is perfect. Let us demonstrate this property on

M_{31}

${M_ {31}}$ .

21st, 22nd and 23rd numbers of Mersenne

Let us turn to the re-discovery of the 21st, 22nd and 23rd numbers of Mersenne (we will denote them further in the form of

\ # 21

$\ # 21$ ):

\ # 21 = {M_ {9689}}

$\ # 21 = {M_ {9689}}$ ,

\ # 22 = {M_ {9941}}

$\ # 22 = {M_ {9941}}$ ,

\ # 23 = {M_ {11213}}

$\ # 23 = {M_ {11213}}$ . All of them were discovered by Donald Gillis, who ran the LLT on ILLIAC II throughout the spring of 1963 (see here ). To check all numbers of the form

2^{p} - 1

${2 ^ p} - 1$ for prime numbers in between

7927 l e q s l a n t p l e q s l a n t $ 1738

$7927 \ leqslant p \ leqslant $ 1738$ it took us about 6 minutes.

24th, 25th and 26th numbers of Mersenne

Next, we expand the search to find

\ # 24 = {M_ {19937}}

$\ # 24 = {M_ {19937}}$ ,

\ # 25 = {M_ {21701}}

$\ # 25 = {M_ {21701}}$ ,

\ # 26 = {M_ {23209}}

$\ # 26 = {M_ {23209}}$ . The last of them was discovered in February 1979 by Landon Kurt Noll and Laura Nickel. They searched in range from

M_{21001}

${M_ {21001}}$ before

M_{24499}

${M_ {24499}}$ on the CDC Cyber 174 supercomputer (you can read about it here ). Our calculations become longer, so we start using parallel processing. Since the tests are independent, we can use ParallelMap to speed up the work. Range check

17393 l e q s l a n t p l e q s l a n t $ 2744

$17393 \ leqslant p \ leqslant $ 2744$ takes about three and a half minutes (4 cores are used).

Note that Luke- Lemere's specialized test is significantly faster than the more general PrimeQ function (for given Mersenne numbers).

27th and 28th of Mersenne

Next we checked the range

27457 l e q s l a n t p l e q s l a n t $ 4861

$27457 \ leqslant p \ leqslant $ 4861$ to find the number

\ # 27 = {M_ {44497}}

$\ # 27 = {M_ {44497}}$ . It was discovered in April 1979 by Harry Nelson and his team (they used the Cray-1 supercomputer). Our search was completed in 15 minutes.

The next number is mersenne,

\ # 28 = {M_ {86243}}

$\ # 28 = {M_ {86243}}$ . It was opened in September 1982 by David Slowinski - also on Cray-1. This supercomputer weighed about 5 tons and consumed about 115 kilowatts of electricity, and its computing performance reached 160 megaflops . It came with 1 million 64-bit words of memory (8 megabytes), and cost about $ 16000000 in today's prices. The detail of its cooling system is shown below. For comparison, the Raspberry Pi weighs a few ounces, runs at 4 watts, provides about 410 megaflops and is equipped with 1GB of RAM, and that’s all for $ 40. And it comes immediately with Mathematica .

Number

\ # 28 = {M_ {86243}}

$\ # 28 = {M_ {86243}}$ contains 25962 digits. We found this value in 1 hour and 14 minutes (on my laptop, not on the Raspberry Pi), conducting tests in the range

48, 619 l e q s l a n t p l e q s l a n t $ 8753

$48,619 \ leqslant p \ leqslant $ 8753$ .

29th number of mersenne

Since we now need more serious computer time, we also produce a time stamp for each run. Now we check the range

87557 l e q s l a n t p l e q s l a n t 110597

$87557 \ leqslant p \ leqslant 110597$ . After 1 hour and 44 minutes, the computer showed:

\ # 29 = {M_ {110503}}

$\ # 29 = {M_ {110503}}$ . This number was first discovered on January 29, 1988 by Walker Colquitt and Luke Welch (NEC DX-2 supercomputer; article can be found here ).

30th and 31st of mersenne

The following are two Mersenne prime numbers:

M_{132049}

${M_ {132049}}$ and

M_{216091}

${M_ {216091}}$ , - were actually discovered even before the 29th (by the same team that found the 28th). They used Cray X-MP to find the 30th number of Mersenne in September 1983 and the 31st in September 1985. Check

\ # 30

$\ # 30$ using the range search function

110603 l e q s l a n t p l e q s l a n t $ 13990

$110603 \ leqslant p \ leqslant $ 13990$ . To check each

M_{p}

${M_p}$ in this range it took 4 hours and 8 minutes.

Great online search for Mersenne numbers

With the discovery of the 34th prime number of Mersenne -

M_{1} 257787

${M_1257787}$ - in September 1996, the era of supercomputers for searching for Mersenne primes was over. The following 15 were found by volunteers of the Great Internet Search for Mersenne Prime Numbers ( GIMPS ), which include the Luke-Lemer test variant (as a background process) on personal computers. This large-scale distributed computing project currently reaches a performance level equivalent to about 300 teraflops per second, with downtime of more than 1.3 million computers.

Check the 34th of Mersenne with the Luke-Lemer test. At this stage, we have reached the limit of the possibilities of a personal computer. Testing thousands of Mersenne numbers in this range will take many days. It is interesting to note that the Luke-Lemere test is often used as a stress test for the reliability of computer hardware and software, since even one arithmetic error among the billions of calculations required to test one large prime number would entail an incorrect conclusion, which would mean a loss Mersenne numbers or false answer. The fact that we checked every

M_{p}

${M_p}$ for primes between 2 and 139901, convincingly proves the reliability of the arithmetic of large numbers and binary operations in the Mathematica system and the Wolfram Language.

Mersenne number factorization

As we have already seen, the number of possible factors in the expansion of numbers of the form

2^{p} - 1

${2 ^ p} - 1$ according to the theorem of multipliers, Mersenne is limited. This allowed for an effective computerized search for the divisors of large numbers of this form. At the time of this writing, all Mersenne numbers (up to

2^{1201} - 1

${2 ^ {1201}} - 1$ ) were fully factorized (illustrations can be found here ). The GIMPS project also led to the discovery of the large multipliers of many Mersenn numbers as a by-product of checking the simplicity of numbers. A new article, which is a modern approach to solving this problem (along with 17 new factorizations), can be found here . The largest factorized number was

2^{1199} - 1

${2 ^ {1199}} - 1$ ; its smallest divisor found has 76 decimal digits. Its smallest divider is 23. The total time required to get this result is 7500 years (talking about computer time).

We can quickly find the first few factors.

2^{1201} - 1

${2 ^ {1201}} - 1$ using the FactorInteger function.

All the Mersenne prime numbers found to date are cataloged in the Wolfram Language (before the 44th). Access to this information is provided by the MersennePrimeExponent and MersennePrimeExponentQ functions.