mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2014-11-03, 01:32   #1
Trilo
 
Trilo's Avatar
 
"W. Byerly"
Aug 2013
1423*2^2179023-1

2·47 Posts
Default 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
Trilo is offline   Reply With Quote
Old 2014-11-03, 02:13   #2
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

22×5×293 Posts
Default

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.
CRGreathouse is offline   Reply With Quote
Old 2014-11-03, 02:44   #3
Trilo
 
Trilo's Avatar
 
"W. Byerly"
Aug 2013
1423*2^2179023-1

10111102 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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
Trilo is offline   Reply With Quote
Old 2014-11-03, 04:33   #4
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

22×5×293 Posts
Default

Probably not, since the moduli are coprime and s_{n-1} is much larger than they are.
CRGreathouse is offline   Reply With Quote
Old 2014-11-03, 06:35   #5
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
Rep├║blica de California

22·3·72·19 Posts
Default

Quote:
Originally Posted by Trilo View Post
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.
ewmayer is offline   Reply With Quote
Old 2014-11-03, 13:25   #6
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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.
science_man_88 is offline   Reply With Quote
Old 2014-11-04, 02:39   #7
Trilo
 
Trilo's Avatar
 
"W. Byerly"
Aug 2013
1423*2^2179023-1

2×47 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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.
Trilo is offline   Reply With Quote
Old 2014-11-04, 03:12   #8
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

13·419 Posts
Default

Quote:
Originally Posted by Trilo View Post
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.
retina is offline   Reply With Quote
Old 2014-11-04, 12:04   #9
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

205448 Posts
Default

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
LaurV is offline   Reply With Quote
Old 2014-11-04, 15:47   #10
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

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
science_man_88 is offline   Reply With Quote
Old 2014-11-04, 21:36   #11
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
Rep├║blica de California

256448 Posts
Default

Quote:
Originally Posted by retina View Post
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)).
ewmayer is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 19:44.

Thu Jun 4 19:44:37 UTC 2020 up 71 days, 17:17, 1 user, load averages: 2.27, 1.78, 1.60

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.