mersenneforum.org New theorem to split LL tests(Published)
 Register FAQ Search Today's Posts Mark Forums Read

 2007-05-21, 15:17 #1 nuggetprime     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*(x-1))Mod Mx + 2^(2*(x-2)) Mod Mx +... 2^0 Mod Mx. I proved it up to M17 at the moment. Sample: residue for M11 is 2045. M11-2045 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
 2007-05-21, 15:55 #2 akruppa     "Nancy" Aug 2002 Alexandria 1001101000112 Posts > 2^(2*(x-1)) 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
2007-05-21, 16:28   #3
akruppa

"Nancy"
Aug 2002
Alexandria

2,467 Posts

Quote:
 Originally Posted by akruppa > 2^(2*(x-1)) Takes about 2x modular squarings, or about twice as long as an LL test.
No wait... I've misread that as 2^(2^(2*x-1)). Sorry.

So you're computing $\sum_{i=0}^{x-1} 4^i = (4^x-1)/3$.

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 2007-05-21 at 16:40

 2007-05-21, 23:07 #4 Mini-Geek 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...
 2007-05-22, 07:09 #5 Eivind   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**5-1 = 31 and 31 is prime, so far so god. Now formula: 2^2*(5-1) = 256 2^2*(5-2) = 64 2^2*(5-3) = 16 2^2*(5-4) = 4 2^2*(5-5) = 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
 2007-05-22, 07:27 #6 Eivind   Feb 2006 3×17 Posts Update: This Python code should print the term after each Mod operation: Code: Mx = 5 term = 2**(2*(Mx-1)) for i in range(2,Mx+1): print term term = term % (Mx + 2**(2*(Mx-i))) print term Result: Code: >>> ================================ RESTART ================================ >>> 256 49 7 7 1 >>> -Eivind
2007-05-22, 14:28   #7
Mini-Geek
Account Deleted

"Tim Sorbera"
Aug 2006
San Antonio, TX USA

102678 Posts

Quote:
 Originally Posted by Eivind I have some problems with the formula, lets try with the numer 5. We know 5 is a Mersenne Prime, since 2**5-1 = 31 and 31 is prime, so far so god. Now formula: 2^2*(5-1) = 256 2^2*(5-2) = 64 2^2*(5-3) = 16 2^2*(5-4) = 4 2^2*(5-5) = 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
Um...where'd you get the idea of that second step? (the one with the Mod) Not from nuggetprime's post, unless I'm misunderstanding something big.

As I understand it, here's what you do:
2^2*(5-1) = 8 Mod 31
2^2*(5-2) = 2 Mod 31
2^2*(5-3) = 16 Mod 31
2^2*(5-4) = 4 Mod 31
2^2*(5-5) = 1 Mod 31

8+2+16+4+1 = 0 Mod 31

Since 8+2+16+4+1 = 0 Mod 31, 31 is prime

 2007-05-23, 06:59 #8 Eivind   Feb 2006 3×17 Posts Hi OK, I get it. I thought: To test Mx you do: 2^(2*(x-1))Mod Mx + 2^(2*(x-2)) Mod Mx +... 2^0 Mod Mx. Was to be interpretatet as: (2^(2*(x-1))Mod (Mx + 2^(2*(x-2)))) Mod (Mx +... 2^0) Mod Mx. So, let's test it with x = 9 Mx = 2**9-1 = 511 2^(2*(9-1)) = 128 Mod 511 2^(2*(9-2)) = 32 Mod 511 2^(2*(9-3)) = 8 Mod 511 2^(2*(9-4)) = 2 Mod 511 2^(2*(9-5)) = 256 Mod 511 2^(2*(9-6)) = 64 Mod 511 2^(2*(9-7)) = 16 Mod 511 2^(2*(9-8)) = 4 Mod 511 2^(2*(9-9)) = 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 2007-05-23 at 07:59
2007-05-23, 11:24   #9
Mini-Geek
Account Deleted

"Tim Sorbera"
Aug 2006
San Antonio, TX USA

11×389 Posts

Quote:
 Originally Posted by Eivind Hi OK, I get it. I thought: To test Mx you do: 2^(2*(x-1))Mod Mx + 2^(2*(x-2)) Mod Mx +... 2^0 Mod Mx. Was to be interpretatet as: (2^(2*(x-1))Mod (Mx + 2^(2*(x-2)))) Mod (Mx +... 2^0) Mod Mx. So, let's test it with x = 9 Mx = 2**9-1 = 511 2^(2*(9-1)) = 128 Mod 511 2^(2*(9-2)) = 32 Mod 511 2^(2*(9-3)) = 8 Mod 511 2^(2*(9-4)) = 2 Mod 511 2^(2*(9-5)) = 256 Mod 511 2^(2*(9-6)) = 64 Mod 511 2^(2*(9-7)) = 16 Mod 511 2^(2*(9-8)) = 4 Mod 511 2^(2*(9-9)) = 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 ..
Unless we're not doing it the way nuggetprime was thinking, this is just a very roundabout way of saying the binary 111111111. (for reference, this is because our way of representation is the digit*the base^(the amount of numbers to the right of it), e.g., 1*2^8 + 1*2^7 + 1*2^6 + 1*2^5 + 1*2^4 + 1*2^3 + 1*2^2 + 1*2^1 + 1*2^0 = 128 + 32 + 8 + 2 + 256 + 64 + 16 + 4 + 1 = 511(base 10) = 111111111(base 2)) nuggetprime, are we doing it right? For clarity's sake, perhaps you could attach an xls demonstrating your theorem (zip it then attach).

 2007-05-23, 13:47 #10 Eivind   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 2007-05-23 at 13:53

 Similar Threads Thread Thread Starter Forum Replies Last Post philmoore Five or Bust - The Dual Sierpinski Problem 4 2009-04-10 23:59 joblack Information & Answers 1 2009-01-06 08:45 JHansen Homework Help 4 2007-11-20 15:02 axn Forum Feedback 9 2006-04-27 16:39 rogue Sierpinski/Riesel Base 5 8 2006-03-04 13:59

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

Wed Dec 7 07:51:56 UTC 2022 up 111 days, 5:20, 0 users, load averages: 0.60, 0.80, 0.80