Why Lucas-Lehmer Test Works

A question was asked on Mersenneforum.org about why the Lucas-Lehmer test works. The answer given was basically "You need to study Number Theory for years and years to understand the complexity behind why the test works".

Okay, so that's my tongue-in-cheek summarization, but the thread did get a little heated.

I've done a little work with the Lucas-Lehmer sequence, and have found some surprising relationships to Quadratic Residues. Of course, without the years and years of Number Theory studies, I can't come up with a proof, so I'll never get my name on it. ;-)

Basically, it comes down to the fact that all terms of the Lucas-Lehmer sequence modulo a Mersenne number (Mp = 2^p - 1) must be a quadratic residue of that Mersenne number for it to be a Mersenne Prime. If you hit a term in the LL sequence that is not a QR of Mp, then Mp is composite.

Note: I'll qualify by saying that you need to verify that +/- the LL term must be a QR, because of one of those weird Number Theory things. For example, term 2 of the LL modulo 127 is 67. However, 67 is not a QR of 127. But, 127 - 67 = 60, which is a QR, so the test still passes.

So, here appears to be a necessary condition for primality. But that still does not answer the question of "why".

Well, this is where Number Fields come in handy. I'm no expert on fields, but you don't need to be in order to see how a field behaves.

Quadratic residues of a Mersenne Prime form a field of numbers with exactly (2^(p-1) - 1) elements. Each of these elements, when squared (mod Mp) results in another number in the field. This leads to a beautiful cyclical sub-field of exactly p-1 elements (meaning that the subfield starts to repeat itself every p element).

Here is an example of that sub-field effect starting with 44 modulo 127:

44	31	72	104	21	60	44

31 = 44^2 mod 127; 72 = 31^2 mod 127; etc

This behavior does not always exist with composite numbers, because the prime factors of those numbers somehow interfere with the field's behavior (during the modulo operation, I would guess). You end up with something like the fields for each prime factor overlapping, which distorts the results.

For example, here's two subfields modulo 2047 (a Mersenne composite = 23*89). Each starting number is a QR of 2047, but :

64	2	4	16	256	32	1024	512	128	8	64

36	1296	1076	1221	625	1695	1084	78	1990	1202	1669

Notice that 64's subfield correctly "wraps around" after 11 iterations, but 36 fails to. This shows that some subfields are cyclical, while others aren't (because of that interference effect).

When we continue squaring the subfield modulo 2047, we see that we actually jump into another cyclical subfield of the proper length:

36	1296	1076	1221	625	1695	1084	78	1990	1202	1669	1641	1076

In this case, both 1296 and 1641 are modular square roots of 1076, but the subfield containing 1296 actually turns into the subfield containing 1641. The fact that there are two roots for a QR is not unusual, but these numbers are not +/- the same number, as the roots of a prime's QR would be. The overall result is that the field containing all QR's of a Mersenne composite turns out to contain less than 2^(p-1) - 1 elements. (In this example, think because 36 did not have it's own 11 numbers, it only added 2 numbers to the total field).

So, the LL sequence is related to the same mechanism that causes the beautiful cyclical patterns of the quadratic residue subfields. These patterns only exist modulo prime numbers. Composite numbers cause one subfield to change into another. This same mechanism leads to the LL sequence to fail for composite numbers.

And, of course, I don't have any further explaination for this phenomenon, so you'll need to study Number Theory for a while. ;-)

For reference, here is a breakout for M7 (127 = 2^7 - 1). The field of QR's shown are x^2 % Mp, and are Quadratic Residues because they have modulo square roots (x).

Mp	LL	-LL	x	QR	x	QR

127	4	123	1	1	33	73

	14	113	2	4	34	13

	67	60	3	9	35	82

	42	85	4	16	36	26

	111	16	5	25	37	99

-->	0	127	6	36	38	47

	125	2	7	49	39	124

	2	125	8	64	40	76

	2	125	9	81	41	30

	2	125	10	100	42	113

	2	125	11	121	43	71

	2	125	12	17	44	31

	2	125	13	42	45	120

	2	125	14	69	46	84

	2	125	15	98	47	50

			16	2	48	18

			17	35	49	115

			18	70	50	87

			19	107	51	61

			20	19	52	37

			21	60	53	15

			22	103	54	122

			23	21	55	104

			24	68	56	88

			25	117	57	74

			26	41	58	62

			27	94	59	52

			28	22	60	44

			29	79	61	38

			30	11	62	34

			31	72	63	32

			32	8