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

22×3×7×47 Posts
Default

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)

Code:
(L+2)^2==L^2+4*L+4==4*L+3 
(L+2)^3==(4*L+3)*(L+2)==4*L^2+11*L+6==0*L+6-4==2
(L+2)^6==2^2==4
(L+2)^12==4^2==16==5
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:

Code:
(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