View Single Post
Old 2005-08-25, 14:52   #4
R.D. Silverman
R.D. Silverman's Avatar
Nov 2003

22·5·373 Posts

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).

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

In short, the idea is unlikely to be useful.
R.D. Silverman is offline   Reply With Quote