PPP Extended test -- based on François Olivier Raoul Perrin's Sequence

[paulunderwood]

Recall the cubic route is given by the test:

{kill(x);TPPPC(n)=my(a=0,f,X=x);
while(X==x,a++;f=x^3-x-a;
  while(gcd(a,n)!=1||kronecker(poldisc(f),n)!=1,a++;f=x^3-x-a);
  X=Mod(Mod(x,n),f)^n);
gcd(polcoef(lift(lift(X)),2),n)==1&&X^3-X-a==0;}

For exponentiation of x consider the intermediate value s*x^2+t*x+u.

Squaring:

Mod(s*x^2+t*x+u,x^3-x-a)^2
Mod((s^2 + 2*u*s + t^2)*x^2 + (a*s^2 + 2*t*s + 2*u*t)*x + (2*a*t*s + u^2), x^3 - x - a)

Which can be calculated as ((s + t)^2-2*s*t + 2*u*s)*x^2 + (a*s^2 + 2*t*s + 2*u*t)*x + (2*a*t*s + u^2).

Totting up the different multiplications (and discounting multiplication by small a) gives 6 selfridges. There may be other ways to arrange this calculation or just leave it as PARI/GP has shown: 3 squares plus 3 mults (which all have to be modularly reduced over n).

Multiplying by the base, x, when the bit is one:

Mod(s*x^2+t*x+u,x^3-x-a)*x
Mod(t*x^2 + (s + u)*x + a*s, x^3 - x - a)

Simple enough.

Here it is:

{Cubo(n,a)=my(s=Mod(0,n),t=Mod(1,n),u=Mod(0,n),s2,t2,u2,st,tu,us,k,LEN=#digits(n,2)-2,tmp);
forstep(k=LEN,0,-1,s2=sqr(s);t2=sqr(t);u2=sqr(u);st=s*t;tu=t*u;us=u*s;s=s2+2*us+t2;t=a*s2+2*st+2*tu;u=2*a*st+u2;
if(bittest(n,k),tmp=s;s=t;t=tmp+u;u=a*tmp));
Mod(s*x^2+t*x+u,x^3-x-a)}

{kill(x);TPPPC(n)=my(a=0,f,X=x);
while(X==x,a++;f=x^3-x-a;
  while(gcd(a,n)!=1||kronecker(poldisc(f),n)!=1,a++;f=x^3-x-a);
  X=Cubo(n,a));
gcd(polcoef(lift(lift(X)),2),n)==1&&X^3-X-a==0;}

Timings:

? n=2^44497-1;Mod(Mod(x,n),x^3-x-1)^n;
? ##
  ***   last result: cpu time 3min, 2,654 ms, real time 3min, 3,078 ms.
? n=2^44497-1;Cubo(n,1);
? ##
  ***   last result: cpu time 1min, 59,033 ms, real time 1min, 59,127 ms.

Time for some verification of the cubic "route"! Something like this will do:

{for(n=11,1000000,if(!ispseudoprime(n),
for(a=1,n,
if(gcd(a,n)==1&&kronecker(poldisc(x^3-x-a),n)==1&&
(X=Cubo(n,a))&&X!=x&&gcd(polcoef(lift(lift(X)),2),n)==1&&X^3-X-a==0,
print([n,a])))))}

[paulunderwood]

Note that poldisc(x^3-1-a) is 4-27*a^2. Also working over x^3-x-a is the same as x^3-x+a.

{for(n=11,1000000,if(!ispseudoprime(n),
for(a=1,(n-1)/2,if(gcd(a,n)==1&&kronecker(4-27*a^2,n)==1&&
(X=Cubo(n,a))&&X!=x&&gcd(polcoef(lift(lift(X)),2),n)==1&&X^3-X-a==0,
print([n,a])))))}

I'll convert this all to The C Language over the coming week.