20070521, 15:17  #1 
Mar 2007
Austria
2×151 Posts 
New theorem to split LL tests(Published)
Hi,
here is a new theorem to prove the primality of Mersenne numbers: To test Mx you do: 2^(2*(x1))Mod Mx + 2^(2*(x2)) Mod Mx +... 2^0 Mod Mx. I proved it up to M17 at the moment. Sample: residue for M11 is 2045. M112045 is 2 and 2*11+1 divides M11 so it is maybe also a method to find a factor for Mx. But the main help of this method probably is to make it possible to split the test of Mx on many computers. Maybe it's also faster than the normal LL test. I haven't a proof for this theorem yet so maybe a number theorist could analyze, tell me if it's already known, tell me corrections and prove/deprove it. Thanks, nuggetprime 
20070521, 15:55  #2 
"Nancy"
Aug 2002
Alexandria
100110100011_{2} Posts 
> 2^(2*(x1))
Takes about 2x modular squarings, or about twice as long as an LL test. > I haven't a proof for this theorem So it's not a theorem. Alex 
20070521, 16:28  #3  
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
Quote:
So you're computing . What is this value meant to signify? Edit: Working mod Mx, 4^x ≡ 1, so if 3 does not divide Mx, your residue will be 0, and 3 divides Mx iff x is even. What is the purpose of this test? Alex Last fiddled with by akruppa on 20070521 at 16:40 

20070521, 23:07  #4 
Account Deleted
"Tim Sorbera"
Aug 2006
San Antonio, TX USA
11×389 Posts 
If you do those calculations starting at 2^0 and working up, you'll notice that each one is the last times four, until the result is over Mx (which, in my two tests of this, is around half way through), at which point the number goes down to two, and it again begins the times four repetition.
Just an observation... 
20070522, 07:09  #5 
Feb 2006
3×17 Posts 
I have some problems with the formula, lets try with the numer 5.
We know 5 is a Mersenne Prime, since 2**51 = 31 and 31 is prime, so far so god. Now formula: 2^2*(51) = 256 2^2*(52) = 64 2^2*(53) = 16 2^2*(54) = 4 2^2*(55) = 1 256 Mod (5+64) = 49 49 Mod (5+16) = 7 7 Mod (5+4) = 7 7 Mod (5+1) = 1 1 Mod (5+0) = 1 So I just proved that 5 is not a Mersenne prime, or what? Eivind 
20070522, 07:27  #6 
Feb 2006
3×17 Posts 
Update:
This Python code should print the term after each Mod operation: Code:
Mx = 5 term = 2**(2*(Mx1)) for i in range(2,Mx+1): print term term = term % (Mx + 2**(2*(Mxi))) print term Code:
>>> ================================ RESTART ================================ >>> 256 49 7 7 1 >>> 
20070522, 14:28  #7  
Account Deleted
"Tim Sorbera"
Aug 2006
San Antonio, TX USA
10267_{8} Posts 
Quote:
As I understand it, here's what you do: 2^2*(51) = 8 Mod 31 2^2*(52) = 2 Mod 31 2^2*(53) = 16 Mod 31 2^2*(54) = 4 Mod 31 2^2*(55) = 1 Mod 31 8+2+16+4+1 = 0 Mod 31 Since 8+2+16+4+1 = 0 Mod 31, 31 is prime 

20070523, 06:59  #8 
Feb 2006
3×17 Posts 
Hi
OK, I get it. I thought: To test Mx you do: 2^(2*(x1))Mod Mx + 2^(2*(x2)) Mod Mx +... 2^0 Mod Mx. Was to be interpretatet as: (2^(2*(x1))Mod (Mx + 2^(2*(x2)))) Mod (Mx +... 2^0) Mod Mx. So, let's test it with x = 9 Mx = 2**91 = 511 2^(2*(91)) = 128 Mod 511 2^(2*(92)) = 32 Mod 511 2^(2*(93)) = 8 Mod 511 2^(2*(94)) = 2 Mod 511 2^(2*(95)) = 256 Mod 511 2^(2*(96)) = 64 Mod 511 2^(2*(97)) = 16 Mod 511 2^(2*(98)) = 4 Mod 511 2^(2*(99)) = 1 Mod 511 128+32+8+2+256+64+16+4+1 = 511 511 = 0 Mod 511. Then 9 is a prime, is that it? Eivind Update: A quice search also show problems with x=15,25,27 .. Last fiddled with by Eivind on 20070523 at 07:59 
20070523, 11:24  #9  
Account Deleted
"Tim Sorbera"
Aug 2006
San Antonio, TX USA
11×389 Posts 
Quote:


20070523, 13:47  #10 
Feb 2006
3·17 Posts 
The way I see it, this algoritm is a verry long way to tell if a number is even or odd.
Please nuggetprime, provide further clarity. Most of these testing algoritms are easy peasy programable so testing with a lot of candidats are no problem. Eg. the LL test can be made in 5 simpel lines and it will test x = 1..1000 in about 15 sec. Eivind Last fiddled with by Eivind on 20070523 at 13:53 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Paper on Sierpinski problems just published  philmoore  Five or Bust  The Dual Sierpinski Problem  4  20090410 23:59 
split a prime95 queue & client installation  joblack  Information & Answers  1  20090106 08:45 
Formula split up  JHansen  Homework Help  4  20071120 15:02 
Split "Other Projects" subforum?  axn  Forum Feedback  9  20060427 16:39 
Delayed status report (split from main reservation thread)  rogue  Sierpinski/Riesel Base 5  8  20060304 13:59 