New theorem to split LL tests(Published)

[nuggetprime]

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

[akruppa]

> 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]

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

[TimSorbet]

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...

[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

[Eivind]

Update:

This Python code should print the term after each Mod operation:

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:

>>> ================================ RESTART ================================
>>> 
256
49
7
7
1
>>>

-Eivind

[TimSorbet]

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

[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 ..

[TimSorbet]

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).

[Eivind]

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