View Single Post
Old 2021-11-05, 02:47   #980
charybdis's Avatar
Apr 2020

25516 Posts

Depends how much detail you want

NFS has three stages.

1. Polynomial selection. You need to find two polynomials f(x) and g(x) that have a common root modulo N, the number you want to factor. In general smaller coefficients are better. Almost always g(x) (the "rational polynomial") will be linear, and f(x) (the "algebraic polynomial") will have higher degree, usually 4, 5 or 6.
SNFS is when the form of the number naturally gives you such polynomials: for the number we're discussing here, these are 31479823396757*x^6-1 and x-31479823396757^3, which have common root 31479823396757^3 mod N.
GNFS is for numbers that don't have a special form, and the polynomials must be found by computer search. There are algorithms for this that are used by msieve and CADO.
The "c6" and "c0" lines in the polynomial file are the coefficients of the algebraic polynomial; I omitted c5 to c1 because those are all zero. The rational polynomial coefficients are Y1 and Y0.

2. Sieving. This consists of finding some large number of "relations". In some sense these are like equations in a large number of variables, such that if enough are found, the resulting system of equations can be solved. I like LaurV's explanation here.
There are lots of different parameters that control sieving: this is what rlim/alim, lpbr/lpba etc are doing.

3. Postprocessing. This is where the relations are combined together and the system of equations is solved. Each solution to the equations has a 50% chance of finding the factors.

SNFS is much faster than GNFS for numbers of the same size (where, as I mentioned above, it's the size of the original number that matters for SNFS). A rough approximation is that SNFS of d digits is equivalent to GNFS of 0.69*d digits, but this doesn't hold when the SNFS polynomial has large coefficients or the "wrong" degree for the size of the number. GNFS difficulty roughly doubles every 5.5 digits.

This thread has some more detailed mathematical explanations if you're interested. These are very much not ELI5, though maybe some are ELI18.

Last fiddled with by charybdis on 2021-11-05 at 02:48
charybdis is offline   Reply With Quote