The Frobenius primality test is an algebraic type primality test which perhaps deserves to be better known. Like other tests, it is sure to label genuine prime numbers as prime, but is liable to misidentify some composite numbers as primes. The test was first described by Jon Grantham in a 1998 preprint. There are a number of versions of the Frobenius test, and the one that I’ve been studying is that of Sergey Khashin in his 2013 preprint “Counterexamples for Frobenius primality test” : https://arxiv.org/pdf/1307.7920.pdf . If n is an odd integer that is not a square, and c is coprime to n with Jacobi(n,c)=-1 , then (1+sqrt(c))^n == 1-sqrt(c) (mod n) when n is prime. If a composite odd n which is non-square satifies this congruence, then we say that n is a Frobenius pseudoprime, and that c is a liar. This is analogous to the usage of the terms witness and liar with respect to the Fermat primality test, cf.: https://en.wikipedia.org/wiki/Fermat_primality_test . The theoretical basis for the Frobenius test resides in properties of the Frobenius automorphism over finite fields, in particular the field with n^2 elements where n is a prime, cf.: https://en.wikipedia.org/wiki/Frobenius_endomorphism .
In my experimentation with the Frobenius test, I tried varying the base a+b*sqrt(c), as well as varying the quadratic non-residue c. With a fixed c, I saw that when one base (a,b) is a liar, saying a composite n is prime, then in general a large number of bases are liars, when compared to all possible bases. By contrast, if we fix a=b=1 , and let c vary over the quadratic non-residues between 1 and 1000, then empirically there are very few liars, even in the worst case scenario. For odd composite non-square n between 2000 and 700,000 there are 27 Frobenius pseudoprimes, and all of these have only one value of the quadratic non-residue c such that (1+sqrt(c))^n == 1-sqrt(c) (mod n) .
In my opinion, this provides some evidence that repeated Frobenius tests with a=b=1, and c between 1 and 1000, are more discriminating of composites than repeated Rabin-Miller tests, for which there may be as many as 1/4 liars in the randomly chosen bases , cf.: https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test#Accuracy . For numbers with many Fermat liars, one has the Carmichael numbers, cf.: https://en.wikipedia.org/wiki/Carmichael_number .
The data on the Frobenius tests is provided below, with each line containing one Frobenius pseudoprime. In my first installment or series of test, I neglected the proviso that c be an odd prime (per Khashin’s Frobenius test specification). In a second installment of tests, I include that proviso, and test all qualified odd numbers between 3 and n/2. There are very few pairs of (n, q) where n is an odd number, non-square, and q is an odd prime between 3 and n/2 such that (1+sqrt(c))^n == 1-sqrt(c) (modulo n). The first installment appears under Table A, and the second under Table B.
Table A:
================
n a b lying c's
3827 1 1 count=1
8149 1 1 count=1
8651 1 1 count=1
9809 1 1 count=1
13067 1 1 count=1
27971 1 1 count=1
35459 1 1 count=1
39059 1 1 count=1
43289 1 1 count=1
58829 1 1 count=1
84587 1 1 count=1
117739 1 1 count=1
134579 1 1 count=1
143009 1 1 count=1
155819 1 1 count=1
189419 1 1 count=1
437579 1 1 count=1
469699 1 1 count=1
473891 1 1 count=1
548627 1 1 count=1
597001 1 1 count=1
600059 1 1 count=1
643259 1 1 count=1
656083 1 1 count=1
677379 1 1 count=1
724883 1 1 count=1
783579 1 1 count=1
828827 1 1 count=1
895299 1 1 count=1 Table B
=====
n number of ‘c’ liars
.29539 1 1 count=1 Liar rate=0.0011890606420927467300832342449464922711
.58829 1 1 count=1 Liar rate=0.00062735257214554579673776662484316185696
.71639 1 1 count=1 Liar rate=0.00052383446830801466736511262441068622315
.86221 1 1 count=1 Liar rate=0.00043917435221783047870004391743522178305
94301 1 1 count=2 Liar rate=0.00080808080808080808080808080808080808081
…143009 1 1 count=1 Liar rate=0.00027631942525559546836142580823431887262
143989 1 1 count=1 Liar rate=0.00027700831024930747922437673130193905817
144157 1 1 count=1 Liar rate=0.00027510316368638239339752407152682255846
.164891 1 1 count=1 Liar rate=0.00024981264051961029228078940794404196852
170969 1 1 count=1 Liar rate=0.00023562676720075400565504241281809613572
178991 1 1 count=2 Liar rate=0.00045620437956204379562043795620437956205
.190651 1 1 count=1 Liar rate=0.00021843599825251201397990388816076889471
194221 1 1 count=1 Liar rate=0.00021159542953872196360558611933982225984
.215209 1 1 count=1 Liar rate=0.00019394879751745539177657098525989138867
.
By way of contrast, the liar rates and liar counts for the Fermat test, where one counts bases to which a composite n passes a^(n-1) == 1 (mod n) are much higher. The data and Pari/gp code are provided below:
? upper_limit=15000;for(n=3,upper_limit,if(isprime(n)||n%2==0,next);liar_count=0;for(base=2,n-2,if((lift(Mod(base,n)^(n-1))==1),liar_count++;););liar_rate=0.0+liar_count/(n-2);if(liar_rate>0.25, print("n =",n," Liar rate =",liar_rate)););
ratio of liar bases to n-2:
n =91 Liar rate =0.38202247191011235955056179775280898876
n =133 Liar rate =0.25954198473282442748091603053435114504
n =341 Liar rate =0.28908554572271386430678466076696165192
n =481 Liar rate =0.29645093945720250521920668058455114823
n =561 Liar rate =0.56887298747763864042933810375670840787 // Carmichael number
n =703 Liar rate =0.45934379457917261055634807417974322397
n =1105 Liar rate =0.69446962828649138712601994560290117861
n =1541 Liar rate =0.31319038336582196231319038336582196231
n =1729 Liar rate =0.74927620150550086855819339895773016792
n =1891 Liar rate =0.47538380095288512440444679724722075172
n =2465 Liar rate =0.72675598863174989849776695087291920422
n =2701 Liar rate =0.47943682845498332715820674323823638385
n =2821 Liar rate =0.76551968783256473926924441291238027669
n =4033 Liar rate =0.32101215579260729347556437608533862565
n =5461 Liar rate =0.32276973804726140318739695915002747756
n =6533 Liar rate =0.32368703108252947481243301178992497321
n =6601 Liar rate =0.79981815426579784815881194120321260797
n =8321 Liar rate =0.32479865368433705974275754297391513403
n =8911 Liar rate =0.79986530474800763273094623414524638006
n =10585 Liar rate =0.76178777284323915713880752149674005481
n =11041 Liar rate =0.32593532022828154724159797083069118580
n =11305 Liar rate =0.30558258869326727417499778819782358666
n =12403 Liar rate =0.49044431900653173131199096847028465446
n =13333 Liar rate =0.32660715625234416022803990698372215138
n =13981 Liar rate =0.42907217969811860648115029687388225195
n =14981 Liar rate =0.32699112090259696909005941651645637226For the Khashin Frobenius primality test based on the congruence (1+sqrt(c))^n == 1-sqrt(c) (mod n), as above, I’ve looked at quadratic non-residues c between 1 and n/2 that are liars for a composite n. Most composites fail this test, no matter what the value of c in [1,n/2] is . For all odd n, the largest value of the liar rate is 0.0018 for n=5719, in an exhaustive search now past 137,000 :
? for(Y=20,10^8,N=1+2*Y; galoisinit2(N,1,1);count=0; if(!issquare(n), candidates=0; for(Z=1,N\2, t3=kronecker(Z,N)==-1; 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>0, print(n,” “,A,” “
,B,” count=”,count,” Liar rate=”,0.0+count/candidates);););)
3827 1 1 count=1 Liar rate=0.0011223344556677890011223344556677890011
5719 1 1 count=2 Liar rate=0.0018083182640144665461121157323688969259
8149 1 1 count=3 Liar rate=0.0015306122448979591836734693877551020408
8651 1 1 count=2 Liar rate=0.00097895252080274106705824767498776309349
9017 1 1 count=1 Liar rate=0.00045351473922902494331065759637188208617
9809 1 1 count=4 Liar rate=0.0017361111111111111111111111111111111111
13067 1 1 count=1 Liar rate=0.00031655587211142766698322253877809433365
13817 1 1 count=2 Liar rate=0.00059523809523809523809523809523809523810
14351 1 1 count=1 Liar rate=0.00028935185185185185185185185185185185185
16393 1 1 count=1 Liar rate=0.00026709401709401709401709401709401709402
20591 1 1 count=1 Liar rate=0.00020189783969311528366646476882697355138
22753 1 1 count=1 Liar rate=0.00017921146953405017921146953405017921147
27971 1 1 count=1 Liar rate=0.00014716703458425312729948491537895511405
29539 1 1 count=1 Liar rate=0.00013825521913452232821789022535600718927
32773 1 1 count=2 Liar rate=0.00026455026455026455026455026455026455026
34829 1 1 count=1 Liar rate=0.00011904761904761904761904761904761904762
35333 1 1 count=1 Liar rate=0.00011478420569329660238751147842056932966
35459 1 1 count=1 Liar rate=0.00011594202898550724637681159420289855073
39059 1 1 count=1 Liar rate=0.00010478885046631038457508121135911139055
43289 1 1 count=3 Liar rate=0.00028153153153153153153153153153153153153
43361 1 1 count=1 Liar rate=9.3240093240093240093240093240093240093 E-5
43553 1 1 count=2 Liar rate=0.00018601190476190476190476190476190476191
45109 1 1 count=1 Liar rate=8.9968511021142600089968511021142600090 E-5
58829 1 1 count=7 Liar rate=0.00048209366391184573002754820936639118457
63433 1 1 count=1 Liar rate=6.3564708873633358759216882786676837020 E-5
71639 1 1 count=3 Liar rate=0.00017184098980410127162332455034941001260
84587 1 1 count=1 Liar rate=4.7989250407908628467223341971398406757 E-5
85073 1 1 count=1 Liar rate=4.7348484848484848484848484848484848485 E-5
86221 1 1 count=2 Liar rate=9.3567251461988304093567251461988304094 E-5
86591 1 1 count=1 Liar rate=4.6985857256965653338345158107409669690 E-5
94301 1 1 count=3 Liar rate=0.00012820512820512820512820512820512820513
96029 1 1 count=2 Liar rate=8.4175084175084175084175084175084175084 E-5
98623 1 1 count=1 Liar rate=4.8398025360565288936211402574774949182 E-5
99269 1 1 count=2 Liar rate=8.2182774490466798159105851413543721236 E-5
102311 1 1 count=4 Liar rate=0.00017780938833570412517780938833570412518
102719 1 1 count=6 Liar rate=0.00023890105514632689627712522396973919968
106609 1 1 count=1 Liar rate=4.1152263374485596707818930041152263375 E-5
112529 1 1 count=1 Liar rate=3.5861574323112784651246189707728169267 E-5
114911 1 1 count=1 Liar rate=3.5401989591815060006372358126526710801 E-5
117151 1 1 count=1 Liar rate=3.4487515519381983721892674851703683267 E-5
117739 1 1 count=1 Liar rate=3.4310025389418788169903245728401839017 E-5
122747 1 1 count=1 Liar rate=3.2996766316900943707516663366990034977 E-5
123251 1 1 count=1 Liar rate=3.3276762836511264184220159062926358524 E-5
134413 1 1 count=2 Liar rate=6.0011402166411618207459417289284964143 E-5
134579 1 1 count=1 Liar rate=3.0405302684788227066800449998479734866 E-5
134693 1 1 count=1 Liar rate=3.2212343770132714856332946785208091741 E-5
137461 1 1 count=1 Liar rate=2.9411764705882352941176470588235294118 E-5
I’ve also gathered data on the liar rate for the Miller-Rabin test ( https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test ). The liar rate is the proportion of candidate bases which are strong liars, as defined in the Wikipedia article.
? upper_limit=1000000;for(n=3,upper_limit,if(isprime(n)||n%2==0,next);liar_count=0;for(a=2,n-2,if(millerRabinSingleTest(n,a),liar_count++;););liar_rate=0.0+
liar_count/(n-3);if(liar_rate>0.1,print(“n = “,n,” Liar rate = “,liar_rate);););
n = 91 Liar rate = 0.18181818181818181818181818181818181818
n = 133 Liar rate = 0.12307692307692307692307692307692307692
n = 341 Liar rate = 0.14201183431952662721893491124260355030
n = 451 Liar rate = 0.10714285714285714285714285714285714286
n = 481 Liar rate = 0.10878661087866108786610878661087866109
n = 703 Liar rate = 0.22857142857142857142857142857142857143
n = 1387 Liar rate = 0.11560693641618497109826589595375722543
n = 1541 Liar rate = 0.15604681404421326397919375812743823147
n = 1891 Liar rate = 0.23728813559322033898305084745762711864
n = 2047 Liar rate = 0.11741682974559686888454011741682974560
n = 2701 Liar rate = 0.17939214232765011119347664936990363232
n = 4033 Liar rate = 0.12009925558312655086848635235732009926
n = 5461 Liar rate = 0.16123122022718944668376694759985342616
n = 6533 Liar rate = 0.16171516079632465543644716692189892803
n = 8321 Liar rate = 0.12166386150516951190189949507093051214
n = 8911 Liar rate = 0.19982038616973506960035922766052986080
n = 11041 Liar rate = 0.12212357311107084616778401884399347708
n = 12403 Liar rate = 0.24516129032258064516129032258064516129
n = 13333 Liar rate = 0.16324081020255063765941485371342835709
n = 13747 Liar rate = 0.12223515715948777648428405122235157160
n = 14981 Liar rate = 0.16343971157697957003605287755374549339
n = 18721 Liar rate = 0.16433379634576343626455817929265947217
n = 19951 Liar rate = 0.12271906958091036695408060958492079407
n = 24727 Liar rate = 0.12295745025076848406406730302540042064
n = 29341 Liar rate = 0.13797804894675847024337037289522121481
n = 31621 Liar rate = 0.16446328040989309886773356948573597318
n = 38081 Liar rate = 0.11061505331162350963811124533851567835
n = 38503 Liar rate = 0.24727272727272727272727272727272727273
n = 42127 Liar rate = 0.12344506694520938182508783591301870668
n = 48133 Liar rate = 0.16488676501142738416787866195719925203
n = 49141 Liar rate = 0.18568114290365908258374374211404615573
n = 56033 Liar rate = 0.11343922898447260396216312689630555060
n = 68251 Liar rate = 0.12378384714570390341108896964013597468
n = 79003 Liar rate = 0.24810126582278481012658227848101265823
n = 79381 Liar rate = 0.16528509158708962180956940210133790219
n = 83333 Liar rate = 0.16531861274450978039121564862594503780
n = 88831 Liar rate = 0.24821002386634844868735083532219570406
n = 90751 Liar rate = 0.12394763520959139595362983206241459867
n = 97921 Liar rate = 0.12406299148266917216446414346698257726
n = 104653 Liar rate = 0.18625895843287147634973721930243669374
n = 109061 Liar rate = 0.16548992279337600176053109354655321022
n = 111361 Liar rate = 0.11038272957488460640456904757628549363
n = 133141 Liar rate = 0.16560260782045696946025927984497288528
n = 145351 Liar rate = 0.12417095522470209428406307620331893112
n = 146611 Liar rate = 0.24860853432282003710575139146567717996
n = 188191 Liar rate = 0.24877250409165302782324058919803600655
n = 188501 Liar rate = 0.16577364216065952954408004328958397437
