View Single Post
Old 2021-09-18, 08:37   #2
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

393410 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