testcubicsym =
(n)->f=x^3-3*x-1;roots=vector(3);for(j=1,3,roots[j]=Mod(Mod(x,f),n)^(n^(j-1)));res=vector(3);for(k=1,7,m=8+k;d=digits(m,2);pr=1;for(j=1,3,if(d[j+1],pr=pr*roots[j]));sumd=0;for(j2=1,3,sumd=sumd+d[j2+1]);res[sumd]=res[sumd]+pr);t=0;for(j=1,3,t=t+(lift(res[j])==Mod(((-1)^j)*polcoef(f,3-j),n)));return(t)
For n == 2, 4, 5, 7 (mod 9), if n is prime, testcubicsym(n) returns 3. It's a cubic Frobenius test (similar to the quadratic test of Grantham), but specialized to the cubic polynomial f = x^3 -3x - 1.
There are composites in the same residue classes modulo 9 that satisfy 1/3 congruences. These are listed below:
1333615747
2027591113
7182672721
Similarly, one can write a test for the polynomial f = x^3 - 7x -7 which yields an extension of Q of conductor 9.
test_passes =
(n)->if(n%2==0,return(0));if(n%7==0||n%7==1||n%7==6,return(0));my(f=Mod(1,n)*x^3-Mod(7,n)*x-Mod(7,n));my(alpha=Mod(x,f));my(alpha_n=alpha^n);my(alpha_n2=alpha_n^n);my(s1=alpha+alpha_n+alpha_n2);my(s2=alpha*alpha_n+alpha_n*alpha_n2+alpha*alpha_n2);my(s3=alpha*alpha_n*alpha_n2);return((s1==Mod(0,n))||(s2==Mod(-7,n))||(s3==Mod(7,n)))
There are no pseudoprimes below 10^10 (even partial):
job =
()->count=0;for(n=2,10^10,if(n%2==0||isprime(n),next());if(test_passes(n),count++;print(n)););print("False positives found: ",count)
? job()
False positives found: 0
? ##
*** last result computed in 13h, 46min, 22,908 ms.
Related
