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

[CRGreathouse]

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

[Trilo]

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 M_n and n mod M_n+1

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


S_x (mod M_n)------M_n/S_x
---------------------------------------

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 S_x (mod M_n+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 S_x (mod M_n+ 1) rather than S_x (mod M_n).


S_x (mod M_n+1)---(M_n+1)/S_x
------------------------------------------

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

d₀ = M_n/S_x,
d₁ = (M_n+1)/S_x
m₀ = S_x (mod M_n)
m₁= S_x (mod M_n+1)

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

d₀= d₁ + 1 if m₀ - d₀ < 0 and
d₀= d₁ if m₀ - d₀ >= 0

one may also notice

m₁= m₀+ d₀ if d₀= d₁ and
m₁= (m₀+ d₀ - 1) - M_n if d₀= d₁ + 1

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

m₁= m₀+ d₀ if m₀ - d₀ >= 0 and
m₁= (m₀+ d₀ - 1) - M_n if m₀ - d₀ < 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¹⁰-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.

[retina]

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.

[Trilo]

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.

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

.

[science_man_88]

Originally Posted by Trilo

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

d₀ = M_n/S_x,
d₁ = (M_n+1)/S_x
m₀ = S_x (mod M_n)
m₁= S_x (mod M_n+1)

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

d₀= d₁ + 1 if m₀ - d₀ < 0 and
d₀= d₁ if m₀ - d₀ >= 0

one may also notice

m₁= m₀+ d₀ if d₀= d₁ and
m₁= (m₀+ d₀ - 1) - M_n if d₀= d₁ + 1

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

m₁= m₀+ d₀ if m₀ - d₀ >= 0 and
m₁= (m₀+ d₀ - 1) - M_n if m₀ - d₀ < 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¹⁰-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 d₀ = d₁+1 is true then the part using m₀+d₀-1 gets simplified to m₀+d₁ 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.

[Trilo]

Originally Posted by science_man_88

I like patterns but one thing I'd point out is that if d₀ = d₁+1 is true then the part using m₀+d₀-1 gets simplified to m₀+d₁ 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 m₀ and d₀ is trivial to do on a computer while d₁ and m₁ is not trivial to compute and it gets rid of the whole purpose of writing m₁ in terms of m₀ and d₀.

[science_man_88]

Originally Posted by Trilo

That and calculating m₀ and d₀ is trivial to do on a computer while d₁ and m₁ is not trivial to compute and it gets rid of the whole purpose of writing m₁ in terms of m₀ and d₀.

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

[LaurV]

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

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

[flagrantflowers]

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…

[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".

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.

[ewmayer]

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