I’ve been experimenting with S. Khashin’s Frobenius primality test, as described in a preprint of his, Counterexamples for Frobenius primality test, at https://arxiv.org/abs/1307.7920 . Given an odd number n>1 that is not a square, let c be an odd prime number with (c/n)=-1, (c/n) being the Jacobi symbol. If n is prime, then (1+sqrt(c))^n == 1-sqrt(c) (modulo n), a consequence of the properties of the Frobenius automorphism over finite fields. If a composite odd n satisfies the foregoing congruence, we shall say that n is a Frobenius pseudoprime, and that c is a Frobenius liar for n. Khashin’s choice of c in his version of the Frobenius test is to let c be the least odd prime with (c/n)=-1. The main result of his paper is Proposition 3.12: There are no FPP less than 2^60 with c<128 and without divisors <=17. This got me interested in finding which odd numbers n, candidates for Khashin’s Frobenius test, have liars c with c<n/2. I’m conducting an exhaustive search of smallest liars of Khashin’s Frobenius test, and the main point up to the present time is that for all candidate n up to 10^6, all liars c are greater than 2000. Thus, in a sense, there are no small liars. By comparison, in the case of the Fermat test or the Miller-Rabin test, already for n=2047 (a composite number) the base 2 is a strong liar (a liar for the Miller-Rabin test and, a fortiori, a liar for the Fermat test). I’ve been thinking about the potential strength (theoretically) of two or more rounds of Khashin’s Frobenius test. All I can say is that after a modest amount of testing, Khashin’s Frobenius test appears quite discriminating of composite n. The data up till now is copied below.
n Smallest liar c
.29539 1 1 count=1 smallest liar=4397 Liar rate=0.0011890606420927467300832342449464922711
.58829 1 1 count=1 smallest liar=10357 Liar rate=0.00062735257214554579673776662484316185696
.71639 1 1 count=1 smallest liar=21191 Liar rate=0.00052383446830801466736511262441068622315
.86221 1 1 count=1 smallest liar=32381 Liar rate=0.00043917435221783047870004391743522178305
94301 1 1 count=2 smallest liar=27197 Liar rate=0.00080808080808080808080808080808080808081
...143009 1 1 count=1 smallest liar=53653 Liar rate=0.00027631942525559546836142580823431887262
143989 1 1 count=1 smallest liar=51817 Liar rate=0.00027700831024930747922437673130193905817
144157 1 1 count=1 smallest liar=37013 Liar rate=0.00027510316368638239339752407152682255846
.164891 1 1 count=1 smallest liar=79687 Liar rate=0.00024981264051961029228078940794404196852
170969 1 1 count=1 smallest liar=26891 Liar rate=0.00023562676720075400565504241281809613572
178991 1 1 count=2 smallest liar=24103 Liar rate=0.00045620437956204379562043795620437956205
.190651 1 1 count=1 smallest liar=32579 Liar rate=0.00021843599825251201397990388816076889471
194221 1 1 count=1 smallest liar=10627 Liar rate=0.00021159542953872196360558611933982225984
.215209 1 1 count=1 smallest liar=55073 Liar rate=0.00019394879751745539177657098525989138867
.228241 1 1 count=4 smallest liar=6619 Liar rate=0.00073637702503681885125184094256259204713
239149 1 1 count=1 smallest liar=10529 Liar rate=0.00017479461632581716483132319524558643594
.259487 1 1 count=1 smallest liar=68659 Liar rate=0.00016556291390728476821192052980132450331
259505 1 1 count=2 smallest liar=89867 Liar rate=0.00032578595862518325460172666558071347125
and
n Least liar c<5000
496145 1 1 count=1 smallest liar=2017
604421 1 1 count=1 smallest liar=2273
My current Pari/gp user-defined functions plus command line 2/24/2024 10:30 am:
? for(Y=2200000,10^8,N=1+2*Y;if(0==(Y%100000), print("Y=",Y)); galoisinit2(N,1,1);count=0; if(!issquare(n), candidates=0; for(Z=3,2100, t3=(kronecker(Z,N)==
-1)&&(isprime(Z)); if(t3, candidates = candidates+1; c=Z;C=Mod(c,n);aaa=Frobeniustest(); t= ((lift(aaa[1])-A)==(0))&&((lift(aaa[2])+B)==n); if(t&&(!isprime(
n)), count=count+1; if(count==1, liar1=c) ););); if(count>0, print(n," ",A," ",B," count=",count," smallest liar=",liar1," Liar rate=",0.0+count/candidate
s);););)
Frobeniustest =
()->l=length(bin);product=identity;for(X=1,l,product=square(product,C);if(bin[X],product=mulbase(product,C)));return(product)
findc =
()->s=1+random(n-3);while(kronecker(s,n)>-1,s=1+random(n-3));return(s)
galoisinit2 =
(N,a,b)->n=N;identity=vector(2);identity[1]=Mod(1,n);identity[2]=Mod(0,n);base=vector(2);base[1]=Mod(a,n);base[2]=Mod(b,n);bin=digits(n,2);A=a;B=b
galoisproduct =
(X,Y,C)->v=vector(2);v[1]=X[1]*Y[1]+C*X[2]*Y[2];v[2]=X[1]*Y[2]+X[2]*Y[1];return(v)
mulbase =
(X,C)->galoisproduct(X,base,C)
square =
(X,C)->galoisproduct(X,X,C)