Thread: New Wagstaff PRP exponents View Single Post
 2013-10-18, 01:33 #27 paulunderwood     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) 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