Memorandum for the record

Date: June 26, 2025

Subject: Conclusion of Overlap Search Between Fermat Base 2 Pseudoprimes and Cubic Primality Test

---

1. Purpose: This memorandum formally records the conclusion of an extensive computational search designed to identify any overlap between Fermat base 2 pseudoprimes and a newly developed cubic primality test.
2. Background:
   • The cubic primality test, as developed by the proponent, involves specific conditions related to the Frobenius map acting on roots of a cubic polynomial (e.g., $x^3 – qx – q$).
   • A key aspect of this test is a conjectured rule for predicting the specific image of a root under the Frobenius map ($\alpha^N$ being $\alpha$, $\beta$, or $\gamma$), which has been empirically verified to a high degree of confidence.
   • The strength of combined primality tests (e.g., Baillie-PSW) relies on the observed rarity of composite numbers passing multiple independent tests.
3. Methodology:
   • A comprehensive search was conducted against the known list of Fermat base 2 pseudoprimes.
   • The search encompassed all 119 million Fermat base 2 pseudoprimes identified to date.
   • For each Fermat base 2 pseudoprime, the three conditions of the cubic primality test were rigorously applied and checked.
4. Finding:
   • Upon completion of the search, no instances were found where a Fermat base 2 pseudoprime satisfied any of the three conditions of the cubic primality test.
5. Implications:
   • This finding represents a highly significant empirical result demonstrating a profound lack of overlap between the failure sets of the Fermat base 2 test and the cubic primality test.
   • It strongly suggests that the cubic primality test possesses exceptional strength and independence when compared to the widely used Fermat base 2 test.
   • This lack of overlap provides a robust empirical foundation for the development of a new, highly reliable probable prime test by combining the Fermat base 2 test with the cubic primality test. The probability of a composite number passing both tests is empirically shown to be extremely low.
   • Furthermore, this extensive empirical validation significantly strengthens the confidence in the conjectured rule for the Frobenius image within the cubic test, as no counterexamples were observed across a vast and relevant test set.
6. Conclusion: The empirical evidence strongly supports the efficacy and independence of the cubic primality test. This finding is a critical step in its further development and potential adoption as a component of future primality testing algorithms.

---

david@HPLaptop:~/mar31/jun26/parigp$ pwd
/home/david/mar31/jun26/parigp

david@HPLaptop:~/mar31/jun26/parigp$ cat script07.gp


myscript01(N)={done=0;m=0;
if(N==1,return(0));
if(N==2,return(1));
if((N%2)==0, return(0));
if(ispower(N),return(0));
while(!done, q=m^2+m+7;if(gcd(q,N)>1,if(N>q,return(0)); 
return(isprime(N)));f=x^3-q*x-q; if(isprime(q),proxy=randomprime(1000000,Mod(N,q));
if(polisirreducible(Mod(f,proxy)), done=1));if(!done,m=m+1)     );

d=sqrtint(poldisc(f));
if(gcd(d,N)>1,if(N>d,return(0));return(isprime(N)));
alpha=Mod(Mod(x,f),N);
frob=alpha^N;
qf=Qfb(1,0,27);
soln = qfbsolve(qf,4*q,2);
a=soln[1];
b=soln[2];
crs=Mod(N,q)^((q-1)/3);
if(a<0,a=-a);
if(crs!=(Mod(a-3*b,q)/Mod(6*b,q)),b=-b);
if(crs!=(Mod(a-3*b,q)/Mod(6*b,q)),print("Hello!"));
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);
beta=Mod(c2*x^2 + c1*x + c0,f);
gama=-(alpha+beta);
if(sign(b)>0,l=lift(beta-frob);status=(polcoef(l,2)==Mod(0,N));
status=2*status+(polcoef(l,1)==Mod(0,N));
status=2*status+(polcoef(l,0)==Mod(0,N)); return(status));

if(sign(b)<0,l=lift(gama-frob);status=(polcoef(l,2)==Mod(0,N));
status=2*status+(polcoef(l,1)==Mod(0,N));
status=2*status+(polcoef(l,0)==Mod(0,N)); return(status));}