Lucas–Lehmer primality test

The Lucas -Lehmer test is a primality test for Mersenne numbers, that is, for numbers of the form. The test is (English: Great Internet Mersenne Prime Search ) in the GIMPS project, finding not previously known Mersenne primes used.

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

Operation

The Lucas- Lehmer test is suitable for testing Mersenne numbers from M3. He is very much based on the Mersenne numbers in the binary system only consist of all ones and works as follows:

This rate was found in 1930 by Derrick Lehmer and goes back (see picture) on Édouard Lucas. Using the modulo function mod can be formulated as the set:

Examples

Example 1: We consider this procedure if M5 = 25-1 = 31 is a prime number:

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 Since S (4) = 0, is M5 = 31 is a prime number.

Example 2: We check if M11 = 211-1 = 2047 is a prime number:

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 = 620 942 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 Since S (10 )> 0, M11 = 2047 is not prime ( it is 2047 = 23.89 ).

Example 3: We check if M19 = 219-1 = 524 287 is a prime number:

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 = 218 767   S ( 6) = ( 218 767 ² - 2 ) mod 524287 = 510066   S (7 ) = ( 510066 ² - 2 ) mod 524287 = 386 344   S ( 8) = ( 386 344 ² - 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 = 417 706   S ( 13 ) = ( 417 706 ² - 2 ) mod 524287 = 307 417   S ( 14 ) = ( 307 417 ² - 2 ) mod 524287 = 382 989   S ( 15 ) = ( 382 989 ² - 2 ) mod 524287 = 275 842   S ( 16 ) = ( 275 842 ² - 2 ) mod 524287 = 85226   S ( 17) = ( 85226 ² - 2 ) mod 524287 = 523 263   S ( 18 ) = ( 523 263 ² - 2 ) mod 524287 = 0 Since S (18) = 0, M19 = 524287 a prime number (this is known since 1603).

Example implementation in Python

The following program implements the Lucas- Lehmer test in the Python programming language. In Python, it is possible to expect any large integers that are limited only by available memory. The presented implementation does not consider that the Lucas- Lehmer test ideally already aborts if p is odd or non- prime, this is left to the user. Thus, the program would provide for entry of p = 2, the false statement that the number 3 is not a Mersenne prime.

On an Intel Pentium 4 from 2005, the bill for p = 11213 required with this program just 41 seconds. The bill in 1963, was detected with the that M11213 is prime, on the other hand lasted with a former supercomputer Illiac II (see en: ILLIAC II) for 2 ¼ hours.

# Lucas- Lehmer test for Python 2.6/2.7 print ' Lucas- Lehmer test ( Mersenne numbers ) ' p = int ( raw_input ( ' exponent p of 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 ' is ', if not s == 0:      print ' no ', print ' Mersenne primes ' literature

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