20040819, 12:03  #1 
Feb 2004
France
929 Posts 
Use Pepin's Tests for proving primality of Mersenne numbers ?
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: Code:
q prime, M_q = 2^q1 is prime iff 3^(M_q1)/2 ~= 1 (mod M_q) . Code:
S_0 = 3 S_i = S_(i1)^2 q prime, M_q = 2^q1 is prime iff M_q  S_(q1) + 3 . Code:
S_i = 3^(2^i) Since: (M_q1)/2 = 2^(q1)1 Then: S_(q1) = 3^(2^(q1)) = 3^((M_q1)/2) * 3 And, if 3^(M_q1)/2 = 1 , then: S_(q1) = 3 . Code:
? L1(q)= Mq=2^q1;S=3;for(i=1,q1,S=(S*S)%Mq);if(S!=(Mq3),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 ... 
20040819, 14:10  #2 
Feb 2004
France
929 Posts 
Differences with Pepin's Test
Note that though the Pepin's Test for Fermat numbers can use 3, 5, 10, ... as value for k in:
Code:
k^((F_n1)/2) ~= 1 (mod F_n) Using 5 and 10 as value for k requires to test with 1 and 1 instead of only 1. Example: Code:
k=10 L1(q)= Mq=2^q1;S=k;for(i=1,q1,S=(S*S)%Mq);if(S!=k&&S!=(Mqk),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 .... 
20040915, 16:44  #3 
Feb 2004
France
1110100001_{2} Posts 
Check of the conjecture
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 
20040921, 07:11  #4 
Feb 2004
France
929_{10} Posts 
Fermat Little Theorem is everywhere
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_q1)/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 counterexample. Up to M87509 , none of the composite Mersenne numbers verifies the property above. Done with a modified version of GLucas (thanks Guillermo). Tony 
20040922, 08:49  #5 
"Nancy"
Aug 2002
Alexandria
9A3_{16} Posts 
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 
20040923, 08:23  #6 
Feb 2004
France
929 Posts 
NMBRTHRY mailing list
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 counterexample 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 
20040923, 10:04  #7 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
Yes, afaik the probability of a number passing as a pseudoprime becomes smaller for larger numbers. Your test is basically a Euler probable primality test as 3 is known to be a quadratic nonresidue for Mersenne primes. It'd be interesting to know if the expected value for the number of prime exponent Mersennes that are base3 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 Fermatstyle 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^((Mp1)/2+1) which avoids the multiplications by 3 and then multiply by 1/3 at the end. Still slower than p subtractions, though. Alex 
20040928, 21:05  #8  
Feb 2004
France
1641_{8} Posts 
Maybe only a base3 Euler probable primality test ...
Quote:
Quote:
Quote:
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 

20040930, 17:44  #9 
Aug 2002
3×37 Posts 
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 
20160329, 14:18  #10 
Jul 2014
Montenegro
26_{10} Posts 

20160402, 23:11  #11  
"Jeppe"
Jan 2016
Denmark
2×7×13 Posts 
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Fast and robust error checking on Proth/Pepin tests  R. Gerbicz  Number Theory Discussion Group  15  20180901 13:23 
nonMersenne primality tests  Visar  Information & Answers  33  20151201 18:27 
What are the Primality Tests ( not factoring! ) for Fermat Numbers?  Erasmus  Math  46  20140808 20:05 
Primality proving  CRGreathouse  Software  13  20110130 14:30 
Two Primality tests for Fermat numbers  T.Rex  Math  2  20040911 07:26 