Lucas-Lehmer test

Detail from page 316 of the work Théorie des Fonctions Numériques Simplement Périodiques by Édouard Lucas (1878)

The Lucas-Lehmer test is a prime number test for Mersenne numbers , that is, for numbers of the form . The test is used in the GIMPS project ( Great Internet Mersenne Prime Search ) - the search for previously unknown Mersenne prime numbers. ${\displaystyle M_{n}=2^{n}-1}$

This test is based on properties of the Lucas sequences and not, like the Lucas test, on Fermat's little theorem .

functionality

The Lucas-Lehmer test is suitable for testing Mersenne numbers from . It is essentially based on the fact that the Mersenne numbers in the dual system (binary system) consist only of ones. ${\displaystyle M_{3}}$

The Mersenne prime number is a prime number that is written exclusively with the binary digit "1".
binary	11	111	11111	1111111	1111111111111	11111111111111111	1111111111111111111	1111111111111111111111111111111	...
power	2 2 −1	2 3 −1	2 5 −1	2 7 −1	2 13 −1	2 17 −1	2 19 −1	2 31 −1	...
decimal	3	7th	31	127	8,191	131,071	524.287	2,147,483,647	...
The most important property of a Mersenne prime number: "The number of binary digits must be a prime number." The Mersenne number is a binary number that consists of ones ( repunit , palindrome of numbers ). ${\displaystyle M_{n}}$ ${\displaystyle n}$

The Lucas-Lehmer test works as follows:

Be odd and prime. The consequence is defined by . ${\displaystyle p}$ ${\displaystyle S(k)}$ ${\displaystyle S(1)=4,S(k+1)=S(k)^{2}-2}$

Then: is a prime number if and only if is divisible by . ${\displaystyle M_{p}=2^{p}-1}$ ${\displaystyle S(p-1)}$ ${\displaystyle M_{p}}$

This sentence was found in 1930 by Derrick Henry Lehmer and goes back to Édouard Lucas (see illustration). With the help of the modulo function mod, the sentence can be formulated as follows:

Be and . Then: is a prime number if and only if . ${\displaystyle S(1)=4}$ ${\displaystyle S(k+1)\equiv S(k)^{2}-2\ mod\ M_{p}}$ ${\displaystyle M_{p}}$ ${\displaystyle S(p-1)=0}$

Examples

Example 1: We use this procedure to check whether a number is prime: ${\displaystyle M_{5}=2^{5}-1=31}$

 S(1) = 4
 S(2) = ( 4² - 2) mod 31 =  14 mod 31 = 14
 S(3) = (14² - 2) mod 31 = 194 mod 31 = 8
 S(4) = ( 8² - 2) mod 31 =  62 mod 31 = 0

There is is a prime number. ${\displaystyle S(4)=0}$ ${\displaystyle M_{5}=31}$

Example 2: We check whether a number is prime: ${\displaystyle M_{11}=2^{11}-1=2047}$

 S( 1) = 4
 S( 2) = (   4² - 2) mod 2047 =      14 mod 2047 = 14
 S( 3) = (  14² - 2) mod 2047 =     194 mod 2047 = 194
 S( 4) = ( 194² - 2) mod 2047 =   37634 mod 2047 = 788
 S( 5) = ( 788² - 2) mod 2047 =  620942 mod 2047 = 701
 S( 6) = ( 701² - 2) mod 2047 =  491399 mod 2047 = 119
 S( 7) = ( 119² - 2) mod 2047 =   14159 mod 2047 = 1877
 S( 8) = (1877² - 2) mod 2047 = 3523127 mod 2047 = 240
 S( 9) = ( 240² - 2) mod 2047 =   57598 mod 2047 = 282
 S(10) = ( 282² - 2) mod 2047 =   79522 mod 2047 = 1736

There is is not a prime number (it holds ). ${\displaystyle S(10)>0}$ ${\displaystyle M_{11}=2047}$ ${\displaystyle 2047=23\cdot 89}$

Example 3: We check whether a number is prime: ${\displaystyle M_{19}=2^{19}-1=524287}$

 S( 1) = 4
 S( 2) = (      4² - 2) mod 524287 =     14
 S( 3) = (     14² - 2) mod 524287 =    194
 S( 4) = (    194² - 2) mod 524287 =  37634
 S( 5) = (  37634² - 2) mod 524287 = 218767
 S( 6) = ( 218767² - 2) mod 524287 = 510066
 S( 7) = ( 510066² - 2) mod 524287 = 386344
 S( 8) = ( 386344² - 2) mod 524287 = 323156
 S( 9) = ( 323156² - 2) mod 524287 = 218526
 S(10) = ( 218526² - 2) mod 524287 = 504140
 S(11) = ( 504140² - 2) mod 524287 = 103469
 S(12) = ( 103469² - 2) mod 524287 = 417706
 S(13) = ( 417706² - 2) mod 524287 = 307417
 S(14) = ( 307417² - 2) mod 524287 = 382989
 S(15) = ( 382989² - 2) mod 524287 = 275842
 S(16) = ( 275842² - 2) mod 524287 =  85226
 S(17) = (  85226² - 2) mod 524287 = 523263
 S(18) = ( 523263² - 2) mod 524287 =      0

There is is a prime number (this has been known since 1603). ${\displaystyle S_{18}=0}$ ${\displaystyle M_{19}=524287}$

Example implementation in Python

The following program implements the Lucas-Lehmer test in the Python programming language . In Python it is possible to calculate with arbitrarily large whole numbers that are only limited by the available memory. The implementation presented here does not take into account that the Lucas-Lehmer test ideally breaks off when it is even or not prime, this is left to the user. If you entered the program would give the wrong statement that the number 3 is not a Mersenne prime number. ${\displaystyle p}$ ${\displaystyle p=2}$

Postmark for the discovery of the Mersenne prime number 2 ¹¹²¹³ -1

On an Intel Pentium 4 from 2005, the calculation for this program only takes 41 seconds. The calculation in 1963, with which it was proven that is prime, took another 2¼ hours with a supercomputer Illiac II at the time . ${\displaystyle p=11213}$ ${\displaystyle M_{11213}}$

#Lucas-Lehmer-Test fuer Python 3
print('Lucas-Lehmer-Test (Mersenne-Zahlen)')
p = int(input('Exponent p von 2^p-1 '))
m = 2 ** p-1
print('m = 2 ^', p, '- 1 =', m)
s = 4
for i in range (2, p):
    s = (s * s - 2) % m
print('ist {}eine Mersenne-Primzahl'.format('' if s == 0 else 'k'))

literature

• Paulo Ribenboim : The world of prime numbers. Secrets and Records. Springer Verlag, Berlin a. a. 2006, ISBN 3-540-34283-4 ( Springer textbook ).
• Édouard Lucas : Théorie des Fonctions Numériques Simplement Périodiques. In: American Journal of Mathematics. 1, No. 4, 1878, pp. 289-321, ISSN  0002-9327 (third part of the treatise).
• Derrick Henry Lehmer : An extended theory of Lucas' functions. In: The Annals of Mathematics. 31, No. 3, 1930, pp. 419-448, ISSN  0003-486X .
  ( first page of his doctoral thesis from 1930 in an exhibition in Berkeley and further photos ).

Individual evidence

1. ↑ For proof, see Ribenboim: Die Welt der Prime numbers , pp. 78/79.
2. ↑ ILLIAC II in the English language Wikipedia
3. ^ Donald B. Gillies: Three new Mersenne primes and a statistical theory