# Pseudo-primality test for Mersenne numbers faster than Lucas-Lehmer test?

Definition

Let $M_p=2^p-1$ with $p$ prime and $p>2$ .

Lucas-Lehmer Test

$M_p$ is prime if and only if $S_{p-2} \equiv 0 \pmod {M_p}$

where $S_{k+1}=S^2_{k}-2$ and $S_0=4$ .

Pseudo-Primality Test

If $M_p$ is prime then $3^{\frac{M_p-1}{2}} \equiv -1 \pmod {M_p}$

For proof see this question .

Question

Is this pseudo-primality test faster than Lucas-Lehmer test ?

My PARI/GP implementation of PPT (see below) is approximately $1.5$ times faster than PARI/GP implementation of LLT .

LLT(p)=
{
my(s=Mod(4,2^p-1));
for(i=1,p-2, s=s^2-2);
if(s==0,print("prime"),print("composite"))
}


PPT(p)=
{
M=2^p-1;
if(lift(Mod(3,M)^((M-1)/2))==M-1,print("probably prime"),print("composite"))
}

• Faster at what? – user21820 Mar 31 '16 at 7:13
• Don't you mean $S_{p-2}$ instead of $S_{n-2}$ ? – Peter Mar 31 '16 at 7:16
• @Petter Thanks ! Fixed – Peđa Terzić Mar 31 '16 at 7:17

Both tests need about $p$ multiplications modulo $M_p$, so they should be equally fast.
The disadvantage of the pseudoprime-test is, of course, that the result is not $100$% correct, in contrary to the Lucas-Lehmer-Test.
• Are there any known counterexamples, i.e. primes $p$ such that $3^{(M_p-1)/2} \equiv 1 \pmod{M_p}$ but $M_p$ is not prime? – Dave Radcliffe Aug 5 '18 at 19:41