Modifying the Lucas Lehmer Primality Test into a fast test of nothing
 

I have been looking into how the Lucas Lehmer test works. The test states to define a sequence [I]s[SUB]n[/SUB][/I] where [I]s[SUB]0[/SUB][/I]= 4 and [I]s[SUB]n[/SUB][/I]= [I]s[SUB]n-1[/SUB][SUP]2[/SUP][/I]-2 and if [I]s[SUB]n-2[/SUB][/I] evently divides M[SUB]n[/SUB] then M[SUB]n[/SUB] is prime.

What I am wondering is if it is possible to modify the test to instead prove M[SUB]n[/SUB] prime iff M[SUB]n[/SUB]+1 evenly divides [I]s[SUB]n-2[/SUB][/I]

The basic idea of most compositeness tests (aside from trial division!) is to work in the ring $(\mathbb{Z}/N\mathbb{Z})^*$ and show that it isn't a field. The basic idea of most primality tests is to work in the same ring and show that it must be a field. Neither of these ideas work if you use a modulus other than the number itself.

[QUOTE=CRGreathouse;386745]The basic idea of most compositeness tests (aside from trial division!) is to work in the ring $(\mathbb{Z}/N\mathbb{Z})^*$ and show that it isn't a field. The basic idea of most primality tests is to work in the same ring and show that it must be a field. Neither of these ideas work if you use a modulus other than the number itself.[/QUOTE]

Thats what I thought. If I knew what [I]s[SUB]n-2[/SUB][/I] (mod M[SUB]n[/SUB]+1) was, is there any way to easily find [I]s[SUB]n-2[/SUB][/I] (mod M[SUB]n[/SUB]) computation wise?

Probably not, since the moduli are coprime and [TEX]s_{n-1}[/TEX] is much larger than they are.

[QUOTE=Trilo;386743]I have been looking into how the Lucas Lehmer test works. The test states to define a sequence [I]s[SUB]n[/SUB][/I] where [I]s[SUB]0[/SUB][/I]= 4 and [I]s[SUB]n[/SUB][/I]= [I]s[SUB]n-1[/SUB][SUP]2[/SUP][/I]-2 and if [I]s[SUB]n-2[/SUB][/I] evently divides M[SUB]n[/SUB] then M[SUB]n[/SUB] is prime. [/QUOTE]
You apparently haven't been looking very hard, because you got the what-divides-what backwards.

[QUOTE]What I am wondering is if it is possible to modify the test to instead prove M[SUB]n[/SUB] prime iff M[SUB]n[/SUB]+1 evenly divides [I]s[SUB]n-2[/SUB][/I][/QUOTE]
You might as well ask, "I know that M[SUB]n[/SUB]+1 is a power of 2 -- what does that tell me about primality (or not) of M[SUB]n[/SUB]?" The answer is: nothing whatsoever.

[QUOTE=CRGreathouse;386750]Probably not, since the moduli are coprime and [TEX]s_{n-1}[/TEX] is much larger than they are.[/QUOTE]

[QUOTE="http://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_primality_test#Time_complexity"] [TEX]k\eq (k \pmod {2^n}) + \lfloor{k/2^n}\rfloor \pmod{2^n-1}[/TEX][/QUOTE] okay this may not be easy but it uses one to find the other it's just you need more than just that. I still don't completely see how it speeds it up much if at all.

[QUOTE=science_man_88;386761]okay this may not be easy but it uses one to find the other it's just you need more than just that. I still don't completely see how it speeds it up much if at all.[/QUOTE]

Performing n (mod 2[SUP]m[/SUP]) is equivalent to n & (2[SUP]m[/SUP]- 1) where & is the [URL="http://en.wikipedia.org/wiki/Bitwise_operation#AND"]AND bitwise operator[/URL]. Also, performing n/2[SUP]m[/SUP] can be simplified to n >> m where >> is the [URL="http://en.wikipedia.org/wiki/Bitwise_operation#Arithmetic_shift"]binary right shift operator[/URL]. Note that the remainder/decimal point will be discarded when doing right shifts, so 5 >> 1= 2 and not 2.5 and 11 >> 2= 2 and not 2.75. As you can see, performing n (mod 2[SUP]m[/SUP]) is trivial on a computer, and this is why I was asking whether it was possible to compute n (mod 2[SUP]p[/SUP]+1) given n (mod 2[SUP]p[/SUP]). However, it looks like the Wikipedia page (and GIMPS) has already taken advantage of this specific pattern when applying the Lucas-Lehmer test.

[QUOTE=Trilo;386825]Performing n (mod 2[SUP]m[/SUP]) is equivalent to n & (2[SUP]m[/SUP]- 1) where & is the [URL="http://en.wikipedia.org/wiki/Bitwise_operation#AND"]AND bitwise operator[/URL]. Also, performing n/2[SUP]m[/SUP] can be simplified to n >> m where >> is the [URL="http://en.wikipedia.org/wiki/Bitwise_operation#Arithmetic_shift"]binary right shift operator[/URL]. Note that the remainder/decimal point will be discarded when doing right shifts, so 5 >> 1= 2 and not 2.5 and 11 >> 2= 2 and not 2.75. As you can see, performing n (mod 2[SUP]m[/SUP]) is trivial on a computer, and this is why I was asking whether it was possible to compute n (mod 2[SUP]p[/SUP]+1) given n (mod 2[SUP]p[/SUP]). However, it looks like the Wikipedia page (and GIMPS) has already taken advantage of this specific pattern when applying the Lucas-Lehmer test.[/QUOTE]When compared to mod Mn the "speed up" is negligible. Doing mod Mn is also trivial and comes for free with the way the FFTs are currently done.

Even it would not be so, doing n (mod 2^x-1) where n is a*2^x+b, is equivalent with doing a+b. Which is only a bit split/shift and one addition. For example, 39 mod 15 is 2*16+7 mod 15, or 2+7=9 mod 15. In binary, you just split 100111 into 10 and 0111 and add them. The equivalent calculus could be done for (mod 2^x+1) too. Where you lose the time is actually squaring part, and not taking the mod. Taking the mod is trivial.

the only alteration I can think of is using algebra and starting from the end result of a mersenne prime:

[TEX]S_{n-2} = (4 \times x+2) \times M_{n}[/TEX]

which can use [TEX]{M_n}^2 = M_{n-1}\times M_{n+1} +2^{n-1}[/TEX]

to figure out the next results:

[TEX]S_{n-1} ={(4 \times x +2)}^2 * {M_n}^2 -2 = (16 \times x^2 +16 \times x +4 ) \times (M_{n-1}\times M_{n+1} +2^{n-1}) -2[/TEX]

this can be reduced more and then use (a*b+c)^2-2 to figure it out from there but I think figuring it out algebraically is going to be slower than what is already implemented.

[QUOTE=retina;386828]Doing mod Mn is also trivial and comes for free with the way the FFTs are currently done.[/QUOTE]

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

[QUOTE=ewmayer;386868]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)).[/QUOTE]

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...!

[QUOTE=CRGreathouse;386880]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...![/QUOTE]

Diving a little more into my question I have noticed a pattern between n mod M[SUB]n[/SUB] and n mod M[SUB]n[/SUB]+1

Consider the moduli and divisions (with decimal truncated) after each iteration of the Lucas-Lehmer test of 2[SUP]10[/SUP]-1, where x is the [I]x-th[/I] iteration through the test:


[I]S[SUB]x[/SUB] (mod M[SUB]n[/SUB])[/I]------[I]M[SUB]n[/SUB]/S[SUB]x[/SUB][/I]
---------------------------------------[LIST=1][*]14------------0[*]194----------0[*]806----------36[*]29------------635[*]839----------0[*]95------------688[*]839----------8[*]95------------688[/LIST]
Now consider S[SUB]x[/SUB] (mod M[SUB]n[/SUB]+1). Note that the [I]x-th[/I] iteration was performed using [I]x-1[/I] iterations of the Lucas Lehmer test and the final iteration was performed with a S[SUB]x[/SUB] (mod M[SUB]n[/SUB]+ 1) rather than S[SUB]x[/SUB] (mod M[SUB]n[/SUB]).


[I]S[SUB]x[/SUB] (mod M[SUB]n[/SUB]+1)[/I]---[I](M[SUB]n[/SUB]+1)/S[SUB]x[/SUB][/I]
------------------------------------------[LIST=1][*]14------------0[*]194----------0[*]770----------36[*]418----------634[*]839----------0[*]431----------687[*]831----------8[*]431----------687[/LIST]
Looking at this raw data, one can make a few observations. lets define

d[SUB]0[/SUB] = M[SUB]n[/SUB]/S[SUB]x[/SUB],
d[SUB]1[/SUB] = (M[SUB]n[/SUB]+1)/S[SUB]x[/SUB]
m[SUB]0[/SUB] = S[SUB]x[/SUB] (mod M[SUB]n[/SUB])
m[SUB]1[/SUB]= S[SUB]x[/SUB] (mod M[SUB]n[/SUB]+1)

One may notice that when d[SUB]0[/SUB]=d[SUB]1[/SUB]= 0, m[SUB]0[/SUB]= m[SUB]1[/SUB]. This is obvious. Additionally, notice that either d[SUB]0[/SUB]= d[SUB]1[/SUB] or d[SUB]0[/SUB]= d[SUB]1[/SUB]+1. Upon further inspection, one finds

d[SUB]0[/SUB]= d[SUB]1[/SUB] + 1 if m[SUB]0[/SUB] - d[SUB]0[/SUB] < 0 and
d[SUB]0[/SUB]= d[SUB]1[/SUB] if m[SUB]0[/SUB] - d[SUB]0[/SUB] >= 0

one may also notice

m[SUB]1[/SUB]= m[SUB]0[/SUB]+ d[SUB]0[/SUB] if d[SUB]0[/SUB]= d[SUB]1[/SUB] and
m[SUB]1[/SUB]= (m[SUB]0[/SUB]+ d[SUB]0[/SUB] - 1) - M[SUB]n[/SUB] if d[SUB]0[/SUB]= d[SUB]1[/SUB] + 1

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

m[SUB]1[/SUB]= m[SUB]0[/SUB]+ d[SUB]0[/SUB] if m[SUB]0[/SUB] - d[SUB]0[/SUB] >= 0 and
m[SUB]1[/SUB]= (m[SUB]0[/SUB]+ d[SUB]0[/SUB] - 1) - M[SUB]n[/SUB] if m[SUB]0[/SUB] - d[SUB]0[/SUB] < 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[SUB]n[/SUB]. 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[SUP]10[/SUP]-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.

[QUOTE=Trilo;386969]Like mentioned in a previous post, calculating moduli and division by powers of 2 is extremely trivial to do on a computer ...[/QUOTE]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=retina;386970]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]

[QUOTE=ewmayer;386868]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)).[/QUOTE]

.

[QUOTE=Trilo;386969]

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

d[SUB]0[/SUB] = M[SUB]n[/SUB]/S[SUB]x[/SUB],
d[SUB]1[/SUB] = (M[SUB]n[/SUB]+1)/S[SUB]x[/SUB]
m[SUB]0[/SUB] = S[SUB]x[/SUB] (mod M[SUB]n[/SUB])
m[SUB]1[/SUB]= S[SUB]x[/SUB] (mod M[SUB]n[/SUB]+1)

One may notice that when d[SUB]0[/SUB]=d[SUB]1[/SUB]= 0, m[SUB]0[/SUB]= m[SUB]1[/SUB]. This is obvious. Additionally, notice that either d[SUB]0[/SUB]= d[SUB]1[/SUB] or d[SUB]0[/SUB]= d[SUB]1[/SUB]+1. Upon further inspection, one finds

d[SUB]0[/SUB]= d[SUB]1[/SUB] + 1 if m[SUB]0[/SUB] - d[SUB]0[/SUB] < 0 and
d[SUB]0[/SUB]= d[SUB]1[/SUB] if m[SUB]0[/SUB] - d[SUB]0[/SUB] >= 0

one may also notice

m[SUB]1[/SUB]= m[SUB]0[/SUB]+ d[SUB]0[/SUB] if d[SUB]0[/SUB]= d[SUB]1[/SUB] and
m[SUB]1[/SUB]= (m[SUB]0[/SUB]+ d[SUB]0[/SUB] - 1) - M[SUB]n[/SUB] if d[SUB]0[/SUB]= d[SUB]1[/SUB] + 1

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

m[SUB]1[/SUB]= m[SUB]0[/SUB]+ d[SUB]0[/SUB] if m[SUB]0[/SUB] - d[SUB]0[/SUB] >= 0 and
m[SUB]1[/SUB]= (m[SUB]0[/SUB]+ d[SUB]0[/SUB] - 1) - M[SUB]n[/SUB] if m[SUB]0[/SUB] - d[SUB]0[/SUB] < 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[SUB]n[/SUB]. 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[SUP]10[/SUP]-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.[/QUOTE] I like patterns but one thing I'd point out is that if d[SUB]0[/SUB] = d[SUB]1[/SUB]+1 is true then the part using m[SUB]0[/SUB]+d[SUB]0[/SUB]-1 gets simplified to m[SUB]0[/SUB]+d[SUB]1[/SUB] 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.

[QUOTE=science_man_88;386972]I like patterns but one thing I'd point out is that if d[SUB]0[/SUB] = d[SUB]1[/SUB]+1 is true then the part using m[SUB]0[/SUB]+d[SUB]0[/SUB]-1 gets simplified to m[SUB]0[/SUB]+d[SUB]1[/SUB] 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.[/QUOTE]

That and calculating m[SUB]0[/SUB] and d[SUB]0[/SUB] is trivial to do on a computer while d[SUB]1[/SUB] and m[SUB]1[/SUB] is not trivial to compute and it gets rid of the whole purpose of writing m[SUB]1[/SUB] in terms of m[SUB]0[/SUB] and d[SUB]0[/SUB].

[QUOTE=Trilo;386974]That and calculating m[SUB]0[/SUB] and d[SUB]0[/SUB] is trivial to do on a computer while d[SUB]1[/SUB] and m[SUB]1[/SUB] is not trivial to compute and it gets rid of the whole purpose of writing m[SUB]1[/SUB] in terms of m[SUB]0[/SUB] and d[SUB]0[/SUB].[/QUOTE]

m1 is the last n bits and is the mod (Mn+1) you were talking of at last check ?

[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![/quote]Well, that explains it. You should say so from the start. :razz:
First thing, have a look to [TEX]\TeX[/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=Trilo;386969]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.
[/QUOTE]
It will not be faster. And the proof is trivial. Assume that some number is equal to [TEX]b[/TEX] (mod [TEX]2^n[/TEX]), this means the number is [TEX]a*2^n+b[/TEX], now add and substract [TEX]a[/TEX] to it. You have [TEX]a*2^n+a-a+b[/TEX] and by convenient pairing you have [TEX]a*(2^n-1)+a+b[/TEX], or say, your number is [TEX]a+b[/TEX] (mod [TEX]2^n-1[/TEX]). 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 :wink: (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...

[QUOTE=Trilo;386969]"Apologies if I got any of the math formatting wrong, I am in high school…[/QUOTE]

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…

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.

[QUOTE=gophne;481754]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".[/QUOTE]

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!"

[QUOTE=gophne;481754]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.[/QUOTE]

Iterations that hit -2,-1,0,1,2 mod the mersenne, prior to the final iteration are either bad, or not prime. We also know (uselessly) that the residue has the same parity as the floor of the full number divided by the mersenne. Another useless fact is that a candidate factor can be tested using a modified LL test mod the candidate ( given at least 1 LL test using the mersenne). About the only interesting fact I come up with on the fly, is that a candidate mersenne prime, has to have an even multiple of the product of all previous mersenne primes( except maybe pairs of twin prime exponents), congruent to -2 mod the candidate.

I never find any rule for primes.

I believe that is the only rule true here.

If you detect a rule, wrong way.

[QUOTE=science_man_88;481757]Iterations that hit -2,-1,0,1,2 mod the mersenne, prior to the final iteration are either bad, or not prime. We also know (uselessly) that the residue has the same parity as the floor of the full number divided by the mersenne. Another useless fact is that a candidate factor can be tested using a modified LL test mod the candidate ( given at least 1 LL test using the mersenne). About the only interesting fact I come up with on the fly, is that a candidate mersenne prime, has to have an even multiple of the product of all previous mersenne primes( except maybe pairs of twin prime exponents), congruent to -2 mod the candidate.[/QUOTE]

Wow interesting. Does this last relationship hold for all the known mersenne primes?

[QUOTE=gophne;481886]Wow interesting. Does this last relationship hold for all the known mersenne primes?[/QUOTE]

Has to for primes testable by LL. Once 0 mod a number is hit, -2 mod that number is hit, followed by repeating 2 forever. 2 mod coprimes, is 2 mod their product. Etc.