View Single Post
 2021-09-18, 08:37 #2 paulunderwood     Sep 2002 Database er0rr 25×3×43 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