mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > YAFU

Reply
 
Thread Tools
Old 2021-04-10, 15:58   #12
chris2be8
 
chris2be8's Avatar
 
Sep 2009

111111110112 Posts
Default

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
chris2be8 is offline   Reply With Quote
Old 2021-04-11, 05:43   #13
bur
 
Aug 2020

17010 Posts
Default

charybdis, thanks, I think I got it now.


I'll also have a look at the readme.
bur is offline   Reply With Quote
Old 2021-05-02, 15:49   #14
bur
 
Aug 2020

2528 Posts
Default

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?
bur is offline   Reply With Quote
Old 2021-05-02, 19:56   #15
charybdis
 
charybdis's Avatar
 
Apr 2020

4108 Posts
Default

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 View Post
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.
charybdis is offline   Reply With Quote
Old 2021-05-03, 06:41   #16
bur
 
Aug 2020

AA16 Posts
Default

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?
bur is offline   Reply With Quote
Old 2021-05-03, 13:13   #17
charybdis
 
charybdis's Avatar
 
Apr 2020

23×3×11 Posts
Default

Quote:
Originally Posted by bur View Post
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.
charybdis is offline   Reply With Quote
Reply

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 2021-03-15 19:43
Running YAFU via Aliqueit doesn't find yafu.ini EdH YAFU 8 2018-03-14 17:22
Yafu not writing to the output file as requested BudgieJane YAFU 3 2016-02-22 15:14
Bounds explanation Uncwilly Lounge 4 2011-04-01 19:15
explanation on polynomial 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

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.