PRP Test for Wagstaff and Mersenne prime ?

kijinSeija · 2023-04-30, 16:45

Let $N = \frac{-a^p-1}{-a-1}$ with a = 2 for Wagstaff numbers Wp and a= -2 for Mersenne Numbers Mp.

Let the sequence $S_i = 6 \cdot S_{i-1}^2 + 18 \cdot S_{i-1} + 12$ with $S_0 = 12$ .

$N$ is prime if $S_{p-2} \equiv 0$ (mod Mp or Wp).

The Pari GP code to check the conjecture :

Code:

forprime(p=3,10501,s=Mod(12,(2^p+1)/3);for(x=3,p,s=6*s^2+18*s+12);if(s==0,print([p])))
forprime(p=3,11213,s=Mod(12,(2^p-1));for(x=3,p,s=6*s^2+18*s+12);if(s==0,print([p])))

Of course, this is less efficient than S^2-2 for Mersenne numbers, it can be interesting especially for Wagstaff numbers, but I think there are some theoritical interest for the conjecture and it can be interesting for a proof if the conjecture is true.

kijinSeija · 2023-05-01, 22:51

Quote:

Originally Posted by kijinSeija

Let $N = \frac{-a^p-1}{-a-1}$ with a = 2 for Wagstaff numbers Wp and a= -2 for Mersenne Numbers Mp.

Let the sequence $S_i = 6 \cdot S_{i-1}^2 + 18 \cdot S_{i-1} + 12$ with $S_0 = 12$ .

$N$ is prime if $S_{p-2} \equiv 0$ (mod Mp or Wp).

The Pari GP code to check the conjecture :

Code:

forprime(p=3,10501,s=Mod(12,(2^p+1)/3);for(x=3,p,s=6*s^2+18*s+12);if(s==0,print([p])))
forprime(p=3,11213,s=Mod(12,(2^p-1));for(x=3,p,s=6*s^2+18*s+12);if(s==0,print([p])))

Of course, this is less efficient than S^2-2 for Mersenne numbers, it can be interesting especially for Wagstaff numbers, but I think there are some theoritical interest for the conjecture and it can be interesting for a proof if the conjecture is true.

$S_{p-3}$ numerical observation for p > 3

For Mersenne Numbers Mp :

$N$ is PRP if $S_{p-3} \equiv Mp - 2$ (mod Mp).

PARI GP code :

Code:

forprime(p=5,11213,s=Mod(12,(2^p-1));for(x=4,p,s=6*s^2+18*s+12);if(s==(2^p-3),print1(","p)))

5,7,13,17,19,31,61,89,107,127,521,607,1279,2203,2281,3217,4253,4423,9689,9941,11213

For Wagstaff Numbers Wp :

$N$ is PRP if $S_{p-3} \equiv Wp - 1$ (mod Wp) and $p \equiv 3$ (mod 2)
or
$N$ is PRP if $S_{p-3} \equiv Wp - 2$ (mod Wp) and $p \equiv 3$ (mod 1)

PARI GP code :

Code:

forprime(p=5,10691,s=Mod(12,(2^p+1)/3);for(x=4,p,s=6*s^2+18*s+12);if((s==((2^p+1)/3-1)&&p%3==2)||(s==((2^p+1)/3-2)&&p%3==1),print1(","p)))

5,7,11,13,17,19,23,31,43,61,79,101,127,167,191,199,313,347,701,1709,2617,3539,5807,10501,10691

User140242 · 2023-05-12, 14:21

Quote:

Originally Posted by kijinSeija

$S_{p-3}$ numerical observation for p > 3

For Mersenne Numbers Mp :

$N$ is PRP if $S_{p-3} \equiv Mp - 2$ (mod Mp).

PARI GP code :

Code:

forprime(p=5,11213,s=Mod(12,(2^p-1));for(x=4,p,s=6*s^2+18*s+12);if(s==(2^p-3),print1(","p)))

5,7,13,17,19,31,61,89,107,127,521,607,1279,2203,2281,3217,4253,4423,9689,9941,11213

For Wagstaff Numbers Wp :

$N$ is PRP if $S_{p-3} \equiv Wp - 1$ (mod Wp) and $p \equiv 3$ (mod 2)
or
$N$ is PRP if $S_{p-3} \equiv Wp - 2$ (mod Wp) and $p \equiv 3$ (mod 1)

PARI GP code :

Code:

forprime(p=5,10691,s=Mod(12,(2^p+1)/3);for(x=4,p,s=6*s^2+18*s+12);if((s==((2^p+1)/3-1)&&p%3==2)||(s==((2^p+1)/3-2)&&p%3==1),print1(","p)))

5,7,11,13,17,19,23,31,43,61,79,101,127,167,191,199,313,347,701,1709,2617,3539,5807,10501,10691

Correct me if I'm wrong but the sequence you used is equivalent to

$S_{i}=\frac{3^{(2^{i+2}-1)}-3}{2}$

then

$S_{p-2}=\frac{3^{2^p-1}-3}{2}$ for Mersenne numbers
$S_{p-2}=\frac{3^{2^p-1}-3}{2}=\frac{27^{\frac{2^p+1}{3}}-27}{18}$ for Wagstaff numbers

Applying Fermat's little theorem, we have

$S_{p-2}\equiv 0\pmod{2^p-1}$ for Mersenne prime numbers

$S_{p-2}\equiv 0\pmod{\frac{2^p+1}{3}}$for Wagstaff prime numbers

but also in this case we have equivalently for p>3

for Mersenne prime numbers

$3^{2^p-2}=(3^{2^{p-1}-1})^2\equiv 1\pmod{2^p-1}$

then for Euler's criterion

$3^{2^{p-1}-1}\equiv -1\pmod{2^p-1}$

and

$S_{p-3}=\frac{3^{2^{p-1}-1}-3}{2}\equiv -2\pmod{2^p-1}$

analogous reasoning can be done for Wagstaff numbers.

T.Rex · 2023-05-13, 14:53

Quote:

Originally Posted by User140242

Correct me if I'm wrong but the sequence you used is equivalent to

$S_{i}=\frac{3^{(2^{i+2}-1)}-3}{2}$
...

Nice !!!

Now, the test by kijinSeija also works for Fermat numbers, with a little change : last $S_i$ is equal to the previous one.
(also: I prefer starting at 0, and the code has been optimized (only 2 multiplications))

Let the sequence $S_i = 6 ( S_{i-1} ( S_{i-1} +3) + 2)$ with $S_0 = 0$ .

$F_n=2^2^n+1$ is prime iff $S_{2^n} \equiv S_{2^n-1} \ \pmod{F_n}$ .

And we have: $S_{2^n} = 2 \prod_{i=1}^{n-1}F_i$ .

With the PARI/gp code:

Code:

for(i=0,5,
   q=2^i;
   F=2^q+1;
   s=Mod(0,F);
   for(i=1,q,
      s=6*(s*(s+3)+2);
      if(i==q-1,s1=s);
      print("   ",i," ",lift(s))
   );
   if(s==s1,print(i," P"),print(i," C"))
)

I've been unable to use your trick. Can you?

User140242 · 2023-05-13, 16:16

Quote:

Originally Posted by T.Rex

Nice !!!

Now, the test by kijinSeija also works for Fermat numbers, with a little change : last $S_i$ is equal to the previous one.
(also: I prefer starting at 0, and the code has been optimized (only 2 multiplications))

Let the sequence $S_i = 6 ( S_{i-1} ( S_{i-1} +3) + 2)$ with $S_0 = 0$ .

$F_n=2^2^n+1$ is prime iff $S_{2^n} \equiv S_{2^n-1} \ \pmod{F_n}$ .

And we have: $S_{2^n} = 2 \prod_{i=1}^{n-1}F_i$ .

With the PARI/gp code:

Code:

for(i=0,5,
   q=2^i;
   F=2^q+1;
   s=Mod(0,F);
   for(i=1,q,
      s=6*(s*(s+3)+2);
      if(i==q-1,s1=s);
      print("   ",i," ",lift(s))
   );
   if(s==s1,print(i," P"),print(i," C"))
)

I've been unable to use your trick. Can you?

Provided that from Fermat's little theorem we can obtain that for any integer a

then if p is a prime number you have $a^p\equiv a\pmod p$ but the reverse is false.

If $S_{0}=0$ then $S_i=\frac{3^{2^{i+1}-1}-3}{2}$

the sequence can also be written $S_{i+1}=6\cdot(S_i+1)\cdot(S_i+2)$ with $S_{0}=0$.

then if $F_n=2^{2^n}+1$ is a prime number

$S_{2^n}-S_{2^n-1}=\frac{3^{2^{2^n+1}-1}-3}{2}-\frac{3^{2^{2^n}-1}-3}{2}=\frac{3^{2^{2^n+1}}-3^{2^{2^n}}}{6}=3^{2^{2^n}}\cdot \frac {3^{2^{2^n}}-1}{6}=3^{2^{2^n}}\cdot \frac {3^{2^{2^n}+1}-3}{18}\equiv 0\pmod{2^{2^n}+1}$

User140242 · 2023-05-14, 09:26

Quote:

Originally Posted by User140242

then if $F_n=2^{2^n}+1$ is a prime number

$S_{2^n}-S_{2^n-1}=\frac{3^{2^{2^n+1}-1}-3}{2}-\frac{3^{2^{2^n}-1}-3}{2}=\frac{3^{2^{2^n+1}}-3^{2^{2^n}}}{6}=3^{2^{2^n}}\cdot \frac {3^{2^{2^n}}-1}{6}=3^{2^{2^n}}\cdot \frac {3^{2^{2^n}+1}-3}{18}\equiv 0\pmod{2^{2^n}+1}$

I don't think it is useful in this case it is better to use the sequence

$S_i=\frac{3^{2^i}-1}{2}$

equivalent to $S_{i+1}=2\cdot S_i \cdot(S_i+1)$ with $S_0=1$

Then if $F_n=2^{2^n}+1$ is a prime number

$S_{2^n}\equiv 0\pmod{F_n}$

kijinSeija · 2023-05-14, 20:34

Quote:

Originally Posted by User140242

Correct me if I'm wrong but the sequence you used is equivalent to

$S_{i}=\frac{3^{(2^{i+2}-1)}-3}{2}$

then

$S_{p-2}=\frac{3^{2^p-1}-3}{2}$ for Mersenne numbers
$S_{p-2}=\frac{3^{2^p-1}-3}{2}=\frac{27^{\frac{2^p+1}{3}}-27}{18}$ for Wagstaff numbers

Applying Fermat's little theorem, we have

$S_{p-2}\equiv 0\pmod{2^p-1}$ for Mersenne prime numbers

$S_{p-2}\equiv 0\pmod{\frac{2^p+1}{3}}$for Wagstaff prime numbers

but also in this case we have equivalently for p>3

for Mersenne prime numbers

$3^{2^p-2}=(3^{2^{p-1}-1})^2\equiv 1\pmod{2^p-1}$

then for Euler's criterion

$3^{2^{p-1}-1}\equiv -1\pmod{2^p-1}$

and

$S_{p-3}=\frac{3^{2^{p-1}-1}-3}{2}\equiv -2\pmod{2^p-1}$

analogous reasoning can be done for Wagstaff numbers.

Thanks for your answer and your time for the explanation !

This is really interesting

I'm not a mathematician but I understand the main part I guess even if I should check some definition

2023-04-30, 16:45	#1
kijinSeija Mar 2021 Home 38₁₆ Posts	PRP Test for Wagstaff and Mersenne prime ? Let $N = \frac{-a^p-1}{-a-1}$ with a = 2 for Wagstaff numbers Wp and a= -2 for Mersenne Numbers Mp. Let the sequence $S_i = 6 \cdot S_{i-1}^2 + 18 \cdot S_{i-1} + 12$ with $S_0 = 12$ . $N$ is prime if $S_{p-2} \equiv 0$ (mod Mp or Wp). The Pari GP code to check the conjecture : Code: forprime(p=3,10501,s=Mod(12,(2^p+1)/3);for(x=3,p,s=6s^2+18s+12);if(s==0,print([p]))) forprime(p=3,11213,s=Mod(12,(2^p-1));for(x=3,p,s=6s^2+18s+12);if(s==0,print([p]))) Of course, this is less efficient than S^2-2 for Mersenne numbers, it can be interesting especially for Wagstaff numbers, but I think there are some theoritical interest for the conjecture and it can be interesting for a proof if the conjecture is true.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
New test for Mersenne prime	allasc	Math	34	2022-09-11 13:03
Status of Wagstaff testing? and testing Mersenne primes for Wagstaff-ness	GP2	Wagstaff PRP Search	414	2020-12-27 08:11
New Mersenne Software For Test Mersenne Prime Numbers On Android	thorken	Software	66	2019-01-13 21:08
Statistical odds for prime in Wagstaff vs Mersenne	diep	Math	27	2010-01-13 20:18
another mersenne prime test	jocelynl	Math	8	2006-10-20 19:36