**Conjecture**
Let

such that

is prime and

Let

with

, then

is prime iff

**Maxima Implementations**
LL Test

Code:

p:9689;
(s:4,M:2^p-1,
for i from 1 thru (p-2) do (s:mod(s^2-2,M)))$
(if(s=0) then print("prime") else print("composite"));

Conjecture

Code:

p:9689;
(s:4,M:2^p-1,
for i from 1 thru (p-2)/3 do (s:mod(s^8-8*s^6+20*s^4-16*s^2+2,M)))$
(if(s=0) then print("prime") else print("composite"));

Maxima implementation of this modified test is approximately two times faster than Maxima implementation of original Lucas-Lehmer test .

Maybe someone on this forum can prove or disprove this conjecture .