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

[R.D. Silverman]

Originally Posted by ewmayer

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


The -2 is an utterly trivially time component of an LL test.

Note also that for each of p-1 steps in LL it is "square then subtract a
single precision constant".

Computing 3^(N-1) requires a squaring for each bit in the exponent (as does LL), BUT ALSO additional multiplications depending on how one does the
exponentiation. (simple left to right requires one additional mult for each
lit bit; the binary/trinary method or sliding windows require somewhat less,
but still require additional multiplications)

It wil be SLOWER.

The OP is an idiot.

[science_man_88]

Originally Posted by science_man_88

Okay this follows from Fermat's little theorem.



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

Doh! I realize my mistake now.

[ewmayer]

Originally Posted by R.D. Silverman

Computing 3^(N-1) requires a squaring for each bit in the exponent (as does LL), BUT ALSO additional multiplications depending on how one does the
exponentiation. (simple left to right requires one additional mult for each
lit bit;

Thanks for the clarification - I had in mind the special case of Fermat numbers, where lit-bits-beyond-the-leftmost-one in N-1 (and (N-1)/2) are somewhat scarce. :)

[Batalov]

Berrizbeitia-Iskra (2010) demonstrates another case of a Pépin-like proven strategy (see theorem 3.4, parts 1 and 2).
@OP: They didn't just say: "we've tested it on all known G-M and E-M primes and there were no contra cases, so it must be true". They proved a theorem.

[kladner]

Nice show, gents!

[axn]

Originally Posted by R.D. Silverman

Computing 3^(N-1) requires a squaring for each bit in the exponent (as does LL), BUT ALSO additional multiplications depending on how one does the
exponentiation. (simple left to right requires one additional mult for each
lit bit; the binary/trinary method or sliding windows require somewhat less,
but still require additional multiplications)

It wil be SLOWER.

I think the OP realizes this -- hence his actual calculation uses 3^(N+1)/2 == -3 (mod N). which requires only repeated squarings

Originally Posted by boldi

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)

[boldi]

Originally Posted by Batalov

Berrizbeitia-Iskra (2010) demonstrates another case of a Pépin-like proven strategy (see theorem 3.4, parts 1 and 2).
@OP: They didn't just say: "we've tested it on all known G-M and E-M primes and there were no contra cases, so it must be true".

They proved a theorem.

Thank You for the link.

First of all: In my postings I have never said my conjecture must be true.

On the contrary: In my first post I have pointed out, the conjecture needs a strong mathematical proof.

And all I ask is: Is there a proof for the conjecture, that only Mersenne primes can pass the congruence

mod

You tell me, they have proved a theorem -- thanks (I mean this seriosley), but where is this proof? In the paper You have linked I can see no answer for my question.

Greetings
boldi

[tapion64]

Originally Posted by boldi

Thank You for the link.

First of all: In my postings I have never said my conjecture must be true.

On the contrary: In my first post I have pointed out, the conjecture needs a strong mathematical proof.

And all I ask is: Is there a proof for the conjecture, that only Mersenne primes can pass the congruence

mod

You tell me, they have proved a theorem -- thanks (I mean this seriosley), but where is this proof? In the paper You have linked I can see no answer for my question.

Greetings
boldi

I swear I've seen that conjecture somewhere on the multitude of sites I've been looking at over the past week, but I can't seem to find it. I believe there's a link in one of the GIMPS section threads that mentions it. A similar test is Pepin's:

3^[(Fn-1)/2] = (-1) mod Fn

For Fermat numbers. It seems reasonable that someone conjectured an analogue for Mersenne primes, I just can't find it at the moment. Actually, square both sides of the above and you get 3^(Fn-1) = 1 mod Fn, so maybe you had it mixed up that the conjecture was for Mersenne primes. Clearly if it holds for Fermat numbers, then it doesn't just hold for Mersenne primes.

[R.D. Silverman]

Originally Posted by ewmayer

Thanks for the clarification - I had in mind the special case of Fermat numbers, where lit-bits-beyond-the-leftmost-one in N-1 (and (N-1)/2) are somewhat scarce. :)

It is also unclear whether one could use Crandall's DWFT owing to the
extra multiplications by 3 that need to take place in computing 3^(N-1).

It is also unclear whether one gets the remainder "for free" as we do with
LL/DWFT.

[R.D. Silverman]

Originally Posted by boldi

And all I ask is: Is there a proof for the conjecture, that only Mersenne primes can pass the congruence

mod

You tell me, they have proved a theorem -- thanks (I mean this seriosley), but where is this proof? In the paper You have linked I can see no answer for my question.

Please convey some supporting heuristical/probabilistic arguments as
to why the conjecture SHOULD be true. It is known that every base
is a false witness to infinitely many integers. The question here is
why 3 should be different and why it should not be a false witness to
Mersenne numbers.

I see no reason for it to be true other than that it works for a very small
set of examples.

[science_man_88]

Originally Posted by R.D. Silverman

I see no reason for it to be true other than that it works for a very small
set of examples.

I'm guessing you car more for what the OP thinks ?

My mistake in post 9 is that I took it too far I'll start edit: "I think" with that