 mersenneforum.org > Math Use Pepin's Tests for proving primality of Mersenne numbers ?
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read  2004-08-19, 12:03 #1 T.Rex   Feb 2004 France 3·5·61 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^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: Code: 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: Code: 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: 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   2004-08-19, 14:10 #2 T.Rex   Feb 2004 France 16238 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_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: Code: 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 ....   2004-09-15, 16:44 #3 T.Rex   Feb 2004 France 3·5·61 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   2004-09-21, 07:11 #4 T.Rex   Feb 2004 France 3×5×61 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_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   2004-09-22, 08:49 #5 akruppa   "Nancy" Aug 2002 Alexandria 2,467 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   2004-09-23, 08:23 #6 T.Rex   Feb 2004 France 3·5·61 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 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   2004-09-23, 10:04 #7 akruppa   "Nancy" Aug 2002 Alexandria 2,467 Posts 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   2004-09-28, 21:05   #8
T.Rex

Feb 2004
France

3×5×61 Posts Maybe only a base-3 Euler probable primality test ...

Quote:
 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 ...
Quote:
 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.
Quote:
 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   2004-09-30, 17:44 #9 gbvalor   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   2016-03-29, 14:18 #10 primus   Jul 2014 Montenegro 2×13 Posts    2016-04-02, 23:11   #11
JeppeSN

"Jeppe"
Jan 2016
Denmark

2·83 Posts Quote:
 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   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post R. Gerbicz Number Theory Discussion Group 15 2018-09-01 13:23 Visar Information & Answers 33 2015-12-01 18:27 Erasmus Math 46 2014-08-08 20:05 CRGreathouse Software 13 2011-01-30 14:30 T.Rex Math 2 2004-09-11 07:26

All times are UTC. The time now is 17:03.

Mon Apr 12 17:03:02 UTC 2021 up 4 days, 11:43, 1 user, load averages: 1.47, 2.11, 2.16

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.