Thread: NFS and smooth norm MOD N ? View Single Post
2005-08-25, 14:52   #4
R.D. Silverman

Nov 2003

746010 Posts

Quote:
 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.