 mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Factoring (https://www.mersenneforum.org/forumdisplay.php?f=19)
-   -   How to identify SNFS candidates and factor them? (https://www.mersenneforum.org/showthread.php?t=26852)

 bur 2021-05-30 06:12

How to identify SNFS candidates and factor them?

Since I just spent five days factoring a number with GNFS that could have been done in an hour using SNFS, I'd really like to know how to identify candidates for SNFS and how to factor them efficiently.

All I know (If I got it correct) is that all Mersenne/Proth/Riesel/... numbers should be candidates for SNFS since they all are of the form k*b^n+c.

Is there a guide or how-to on how to identify candidates, prepare a polynomial and which software to use for factoring?

 mathwiz 2021-05-30 07:21

Generally speaking, numbers of the form [\$]b^n-1[/\$] or [\$]b^n+1[/\$] or one of their divisors work best, though there are some other forms that work.

[url]https://www.rieselprime.de/ziki/Special_number_field_sieve[/url] and [url]https://www.rieselprime.de/ziki/SNFS_polynomial_selection[/url] have some more background reading.

As far as running the factorization, [URL="https://mersenneforum.org/forumdisplay.php?f=96"]YAFU[/URL] is very helpful at generating the actual poly for you. It can run the whole factorization, or you can use the poly in conjunction with other tools like CADO or GGNFS.

 charybdis 2021-05-30 13:27

YAFU is the fire-and-forget method, or at least it should be, because a [URL="https://mersenneforum.org/showthread.php?p=579480#post579480"]bug[/URL] seems to have crept in; hopefully Ben will fix this soon.

CADO can run SNFS perfectly well. EdH has written a [URL="https://mersenneforum.org/showthread.php?t=24842"]guide[/URL] for running SNFS with CADO, though it still relies on YAFU for the polynomial so won't work until the bug is fixed. It's mostly very good, but with one small caveat (lambdas are not directly comparable between YAFU and CADO so best to just leave out the lambda lines completely, CADO can choose its own) and one big caveat, which is that copying the [C]tasks.sieve.rels_wanted[/C] line across from the CADO parameter file could lead to collecting vastly more relations than are needed if YAFU's chosen lpb bounds differ from CADO's. The easiest way around this is probably to use YAFU's own estimate of required relations. This is

fudge(lpbr) * 2^lpbr / log(2^lpbr) + fudge(lpba) * 2^lpba / log(2^lpba)

where the logs are natural log and the fudge factors are given by the following table:
[code]lpb fudge(lpb)
24 0.40
25 0.50
26 0.60
27 0.70
28 0.76
29 0.84
30 0.89
31 0.91
32 0.95
33 0.98[/code]

SNFS parameters are trickier to figure out than GNFS ones, because while all GNFS jobs of a certain size will have pretty similar optimal parameters, this is not true of SNFS; you can't just run a bunch of SNFS-160 jobs to figure out what the best parameters are for any SNFS-160, and optimal parameters for similar-difficulty GNFS won't be optimal for most SNFS jobs. But at least 160 digits is a small enough SNFS job that picking slightly suboptimal parameters won't hurt you too much. For large jobs it's essential to test-sieve in order to figure out the best parameters - or indeed the best polynomial, as there are often multiple options.

If you don't want to wait for the YAFU bug to be fixed, it's not hard to adapt the techniques for b^n+-1 in the links that mathwiz gave to k*b^n+c.

 VBCurtis 2021-05-30 14:47

For your proth searches, you want to write your input number as a * (x^5) + c.
Then c5 = a, c0 = c, y1 = 1, y0 = x (I forget if it's positive or negative).

5th degree polys are best for roughly 120 to 200 digits; above 200 digits you would use the same concept but a 6th degree polynomial. There's a gray area where you might test both 5th and 6th degree.

So, say you want to factor 13*2^698 + 1.
698 is close to 700, so multiplying my input by 4 gives me 13*2^700 + 4.
My poly would be 13*(2^140)^5 + 4, so c5 = 13, c0 = 4, and y0 = 2^140.

For 13*2^697+1, I would take out 2 2's from the large power, making 52*2^695+1. c5=52, c0 = 1, y0=2^139.

In your efforts, since your leading coefficient is already large, you won't want to pull out 2's in this manner- rather, you'll use the first style to make c0 bigger rather than making c1 bigger. SNFS difficulty is mostly linked to the size of the largest poly coefficient, so you want to avoid making c5 bigger.

I use wolfram alpha to get the expansions of large powers of 2.

The reference sites mentioned in earlier posts are much more detailed, but I thought maybe a concrete example would be of use.

 charybdis 2021-05-30 15:16

[QUOTE=VBCurtis;579491]For your proth searches, you want to write your input number as a * (x^5) + c.
Then c5 = a, c0 = c, y1 = 1, y0 = x (I forget if it's positive or negative).[/quote]

Y0 needs to be negative here. The requirement is that the two polynomials have a common root mod N. The root is x, not -x, so the rational polynomial must be t-x (t is the variable because you've used x already).

[quote]In your efforts, since your leading coefficient is already large, you won't want to pull out 2's in this manner- rather, you'll use the first style to make c0 bigger rather than making c1 bigger. SNFS difficulty is mostly linked to the size of the largest poly coefficient, so you want to avoid making c5 bigger.[/QUOTE]

This isn't true: the skew compensates for c5 being much larger than c0, so we'd rather multiply c5 by 4 than multiply c0 by 8 even if c5 is huge. The algebraic norm for the polynomials we're considering is c5*a^5 + c0*b^5; the choice of skew ensures that the two terms are roughly the same size, so each coefficient has a similar contribution to the norms and multiplying one by 8 will be worse than multiplying the other by 4.

We ought to take the rational norm into account too. This is Y1*a + Y0*b, so the second term massively dominates. The skew varies by a factor of 2 between the two polynomials, so the "make c0 larger" polynomial has b values around a factor of sqrt(2) smaller than the "make c5 larger" poly. But its Y0 value is doubled (2^140 vs 2^139 for your example), so the rational norm is larger too.

If you calculate some E-scores you'll see that they bear this out.

 xilman 2021-05-30 15:59

[QUOTE=bur;579457]I'd really like to know how to identify candidates for SNFS and how to factor them efficiently.

Is there a guide or how-to on how to identify candidates, prepare a polynomial and which software to use for factoring?[/QUOTE]If you can represent your numbe rN as the value of as a polynomial of degree 4-8 (depending on size of number) with coefficients all of which are very small with respect to N, you are within the SNFS regime.

There are so many numbers which can be represented in that way it is hard to be more precise. For instance, you may be interested in factoring integers N=1+2x+6x[SUP]2[/SUP]-24x[SUP]3[/SUP]-120x[SUP]4[/SUP]+720x[SUP]5[/SUP] for all I know.

 sean 2021-05-30 20:36

A lot of popular projects have numbers which can be handled with SNFS including Cunningham and related, cyclotomic, Cullen, Woodall, Fibonacci and Lucas and related, x^y+y^x. In addition to what has already been mentioned, factordb can sometimes give you a ready made SNFS polynomials (but be aware it is not always right or useful in what it suggests for the polynomial).

As xilman indicates, if you can express your number (or some multiple of your number) as a small degree homogeneous polynomial, then SNFS is probably applicable, although it will not always be the best choice.

 VBCurtis 2021-05-31 03:09

[QUOTE=charybdis;579493]This isn't true: the skew compensates for c5 being much larger than c0, so we'd rather multiply c5 by 4 than multiply c0 by 8 even if c5 is huge. The algebraic norm for the polynomials we're considering is c5*a^5 + c0*b^5; the choice of skew ensures that the two terms are roughly the same size, so each coefficient has a similar contribution to the norms and multiplying one by 8 will be worse than multiplying the other by 4.
[....]
If you calculate some E-scores you'll see that they bear this out.[/QUOTE]

I tried this: I tried OP's 1281979*2^n+1, with n = 647. Multiplying by 8 to make a poly ending in +8 and Y0 = 2^130 had score 6.444e-12, while factoring out a 4 and making a poly ending in +1 with Y0 2^129 had score 7.02e-12.

10% is not a small difference. Thanks for the teaching moment!

 bur 2021-05-31 06:44

Thanks for all the information, I'll be back with some questions probably...

 bur 2021-05-31 18:02

To see if I understood it correctly (that example helped a lot), if I want to factor [TEX]1281979*2^{523}+1[/TEX] with SNFS, I follow EdH's guide, with the following modifications:

1) Using self-created poly, in the example case: [TEX]4*(1281979*2^{523}+1) = 1281979*{(2^{105})}^{5}+4[/TEX], so c5 = 1281979, c0 = 4, y1 = 1, y0 = -2^105 (negative)?

2) Don't copy lambda0 and lambda1 values to params. So I just leave it out or do I use the ones from the original CADO params file?

3) Calculate rels_wanted using your formula.

[QUOTE]or indeed the best polynomial, as there are often multiple options.[/QUOTE]I guess for now I'm good with the default values, but out of curiosity, how could the polynomial be changed? I could just multiply by 4 again, but I guess it's not that simple?

 charybdis 2021-05-31 19:23

[QUOTE=bur;579569]To see if I understood it correctly (that example helped a lot), if I want to factor [TEX]1281979*2^{523}+1[/TEX] with SNFS, I follow EdH's guide, with the following modifications:

1) Using self-created poly, in the example case: [TEX]4*(1281979*2^{523}+1) = 1281979*{(2^{105})}^{5}+4[/TEX], so c5 = 1281979, c0 = 4, y1 = 1, y0 = -2^105 (negative)?

2) Don't copy lambda0 and lambda1 values to params. So I just leave it out or do I use the ones from the original CADO params file?

3) Calculate rels_wanted using your formula.[/quote]

Theoretically, yes. Best to just leave out the lambdas - they're useful for fine-tuning optimal GNFS parameters, but as we don't really have "optimal SNFS parameters" in the same way, we might as well let CADO use its own guess at optimal lambdas.

EdH's guide relies on using YAFU to generate the parameter file, so you'll need a version of YAFU that doesn't have the SNFS poly selection bug that I mentioned. Alternatively you can use CADO sieving parameters - Curtis's params.c120 in this case - but with [C]tasks.sieve.sqside = 0[/C] for rational-side sieving (I think this will be a little faster than algebraic side?) and the algebraic and rational side parameters swapped (lim0 and lim1 etc). You can keep the lambdas in this case. Neither of these options will give optimal parameters, but at this size it really won't matter too much. For larger numbers you would want to test-sieve different choices of parameters, although there are often good theoretical reasons to expect certain parameter choices to be better than others.

[quote]I guess for now I'm good with the default values, but out of curiosity, how could the polynomial be changed? I could just multiply by 4 again, but I guess it's not that simple?[/QUOTE]

You could also represent this number as 8*1281979*2^520+1, giving c5 = 10255832, c0 = 1, Y1 = 1, Y0 = -2^104. This choice of polynomial might even be slightly faster than yours; at least it has a higher E-score. For some numbers there will be even more polynomials to choose between: this will often be the case when near the crossover between degree 5 and degree 6, for instance (and here we have to test-sieve, as E-scores from different degrees are not comparable).

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