20050825, 08:16  #1 
Aug 2005
6_{8} 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^(di)), does smooth f(x,y) mod n and xm*y mod n help? Publications? Thanks. 
20050825, 12:12  #2  
"Bob Silverman"
Nov 2003
North of Boston
2·3^{3}·139 Posts 
Quote:
If the norm is smooth, then it is smooth mod N and viceversa. 

20050825, 13:34  #3  
Aug 2005
2·3 Posts 
Quote:
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. xm*y mod N is smooth (3 seems clear). 

20050825, 14:52  #4  
"Bob Silverman"
Nov 2003
North of Boston
16522_{8} Posts 
Quote:
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 xmy ~ N^(2/d). This value of xmy mod N is still much less than N, but it is much LARGER than we obtain currently. To get xmy 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. 

20050825, 16:05  #5 
Aug 2005
6_{10} 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 xm*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/(t1m),n); x1:=mods(t1*y1,n); print("x1,y1",x1,y1,v,mods(a*x1^2+b*x1*y1+c*y1^2pr1*v^2*y1^2,n),mods(x1m*y1,n)); tt:=solve6(a,0,pr1,b,0,c,n); t1:=xv6; v:=yv6; y1:=mods(pr1/(t1m),n); x1:=mods(t1*y1,n); print("x1,y1",x1,y1,v,mods(a*x1^2+b*x1*y1+c*y1^2pr1*v^2*y1^2,n),mods(x1m*y1,n)); "x1,y1", 99168165403846951535355917433280525834, 81674543910310402924453243016563547418, 126608952858972281385043804924420254710, 0, 3 "x1,y1", 61434838914297589375543999423642115992, 141995700967008953934148883661176819866, 160514624508308669463908190969310392653, 0, 3 
20050825, 17:20  #6  
"Bob Silverman"
Nov 2003
North of Boston
2·3^{3}·139 Posts 
Quote:
Nonsequitur. 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 xm*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. 

20050826, 06:10  #7  
Aug 2005
110_{2} Posts 
Quote:
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. 

20050826, 06:45  #8 
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. 
20050826, 12:13  #9  
"Bob Silverman"
Nov 2003
North of Boston
2·3^{3}·139 Posts 
Quote:
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. 

20050826, 13:29  #10  
Aug 2005
2×3 Posts 
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
norm vs size  chris2be8  Msieve  1  20150913 02:24 
NFS: Sieving the norm over ideals vs. integers  paul0  Factoring  2  20150119 11:52 
Not smooth enough numbers  Sam Kennedy  Factoring  5  20121110 07:54 
Smooth Numbers  Yamato  Math  1  20051211 11:09 
Smooth?  Xyzzy  Factoring  5  20041104 18:20 