mersenneforum.org Singleton / Complex / General Tests -- Trinomiality Preservation
 Register FAQ Search Today's Posts Mark Forums Read

 2021-09-18, 04:44 #1 paulunderwood     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^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. General Case - Double Test - Three Parameters 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, Last fiddled with by paulunderwood on 2021-09-18 at 15:22
 2021-09-18, 08:37 #2 paulunderwood     Sep 2002 Database er0rr 1111000011012 Posts [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 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 2021-09-18 at 19:36 Reason: fixed some typos
2021-09-18, 14:54   #3
paulunderwood

Sep 2002
Database er0rr

3,853 Posts

Quote:
 Originally Posted by paulunderwood [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.

 2021-09-19, 00:07 #4 paulunderwood     Sep 2002 Database er0rr 3,853 Posts If t = 2 and t2 = 3 then the above general test is: Code: { tst_2_3(n,a)= kronecker(a^2-4,n)==-1&& gcd(210,n)==1&& gcd(a+4,n)==1&& gcd(a+6,n)==1&& Mod(2,n)^(n-1)==1&& Mod(3,n)^(n-1)==1&& Mod(Mod(x+2,n),x^2-a*x+1)^(n+1)==5+2*a&& Mod(Mod(x+3,n),x^2-a*x+1)^(n+1)==10+3*a; } 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 Code: { tst_2_4(n,a)= kronecker(a^2-4,n)==-1&& gcd(210,n)==1&& gcd(a+4,n)==1&& gcd(a+8,n)==1&& Mod(2,n)^(n-1)==1&& Mod(Mod(x+2,n),x^2-a*x+1)^(n+1)==5+2*a&& Mod(Mod(x+4,n),x^2-a*x+1)^(n+1)==17+4*a; } 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. Last fiddled with by paulunderwood on 2021-09-19 at 00:38
 2021-09-19, 01:05 #5 paulunderwood     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 2-PRPs n < 2^64 -- I will have to see how far I can get.
 2021-09-19, 06:18 #6 paulunderwood     Sep 2002 Database er0rr 385310 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^2-4,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)^(n-1)==1&& Mod(Mod(x+2,n),x^2-a*x+1)^(n+1)==2*a+5&& Mod(Mod(x+4,n),x^2-a*x+1)^(n+1)==4*a+17; } Last fiddled with by paulunderwood on 2021-09-19 at 06:41
 2021-09-19, 11:19 #7 paulunderwood     Sep 2002 Database er0rr 385310 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^3-a,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 sub-tests with one parameter Last fiddled with by paulunderwood on 2021-09-19 at 11:36
 2021-09-19, 13:13 #8 paulunderwood     Sep 2002 Database er0rr 3,853 Posts 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:- gcd(t^3-t,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 2021-09-19 at 14:30
 2021-09-29, 17:18 #9 paulunderwood     Sep 2002 Database er0rr 74158 Posts Code: {tst(n,a)=gcd(a^3-a,n)==1&&kronecker(a^2-4,n)==-1&&Mod(Mod(x,n),x^2-a*x+1)^(n+1)==1;} {tst1(n,a,t)=gcd(t^2-1,n)==1&&gcd(a+t,n)==1&&gcd(a*t+1,n)==1&& Mod(t,n)^(n-1)==1&&Mod(Mod(x+t,n),x^2-a*x+1)^(n+1)==(a+t)*t+1;} {tst2(n,a,t,t2)=gcd(t^2-t2^2,n)==1&&gcd((t*t2)^2-1,n)==1&& tst(n,a)&&tst1(n,a,t)&&tst1(n,a,t2);} 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! Last fiddled with by paulunderwood on 2021-09-29 at 20:25
 2021-09-30, 19:23 #10 paulunderwood     Sep 2002 Database er0rr 385310 Posts 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? Last fiddled with by paulunderwood on 2021-09-30 at 19:53
2021-09-30, 19:37   #11
Nick

Dec 2012
The Netherlands

174010 Posts

Quote:
 Originally Posted by paulunderwood Consider the semi-prime n=p*q. From A^n+t^n == (A+t)^n mod n we have ...
For that formula, you need n to be prime not just semi-prime (or I have misunderstood what you mean!)

 Similar Threads Thread Thread Starter Forum Replies Last Post MattcAnderson Miscellaneous Math 2 2020-11-26 00:48 devarajkandadai Miscellaneous Math 2 2019-08-27 14:52 bhelmes Math 1 2018-08-08 20:19 fivemack Factoring 5 2007-12-30 11:17 dave_0273 Math 3 2004-11-08 17:15

All times are UTC. The time now is 04:31.

Mon Oct 18 04:31:22 UTC 2021 up 86 days, 23 hrs, 0 users, load averages: 0.68, 0.96, 1.13