Use Pepin's Tests for proving primality of Mersenne numbers ?

[T.Rex]

Who could help proving that the following conjecture is true (or false) ?

The Pepin's Test is well know for proving the primality of Fermat numbers.
It seems that it could also be used for proving primality of Mersenne numbers (but I don't expect performance improvements).

(here after, ~= means: "is congruent to".)

Conjecture:

q prime,  M_q = 2^q-1 is prime  iff  3^(M_q-1)/2 ~= -1 (mod M_q) .

As Pepin noted for his own test, this is equivalent to a LLT-like test:

S_0 = 3
S_i = S_(i-1)^2
q prime,  M_q = 2^q-1 is prime  iff  M_q | S_(q-1) + 3 .

This can be proved easily:

S_i = 3^(2^i)
Since: (M_q-1)/2 = 2^(q-1)-1
Then:  S_(q-1) = 3^(2^(q-1)) = 3^((M_q-1)/2) * 3
And, if 3^(M_q-1)/2 = -1 , then: S_(q-1) = -3 .

This has been checked for all primes up to 2999 and for Mersenne primes up to 23209 by using the following PARI/gp code:

? L1(q)= Mq=2^q-1;S=3;for(i=1,q-1,S=(S*S)%Mq);if(S!=(Mq-3),S="false",S="TRUE");print(q,S);
? L2(a,b)= forprime(q=a,b,L1(q))

? L1(89)
89TRUE

? L2(3,1000)
3TRUE
5TRUE
7TRUE
11false
13TRUE
...

Tony

[T.Rex]

Note that though the Pepin's Test for Fermat numbers can use 3, 5, 10, ... as value for k in:

k^((F_n-1)/2) ~= -1 (mod F_n)

only k = 3 seems to work for all Mersenne numbers with this exact test with -1 .

Using 5 and 10 as value for k requires to test with -1 and 1 instead of only -1.
Example:

k=10
L1(q)= Mq=2^q-1;S=k;for(i=1,q-1,S=(S*S)%Mq);if(S!=k&&S!=(Mq-k),S="false",S="TRUE");print(q,"  ",S)
L2(3,1000)
3  false
5  TRUE
7  TRUE
11  false
13  TRUE
17  TRUE
19  TRUE
23  false
29  false
31  TRUE
37  false
41  false
43  false
47  false
53  false
59  false
61  TRUE
67  false
71  false
73  false
79  false
83  false
89  TRUE
....

[T.Rex]

I've checked the conjecture for all composite Mersenne numbers up to M6569 and all prime Mersenne numbers up to M132049 : still OK.
Does someone have an idea on how to prove the conjecture ?
Or do you know if this result has already been proven in the past ?
Tony

[T.Rex]

OK. What seemed to be a good idea is simply an avatar of Fermat Little Theorem.
That means that if Mq is prime then: 3^(M_q-1)/2 ~= -1 (mod M_q) is true.
But the converse is not true ...
With Pepin's test and Fermat numbers there is a proof that if the converse is true then Fn is a prime number. We don't have such a proof for Mersenne numbers. Any idea ?
Nevertheless, up to now I've not been able to find a counter-example. Up to M87509 , none of the composite Mersenne numbers verifies the property above.
Done with a modified version of GLucas (thanks Guillermo).
Tony

[akruppa]

There was a related discussion on the NMBRTHRY mailing list recently, see http://listserv.nodak.edu/scripts/wa...408&L=nmbrthry, "Mersenne footnote". Maybe it is of interest to you.

Alex

[T.Rex]

Thanks Alex,

Yes, I saw it 2 or 3 days before you did.
I've answered to jj through the NMBRTHRY mailing list, but I think my answer has been lost ...
In a recent post (today ...), he says he searched hard but found no proof ...

I've checked the test is true up to: M132499 .

Don't you think the probability to find a counter-example becomes smaller and smaller with the size of Mersenne composites ?
So maybe this is an interesting probability test if proved faster than LLT. But I guess it is not faster than LLT, since substracting 2 to x^2 should cost much less than x^2 .

I gonna discuss with jj (Joerg).

Tony

[akruppa]

Yes, afaik the probability of a number passing as a pseudo-prime becomes smaller for larger numbers. Your test is basically a Euler probable primality test as 3 is known to be a quadratic non-residue for Mersenne primes. It'd be interesting to know if the expected value for the number of prime exponent Mersennes that are base-3 Euler pseudoprimes converges.

Anyways, I'm pretty sure this test will not be faster than LL. In LL, you only have to subtract 2 after each iteration which takes practically no time at all (it's in O(1)), in any Fermat-style test you'd have to multiply be the base (3 in your case) after each squaring, which takes much longer (O(n)), or, alternatively, compute 3^((Mp-1)/2+1) which avoids the multiplications by 3 and then multiply by 1/3 at the end. Still slower than p subtractions, though.

Alex

[T.Rex]

Originally Posted by akruppa

Yes, afaik the probability of a number passing as a pseudo-prime becomes smaller for larger numbers.

I also think so. But I still continue to check with q prime and composite. No counter-example up to now, and the more I search the less I may find it ...

It'd be interesting to know if the expected value for the number of prime exponent Mersennes that are base-3 Euler pseudoprimes converges.

That's unclear for me.

Anyways, I'm pretty sure this test will not be faster than LL.
Alex

I also think so.
My idea is more to show that Lucas Sequences can be used for Fermat numbers and that Pepin's like test could (once proven ...) be used for Mersenne numbers.

But yes, if we could find some probabilist test for Mersenne numbers that would be faster than LLT, that would help sorting good candidate exponents before running the LLT. I don't know about Mersenne, but I have some idea for Fermat numbers. The problem is that we already know that next Fermat number with unknown state (prime or not) is F33, which is very big. So my idea would help only if it can lead to a faster full primality proof.

Tony

[gbvalor]

Hi,

I've wrote some thougths about the chances we have to find a composite Mersenne number with prime exponent being pseudoprime base 3. It is a draft written by an amateur, and I'm sure there are errors in it . Anyway you can read it here

http://www.oxixares.com/~gbv/mersenne_pseudoprime.html

Please, don't be too hard with me

Guillermo

[primus]

http://math.stackexchange.com/q/1718453

[JeppeSN]

Originally Posted by primus

http://math.stackexchange.com/q/1718453

That is the easy "direction" only. The more interesting part was the converse, i.e. if you had calculated that $3^\frac{M_p-1}{2} \equiv -1 \pmod {M_p}$, would $M_p$ necessarily be a prime, or are there rare cases where $M_p$ is only a pseudoprime ($M_p$ is composite despite "passing" the test). /JeppeSN