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