3 mod 4 with free parameter

[paulunderwood]

Originally Posted by paulunderwood

Taking the obvious case of r=1, then a Lucas test over y^2-4*y+5 can be transformed into a 5-Euler PRP test and a Euler-Lucas test over f(z)=z^2-6/5*z+1 (for gcd(5,n)==1). This has solutions of f(z)=0 for z=(3+-4*i)/5. The corresponding companion matrix is Z=[3/5,-4/5;1,0], the determinant of which is 4/5. Thus if n is base 2-Fermat PRP there is no need to do the base 5-Euler PRP test -- it is implied since det(Z)^k == det(Z^k) for all k.

My logic is flawed that base 2 Fermat PRPs can replace base 5 Euler PRPs. I mistakenly wrote the wrong matrix Z; It should be [3/5,-4/5;4/5,3/5] (the determinant of which is 1). No more over egging the pudding.

[paulunderwood]

Originally Posted by paulunderwood

I'll call it day after verification to 10^15 of the test:

n==3 mod 4
2^n==2 mod n
(I+2^r)^n==-I+2^r mod n where I is the sqrt(-1)
gcd(r,n-1)==1

FWIW testing has reached 10^15