 mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Miscellaneous Math (https://www.mersenneforum.org/forumdisplay.php?f=56)
-   -   Modifying the Lucas Lehmer Primality Test into a fast test of nothing (https://www.mersenneforum.org/showthread.php?t=19803)

 Trilo 2014-11-03 01:32

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]

 CRGreathouse 2014-11-03 02:13

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 2014-11-03 02:44

[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?

 CRGreathouse 2014-11-03 04:33

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

 ewmayer 2014-11-03 06:35

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

 science_man_88 2014-11-03 13:25

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

 Trilo 2014-11-04 02:39

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

 retina 2014-11-04 03:12

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

 LaurV 2014-11-04 12:04

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 2014-11-04 15:47

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.

 ewmayer 2014-11-04 21:36

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

All times are UTC. The time now is 04:35.