Re: ispseudoprime speed-up

[Aurel Page <aurel.page@normalesup.org>]

Dear Paul,

I think you forgot to test that n is odd, try n=8, 22, 26, etc.

Can you elaborate on your claim? What speedup to you expect 
asymptotically? Should there exist more pseudoprimes for this test?

Cheers,
Aurel

On 10/27/26 14:16, Paul Underwood wrote:
> {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