Penultimate Lucas-Lehmer step

[maxal]

Following the email by Peter-Lawrence Montgomery dated 11 Dec 2003 (quoted below).

1) There are results about some other starting values in Bas Jansen's thesis "Mersenne primes and class field theory" available in PDF file pages 1855-1858 (57-60)

2) Now we have 43 Mersenne primes known. Is it possible to get the sign of a[p-2]/2^((p+1)/2) mod Mp for them from the existing databases (without re-doing Lucas-Lehmer iterations)?

Mersenne: Penultimate Lucas-Lehmer step
Peter-Lawrence . Montgomery
Thu, 11 Dec 2003 08:46:49 -0800

Let p > 2 be prime and Mp = 2^p - 1.
The familiar Lucas-Lehmer test sets a[0] = 4
and a[j+1] = a[j]^2 - 2 for j >= 0.
Mp is prime if and only if a[p-1] == 0 mod Mp.

When Mp is prime, then

a[p-2]^2 == 2 == 2*Mp + 2 = 2^(p+1) (mod Mp).

Taking square roots, either

a[p-2] == 2^((p+1)/2) mod Mp
or
a[p-2] == -2^((p+1)/2) mod Mp.


Around 20 years ago I heard that nobody could predict
which of these would occur. For example,

p = 3 a[1] = 4 == 2^2 (mod 7)
p = 5 a[3] = 194 == 2^3 (mod 31)
p = 7 a[5] = 1416317954 == -2^4 (mod 127).

Now that 40 Mersenne primes are known, can anyone
extend this table further? That will let us test
heuristics, such as whether both +- 2^((p+1)/2)
seem to occur 50% of the time, and
provide data to support or disprove conjectures.

Peter Montgomery

[T.Rex]

Originally Posted by maxal

... in Bas Jansen's thesis "Mersenne primes and class field theory" available in PDF file pages 1855-1858 (57-60)

This document is not the Thesis of Bas Jansen. Where is his thesis available ?
This document is'nt crystal clear for me, probably because it is only a summary (and because I'm an amateur ...). Is that all clear for you ?
Thanks,
Tony

[maxal]

Originally Posted by T.Rex

This document is not the Thesis of Bas Jansen. Where is his thesis available ?

Under "thesis" I meant a short report not a dissertation. And his report is there.

Originally Posted by T.Rex

This document is'nt crystal clear for me, probably because it is only a summary (and because I'm an amateur ...). Is that all clear for you ?

His result is clearly stated there although there is no complete proof.

[T.Rex]

I know about another guy doing a PhD thesis on the same kind of subject. I've forgotten his (complex) name. I think I remember his thesis is planned to end soon. I'll try to find his name in my emails ...
T.

[maxal]

Originally Posted by T.Rex

I know about another guy doing a PhD thesis on the same kind of subject. I've forgotten his (complex) name. I think I remember his thesis is planned to end soon. I'll try to find his name in my emails ...

Isn't that the guy who Bas refers to in the very first paragraph? Gebre-Egziabher?

[T.Rex]

Originally Posted by maxal

Isn't that the guy who Bas refers to in the very first paragraph? Gebre-Egziabher?

YES! I read this part too fast.
T.

[ATH]

• M2: p = 3, s[p-3] = 2^2 (mod Mp)
• M3: p = 5, s[p-3] = 2^3 (mod Mp)
• M4: p = 7, s[p-3] = -2^4 (mod Mp).
• M5: p = 13, s[p-3] = 2^7 (mod Mp).
• M6: p = 17, s[p-3] = -2^9 (mod Mp).
• M7: p = 19, s[p-3] = -2^10 (mod Mp).
• M8: p = 31, s[p-3] = 2^16 (mod Mp).
• M9: p = 61, s[p-3] = 2^31 (mod Mp).
• M10: p = 89, s[p-3] = -2^45 (mod Mp).
• M11: p = 107, s[p-3] = -2^54 (mod Mp).
• M12: p = 127, s[p-3] = 2^64 (mod Mp).
• M13: p = 521, s[p-3] = -2^261 (mod Mp).
• M14: p = 607, s[p-3] = -2^304 (mod Mp).
• M15: p = 1279, s[p-3] = -2^640 (mod Mp).
• M16: p = 2203, s[p-3] = 2^1102 (mod Mp).
• M17: p = 2281, s[p-3] = -2^1141 (mod Mp).
• M18: p = 3217, s[p-3] = -2^1609 (mod Mp).
• M19: p = 4253, s[p-3] = 2^2127 (mod Mp).
• M20: p = 4423, s[p-3] = -2^2212 (mod Mp).
• M21: p = 9689, s[p-3] = -2^4845 (mod Mp).
• M22: p = 9941, s[p-3] = 2^4971 (mod Mp).
• M23: p = 11213, s[p-3] = -2^5607 (mod Mp).
• M24: p = 19937, s[p-3] = 2^9969 (mod Mp).
• M25: p = 21701, s[p-3] = -2^10851 (mod Mp).
• M26: p = 23209, s[p-3] = 2^11605 (mod Mp).
• M27: p = 44497, s[p-3] = -2^22249 (mod Mp).
• M28: p = 86243, s[p-3] = 2^43122 (mod Mp).
• M29: p = 110503, s[p-3] = 2^55252 (mod Mp).
• M30: p = 132049, s[p-3] = 2^66025 (mod Mp).
• M31: p = 216091, s[p-3] = -2^108046 (mod Mp).
• M32: p = 756839, s[p-3] = 2^378420 (mod Mp).

This is as far as I got with just C++ and GMP library:

From M2-M32:
15 times s[p-3]=+2^((p+1)/2)
16 times s[p-3]=-2^((p+1)/2)

We need prime95 to be configured to save last iteration for the rest of them.

[ATH]

I went back and finished the list with prime95:

M2: p=3 s[p-3]== 2^((p+1)/2) (mod Mp)
M3: p=5 s[p-3]== 2^((p+1)/2) (mod Mp)
M4: p=7 s[p-3]== -2^((p+1)/2) (mod Mp).
M5: p=13 s[p-3]== 2^((p+1)/2) (mod Mp).
M6: p=17 s[p-3]== -2^((p+1)/2) (mod Mp).
M7: p=19 s[p-3]== -2^((p+1)/2) (mod Mp).
M8: p=31 s[p-3]== 2^((p+1)/2) (mod Mp).
M9: p=61 s[p-3]== 2^((p+1)/2) (mod Mp).
M10: p=89 s[p-3]== -2^((p+1)/2) (mod Mp).
M11: p=107 s[p-3]== -2^((p+1)/2) (mod Mp).
M12: p=127 s[p-3]== 2^((p+1)/2) (mod Mp).
M13: p=521 s[p-3]== -2^((p+1)/2) (mod Mp).
M14: p=607 s[p-3]== -2^((p+1)/2) (mod Mp).
M15: p=1279 s[p-3]== -2^((p+1)/2) (mod Mp).
M16: p=2203 s[p-3]== 2^((p+1)/2) (mod Mp).
M17: p=2281 s[p-3]== -2^((p+1)/2) (mod Mp).
M18: p=3217 s[p-3]== -2^((p+1)/2) (mod Mp).
M19: p=4253 s[p-3]== 2^((p+1)/2) (mod Mp).
M20: p=4423 s[p-3]== -2^((p+1)/2) (mod Mp).
M21: p=9689 s[p-3]== -2^((p+1)/2) (mod Mp).
M22: p=9941 s[p-3]== 2^((p+1)/2) (mod Mp).
M23: p=11213 s[p-3]== -2^((p+1)/2) (mod Mp).
M24: p=19937 s[p-3]== 2^((p+1)/2) (mod Mp).
M25: p=21701 s[p-3]== -2^((p+1)/2) (mod Mp).
M26: p=23209 s[p-3]== 2^((p+1)/2) (mod Mp).
M27: p=44497 s[p-3]== -2^((p+1)/2) (mod Mp).
M28: p=86243 s[p-3]== 2^((p+1)/2) (mod Mp).
M29: p=110503 s[p-3]== 2^((p+1)/2) (mod Mp).
M30: p=132049 s[p-3]== 2^((p+1)/2) (mod Mp).
M31: p=216091 s[p-3]== -2^((p+1)/2) (mod Mp).
M32: p=756839 s[p-3]== 2^((p+1)/2) (mod Mp).
M33: p=859433 s[p-3]== -2^((p+1)/2) (mod Mp).
M34: p=1257787 s[p-3]== -2^((p+1)/2) (mod Mp).
M35: p=1398269 s[p-3]== 2^((p+1)/2) (mod Mp).
M36: p=2976221 s[p-3]== 2^((p+1)/2) (mod Mp).
M37: p=3021377 s[p-3]== 2^((p+1)/2) (mod Mp).
M38: p=6972593 s[p-3]== 2^((p+1)/2) (mod Mp).
M39: p=13466917 s[p-3]== 2^((p+1)/2) (mod Mp).
M40?:p=20996011 s[p-3]== 2^((p+1)/2) (mod Mp).
M41?:p=24036583 s[p-3]== -2^((p+1)/2) (mod Mp).
M42?:p=25964951 s[p-3]== 2^((p+1)/2) (mod Mp).
M43?:p=30402457 s[p-3]== -2^((p+1)/2) (mod Mp).
M44?:p=32582657 s[p-3]== -2^((p+1)/2) (mod Mp).

So 22+ and 21- so far.

Here is residues from the last iterations from prime95 for each exponent: results.txt

I have intermediate savefiles from M32-M44 if anyone needs for anything else.

Edit: Prime95 gave some wierd residues for p<521 so I calculated them myself and pasted into the Prime95 log.

[ewmayer]

Nice work, ATH. No correlation with the usual suspects (congruence of exponent mod 4 and 6), and no apparent correlation with regular/irregular-prime status of the exponent -- the roughly equal fraction of +- signs would also seem to rule the latter out, even in the absence of an exponent-by-exponent comparison. (Not that we expect any correlation based on that to begin with, but just by way of kicking the tires, as it were.)

Seems pretty random to me...

[maxal]

Thanks, ATH.
Please submit more terms to http://www.research.att.com/~njas/sequences/A123271

[ATH]

I'm not sure how to submit terms, can you do it? The missing terms are:
-1, -1, 1, 1, 1, 1, 1, 1, -1, 1, -1, -1

Btw it doesn't say that the sequence starts for n=2 or is that what "OFFSET 2,1" means?