Re: Primality test similar to the AKS test

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

On Tue, Feb 11, 2020 at 04:36:28PM +0000, Predrag Terzic wrote:
> Here is a working pari/gp implementation of my variation (see here<https://mathoverflow.net/questions/287560/primality-test-similar-to-the-aks-test>) of AKS test<https://en.wikipedia.org/wiki/AKS_primality_test> . Problem is that my code is extremely slow. Is there something that I could change in code to achieve a better running time?
> 
>     xmat(r,n,a) = [2*x, a; 1, 0]*Mod(1,x^r-1)*Mod(1,n);
>     AKSv2(n)={
>     if(!(ispower(n)==0),print("Composite!"),r=2;
>     while(!(gcd(n,r)==1),r++);while(znorder(Mod(n,r))<=(log(n)/log(2))^2,r++;while(!(gcd(n,r)==1),r++));
>     i=0;for(a=2,min(r,n-1),if(Mod(n,a)==0,print("Composite!");i++;break));
>     if(i==0,if(n<=r,print("Prime!"),j=0;for(a=1,floor(sqrt(eulerphi(r))*(log(n)/log(2))),my(xp = xmat(r,n,a)^n*[x,1]~);
>     if(!(xp[2] == Mod(x*Mod(1,n),x^r-1)^n),print("Composite!");j++;break));if(j==0,print("Prime!")))))}

AKS is slow in general.
You can speed it up by replacing xmat by operations with POLMOD.
I join a version I have since 2007.

Cheers,
Bill.

aks6(n)=
{
local(r,l,a,bornesup,X);
if( ispower(n),
	return(0);break,
	r=2; l=log(n)/log(2);
	while( 1==1,		
		if( gcd(r,n)==1, if( znorder(Mod(n,r))<(l^2),r++,break), r++)
		);
	for( a=2, r, if( gcd(a,n) != 1, return(0);break));
	if( n<5690035 && !n>r, return(1);break);
	bornesup=floor(sqrt(eulerphi(r))*l);
	X = Mod(Mod(1,n)*x,x^r-1);
    	for( a=1, bornesup,
        	if( (X+a)^n != X^n+a, return(0);break);
    	   );
	return(1);
)
}