- **Factoring**
(*https://www.mersenneforum.org/forumdisplay.php?f=19*)

- - **NFS and smooth norm MOD N ?**
(*https://www.mersenneforum.org/showthread.php?t=4553*)

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

[QUOTE=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.[/QUOTE] 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. |

[QUOTE=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.[/QUOTE] 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). |

[QUOTE=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).[/QUOTE] 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. |

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[/CODE] |

[QUOTE=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 [/QUOTE] "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. |

[QUOTE=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. [/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. |

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

[QUOTE=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.[/QUOTE] (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. |

[QUOTE=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.[/QUOTE] Sure they are rare in Z, but they come at very reasonable price in Zn *if they can be used at all*. |

All times are UTC. The time now is 22:26. |

Powered by vBulletin® Version 3.8.11

Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.