mersenneforum.org Modifying the Lucas Lehmer Primality Test into a fast test of nothing
 Register FAQ Search Today's Posts Mark Forums Read

2014-11-05, 00:29   #12
CRGreathouse

Aug 2006

32×5×7×19 Posts

Quote:
 Originally Posted by ewmayer Anyone who's ever implemented the IBDWT knows it's not trivial, and to do it efficiently even less so. But yes, once you've got an efficient implementation the implicit-mod is nearly free (say < 10% of runtime, and costing O(n) vs the FFT's O(n lg n)).
It wouldn't surprise me if (with a horrendous amount of effort) one could code a LL-like 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...!

2014-11-06, 00:17   #13
Trilo

"W. Byerly"
Aug 2013
1423*2^2179023-1

103 Posts

Quote:
 Originally Posted by CRGreathouse It wouldn't surprise me if (with a horrendous amount of effort) one could code a LL-like 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...!
Diving a little more into my question I have noticed a pattern between n mod Mn and n mod Mn+1

Consider the moduli and divisions (with decimal truncated) after each iteration of the Lucas-Lehmer test of 210-1, where x is the x-th iteration through the test:

Sx (mod Mn)------Mn/Sx
---------------------------------------
1. 14------------0
2. 194----------0
3. 806----------36
4. 29------------635
5. 839----------0
6. 95------------688
7. 839----------8
8. 95------------688

Now consider Sx (mod Mn+1). Note that the x-th iteration was performed using x-1 iterations of the Lucas Lehmer test and the final iteration was performed with a Sx (mod Mn+ 1) rather than Sx (mod Mn).

Sx (mod Mn+1)---(Mn+1)/Sx
------------------------------------------
1. 14------------0
2. 194----------0
3. 770----------36
4. 418----------634
5. 839----------0
6. 431----------687
7. 831----------8
8. 431----------687

Looking at this raw data, one can make a few observations. lets define

d0 = Mn/Sx,
d1 = (Mn+1)/Sx
m0 = Sx (mod Mn)
m1= Sx (mod Mn+1)

One may notice that when d0=d1= 0, m0= m1. This is obvious. Additionally, notice that either d0= d1 or d0= d1+1. Upon further inspection, one finds

d0= d1 + 1 if m0 - d0 < 0 and
d0= d1 if m0 - d0 >= 0

one may also notice

m1= m0+ d0 if d0= d1 and
m1= (m0+ d0 - 1) - Mn if d0= d1 + 1

From the previous observation, one may substitute the if conditions to obtain

m1= m0+ d0 if m0 - d0 >= 0 and
m1= (m0+ d0 - 1) - Mn if m0 - d0 < 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) Mn. 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 210-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.

2014-11-06, 00:35   #14
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

29·211 Posts

Quote:
 Originally Posted by Trilo Like mentioned in a previous post, calculating moduli and division by powers of 2 is extremely trivial to do on a computer ...
Yup, it is. And like you have already been told by LaurV, doing mod Mn is also trivial so you are not gaining anything here.

2014-11-06, 00:38   #15
Trilo

"W. Byerly"
Aug 2013
1423*2^2179023-1

103 Posts

Quote:
 Originally Posted by retina Yup, it is. And like you have already been told by LaurV, doing mod Mn is also trivial so you are not gaining anything here.
Quote:
 Originally Posted by ewmayer Anyone who's ever implemented the IBDWT knows it's not trivial, and to do it efficiently even less so. But yes, once you've got an efficient implementation the implicit-mod is nearly free (say < 10% of runtime, and costing O(n) vs the FFT's O(n lg n)).
.

Last fiddled with by Trilo on 2014-11-06 at 00:39

2014-11-06, 00:48   #16
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 Originally Posted by Trilo Looking at this raw data, one can make a few observations. lets define d0 = Mn/Sx, d1 = (Mn+1)/Sx m0 = Sx (mod Mn) m1= Sx (mod Mn+1) One may notice that when d0=d1= 0, m0= m1. This is obvious. Additionally, notice that either d0= d1 or d0= d1+1. Upon further inspection, one finds d0= d1 + 1 if m0 - d0 < 0 and d0= d1 if m0 - d0 >= 0 one may also notice m1= m0+ d0 if d0= d1 and m1= (m0+ d0 - 1) - Mn if d0= d1 + 1 From the previous observation, one may substitute the if conditions to obtain m1= m0+ d0 if m0 - d0 >= 0 and m1= (m0+ d0 - 1) - Mn if m0 - d0 < 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) Mn. 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 210-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.
I like patterns but one thing I'd point out is that if d0 = d1+1 is true then the part using m0+d0-1 gets simplified to m0+d1 is there a reason I'm missing for not simplifying ? edit: realized I didn't use the full equation when I was talking about what I said.

Last fiddled with by science_man_88 on 2014-11-06 at 00:56

2014-11-06, 01:06   #17
Trilo

"W. Byerly"
Aug 2013
1423*2^2179023-1

1478 Posts

Quote:
 Originally Posted by science_man_88 I like patterns but one thing I'd point out is that if d0 = d1+1 is true then the part using m0+d0-1 gets simplified to m0+d1 is there a reason I'm missing for not simplifying ? edit: realized I didn't use the full equation when I was talking about what I said.
That and calculating m0 and d0 is trivial to do on a computer while d1 and m1 is not trivial to compute and it gets rid of the whole purpose of writing m1 in terms of m0 and d0.

2014-11-06, 01:24   #18
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 Originally Posted by Trilo That and calculating m0 and d0 is trivial to do on a computer while d1 and m1 is not trivial to compute and it gets rid of the whole purpose of writing m1 in terms of m0 and d0.
m1 is the last n bits and is the mod (Mn+1) you were talking of at last check ?

2014-11-06, 04:02   #19
LaurV
Romulan Interpreter

Jun 2011
Thailand

100100100111112 Posts

Quote:
 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!
Well, that explains it. You should say so from the start.
First thing, have a look to $\TeX$ 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).

Quote:
 Originally Posted by Trilo 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.
It will not be faster. And the proof is trivial. Assume that some number is equal to $b$ (mod $2^n$), this means the number is $a*2^n+b$, now add and substract $a$ to it. You have $a*2^n+a-a+b$ and by convenient pairing you have $a*(2^n-1)+a+b$, or say, your number is $a+b$ (mod $2^n-1$). 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 modular-math 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 2014-11-06 at 04:05

2014-11-06, 06:20   #20
flagrantflowers

Apr 2014

27 Posts

Quote:
 Originally Posted by Trilo "Apologies if I got any of the math formatting wrong, I am in high school…
The fact that you acknowledge that your ideas may not be unique and may in fact be trivial is a big place to be in high school. I didn't have that and I don't think that most of the talented people here had that.

Keep on plugin' on…

 2018-03-07, 02:22 #21 gophne   Feb 2017 2458 Posts Markers in Lucas-Lehmer? The fact that the Lucas-Lehmer iteration works suggests to me that the distribution of mersenne prime numbers are "regular', dependant on the outcome of the LL iteration, but never-the-less "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.
2018-03-07, 02:57   #22
ewmayer
2ω=0

Sep 2002
República de California

3×53×31 Posts

Quote:
 Originally Posted by gophne The fact that the Lucas-Lehmer iteration works suggests to me that the distribution of mersenne prime numbers are "regular', dependant on the outcome of the LL iteration, but never-the-less "regular".
One could make the same claim with regard to, say, the base-2 Fermat compositeness test and the primes. Such tests 'work' because they rely in one manner or another on the existence of a primitive root of the mathematical group defined by multiplication modulo N, which means a root of the maximal possible order N−1. Such tests already short-cut the primitive-root checking as much as possible by proceeding (in effect) to computing an (N-1)th modular power via one-modmul-per-bit-of-N powering ladder; if you want to believe that this work estimate can be further improved on or that the fact that there exist fast methods of confirming existence of such a primitive root for various special classes of moduli equates to "theres a pattern to these primes" be my guest, but belief != proof (nor even plausibility).

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 2018-03-07 at 02:58

 Similar Threads Thread Thread Starter Forum Replies Last Post Mathsgirl Information & Answers 23 2014-12-10 16:25 kurtulmehtap Math 13 2009-10-02 12:12 storm5510 Math 22 2009-09-24 22:32 alpertron mersennewiki 16 2006-03-18 07:23 CMOSMIKE Math 5 2002-09-06 18:46

All times are UTC. The time now is 17:23.

Sat Apr 17 17:23:22 UTC 2021 up 9 days, 12:04, 0 users, load averages: 1.51, 1.75, 1.64