mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2005-08-25, 08:16   #1
bonju
 
Aug 2005

68 Posts
Default 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.
bonju is offline   Reply With Quote
Old 2005-08-25, 12:12   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

746010 Posts
Thumbs up

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.
R.D. Silverman is offline   Reply With Quote
Old 2005-08-25, 13:34   #3
bonju
 
Aug 2005

1102 Posts
Default

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).
bonju is offline   Reply With Quote
Old 2005-08-25, 14:52   #4
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

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.
R.D. Silverman is offline   Reply With Quote
Old 2005-08-25, 16:05   #5
bonju
 
Aug 2005

2×3 Posts
Default

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
bonju is offline   Reply With Quote
Old 2005-08-25, 17:20   #6
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

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.
R.D. Silverman is offline   Reply With Quote
Old 2005-08-26, 06:10   #7
bonju
 
Aug 2005

2×3 Posts
Default

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.
bonju is offline   Reply With Quote
Old 2005-08-26, 06:45   #8
bonju
 
Aug 2005

610 Posts
Default

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.
bonju is offline   Reply With Quote
Old 2005-08-26, 12:13   #9
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

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.
R.D. Silverman is offline   Reply With Quote
Old 2005-08-26, 13:29   #10
bonju
 
Aug 2005

2·3 Posts
Default

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*.
bonju is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
norm vs size chris2be8 Msieve 1 2015-09-13 02:24
NFS: Sieving the norm over ideals vs. integers paul0 Factoring 2 2015-01-19 11:52
Not smooth enough numbers Sam Kennedy Factoring 5 2012-11-10 07:54
Smooth Numbers Yamato Math 1 2005-12-11 11:09
Smooth? Xyzzy Factoring 5 2004-11-04 18:20

All times are UTC. The time now is 03:01.

Thu Apr 22 03:01:02 UTC 2021 up 13 days, 21:41, 0 users, load averages: 2.32, 1.91, 2.04

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.