Lucas–Lehmer primality test

This article page is a stub, please help by expanding it.

This article needs more work.

Please help by expanding it!

The Lucas–Lehmer test (LLT) is a primality test for Mersenne numbers. The test was originally developed by Édouard Lucas in 1856, and subsequently improved by Lucas in 1878 and D. H. Lehmer in the 1930s.

Lucas–Lehmer primality test

The Lucas–Lehmer test works as follows. Let

Mp = 2 p  −  1

be the Mersenne number to test with

p

an odd prime (because

p

is exponentially smaller than

Mp

, we can use a simple algorithm like trial division for establishing its primality). Define a sequence

{si}i   ≥  0

as

s0 = 4;

si = (si  − 1 ) 2 − 2, i ≥ 1.

A003010 A Lucas–Lehmer sequence:

a (0) = 4

; for

n > 0, a (n) = (a (n  −  1)) 2  −  2

.

{4, 14, 194, 37634, 1416317954, 2005956546822746114, 4023861667741036022825635656102100994, 16191462721115671781777559070120513664958590125499158514329308740975788034, ...}

Then

Mp

is prime if and only if

sp  − 2 ≡ 0  (mod Mp ).

The number

sp  − 2 mod Mp

is called the Lucas–Lehmer residue of

p

. (Some authors equivalently set

s1 = 4

and test

sp  − 1 mod Mp

). In pseudocode, the test might be written:

// Determine if M_p = 2^p − 1 is prime, where p is an odd prime.

Lucas–Lehmer(p)
    var s = 4
    var M = 2^p − 1
    repeat p − 2 times:
        s = (s^2 − 2) mod M
    if s = 0 return PRIME else return COMPOSITE

By performing the mod M at each iteration, we ensure that all intermediate results are at most

p

bits (otherwise the number of bits would double each iteration). It is exactly the same strategy employed in modular exponentiation.

Residues of the Lucas–Lehmer primality test

In the table,

M  (  pk ) = 2  pk  −  1

is the

k

th Mersenne number, where the index

pk

refers to the

k

th prime.

Residues of the Lucas–Lehmer primality test

k	pk	M (  pk )	Residues r (n), 0   ≤   n   ≤   k  −  2, for M (  pk ) (  M (  pk ) is prime if and only if r (k  −  2) = 0  )	A-number
1	2	3 Prime Y 1 × 2 + 1	2 being even, the Lucas–Lehmer primality test can’ t be used!
2	3	7 Prime Y 2 × 3 + 1	{4, 0}
3	5	31 Prime Y 6 × 5 + 1	{4, 14, 8, 0}	A??????
4	7	127 Prime Y 18 × 7 + 1	{4, 14, 67, 42, 111, 0}	A129219
5	11	2047 Not prime Y 23 × 89 (2 × 11 + 1) × (8 × 11 + 1)	{4, 14, 194, 788, 701, 119, 1877, 240, 282, 1736}	A129220
6	13	8191 Prime Y 630 × 13 + 1	{4, 14, 194, 4870, 3953, 5970, 1857, 36, 1294, 3470, 128, 0}	A129221
7	17	131071 Prime Y 7710 × 17 + 1	{4, 14, 194, 37634, 95799, 119121, 66179, 53645, 122218, 126220, 70490, 69559, 99585, 78221, 130559, 0}	A129222
8	19	524287 Prime Y 27594 × 19 + 1	{4, 14, 194, 37634, 218767, 510066, 386344, 323156, 218526, 504140, 103469, 417706, 307417, 382989, 275842, 85226, 523263, 0}	A129223
9	23	8388607 Not prime Y 47 × 178481 (2 × 23 + 1) × (7760 × 23 + 1)	{4, 14, 194, 37634, 7031978, 7033660, 1176429, 7643358, 3179743, 2694768, 763525, 4182158, 7004001, 1531454, 5888805, 1140622, 4321431, 7041324, 2756392, 1280050, 6563009, 6107895}	A129224
10	29	536870911 Not prime Y 233 × 1103 × 2089 (8 × 29 + 1) × (72 × 29 + 1)	{4, 14, 194, 37634, 342576132, 250734296, 433300702, 16341479, 49808751, 57936161, 211467447, 71320725, 91230447, 153832672, 217471443, 239636427, 223645010, 90243197, 27374393, 490737401, 35441039, 303927542, 202574536, 515018664, 330289146, 148819211, 365171774, 458738443}	A129225
11	31	2147483647 Prime Y (69273666 × 31 + 1)	{4, 14, 194, 37634, 1416317954, 669670838, 1937259419, 425413602, 842014276, 12692426, 2044502122, 1119438707, 1190075270, 1450757861, 877666528, 630853853, 940321271, 512995887, 692931217, 1883625615, 1992425718, 721929267, 27220594, 1570086542, 1676390412, 1159251674, 211987665, 1181536708, 65536, 0}	A129226
12	37	137438953471 Not prime Y 223 × 616318177 (6 × 37 + 1) × (16657248 × 37 + 1)	{4, 14, 194, 37634, 1416317954, ..., 117093979072}	A??????
13	41	2199023255551 Not prime Y 13367 × 164511353 (326 × 41 + 1) × (4012472 × 41 + 1)	{4, 14, 194, 37634, 1416317954, ..., 856605019673}	A??????
14	43	8796093022207 Not prime Y 431 × 9719 × 2099863 (10 × 43 + 1) × (226 × 43 + 1) × (48834 × 43 + 1)	{4, 14, 194, 37634, 1416317954, ..., 5774401272921}	A??????
15	47	140737488355327 Not prime Y 2351 × 4513 × 13264529 (50 × 47 + 1) × (96 × 47 + 1) × (282224 × 47 + 1)	{4, 14, 194, 37634, 1416317954, ..., 96699253829728}	A??????

A095847 Lucas–Lehmer residues for Mersenne numbers with prime indices.

{1, 0, 0, 0, 1736, 0, 0, 0, 6107895, 458738443, 0, 117093979072, 856605019673, 5774401272921, 96699253829728, 5810550306096509, 450529175803834166, 0, 44350645312365507266, 271761692158955752596, 2941647823169311845731, ...}