mersenneforum.org - View Single Post - Singleton / Complex / General Tests -- Trinomiality Preservation

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 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).

2021-09-18, 08:37	#2
paulunderwood Sep 2002 Database er0rr 11×383 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+2T)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+2T,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*