Bill Allombert on Tue, 11 Feb 2020 18:39:44 +0100

[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: Primality test similar to the AKS test

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<>) of AKS 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.

if( ispower(n),
	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);
	X = Mod(Mod(1,n)*x,x^r-1);
    	for( a=1, bornesup,
        	if( (X+a)^n != X^n+a, return(0);break);