Thread: NFS and smooth norm MOD N ? View Single Post
 2005-08-25, 16:05 #5 bonju   Aug 2005 2·3 Posts I believe that squares in the norm do not diminish smoothness (modulo algebraic stuff and terminology). Schnorr and Pollard gave efficient solution to bivariate quadratics modulo composite. solve a*t^2+b*t+c=3*v^2 for t,v let t=x/y. solve x-m*y=3 Below are two relations mod F7 - the prime base consists of only "3" and squares. Code: n:=2^(2^7)+1; a:=1;b:=3; m:=mods(-1/42,n); c:= -mods(a*m^2+b*m,n); print("0=",mods(a*m^2+b*m+c,n)); pr1:=3; tt:=solve6(a,0,-pr1,b,0,c,n); // Schnorr/Pollard x^2+k*y^2=m mod n t1:=xv6; v:=yv6; y1:=mods(pr1/(t1-m),n); x1:=mods(t1*y1,n); print("x1,y1",x1,y1,v,mods(a*x1^2+b*x1*y1+c*y1^2-pr1*v^2*y1^2,n),mods(x1-m*y1,n)); tt:=solve6(a,0,-pr1,b,0,c,n); t1:=xv6; v:=yv6; y1:=mods(pr1/(t1-m),n); x1:=mods(t1*y1,n); print("x1,y1",x1,y1,v,mods(a*x1^2+b*x1*y1+c*y1^2-pr1*v^2*y1^2,n),mods(x1-m*y1,n)); "x1,y1", 99168165403846951535355917433280525834, -81674543910310402924453243016563547418, 126608952858972281385043804924420254710, 0, 3 "x1,y1", -61434838914297589375543999423642115992, -141995700967008953934148883661176819866, 160514624508308669463908190969310392653, 0, 3