Aw: Re: ispseudoprime speed-up

[Paul Underwood <paulunderwood@mindless.com>]

Yes I forgot to test for even numbers.

 

I should have used logint and bittest.

 

I should have used a forprime loop for the a selection.

 

gcd(a^6-1,n) should detect composites.

 

The code is just proof-of-concept.

 

It is equivalent to Mod(Mod(x,n),x^2-x-a)^n==-x+1 where a is prime.

 

It uses a primitive Barrett reduction.

 

Proper coding will make it more efficient.

 

As for scaling, there will be thresholds where this test becomes quicker than ispseudoprime.

 

As for my "claim", initial testing shows no psedoprimes, the first being for a = 251 where the chance of no finding a previous prime a is < 10^-60

 

Paul

 

Sent: Tuesday, October 27, 2026 at 1:38 PM

From: "Aurel Page" <aurel.page@normalesup.org>

To: "Paul Underwood" <paulunderwood@mindless.com>, pari-dev@pari.math.u-bordeaux.fr

Subject: Re: ispseudoprime speed-up

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