mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2007-05-21, 15:17   #1
nuggetprime
 
nuggetprime's Avatar
 
Mar 2007
Austria

2×151 Posts
Default 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
nuggetprime is offline   Reply With Quote
Old 2007-05-21, 15:55   #2
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

1001101000112 Posts
Default

> 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
akruppa is offline   Reply With Quote
Old 2007-05-21, 16:28   #3
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

Quote:
Originally Posted by akruppa View Post
> 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
akruppa is offline   Reply With Quote
Old 2007-05-21, 23:07   #4
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

11×389 Posts
Default

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...
Mini-Geek is offline   Reply With Quote
Old 2007-05-22, 07:09   #5
Eivind
 
Feb 2006

3×17 Posts
Default

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
Eivind is offline   Reply With Quote
Old 2007-05-22, 07:27   #6
Eivind
 
Feb 2006

3×17 Posts
Default

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
Eivind is offline   Reply With Quote
Old 2007-05-22, 14:28   #7
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

102678 Posts
Default

Quote:
Originally Posted by Eivind View Post
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
Mini-Geek is offline   Reply With Quote
Old 2007-05-23, 06:59   #8
Eivind
 
Feb 2006

3×17 Posts
Default

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
Eivind is offline   Reply With Quote
Old 2007-05-23, 11:24   #9
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

11×389 Posts
Default

Quote:
Originally Posted by Eivind View Post
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).
Mini-Geek is offline   Reply With Quote
Old 2007-05-23, 13:47   #10
Eivind
 
Feb 2006

3·17 Posts
Default

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
Eivind is offline   Reply With Quote
Reply

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 2009-04-10 23:59
split a prime95 queue & client installation joblack Information & Answers 1 2009-01-06 08:45
Formula split up JHansen Homework Help 4 2007-11-20 15:02
Split "Other Projects" sub-forum? axn Forum Feedback 9 2006-04-27 16:39
Delayed status report (split from main reservation thread) 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔