20141105, 00:29  #12 
Aug 2006
5933_{10} Posts 
It wouldn't surprise me if (with a horrendous amount of effort) one could code a LLlike test which worked mod M_p + 1 instead of M_p and ran, say, 5% faster by cutting out the rest of the reduction cost. There's just the little issue by which the result would tell you nothing about the primality of the number...!

20141106, 00:17  #13  
"W. Byerly"
Aug 2013
1423*2^21790231
5×19 Posts 
Quote:
Consider the moduli and divisions (with decimal truncated) after each iteration of the LucasLehmer test of 2^{10}1, where x is the xth iteration through the test: S_{x} (mod M_{n})M_{n}/S_{x} 
Now consider S_{x} (mod M_{n}+1). Note that the xth iteration was performed using x1 iterations of the Lucas Lehmer test and the final iteration was performed with a S_{x} (mod M_{n}+ 1) rather than S_{x} (mod M_{n}). S_{x} (mod M_{n}+1)(M_{n}+1)/S_{x} 
Looking at this raw data, one can make a few observations. lets define d_{0} = M_{n}/S_{x}, d_{1} = (M_{n}+1)/S_{x} m_{0} = S_{x} (mod M_{n}) m_{1}= S_{x} (mod M_{n}+1) One may notice that when d_{0}=d_{1}= 0, m_{0}= m_{1}. This is obvious. Additionally, notice that either d_{0}= d_{1} or d_{0}= d_{1}+1. Upon further inspection, one finds d_{0}= d_{1} + 1 if m_{0}  d_{0} < 0 and d_{0}= d_{1} if m_{0}  d_{0} >= 0 one may also notice m_{1}= m_{0}+ d_{0} if d_{0}= d_{1} and m_{1}= (m_{0}+ d_{0}  1)  M_{n} if d_{0}= d_{1} + 1 From the previous observation, one may substitute the if conditions to obtain m_{1}= m_{0}+ d_{0} if m_{0}  d_{0} >= 0 and m_{1}= (m_{0}+ d_{0}  1)  M_{n} if m_{0}  d_{0} < 0 Like mentioned in a previous post, calculating moduli and division by powers of 2 is extremely trivial to do on a computer (along with addition and subtraction), so this is a very simple way of calculating n (mod) M_{n}. The question now is will this be a faster implementation of modulus than the previous algorithm, and can my observations be proven? I may prove them later; I suspect most of the observations can be proven by induction, so it should be a fairly trivial proof. Apologies if I got any of the math formatting wrong, I am in high school, and I still have a lot of practicing to do to get good at writing my observations in mathematical terms! If my hypothesis is wrong, I suspect the issue may lie in writing it mathematically rather than an issue with the hypothesis itself. I also tested this out on many more (and larger) Lucas Lehmer tests than just 2^{10}1 but I posted this small one as an example so you could follow my hypothesis with me. Just 8 iterations is not enough data to draw any conclusions upon indeed. 

20141106, 00:35  #14 
Undefined
"The unspeakable one"
Jun 2006
My evil lair
2^{6}·7·13 Posts 

20141106, 00:38  #15  
"W. Byerly"
Aug 2013
1423*2^21790231
5·19 Posts 
Quote:
Last fiddled with by Trilo on 20141106 at 00:39 

20141106, 00:48  #16  
"Forget I exist"
Jul 2009
Dumbassville
8,369 Posts 
Quote:
Last fiddled with by science_man_88 on 20141106 at 00:56 

20141106, 01:06  #17  
"W. Byerly"
Aug 2013
1423*2^21790231
5×19 Posts 
Quote:


20141106, 01:24  #18 
"Forget I exist"
Jul 2009
Dumbassville
8,369 Posts 
m1 is the last n bits and is the mod (Mn+1) you were talking of at last check ?

20141106, 04:02  #19  
Romulan Interpreter
Jun 2011
Thailand
2^{2}·7·317 Posts 
Quote:
First thing, have a look to if you want to write math stuff in the future, hehe. Using lots of sub/sub/sup/sup does not look nice, and is "heavy" (not mentioning very difficult to write, but try a reply to your own post and see how it looks in quotes). It will not be faster. And the proof is trivial. Assume that some number is equal to (mod ), this means the number is , now add and substract to it. You have and by convenient pairing you have , or say, your number is (mod ). That is what I said in the former post. You can do about the same for the +1 side. You didn't find anything beside a very trivial modularmath result, so simple it does not need any proof. Still ok, if you found that by yourself. That is approximately how I started too, years ago (and don't look to me, I am just a big mouth, but some big guns here also started like that, even if they don't want to recognize it anymore). The key is to work hard and learn new things... Last fiddled with by LaurV on 20141106 at 04:05 

20141106, 06:20  #20  
Apr 2014
2^{7} Posts 
Quote:
Keep on plugin' on… 

20180307, 02:22  #21 
Feb 2017
3×5×11 Posts 
Markers in LucasLehmer?
The fact that the LucasLehmer iteration works suggests to me that the distribution of mersenne prime numbers are "regular', dependant on the outcome of the LL iteration, but nevertheless "regular".
My question would be if anybody has ever looked or found any "marker/s" in the set of values generated by each mersenne prime iteration. Such things as say the term nearest to the "square root" position value of the set of iterations being of a certain relationship to the value of the successful value which would yield a return of "0", or any other relationship between the values comprising the set of iterations for a specific mersenne prime. Any such marker could then either reduce the time needed to "prove" primality, or be an indicator whether it would be fruitful to continue with that iteration. 
20180307, 02:57  #22  
∂^{2}ω=0
Sep 2002
República de California
2^{2}·31·79 Posts 
Quote:
One could just as well argue that "trial division up to sqrt(N) fails for N prime  thus there must a pattern!" Last fiddled with by ewmayer on 20180307 at 02:58 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
LucasLehmer test  Mathsgirl  Information & Answers  23  20141210 16:25 
proof the lucas lehmer test  kurtulmehtap  Math  13  20091002 12:12 
LucasLehmer Test  storm5510  Math  22  20090924 22:32 
LucasLehmer Test proof  alpertron  mersennewiki  16  20060318 07:23 
LucasLehmer primality test  CMOSMIKE  Math  5  20020906 18:46 