24810Re: mod quartic composite tests
- Jan 9, 2013--- In firstname.lastname@example.org,
Paul Underwood wrote:
> (L+2)^n==-L^3+(x^2-2)*L+2 (mod n, (L^2-x*L+1)*(L^2+x*L+1))I can do it in 6 selfridges for generic x.
> This test is (1)+(1)+(2)+(2)+9 selfridge for small x
Where do your "9" selfridges come from, Paul?
With kronecker(x^4-2,n) = -1 and prime n, we have
(L+a)^n = a+x-L mod(n, L^2-L*x+1) ... 
(L+a)^n = a-x-L mod(n, L^2+L*x+1) ... 
and the two Frobenius tests cost 3+3=6 selfridges, generically.
Now let f(x,L) = -L^3+(x^2-2)*L and observe
from simple algebra (no modularity involved) that
f(x,L) + a = (a+x-L) - (L+x)*(L^2-x*L+1)
f(x,L) + a = (a-x-L) - (L-x)*(L^2+x*L+1)
Hence  and  imply that
(L+a)^n = f(x,L) + a mod(n, (L^2-x*L+1)*(L^2+x*L+1)) ... 
and Paul has set a = 2 in .
Since this is a double-Frobenius test, the gremlins
reserve the right to choose /both/ parameters (a,x) in .
- << Previous post in topic Next post in topic >>