View Single Post
Old 2005-08-25, 16:05   #5
bonju
 
Aug 2005

2·3 Posts
Default

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
bonju is offline   Reply With Quote