NFS and smooth norm MOD N ?

[bonju]

Is it possible the NFS to take advantage of ("pseudo") relations in which the
norm is smooth *MOD N*?

So if one is looking for smooth f(x,y)=sum(a[i]*x^i*y^(d-i)),
does smooth
f(x,y) mod n
and
x-m*y mod n help?

Publications?

Thanks.

[R.D. Silverman]

Originally Posted by bonju

Is it possible the NFS to take advantage of ("pseudo") relations in which the
norm is smooth *MOD N*?

So if one is looking for smooth f(x,y)=sum(a[i]*x^i*y^(d-i)),
does smooth
f(x,y) mod n
and
x-m*y mod n help?

Publications?

Thanks.

What you ask is meaningless. The norms are substantially smaller than N.
If the norm is smooth, then it is smooth mod N and vice-versa.

[bonju]

Originally Posted by R.D. Silverman

What you ask is meaningless. The norms are substantially smaller than N.
If the norm is smooth, then it is smooth mod N and vice-versa.

I know they are smaller than N.

Is of any use this in some kind of modification of nfs:
1. f(x,y) > N
2. f(x,y) mod N is smooth
3. x-m*y mod N is smooth
(3 seems clear).

[R.D. Silverman]

Originally Posted by bonju

I know they are smaller than N.

Is of any use this in some kind of modification of nfs:
1. f(x,y) > N
2. f(x,y) mod N is smooth
3. x-m*y mod N is smooth
(3 seems clear).

Explain:

How you get both norms to be simultaneously small mod N when
f(x,y) is large. And if they are not small, then trying to factor them
will be fruitless.

Indeed, suppose d is the degree. then m ~ N^(1/d). (or N^(1/(d+1))
We want f(x,y) > N, implying that x,y are about equal to m, or slightly
larger. Thus, even if f(x,y) mod N is small, we have x-my ~ N^(2/d).

This value of x-my mod N is still much less than N, but it is much LARGER
than we obtain currently. To get x-my mod N to be small, you would need
y ~ N/m. Now f(x,y) mod N is VERY UNLIKELY to be small enough to be
smooth. Indeed. Set y0 ~ N/m, and look at d f(x,y)/d y near y0.
You will see that a small change in y will make a very large change in the
norm.

In short, the idea is unlikely to be useful.

[bonju]

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.

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

[R.D. Silverman]

Originally Posted by bonju

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

"I believe that squares in the norm do not diminish smoothness (modulo algebraic stuff and terminology)."


Non-sequitur. Where, in any of my prior response did I discuss "squares
in the norm". And "diminish smoothness" is meaningless gibberish.

We are discussing the SIZE of the norms taken mod N. For your "scheme"
to work, BOTH f(x,y) and x-m*y taken mod N need to be sufficiently
small so there is a reasonable change that they will be smooth. Furthermore,
to have any advantage over existing methods, the norms would need to
be *smaller* than what we can obtain currently.

I showed that for f(x,y) mod N to be small, that x,y needed to be near
or slightly larger than N^1/d. However, when this happens x - b*y
becomes much larger (near N^2/d instead of N^1/d) than we obtain
currently.

Your discussion of solving quadratics modulo a composite is irrelevant to
what you first asked.

[bonju]

Originally Posted by R.D. Silverman

"\

Non-sequitur. Where, in any of my prior response did I discuss "squares
in the norm". And "diminish smoothness" is meaningless gibberish.

For the sake of the flame, let's call p[k1]^e1*p[k2]^e2*p[ki]^ki*u^2, p[k] - prime in the prime base,
"pseudo smooth".

If you are sieving with quadratic and nfs, will you throw away "pseudo smooth" norms in Z?

When one constructs the final squares mod n, one will have to take in account "u", which is with even exponent, so it doesn't affect solving the matrix.

[bonju]

I may be wrong, but if one finds "pseudo smooth" relation, one may add (the ideal) "u" to the (algebraic) factor base. Since it is with even exponent, it seems that no additional algebraic relation is needed to construct an algebraic square. Since I don't quite understand all the stuff, not all "u"s may be good, but there is chance some "u" are good.

btw, this approach works for the quadratic sieve, but Pollard/Schnorr's method is not applicable in this case.

[R.D. Silverman]

Originally Posted by bonju

For the sake of the flame, let's call p[k1]^e1*p[k2]^e2*p[ki]^ki*u^2, p[k] - prime in the prime base,
"pseudo smooth".

If you are sieving with quadratic and nfs, will you throw away "pseudo smooth" norms in Z?

When one constructs the final squares mod n, one will have to take in account "u", which is with even exponent, so it doesn't affect solving the matrix.

(1) Such norms are extremely rare; They are so extremely rare that they are
not worth worrying about. When a prime in the factor base, other than
the smallest primes (say those less than 10000), divides a norm it
almost always does so to the first power.

(2) Your "pseudo smooth" relation will be found anyway if u is below the large
prime bound. But they are not worth looking for.

[bonju]

Originally Posted by R.D. Silverman

(1) Such norms are extremely rare; They are so extremely rare that they are
not worth worrying about. When a prime in the factor base, other than
the smallest primes (say those less than 10000), divides a norm it
almost always does so to the first power.

(2) Your "pseudo smooth" relation will be found anyway if u is below the large
prime bound. But they are not worth looking for.

Sure they are rare in Z, but they come at very reasonable price in Zn *if they can be used at all*.