View Single Post
Old 2013-10-18, 01:33   #27
paulunderwood's Avatar
Sep 2002
Database er0rr

22×3×7×47 Posts

The modular reduction is done over "n" and "L^2+1". Here is a worked example for n=11 where L^2==-1 (mod 11, L^2+1)

This will work for all prime n==3 (mod 4), but is not proven that all composites will fail. Wagstaff are 3 (mod 4)

To cover all n, I take minimal x>=0 such that jacobiSymbol(x^2-4,n)==-1, and check:

(L+2)^(n+1)==5+2*x (mod n, L^2-x*L+1)
This is the basis of my JavaScript program, which has the running time of 2 Miller-Rabin rounds. It is explained in my pre-print "Quadratic Composite Tests" where I used \lambda instead of "L". The general "minimal x" method is good for n < 10^13 -- I am currently testing n < 7*10^13.

Last fiddled with by paulunderwood on 2013-10-18 at 01:47
paulunderwood is online now   Reply With Quote