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]n1[/SUB][SUP]2[/SUP][/I]2 and if [I]s[SUB]n2[/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]n2[/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]n2[/SUB][/I] (mod M[SUB]n[/SUB]+1) was, is there any way to easily find [I]s[SUB]n2[/SUB][/I] (mod M[SUB]n[/SUB]) computation wise? 
Probably not, since the moduli are coprime and [TEX]s_{n1}[/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]n1[/SUB][SUP]2[/SUP][/I]2 and if [I]s[SUB]n2[/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 whatdivideswhat 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]n2[/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_{n1}[/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^n1}[/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 LucasLehmer 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 LucasLehmer 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^x1) 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_{n2} = (4 \times x+2) \times M_{n}[/TEX] which can use [TEX]{M_n}^2 = M_{n1}\times M_{n+1} +2^{n1}[/TEX] to figure out the next results: [TEX]S_{n1} ={(4 \times x +2)}^2 * {M_n}^2 2 = (16 \times x^2 +16 \times x +4 ) \times (M_{n1}\times M_{n+1} +2^{n1}) 2[/TEX] this can be reduced more and then use (a*b+c)^22 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 implicitmod is nearly free (say < 10% of runtime, and costing O(n) vs the FFT's O(n lg n)). 
All times are UTC. The time now is 04:35. 
Powered by vBulletin® Version 3.8.11
Copyright ©2000  2021, Jelsoft Enterprises Ltd.