mersenneforum.org NFS and smooth norm MOD N ?
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2005-08-25, 08:16 #1 bonju   Aug 2005 610 Posts NFS and smooth norm MOD N ? 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.
2005-08-25, 12:12   #2
R.D. Silverman

Nov 2003

22×5×373 Posts

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

2005-08-25, 13:34   #3
bonju

Aug 2005

2×3 Posts

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

2005-08-25, 14:52   #4
R.D. Silverman

Nov 2003

22×5×373 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.

 2005-08-25, 16:05 #5 bonju   Aug 2005 610 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
2005-08-25, 17:20   #6
R.D. Silverman

Nov 2003

22×5×373 Posts

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

2005-08-26, 06:10   #7
bonju

Aug 2005

2·3 Posts

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

 2005-08-26, 06:45 #8 bonju   Aug 2005 2·3 Posts 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.
2005-08-26, 12:13   #9
R.D. Silverman

Nov 2003

1D2416 Posts

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

2005-08-26, 13:29   #10
bonju

Aug 2005

68 Posts

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

 Similar Threads Thread Thread Starter Forum Replies Last Post chris2be8 Msieve 1 2015-09-13 02:24 paul0 Factoring 2 2015-01-19 11:52 Sam Kennedy Factoring 5 2012-11-10 07:54 Yamato Math 1 2005-12-11 11:09 Xyzzy Factoring 5 2004-11-04 18:20

All times are UTC. The time now is 21:09.

Sat Apr 10 21:09:40 UTC 2021 up 2 days, 15:50, 1 user, load averages: 1.69, 1.64, 1.55