Primality test similar to the AKS test

[Predrag Terzic <pedja.terzic@hotmail.com>]

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!")))))}

    

You can run this code here.

Best regards,

Pedja