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

[Trilo]

I have been looking into how the Lucas Lehmer test works. The test states to define a sequence s_n where s₀= 4 and s_n= s_n-1²-2 and if s_n-2 evently divides M_n then M_n is prime.

What I am wondering is if it is possible to modify the test to instead prove M_n prime iff M_n+1 evenly divides s_n-2

[CRGreathouse]

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.

[Trilo]

Originally Posted by CRGreathouse

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.

Thats what I thought. If I knew what s_n-2 (mod M_n+1) was, is there any way to easily find s_n-2 (mod M_n) computation wise?

[CRGreathouse]

Probably not, since the moduli are coprime and is much larger than they are.

[ewmayer]

Originally Posted by Trilo

I have been looking into how the Lucas Lehmer test works. The test states to define a sequence s_n where s₀= 4 and s_n= s_n-1²-2 and if s_n-2 evently divides M_n then M_n is prime.

You apparently haven't been looking very hard, because you got the what-divides-what backwards.

What I am wondering is if it is possible to modify the test to instead prove M_n prime iff M_n+1 evenly divides s_n-2

You might as well ask, "I know that M_n+1 is a power of 2 -- what does that tell me about primality (or not) of M_n?" The answer is: nothing whatsoever.

[science_man_88]

Originally Posted by CRGreathouse

Probably not, since the moduli are coprime and is much larger than they are.

Originally Posted by http://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_primality_test#Time_complexity

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.

[Trilo]

Originally Posted by science_man_88

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.

Performing n (mod 2^m) is equivalent to n & (2^m- 1) where & is the AND bitwise operator. Also, performing n/2^m can be simplified to n >> m where >> is the binary right shift operator. 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^m) is trivial on a computer, and this is why I was asking whether it was possible to compute n (mod 2^p+1) given n (mod 2^p). However, it looks like the Wikipedia page (and GIMPS) has already taken advantage of this specific pattern when applying the Lucas-Lehmer test.

[retina]

Originally Posted by Trilo

Performing n (mod 2^m) is equivalent to n & (2^m- 1) where & is the AND bitwise operator. Also, performing n/2^m can be simplified to n >> m where >> is the binary right shift operator. 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^m) is trivial on a computer, and this is why I was asking whether it was possible to compute n (mod 2^p+1) given n (mod 2^p). However, it looks like the Wikipedia page (and GIMPS) has already taken advantage of this specific pattern when applying the Lucas-Lehmer test.

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.

[LaurV]

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.

[science_man_88]

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



which can use

to figure out the next results:



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.

[ewmayer]

Originally Posted by retina

Doing mod Mn is also trivial and comes for free with the way the FFTs are currently done.

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