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 .


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 .

for(i=1,p-2, s=s^2-2); 

if(lift(Mod(3,M)^((M-1)/2))==M-1,print("probably prime"),print("composite"))
  • $\begingroup$ Faster at what? $\endgroup$ – user21820 Mar 31 '16 at 7:13
  • $\begingroup$ Don't you mean $S_{p-2}$ instead of $S_{n-2}$ ? $\endgroup$ – Peter Mar 31 '16 at 7:16
  • $\begingroup$ @Petter Thanks ! Fixed $\endgroup$ – 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 lift-command seems to improve the calculation of large powers modulo large numbers, probably the reason PARI/GP is faster using this method.

The disadvantage of the pseudoprime-test is, of course, that the result is not $100$% correct, in contrary to the Lucas-Lehmer-Test.

  • $\begingroup$ 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? $\endgroup$ – Dave Radcliffe Aug 5 '18 at 19:41
  • $\begingroup$ @DaveRadcliffe I think this is unknown. $\endgroup$ – Peter Aug 6 '18 at 7:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.