 mersenneforum.org > YAFU Explanation for yafu output
 Register FAQ Search Today's Posts Mark Forums Read  2021-04-10, 15:58 #12 chris2be8   Sep 2009 111111110112 Posts For NFS a lot of the messages come from msieve (yafu calls it to do the linear algebra). Downloading a current version of msieve and reading the Readme files that come with it will help. The INSTALL and README files shipped with the lattice siever and ggnfs are also worth reading. Chris   2021-04-11, 05:43 #13 bur   Aug 2020 17010 Posts charybdis, thanks, I think I got it now. I'll also have a look at the readme.   2021-05-02, 15:49 #14 bur   Aug 2020 2528 Posts I found good explanations online for quadratic sieve factoring, it can even be used manually for small number which was helpful to understand the mechanism. It seems somewhat similar, but if I understood correctly, then gnfs looks for a,b pairs that satisfy smoothness of the product r of b^d and f(a/b) and also g(a/b) where f and g are polynomials. I guess those polynomials we are searching for at the start? A long list of a,b pairs and the corresponding r,s pairs is the result. I am not sure what happens afterwards. In quadratic sieve the a,b congruences are multiplied using linear algebra to yield perfect squares x^2 == y^2 (mod N). What is the equivalent in gnfs? Are we just doing the same but with r and s? And the square root step in the end would be calculating x and y from x^2 and y^2?   2021-05-02, 19:56   #15
charybdis

Apr 2020

4108 Posts NFS requires much more advanced mathematics - specifically algebraic number theory - to understand fully than QS does, so simple explanations usually include some caveats. I'll try (probably unsuccessfully) to explain as much as I can without delving into the inner workings of the algorithm.

Quote:
 Originally Posted by bur It seems somewhat similar, but if I understood correctly, then gnfs looks for a,b pairs that satisfy smoothness of the product r of b^d and f(a/b) and also g(a/b) where f and g are polynomials. I guess those polynomials we are searching for at the start?
Yes, these are the two polynomials that GNFS searches for at the start. With SNFS the special form of the number allows polynomials to be selected by hand.

Quote:
 A long list of a,b pairs and the corresponding r,s pairs is the result. I am not sure what happens afterwards. In quadratic sieve the a,b congruences are multiplied using linear algebra to yield perfect squares x^2 == y^2 (mod N). What is the equivalent in gnfs? Are we just doing the same but with r and s?
Broadly speaking, we're looking for a set of (a,b) pairs such that the products of the corresponding r and s are both squares. This isn't the whole story: if f has multiple roots modulo p, then we have to treat copies of p as different factors if they correspond to different roots of f mod p.

For example, suppose f(x) = x^2-3. Then (a,b) = (4,1) gives r = 13, and (a,b) = (1,3) gives r = -26. These both have a factor of 13. But (4,1) corresponds to the root 4/1 = 4 mod 13, and (1,3) corresponds to the root 1/3 = 9 mod 13, so we have to treat these two 13s as different when trying to find a product of r values that is a square.

Quote:
 And the square root step in the end would be calculating x and y from x^2 and y^2?
Kind of. When we finish the linear algebra, we have products of r and s that are both squares, but why would they be the same mod N? The products actually represent square elements of number fields, and we need to take the square root in the relevant number fields before converting to mod N. The choice of polynomials ensures that after this conversion the resulting x and y will have x^2 == y^2 mod N. In practice, one of the number fields is just the rational numbers, but the other one is not so convenient to work with, and finding the square root is time-consuming.   2021-05-03, 06:41 #16 bur   Aug 2020 AA16 Posts Thanks for the explanation. My main problem is probably that I don't know anything about the concept of "number fields", I'll try and look it up. Simplified, could it be said that NFS is still coming from the "difference of squares" factorization but with a lot of variations that make it faster than QS?   2021-05-03, 13:13   #17
charybdis

Apr 2020

23×3×11 Posts Quote:
 Originally Posted by bur Simplified, could it be said that NFS is still coming from the "difference of squares" factorization but with a lot of variations that make it faster than QS?
In the sense that we find x and y such that x^2 == y^2 mod N, yes. QS, CFRAC and Dixon's algorithm all do this by finding a product of squares that is equal to a (hopefully different) square mod N. NFS does this in a different way.   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post James Heinrich YAFU 8 2021-03-15 19:43 EdH YAFU 8 2018-03-14 17:22 BudgieJane YAFU 3 2016-02-22 15:14 Uncwilly Lounge 4 2011-04-01 19:15 firejuggler Aliquot Sequences 7 2010-05-29 02:46

All times are UTC. The time now is 04:10.

Sun May 16 04:10:46 UTC 2021 up 37 days, 22:51, 0 users, load averages: 1.15, 1.66, 1.59