20210918, 04:44  #1 
Sep 2002
Database er0rr
3,853 Posts 
Singleton / Complex / General Tests  Trinomiality Preservation
Singleton Case  2 Selfridges
If n = 3 mod 4 then (x+2)^(n+1)==5 (mod n, x^2+1), which has been verified to 2^50. Complex Case  Double Test  Two Parameters Only for n==3 mod 4. Let CT(t,n) = gcd(t^3t,n)==1 && Mod(t,n)^(n1)==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)^21,n)==1 && gcd(t^2t2^2,n)==1; This test is 2*(1+3) Selfridges. General Case  Double Test  Three Parameters Let {GT(t,a,n) = kronecker(a^24,n)==1 && gcd((t^3t)*(a+2*t)*(a2*t)*(a*t2)*(a*t+2),n)==1 && Mod(t,n)^(n1)==1 && Mod(Mod(x+t,n),x^2a*x+1)^(n+1)=(t+a)*t+1;} and GT2(t,t2,a,n) = GT(t,a) && GT(t2,a) && gcd((t*t2)^21,n)==1 && gcd(t^2t2^2,n)==1; This is also 2*(1+3) Selfridges, Last fiddled with by paulunderwood on 20210918 at 15:22 
20210918, 08:37  #2 
Sep 2002
Database er0rr
F0D_{16} Posts 
[Side note: gcd(t^3t,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 Fermatt is the same as Fermat(t), Fermat(1/t) and Fermat(1/t). So let T be one of these, Essentially I am taking FermatT 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 trinomiality 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). Last fiddled with by paulunderwood on 20210918 at 19:36 Reason: fixed some typos 
20210918, 14:54  #3 
Sep 2002
Database er0rr
3,853 Posts 
With the counterexample [n, a, t, t2, gcd((t*t2)^21,n), gcd(t^2t2^2,n)] = [5983, 5514, 5512, 5982, 1, 1] it is advisable to take the above GCD giving a nondegenerative Fermat PRPt test. For this "counterexample" gcd(5982^21,5983) = 5983.

20210919, 00:07  #4 
Sep 2002
Database er0rr
F0D_{16} Posts 
If t = 2 and t2 = 3 then the above general test is:
Code:
{ tst_2_3(n,a)= kronecker(a^24,n)==1&& gcd(210,n)==1&& gcd(a+4,n)==1&& gcd(a+6,n)==1&& Mod(2,n)^(n1)==1&& Mod(3,n)^(n1)==1&& Mod(Mod(x+2,n),x^2a*x+1)^(n+1)==5+2*a&& Mod(Mod(x+3,n),x^2a*x+1)^(n+1)==10+3*a; } Dropping a Selfridge can be done by letting t = 2 and t2 = 4 such that the test is Code:
{ tst_2_4(n,a)= kronecker(a^24,n)==1&& gcd(210,n)==1&& gcd(a+4,n)==1&& gcd(a+8,n)==1&& Mod(2,n)^(n1)==1&& Mod(Mod(x+2,n),x^2a*x+1)^(n+1)==5+2*a&& Mod(Mod(x+4,n),x^2a*x+1)^(n+1)==17+4*a; } Last fiddled with by paulunderwood on 20210919 at 00:38 
20210919, 01:05  #5 
Sep 2002
Database er0rr
3,853 Posts 
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 2PRPs n < 2^64  I will have to see how far I can get.
<placeholder for code> 
20210919, 06:18  #6 
Sep 2002
Database er0rr
3,853 Posts 
[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.
Fixing the last practical test, tst_2_4 is now: Code:
{ tst_2_4(n,a)= kronecker(a^24,n)==1&& gcd(210,n)==1&& gcd(a+2,n)==1&&gcd(2*a+1,n)==1&& gcd(a+4,n)==1&&gcd(4*a+1,n)==1&& gcd(a+8,n)==1&&gcd(8*a+1,n)==1&& Mod(2,n)^(n1)==1&& Mod(Mod(x+2,n),x^2a*x+1)^(n+1)==2*a+5&& Mod(Mod(x+4,n),x^2a*x+1)^(n+1)==4*a+17; } Last fiddled with by paulunderwood on 20210919 at 06:41 
20210919, 11:19  #7 
Sep 2002
Database er0rr
3,853 Posts 
[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^3a,n)==1.
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 subtests with one parameter Last fiddled with by paulunderwood on 20210919 at 11:36 
20210919, 13:13  #8 
Sep 2002
Database er0rr
F0D_{16} Posts 
Different tack
Let the matrix A=[a,1;1,0] with kronecker(a^24,n)==1 && gcd(a^3a,n)==1.
The latest test (LT) is A^n+t^n == (A+t)^n mod n. with the following GCDs: gcd(t^3t,n)==1 gcd(a+t,n)==1 gcd(a+2*t,n)==1 gcd(a*t+1,n)==1 Last fiddled with by paulunderwood on 20210919 at 14:30 
20210929, 17:18  #9 
Sep 2002
Database er0rr
111100001101_{2} Posts 
Code:
{tst(n,a)=gcd(a^3a,n)==1&&kronecker(a^24,n)==1&&Mod(Mod(x,n),x^2a*x+1)^(n+1)==1;} {tst1(n,a,t)=gcd(t^21,n)==1&&gcd(a+t,n)==1&&gcd(a*t+1,n)==1&& Mod(t,n)^(n1)==1&&Mod(Mod(x+t,n),x^2a*x+1)^(n+1)==(a+t)*t+1;} {tst2(n,a,t,t2)=gcd(t^2t2^2,n)==1&&gcd((t*t2)^21,n)==1&& tst(n,a)&&tst1(n,a,t)&&tst1(n,a,t2);} 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^3a,n)==1. Otherwise tst will be trivially degenerate into cyclotomy and the counterexample in post #7 would fool it! Last fiddled with by paulunderwood on 20210929 at 20:25 
20210930, 19:23  #10 
Sep 2002
Database er0rr
3,853 Posts 
Consider the semiprime 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*(q1)+1 q = l*(p1)+1 Making the substitution we get: p = k*l*(p1)+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^3a,n)>1? Why are two subtests needed, one for t and one for t2? Last fiddled with by paulunderwood on 20210930 at 19:53 
20210930, 19:37  #11 
Dec 2012
The Netherlands
2^{2}·3·5·29 Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Pythagorean Theorem in Complex Numbers  MattcAnderson  Miscellaneous Math  2  20201126 00:48 
Complex Devaraj numbers  devarajkandadai  Miscellaneous Math  2  20190827 14:52 
biquadratic complex function and possible factorisation  bhelmes  Math  1  20180808 20:19 
Counting ideals during singleton removal  fivemack  Factoring  5  20071230 11:17 
Complex number problem  dave_0273  Math  3  20041108 17:15 