mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2006-05-13, 06:22   #1
maxal
 
maxal's Avatar
 
Feb 2005

111111002 Posts
Default 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
maxal is offline   Reply With Quote
Old 2006-05-13, 13:09   #2
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

2·457 Posts
Default

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
T.Rex is offline   Reply With Quote
Old 2006-05-13, 13:20   #3
maxal
 
maxal's Avatar
 
Feb 2005

3748 Posts
Default

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.
maxal is offline   Reply With Quote
Old 2006-05-13, 13:23   #4
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

2·457 Posts
Default

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.
T.Rex is offline   Reply With Quote
Old 2006-05-13, 13:28   #5
maxal
 
maxal's Avatar
 
Feb 2005

FC16 Posts
Default

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?
maxal is offline   Reply With Quote
Old 2006-05-13, 13:55   #6
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

91410 Posts
Default

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.
T.Rex is offline   Reply With Quote
Old 2006-05-24, 23:31   #7
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

23·7·53 Posts
Default

  • 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
ATH is offline   Reply With Quote
Old 2007-05-14, 11:55   #8
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

296810 Posts
Default

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
ATH is offline   Reply With Quote
Old 2007-05-14, 17:28   #9
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
Rep├║blica de California

100110001111112 Posts
Default

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...
ewmayer is offline   Reply With Quote
Old 2007-05-14, 22:51   #10
maxal
 
maxal's Avatar
 
Feb 2005

22·32·7 Posts
Default

Thanks, ATH.
Please submit more terms to http://www.research.att.com/~njas/sequences/A123271
maxal is offline   Reply With Quote
Old 2007-05-15, 00:07   #11
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

296810 Posts
Default

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
ATH is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
lucas-lehmer theorem Robot2357 Math 6 2013-06-15 03:10
Can zero be an "intermediate step" value in Lucas-Lehmer? That Don Guy Math 10 2012-02-03 18:02
lucas lehmer outstretch science_man_88 Miscellaneous Math 7 2010-07-14 12:35
Lucas-Lehmer Test storm5510 Math 22 2009-09-24 22:32
Lucas-Lehmer 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.