? \u
aa =
(m)->m^2+m+7
cubictest =
(N,q)->a=sqrtint(4*q-27);d=a*q;s1=Mod(-a-3,q)/Mod(6,q);s2=Mod(a-3,q)/Mod(6,q);c=Mod(N,q)^((q-1)/3);C2=Mod(3*q,N)/Mod(d,N);C1=Mod(-d-9*q,N)/Mod(2*d,N);C0=Mod(-2*q^2,N)/Mod(d,N);flag=(c==s1);alpha=Mod(Mod(x,x^3-q*x-q),N);beta=C2*alpha^2+C1*alpha+Mod(C0,x^3-q*x-q);gama=-(alpha+beta);if(flag,predict=gama);if(!flag,predict=beta);frob=alpha^N;t=(frob==predict);return(t)
cubictest2 =
(N,q)->a=sqrtint(4*q-27);d=a*q;s1=Mod(-a-3,q)/Mod(6,q);s2=Mod(a-3,q)/Mod(6,q);c=Mod(N,q)^((q-1)/3);C2=Mod(3*q,N)/Mod(d,N);C1=Mod(-d-9*q,N)/Mod(2*d,N);C0=Mod(-2*q^2,N)/Mod(d,N);flag=(c==s1);alpha=Mod(Mod(x,x^3-q*x-q),N);beta=C2*alpha^2+C1*alpha+Mod(C0,x^3-q*x-q);gama=-(alpha+beta);if(flag,predict=gama);if(!flag,predict=beta);frob=alpha^N;llfrob=lift(lift(frob));llpredict=lift(lift(predict));t=0;if(polcoef(llfrob,0)==polcoef(llpredict,0),t=t+1);if(polcoef(llfrob,1)==polcoef(llpredict,1),t=t+1);if(polcoef(llfrob,2)==polcoef(llpredict,2),t=t+1);return(t)
valid =
(N,q)->t=(N>2);t=(t&&((N%2)==1));t=t&&(!(issquare(N)));t=t&&(isprime(q));t=t&&(issquare(4*q-27));if(t,t=t&&(lift(Mod(N,q)^((q-1)/3))>1));t=t&&(!ispower(N,3));t=t&&(gcd(N,q)==1);if(t,d=sqrtint(4*q-27);t=t&&(gcd(d,N)==1));return(t)
?
Related
