View Single Post
Old 2022-09-23, 21:43   #12
paulunderwood's Avatar
Sep 2002
Database er0rr

2·3·52·29 Posts

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