View Single Post
Old 2021-10-14, 01:56   #2
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2×11×191 Posts
Default

I can save a few Selfridges by using the weaker form of Fermat's Little Theorem:

Code:
{
tst(n,a)=kronecker(a^2-4,n)==-1&&
gcd(a+4,n)==1&&
Mod(a-1,n)^n==a-1&&
Mod(a,n)^n==a&&
Mod(a+1,n)^n==a+1&&
Mod(a+4,n)^(n-1)==1&&
Mod(Mod(x+2,n),x^2-a*x+1)^(n+1)==2*a+5;
}
Now "a" can be zero. So that the test is a base 4 Fermat test plus the Frobenius. The latter has been tested to 2^50.

"a" can also be +/-1 which means bases 2 and 5, bases 2 and 3 respectfully plus the Frobenius. The Frobenius has also been tested up to 2^50 (excluding the cases for the previous paragraph).

If "a" is +/-3 then a-1 and a+1 are the same Fermat PRP test, resuting in bases 2, 3 and 1 or 7 Fermat PRPs plus Frobenius.

In summary:
a=0 => 1+2 Selfridges
a=-1 => 1+1+2 Selfridges
a=1 => 1+1+2 Selfridges
a=-3 => 1+1+2 Selfridges
a=3 => 1+1+1+2 Selfridges
a=4 => 1+1+1+2 Selfridges
a=-5 => 1+1+1+2 Selfridges
otherwise => 1+1+1+1+2 Selfrdges


Last fiddled with by paulunderwood on 2021-10-14 at 07:34
paulunderwood is offline   Reply With Quote