Single Parameter Frobenius test -- 1+1+1+1+2 Selfridges

paulunderwood · 2021-10-13, 19:13

Code:

{
tst(n,a)=kronecker(a^2-4,n)==-1&&
gcd((a^3-a)*(a+4),n)==1&&
Mod(a-1,n)^(n-1)==1&&
Mod(a,n)^(n-1)==1&&
Mod(a+1,n)^(n-1)==1&&
Mod(a+4,n)^(n-1)==1&&
Mod(Mod(x+2,n),x^2-a*x+1)^(n+1)==2*a+5;}

I am in the early stages of testing this test. Can you beat me to a counterexample?

paulunderwood · 2021-10-14, 01:56

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

paulunderwood · 2021-10-14, 22:03

Semi-primes are being stubborn, but when I feed in Carmichael numbers counterexamples abound such as [n,a]=[19384289, 8494896]

This is yet another test that shows that X Frobenius tests with X parameters can be fooled.

2021-10-13, 19:13	#1
paulunderwood Sep 2002 Database er0rr 2×29×71 Posts	Single Parameter Frobenius test -- 1+1+1+1+2 Selfridges Code: { tst(n,a)=kronecker(a^2-4,n)==-1&& gcd((a^3-a)(a+4),n)==1&& Mod(a-1,n)^(n-1)==1&& Mod(a,n)^(n-1)==1&& Mod(a+1,n)^(n-1)==1&& Mod(a+4,n)^(n-1)==1&& Mod(Mod(x+2,n),x^2-ax+1)^(n+1)==2*a+5;} I am in the early stages of testing this test. Can you beat me to a counterexample?

2021-10-14, 01:56	#2
paulunderwood Sep 2002 Database er0rr 2·29·71 Posts	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-ax+1)^(n+1)==2a+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

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
I wonder if there is a single precision version LL-test for Nvidia GPU computing	Neutron3529	GPU Computing	45	2022-04-18 19:41
was: a deterministic test for primes p=1 or p=7 mod 8 with 2 Selfridges	bhelmes	Miscellaneous Math	0	2021-06-07 00:43
a d̶e̶t̶e̶r̶m̶i̶n̶i̶s̶t̶i̶c̶ test for primes p=1 or p=7 mod 8 with 2 (??) Selfridges	bhelmes	Miscellaneous Math	35	2021-04-10 17:01
1+1 Selfridges PRP test	paulunderwood	Miscellaneous Math	21	2020-11-20 13:16
New program to test a single factor	dsouza123	Programming	6	2004-01-13 03:53

2021-10-14, 22:03	#3
paulunderwood Sep 2002 Database er0rr 1016₁₆ Posts	Semi-primes are being stubborn, but when I feed in Carmichael numbers counterexamples abound such as [n,a]=[19384289, 8494896] This is yet another test that shows that X Frobenius tests with X parameters can be fooled.