 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 2,467 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 .

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 2×3×23×31 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 638 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

102668 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

10000101101102 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  Thread Tools Show Printable Version Email this Page 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 15:16.

Sat Aug 13 15:16:15 UTC 2022 up 37 days, 10:03, 2 users, load averages: 0.96, 0.96, 1.00