20210405, 07:13  #1 
Aug 2020
2×5×17 Posts 
Explanation for yafu output
There are some things I wonder about, is there a simple explanation what's going on? I know this isn't strictly yafu, but I hope this is still the most fitting subforum.
Feel free to explain any single line of the output I pasted, when waiting for a factorization to finish it's interesting to know what is going on. :) My knowledge in math is limited though.

20210405, 07:42  #2 
Romulan Interpreter
Jun 2011
Thailand
13×727 Posts 
Generally, you have to solve a system with m equations, with n variables. As long as you have independent equations, and more equations than variables, you can solve the system. All the "sieving" phase is to find those equations. Then the linear algebra will solve the system.
Say you want to find out x, y, and z, and you ask your friends and one tells you that 2x+3y=7, you still don't know them. Another friend will tell you than x+y+z=6, you still don't know them. Now you ask a third friend and he tells you that 2x+2x+2z=12, you kick his ass, because this is not useful to you, it is not independent from the second, and then he says sorry and tells you 2yz+w=5. Now, you don't need w, but you can't get more from this guy, you already pulled his fingernails and squeezed his nose.. but you continue asking, ans somebody else tells you that 5xw=1. Now you have two "partial" relations which you can add together to get 5x+2yz=6, and you can solve the system, and get x, y, and z. Factoring is the same, but your variables are small primes, the coefficients in front are powers of these primes, and the addition is multiplication. Now you know... With SIQS the things are simple, you start with a number of "variables" (primes) that is dependent of the size of the number you want to factor, larger number, more variables, and you kinda know "exactly" how many equations you will need. With NFS the waters are murky... Five bucks for who explains it simpler.. (and don't kick me hard if the system is not solvable, I made it up as I was writing it, I think it is ok...) Last fiddled with by LaurV on 20210405 at 07:45 
20210405, 12:51  #3 
Feb 2017
Nowhere
10700_{8} Posts 
If memory serves, for quadratic sieves the result you need here is that a homogeneous system of linear equations with more equations than variables automatically contains a linear dependency. (A system is homogeneous when there are no constant terms. A homogeneous system is thus automatically consistent, since setting all the variables equal to 0 gives a solution.
The application to factoring the composite number N is to find a nontrivial solution to x^2 == y^2 (mod N) (i.e. where neither x  y nor x + y is divisible by N). As I recall, the basic idea is to select a bound B, and then look for squares (mod N) whose prime factors are all less than B (i.e are "Bsmooth"). Say there are m such primes, p_{1} to p_{m}. Say we find x^2 == p_{1}^e1*...* p_{m}^em. Since we're only interested in squareness, we can reduce the exponents (mod 2), so the e's are all either 0 or 1. Multiplying xvalues corresponds to adding the exponents (which can then be reduced mod 2). So we can replace our xvalues by rows of m 0's and 1's (mod 2). If we have k such xvalues, we can form a k by m matrix of 0's and 1's (mod 2). Adding rows corresponds to multiplying xvalues. The idea is that if k > m (and there are no duplicate rows) there will automatically be a nontrivial dependency among the rows, which means a nontrivial relation x^2 == y^2 (mod N). Luckily, the integers mod 2 obey the same rules of addition and multiplication as the rational or real numbers (a "field") so dependencies can be found by doing Gaussian elimination on the matrix (linear algebra). The success of the method depends on selecting B appropriately, and finding enough "Bsmooth" squares (mod N). There are ways to fiddle the Bsmoothness requirement slightly, but it's been ages since I looked at this closely. I am not sufficiently familiar with number field sieves (using polynomials of degree greater than 2) to explain much. 
20210405, 15:51  #4  
Apr 2020
2^{3}×3×11 Posts 
Quote:
I don't have much more to say about QS; LaurV and Dr Sardonicus have done a pretty good job of explaining the basics. The one thing I'd add to connect their two posts is that we can allow x^2 mod N to have one or two factors ("large primes") a bit larger than the smoothness bound B; these are the "partial relations" that LaurV refers to, and they can be combined into full relations when the same large prime appears in more than one partial relation. The mathematics involved in NFS is more sophisticated than QS, but the general idea is similar. Roughly speaking, "relations" and "cycles" in NFS correspond respectively to "partial relations" and "full/combined relations" in QS. Quote:
Quote:
How long is spent on each q value depends on which siever yafu chooses. The sievers are labelled gnfslasieve4I<n>e with <n> ranging from 11 to 16; the larger this value, the longer the siever spends on a specific q. Quote:
Quote:
Quote:
Quote:
Quote:
Quote:
With NFS, the principle is the same: we have lots of linear equations mod 2, and each independent solution/dependency has a 1/2 chance of finding the factors. However, in NFS, we don't get x and y such that x^2 = y^2 mod N straight away; we have to take the square root of an enormous complex number to find them. As for the coefficient sizes, you'd have to ask msieve's creator jasonp to find out why they're printed. But at least they give an idea of the size of the number we're taking the square root of. 

20210405, 16:42  #5 
"Ben"
Feb 2007
2×3^{2}×191 Posts 
Excellent info provided so far. The only thing I can add is some specifics on how many relations are needed for NFS and SIQS.
For SIQS, the number of relations needed is just a few more than the number of factor base primes. We know at any point during the sieving process how many relations have been found: the number of full relations + the number of relations combined from partials. A full relation occurs whenever Q(x)/a = (ax + 2b)x + c fully factors over the factor base. (a, b, and c are coefficients of a quadratic polynomial and x is some small integer). If Q(x)/a almost fully factors, with 1 or 2 large primes remaining, then we have a partial relation. These are added to a special data structure that can be quickly processed to tell us how these partial relations can be combined into fulls (I can't beat the simplicity of LaurV's example here). It is a little more work to gather and process these partial relations, but it is well worth it. Large jobs obtain most of their full relations by combining from partials. For NFS, the number of relations needed is mostly a function of the large prime bounds. These are the lpba and lpbr lines of the .job file. This thread provides a little more info on the estimates yafu makes (the last few posts in particular). Last fiddled with by bsquared on 20210405 at 16:44 
20210405, 21:09  #6 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
2·5·587 Posts 
In reality NFS has similar requirements to qs for how many relations are needed. We just count them differently which messes that up. In QS we tend to count full and combined relations while in nfs we count partial relations. For 1 and 2 large primes it is possible to fully count how many combined relations have been found. This becomes a lot harder for 3 or more(a lot of nfs has 2 for rational poly and 2 for algebraic making 4).

20210407, 17:34  #7 
Aug 2020
170_{10} Posts 
Thanks a lot guys, that is some great reading. You know someone really understood a topic if they can explain the basics in very simple terms. Reading it put a smile to my face both due to finally understanding what's going on (on a low level probably) and also because the poor guy got his nails pulled (shame on me).
It also made me appreciate what a genius idea these sieves are and how enormous the computational work is. I will have to go through it a few more times and likely some questions will come up. Thanks again. 
20210407, 17:51  #8 
"Ben"
Feb 2007
6556_{8} Posts 

20210410, 08:52  #9 
Aug 2020
10101010_{2} Posts 
Code:
commencing square root phase reading relations for dependency 1 read 182232 cycles cycles contain 637316 unique relations read 637316 relations multiplying 637316 relations multiply complete, coefficients have about 27.84 million bits initial square root is modulo 98794741 GCD is 1, no factor found reading relations for dependency 2 read 181783 cycles cycles contain 636612 unique relations read 636612 relations multiplying 636612 relations multiply complete, coefficients have about 27.80 million bits initial square root is modulo 96579421 GCD is N, no factor found reading relations for dependency 3 ... If I got you right, more than n relations are found for n variables, so with the excess our chance of finding a factor are is 50% for each excess relation. But why does it happen so often that I still see GCD is 1 or N with this large excess? So it's two questions, first why does it happen so often and second, what is changed (apparently "the dependency") until finally a nontrivial GCD is found? And something else: Code:
begin with 1395803 relations and 1627193 unique ideals reduce to 1343077 relations and 1305488 ideals in 9 passes max relations containing the same ideal: 84 
20210410, 12:50  #10  
Apr 2020
2^{3}·3·11 Posts 
Quote:
Quote:
Last fiddled with by charybdis on 20210410 at 13:38 Reason: rows > columns 

20210410, 15:41  #11 
Romulan Interpreter
Jun 2011
Thailand
13·727 Posts 

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 