mersenneforum.org > Math Penultimate Lucas-Lehmer step
 Register FAQ Search Today's Posts Mark Forums Read

2006-05-13, 06:22   #1
maxal

Feb 2005

111111002 Posts
Penultimate Lucas-Lehmer step

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)?

Quote:
 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

2006-05-13, 13:09   #2
T.Rex

Feb 2004
France

2·457 Posts

Quote:
 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

2006-05-13, 13:20   #3
maxal

Feb 2005

3748 Posts

Quote:
 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.
Quote:
 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.

 2006-05-13, 13:23 #4 T.Rex     Feb 2004 France 2·457 Posts 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.
2006-05-13, 13:28   #5
maxal

Feb 2005

FC16 Posts

Quote:
 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?

2006-05-13, 13:55   #6
T.Rex

Feb 2004
France

91410 Posts

Quote:
 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.

 2006-05-24, 23:31 #7 ATH Einyen     Dec 2003 Denmark 23·7·53 Posts 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. Last fiddled with by ATH on 2006-05-24 at 23:35
 2007-05-14, 11:55 #8 ATH Einyen     Dec 2003 Denmark 296810 Posts 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. Last fiddled with by ATH on 2007-05-14 at 12:14
 2007-05-14, 17:28 #9 ewmayer ∂2ω=0     Sep 2002 República de California 100110001111112 Posts 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...
 2007-05-14, 22:51 #10 maxal     Feb 2005 22·32·7 Posts Thanks, ATH. Please submit more terms to http://www.research.att.com/~njas/sequences/A123271
 2007-05-15, 00:07 #11 ATH Einyen     Dec 2003 Denmark 296810 Posts 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? Last fiddled with by ATH on 2007-05-15 at 00:07

 Similar Threads Thread Thread Starter Forum Replies Last Post Robot2357 Math 6 2013-06-15 03:10 That Don Guy Math 10 2012-02-03 18:02 science_man_88 Miscellaneous Math 7 2010-07-14 12:35 storm5510 Math 22 2009-09-24 22:32 Dougal Information & Answers 9 2009-02-06 10:25

All times are UTC. The time now is 06:59.

Tue Oct 27 06:59:15 UTC 2020 up 47 days, 4:10, 0 users, load averages: 1.46, 1.60, 1.67