-   Miscellaneous Math (
-   -   Singleton / Complex / General Tests -- Trinomiality Preservation (

paulunderwood 2021-09-18 04:44

Singleton / Complex / General Tests -- Trinomiality Preservation
[U]Singleton Case - 2 Selfridges[/U]
If n = 3 mod 4 then (x+2)^(n+1)==5 (mod n, x^2+1), which has been verified to 2^50.

[U]Complex Case - Double Test - Two Parameters[/U]
Only for n==3 mod 4.
Let CT(t,n) = gcd(t^3-t,n)==1 && Mod(t,n)^(n-1)==1 && Mod(Mod(x+t),x^2+1)^(n+1)==t^2+1;
and CT2(t,t2,n) = CT(t) && CT(t2,n) && gcd((t*t2)^2-1,n)==1 && gcd(t^2-t2^2,n)==1;
This test is 2*(1+3) Selfridges.

[U]General Case - Double Test - Three Parameters[/U]
Let {GT(t,a,n) = kronecker(a^2-4,n)==1 && gcd((t^3-t)*(a+2*t)*(a-2*t)*(a*t-2)*(a*t+2),n)==1 &&
Mod(t,n)^(n-1)==1 && Mod(Mod(x+t,n),x^2-a*x+1)^(n+1)=(t+a)*t+1;}
and GT2(t,t2,a,n) = GT(t,a) && GT(t2,a) && gcd((t*t2)^2-1,n)==1 && gcd(t^2-t2^2,n)==1;
This is also 2*(1+3) Selfridges,

paulunderwood 2021-09-18 08:37

[Side note: gcd(t^3-t,n)==1 might not be required in the above tests.]

I'll try to convey my thinking here.

Let A be the matrix [a,-1;1,0] and its characteristic function be X(A).

Note that the probable prime tests Fermat-t is the same as Fermat-(-t), Fermat(1/t) and Fermat-(-1/t). So let T be one of these,

Essentially I am taking Fermat-T and testing (A+T)^(n+1) over X(A) is the determinant of (A+T) i.e 1+(a+T)*T.

The later is the same as as taking a n+1 power x over x^2-(a+2*T)*x+(a+T)*T+1. It is important to preserve [I]trinomiality[/I] of this and not let it degenerate into an Euler PRP test of the determinant. So I take gcd(a+2*T,n)==1 (for all cases of T).

Finally, I observe that two such Fermat+Frobenius tests and the required GCDs seems sufficient (not to fool).


paulunderwood 2021-09-18 14:54

[QUOTE=paulunderwood;588096][Side note: gcd(t^3-t,n)==1 might not be required in the above tests.]


With the counterexample [n, a, t, t2, gcd((t*t2)^2-1,n), gcd(t^2-t2^2,n)] = [5983, 5514, 5512, 5982, 1, 1] it is advisable to take the above GCD giving a non-degenerative Fermat PRP-t test. For this "counterexample" gcd(5982^2-1,5983) = 5983.

paulunderwood 2021-09-19 00:07

If t = 2 and t2 = 3 then the above general test is:


I am testing the "general test" every way I can think of. Can you find a counterexample?


Dropping a Selfridge can be done by letting t = 2 and t2 = 4 such that the test is


Furthermore, the Frobenius tests can each be done in 2 Selfridges (by my published method), making the tst_2_4(n,a) cost 1+2+2 Selfridges.

paulunderwood 2021-09-19 01:05

For the 1+2+2 Selfridges tst_2_4(n,a) it will be nice to write some GMP code against Feitsma's list of Fermat 2-PRPs n < 2^64 -- I will have to see how far I can get. :smile:

<placeholder for code>

paulunderwood 2021-09-19 06:18

[n, a, t, t2]=[8473, 2043, 140, 1252] gives a counterexample, but fear not, I have added gcd(a+t,n)==1 (to GT()) to stop degeneration of the determinant t*(t+a)+1 into unity, and gcd(t*a+1,n)==1 for a possibility of T. :whistle:

Fixing the last practical test, tst_2_4 is now:


paulunderwood 2021-09-19 11:19

[n, t, t2]=[415681338623, 2106331569, 9028142873] is a counterexample to the complex test (CT above). Hmm. I will try to find one for which gcd(a^3-a,n)==1. :grin:

Well that did not take long to fool: [n, a, t, t2]=[166827943, 3, 26368204, 65867518].

Next up, just test [n,a,2,4]. This is however 2 sub-tests with one parameter :ermm:

paulunderwood 2021-09-19 13:13

Different tack
Let the matrix A=[a,-1;1,0] with kronecker(a^2-4,n)==-1 && gcd(a^3-a,n)==1.

The latest test (LT) is A^n+t^n == (A+t)^n mod n.

with the following GCDs:-

paulunderwood 2021-09-29 17:18




This tst2 looks pretty sound. Can any one fool it?

It is based on A^n+t^n == (A+t)^n mod n and A^n+t2^n == (A+t2)^n mod n with the incumbent GCDs

Edit: I added in gcd(a^3-a,n)==1. Otherwise tst will be trivially degenerate into cyclotomy and the counterexample in post #7 would fool it!

paulunderwood 2021-09-30 19:23

Consider the semi-prime n=p*q. From A^n+t^n == (A+t)^n mod n we have both:

A^p+t^p == (A+t)^p mod q
A^q+t^q == (A+t)^q mod p

So in trying to construct a counterexample we might do:

p = k*(q-1)+1
q = l*(p-1)+1

Making the substitution we get:

p = k*l*(p-1)+1 which implies k*l == 1 which means p = q.

If this construction method does not work, can it be extended to more prime factors?

Why do I get the counterexample [n, a, t, t2]=[415681338623, 0, 2106331569, 9028142873] when gcd(a^3-a,n)>1?

Why are two sub-tests needed, one for t and one for t2?

Nick 2021-09-30 19:37

[QUOTE=paulunderwood;589091]Consider the semi-prime n=p*q. From A^n+t^n == (A+t)^n mod n we have ...[/QUOTE]
For that formula, you need n to be prime not just semi-prime (or I have misunderstood what you mean!)

paulunderwood 2021-09-30 20:04





Testing A^n+t^n == (A+t)^n mod n and A^n+t2^n == (A+t2)^n mod n with GCDs.

[QUOTE=Nick;589094]For that formula, you need n to be prime not just semi-prime (or I have misunderstood what you mean!)[/QUOTE]

It works for n prime, always (with kronecker(a^2-4,n)==-1). I am firstly trying to construct a semi-prime counterexample.

paulunderwood 2021-10-01 11:32

[QUOTE=paulunderwood;589091]Consider the semi-prime n=p*q. From A^n+t^n == (A+t)^n mod n we have both:

A^p+t^p == (A+t)^p mod q
A^q+t^q == (A+t)^q mod p


This is wrong. If kronecker(a^2-4,p)==-1 then

1/A^q + t^q == | (A + t)^q | / (A + t)^q mod p (I think).

I can't make nor tails of it. Semi-prime testing has reached p = 2521 and q = 2*k*(p-1)+1 for k=4..14. It is slow going.


[n, a, t, t2]=[79786523, 20692263, 4163322, 8326644] is a counterexample. Once again the primes win!

paulunderwood 2021-10-06 15:57

1 Attachment(s)
David Broadhurst gave me a file (attached to this message) of 100 small frauds that fool tst2, which took 42 seconds to produce.

He also found this 111 digit counterexample:


if(tst2(n,a,t,t2),print("\\\\ fooled at "#Str(n)" digits"));}
\\ fooled at 111 digits

All times are UTC. The time now is 02:12.

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.