ispseudoprime speed-up

[Paul Underwood <paulunderwood@mindless.com>]

{tstwbar2(n)=my(a,BIN,LEN,bit,s,t,s2,t2,spt2,H,M,A);
if(n==2||n==3||n==5||n==7,return(1));
if(n<1||gcd(105,n)!=1||issquare(n),return(0));
BIN=binary(n);LEN=length(BIN);H=ceil(3/2*LEN);M=1<<H-1;A=(1<<H)%n;a=3;
while(!isprime(a)||kronecker(1+4*a,n)!=-1||gcd(a^6-1,n)!=1,a+=2);
s=1;t=0;
for(bit=2,LEN,s2=sqr(s);t2=sqr(t);spt2=sqr(s+t);
  if(BIN[bit],
   s=spt2+a*s2;t=a*(spt2-t2),
   s=spt2-t2;t=a*s2+t2);
 s=(bitand(s,M)+(s>>H)*A)%n;
 t=(bitand(t,M)+(t>>H)*A)%n);
s==-1%n&&t==1;}

? n=numbpart(158381443);

?

? tstwbar2(n)
1
? ##
  ***   last result: cpu time 46,430 ms, real time 46,457 ms.
? 
? Mod(2,n)^n==2
1
? ##
  ***   last result: cpu time 19,768 ms, real time 19,838 ms.
? 
? ispseudoprime(n)
1
? ##
  ***   last result: cpu time 1min, 8,819 ms, real time 1min, 8,909 ms.

 

I claim that the above test, tstwbar2, is enough without a strong base 2 Fermat PRP test

 

Best wishes

 

Paul