20210410, 15:58  #12 
Sep 2009
2042_{10} 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 
20210411, 05:43  #13 
Aug 2020
167 Posts 
charybdis, thanks, I think I got it now.
I'll also have a look at the readme. 
20210502, 15:49  #14 
Aug 2020
167 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? 
20210502, 19:56  #15  
Apr 2020
263 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:
Quote:
For example, suppose f(x) = x^23. 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:


20210503, 06:41  #16 
Aug 2020
167 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? 
20210503, 13:13  #17 
Apr 2020
107_{16} Posts 
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  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
YAFU 1.34.5 sometimes doesn't output all prime factors it finds  James Heinrich  YAFU  8  20210315 19:43 
Running YAFU via Aliqueit doesn't find yafu.ini  EdH  YAFU  8  20180314 17:22 
Yafu not writing to the output file as requested  BudgieJane  YAFU  3  20160222 15:14 
Bounds explanation  Uncwilly  Lounge  4  20110401 19:15 
explanation on polynomial  firejuggler  Aliquot Sequences  7  20100529 02:46 