mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2021-09-18, 04:44   #1
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

F5E16 Posts
Talking 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
paulunderwood is offline   Reply With Quote
Old 2021-09-18, 08:37   #2
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2×7×281 Posts
Default

[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
paulunderwood is offline   Reply With Quote
Old 2021-09-18, 14:54   #3
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2·7·281 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
[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 is offline   Reply With Quote
Old 2021-09-19, 00:07   #4
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2×7×281 Posts
Default

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
paulunderwood is offline   Reply With Quote
Old 2021-09-19, 01:05   #5
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2×7×281 Posts
Default

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.

<placeholder for code>
paulunderwood is offline   Reply With Quote
Old 2021-09-19, 06:18   #6
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2×7×281 Posts
Default

[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
paulunderwood is offline   Reply With Quote
Old 2021-09-19, 11:19   #7
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

393410 Posts
Default

[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
paulunderwood is offline   Reply With Quote
Old 2021-09-19, 13:13   #8
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2·7·281 Posts
Default 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
paulunderwood is offline   Reply With Quote
Old 2021-09-29, 17:18   #9
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2×7×281 Posts
Default

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
paulunderwood is offline   Reply With Quote
Old 2021-09-30, 19:23   #10
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2·7·281 Posts
Default

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
paulunderwood is offline   Reply With Quote
Old 2021-09-30, 19:37   #11
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

2·3·293 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
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!)
Nick is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Pythagorean Theorem in Complex Numbers MattcAnderson Miscellaneous Math 2 2020-11-26 00:48
Complex Devaraj numbers devarajkandadai Miscellaneous Math 2 2019-08-27 14:52
biquadratic complex function and possible factorisation bhelmes Math 1 2018-08-08 20:19
Counting ideals during singleton removal fivemack Factoring 5 2007-12-30 11:17
Complex number problem dave_0273 Math 3 2004-11-08 17:15

All times are UTC. The time now is 11:01.


Thu Dec 2 11:01:25 UTC 2021 up 132 days, 5:30, 0 users, load averages: 1.47, 1.49, 1.37

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

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.