20141103, 01:32  #1 
"W. Byerly"
Aug 2013
81*2^31743531
7×19 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 s_{n} where s_{0}= 4 and s_{n}= s_{n1}^{2}2 and if s_{n2} 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_{n2} Last fiddled with by Trilo on 20141103 at 01:38 
20141103, 02:13  #2 
Aug 2006
2^{2}×3×499 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.

20141103, 02:44  #3  
"W. Byerly"
Aug 2013
81*2^31743531
7×19 Posts 
Quote:
Last fiddled with by Trilo on 20141103 at 02:51 

20141103, 04:33  #4 
Aug 2006
2^{2}×3×499 Posts 
Probably not, since the moduli are coprime and is much larger than they are.

20141103, 06:35  #5  
∂^{2}ω=0
Sep 2002
República de California
2^{2}·2,939 Posts 
Quote:
Quote:


20141103, 13:25  #6  
"Forget I exist"
Jul 2009
Dartmouth NS
10000100000010_{2} Posts 
Quote:
Quote:


20141104, 02:39  #7  
"W. Byerly"
Aug 2013
81*2^31743531
7·19 Posts 
Quote:


20141104, 03:12  #8  
Undefined
"The unspeakable one"
Jun 2006
My evil lair
1101001110110_{2} Posts 
Quote:


20141104, 12:04  #9 
Romulan Interpreter
"name field"
Jun 2011
Thailand
2^{4}×643 Posts 
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.
Last fiddled with by LaurV on 20141104 at 12:05 
20141104, 15:47  #10 
"Forget I exist"
Jul 2009
Dartmouth NS
2·5^{2}·13^{2} Posts 
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)^22 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 20141104 at 15:48 
20141104, 21:36  #11 
∂^{2}ω=0
Sep 2002
República de California
2^{2}·2,939 Posts 
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)).

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
LucasLehmer test  Mathsgirl  Information & Answers  23  20141210 16:25 
proof the lucas lehmer test  kurtulmehtap  Math  13  20091002 12:12 
LucasLehmer Test  storm5510  Math  22  20090924 22:32 
LucasLehmer Test proof  alpertron  mersennewiki  16  20060318 07:23 
LucasLehmer primality test  CMOSMIKE  Math  5  20020906 18:46 