mersenneforum.org Modifying the Lucas Lehmer Primality Test into a fast test of nothing
 Register FAQ Search Today's Posts Mark Forums Read

 2014-11-03, 01:32 #1 Trilo     "W. Byerly" Aug 2013 81*2^3174353-1 7E16 Posts 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 sn where s0= 4 and sn= sn-12-2 and if sn-2 evently divides Mn then Mn is prime. What I am wondering is if it is possible to modify the test to instead prove Mn prime iff Mn+1 evenly divides sn-2 Last fiddled with by Trilo on 2014-11-03 at 01:38
 2014-11-03, 02:13 #2 CRGreathouse     Aug 2006 597910 Posts 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.
2014-11-03, 02:44   #3
Trilo

"W. Byerly"
Aug 2013
81*2^3174353-1

2·32·7 Posts

Quote:
 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 sn-2 (mod Mn+1) was, is there any way to easily find sn-2 (mod Mn) computation wise?

Last fiddled with by Trilo on 2014-11-03 at 02:51

 2014-11-03, 04:33 #4 CRGreathouse     Aug 2006 175B16 Posts Probably not, since the moduli are coprime and $s_{n-1}$ is much larger than they are.
2014-11-03, 06:35   #5
ewmayer
2ω=0

Sep 2002
República de California

32×1,303 Posts

Quote:
 Originally Posted by Trilo I have been looking into how the Lucas Lehmer test works. The test states to define a sequence sn where s0= 4 and sn= sn-12-2 and if sn-2 evently divides Mn then Mn is prime.
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 Mn prime iff Mn+1 evenly divides sn-2
You might as well ask, "I know that Mn+1 is a power of 2 -- what does that tell me about primality (or not) of Mn?" The answer is: nothing whatsoever.

2014-11-03, 13:25   #6
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 Originally Posted by CRGreathouse Probably not, since the moduli are coprime and $s_{n-1}$ is much larger than they are.
Quote:
 Originally Posted by http://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_primality_test#Time_complexity $k\eq (k \pmod {2^n}) + \lfloor{k/2^n}\rfloor \pmod{2^n-1}$
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.

2014-11-04, 02:39   #7
Trilo

"W. Byerly"
Aug 2013
81*2^3174353-1

2·32·7 Posts

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

2014-11-04, 03:12   #8
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

23·3·269 Posts

Quote:
 Originally Posted by Trilo Performing n (mod 2m) is equivalent to n & (2m- 1) where & is the AND bitwise operator. Also, performing n/2m 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 2m) is trivial on a computer, and this is why I was asking whether it was possible to compute n (mod 2p+1) given n (mod 2p). 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.

 2014-11-04, 12:04 #9 LaurV Romulan Interpreter     "name field" Jun 2011 Thailand 2·17·293 Posts 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. Last fiddled with by LaurV on 2014-11-04 at 12:05
 2014-11-04, 15:47 #10 science_man_88     "Forget I exist" Jul 2009 Dumbassville 26·131 Posts the only alteration I can think of is using algebra and starting from the end result of a mersenne prime: $S_{n-2} = (4 \times x+2) \times M_{n}$ which can use ${M_n}^2 = M_{n-1}\times M_{n+1} +2^{n-1}$ to figure out the next results: $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$ 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. Last fiddled with by science_man_88 on 2014-11-04 at 15:48
2014-11-04, 21:36   #11
ewmayer
2ω=0

Sep 2002
República de California

32×1,303 Posts

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

 Similar Threads Thread Thread Starter Forum Replies Last Post Mathsgirl Information & Answers 23 2014-12-10 16:25 kurtulmehtap Math 13 2009-10-02 12:12 storm5510 Math 22 2009-09-24 22:32 alpertron mersennewiki 16 2006-03-18 07:23 CMOSMIKE Math 5 2002-09-06 18:46

All times are UTC. The time now is 10:07.

Tue May 24 10:07:32 UTC 2022 up 40 days, 8:08, 0 users, load averages: 2.38, 1.85, 1.78