mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2004-08-19, 12:03   #1
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

3·5·61 Posts
Default 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
T.Rex is offline   Reply With Quote
Old 2004-08-19, 14:10   #2
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

16238 Posts
Default 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
....
T.Rex is offline   Reply With Quote
Old 2004-09-15, 16:44   #3
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

3·5·61 Posts
Default 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
T.Rex is offline   Reply With Quote
Old 2004-09-21, 07:11   #4
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

3×5×61 Posts
Default 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
T.Rex is offline   Reply With Quote
Old 2004-09-22, 08:49   #5
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

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
akruppa is offline   Reply With Quote
Old 2004-09-23, 08:23   #6
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

3·5·61 Posts
Default 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
T.Rex is offline   Reply With Quote
Old 2004-09-23, 10:04   #7
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

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
akruppa is offline   Reply With Quote
Old 2004-09-28, 21:05   #8
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

3×5×61 Posts
Default 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
T.Rex is offline   Reply With Quote
Old 2004-09-30, 17:44   #9
gbvalor
 
gbvalor's Avatar
 
Aug 2002

3·37 Posts
Default

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
gbvalor is offline   Reply With Quote
Old 2016-03-29, 14:18   #10
primus
 
Jul 2014
Montenegro

2×13 Posts
Default

http://math.stackexchange.com/q/1718453
primus is offline   Reply With Quote
Old 2016-04-02, 23:11   #11
JeppeSN
 
JeppeSN's Avatar
 
"Jeppe"
Jan 2016
Denmark

2·83 Posts
Default

Quote:
Originally Posted by primus View Post
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
JeppeSN is offline   Reply With Quote
Reply

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 2018-09-01 13:23
non-Mersenne primality tests Visar Information & Answers 33 2015-12-01 18:27
What are the Primality Tests ( not factoring! ) for Fermat Numbers? Erasmus Math 46 2014-08-08 20:05
Primality proving CRGreathouse Software 13 2011-01-30 14:30
Two Primality tests for Fermat numbers 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.