A (new) old, (faster) slower mersenne-(primality) PRP test

[boldi]

(First of all please excuse my bad English)

Conjecture: Let p be a odd prime number. Then the Mersenne number M = 2^p -1 holds the congruence relation

3^(M-1) ≡ 1 mod M

if, and only if M is prime. (In comparison to little Fermat theorem there is no Mersenne-pseudoprime who can hold the congruence relation.)

This can be used as a Mersenne primality test. To proof, if a Mersenne number is prime, only check if it holds the congruence relation 3^(M-1) ≡ 1 mod M

Example:
p=7: 3^(127-1)-1 mod 127 = 1 --> prime
p=11: 3^(2047-1)-1 mod 2047 = 1013 --> not prime

I have tested it and it is valid for all Mersenne numbers M = 2^p-1 for p=2 to 23209. But what it needs is a strong mathematical proof.

From the congruence relation we can extract a recursive calculation algorithm if a Mersenne number is prime or not. (It is pretty similar to Lucas-Lehmer test, but a little bit simpler and faster)

I will show an example how it works: Let be p=7 a prime number and the Mersenne number is M_7 = 2^7-1 = 127. Now we want to proof, that M_7 is prim or not. So we are calculating recursive the sequence

S_n = S_(n-1) ∙ S_(n-1) mod M with S_0=3

The sequence will be calculated from n=1 to n=p-1, in our case from 1 to 6:

S_1 = 3∙3 mod 127=9
S_2 = 9∙9 mod 127=81
S_3 = 81∙81 mod 127=84
S_4 = 84∙84 mod 127=71
S_5 = 71∙71 mod 127=88
S_6 = 88∙88 mod 127=124

As result we have got 124. Now we are test, if 124 + S_0 = M_7. If yes, then M ist prime, if no, M is no prime. In our case we have 124 + 3 = 127 = M_7, so M_7 is prime.

Here the code in C:

bool MersennnePrimeTest(p)
{
Bigint n, M, S;

M = 2^p – 1;
S = 3;

for(n = 1, n <= p – 1, n++) S = S*S % M;

if(S + 3 == M) return(true); //M = prime;
else return(false); //M = not prime
}

This test is simpler and faster than the Lucas-Lehmer test, because we have no subtraction. (In Lucas-Lehmer-test we have to calculate the sequence S_n=S_(n-1)∙S_(n-1) - 2 mod M)

greetings
boldi

[ewmayer]

If you think is either new (it isn't), or faster than LL (also false), or a rigorous test of primality (again, no), you are in dire need of a course (or reading-yourself) in elementary number theory.

[Qubit]

Originally Posted by boldi

Conjecture: Let p be a prime number. Then the Mersenne number M = 2^p -1 holds the congruence relation

3^(M-1) ≡ 1 mod M

if, and only if M is prime.

I have tested it and it is valid for all Mersenne numbers M = 2^p-1 for p=2 to 23209. But what it needs is a strong mathematical proof.

Perhaps I misunderstood, but for M = 3 we get 3^2 = 9, which is 0 mod 3.

[tapion64]

Originally Posted by Qubit

Perhaps I misunderstood, but for M = 3 we get 3^2 = 9, which is 0 mod 3.

That's because 3 is the only Mersenne prime index with an even multiplicative order mod 2, which in general just makes all these special rules not apply to it. I'll have to look into this.

[Qubit]

edit: Whoops, miscalculation.

[boldi]

Originally Posted by Qubit

Perhaps I misunderstood, but for M = 3 we get 3^2 = 9, which is 0 mod 3.

Thank You for this statement. I have to specify the conjecture:

Conjecture: Let p be a odd prime number. Then the Mersenne number M = 2^p -1 holds the congruence relation

3^(M-1) ≡ 1 mod M

if, and only if M is prime. (In comparison to little Fermat theorem there is no Mersenne-pseudoprime who can hold the congruence relation.)

Greetings
boldi

[boldi]

Originally Posted by ewmayer

If you think is either new (it isn't)

You have forgotten to name the paper, where this topic is discused.

or faster than LL (also false),

If conjecture holds, it is faster, because there is no subtraction. Because there is no subtraction, further optimazions are possible. Programming my code and measure the time!

or a rigorous test of primality (again, no), you are in dire need of a course (or reading-yourself) in elementary number theory.

If conjecture holds it is an rigorous test. Perhaps You need a course in quoting papers, all I can read from You are unprooven allegations.

greetings
boldi

[ewmayer]

Originally Posted by boldi

You have forgotten to name the paper, where this topic is discused.

I have not - any elementary NT text discusses these kinds of tests, which date back to Fermat himself.

If conjecture holds, it is faster, because there is no subtraction. Because there is no subtraction, further optimazions are possible. Programming my code and measure the time!

The -2 is an utterly trivially time component of an LL test. I *have* programmed both kinds of tests (the test you describe differs from what *is* a rigorous primality test for Fermat numbers only by having one extra modmul), at a very high level of code sophistication, and regularly compare timings. You go program your own code and get back to us when you have results and code others can inspect.

If conjecture holds it is an rigorous test. Perhaps You need a course in quoting papers, all I can read from You are unprooven allegations.

It is you making unproven - in fact long-since-disproven - "allegations".

And your blustery "how dare you question my brilliant insight?" reply just raised your crank score even higher. I suggest you learn at least a little bit of the relevant math and algorithmics before spouting off further.

(But you probably won't take the latter advice, which is OK, as that will serve for amusement.)

[science_man_88]

Originally Posted by boldi

(First of all please excuse my bad English)

Conjecture: Let p be a odd prime number. Then the Mersenne number M = 2^p -1 holds the congruence relation

3^(M-1) ≡ 1 mod M

Okay this follows from Fermat's little theorem.

The sequence will be calculated from n=1 to n=p-1, in our case from 1 to 6:

S_1 = 3∙3 mod 127=9
S_2 = 9∙9 mod 127=81
S_3 = 81∙81 mod 127=84
S_4 = 84∙84 mod 127=71
S_5 = 71∙71 mod 127=88
S_6 = 88∙88 mod 127=124

As result we have got 124. Now we are test, if 124 + S_0 = M_7. If yes, then M ist prime, if no, M is no prime. In our case we have 124 + 3 = 127 = M_7, so M_7 is prime.

so we are testing here ? if = -3 mod M then we can say = -1 mod M, and is 1 mod M, and = 3 mod M no ? can you explain this more. (I really can't say I'm correct as I'm trying to use Fermat's little theorem as well recently, yet didn't read the part talking about Lehmer's theorem in relation to the LL test., and of course as mentioned it's almost positive to have come up before.)

[Batalov]

Must be the springtime! Not just one, but two eloquent cranks, at once!

[R.D. Silverman]

Originally Posted by boldi

You have forgotten to name the paper, where this topic is discused.

It has been discussed EXTENSIVELY in
so many places that it would be impossible to keep track.
It has been discussed numerous times in this forum.

If conjecture holds, it is faster, because there is no subtraction.

HORSESHIT. Analyze the complexity.

Because there is no subtraction, further optimazions are possible. Programming my code and measure the time!

A pointless exercise.

If conjecture holds it is an rigorous test.

And there is no proof.

Perhaps You need a course in quoting papers, all I can read from You are unprooven allegations.

You need a course in how to respect your elders and those possessing
superior education and knowledge. How many papers have YOU published
in this subject area?? Ernst is a acknowledged expert in this subject.
Go to any number theory conference and ask.

Now what have YOU done to earn respect?

You come across as an arrogant and ignorant ass.