mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2021-05-30, 06:12   #1
bur
 
bur's Avatar
 
Aug 2020

12C16 Posts
Default 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?
bur is offline   Reply With Quote
Old 2021-05-30, 07:21   #2
mathwiz
 
Mar 2019

3×61 Posts
Default

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.

https://www.rieselprime.de/ziki/Spec...er_field_sieve and https://www.rieselprime.de/ziki/SNFS...mial_selection have some more background reading.

As far as running the factorization, YAFU 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.

Last fiddled with by mathwiz on 2021-05-30 at 07:23
mathwiz is offline   Reply With Quote
Old 2021-05-30, 13:27   #3
charybdis
 
charybdis's Avatar
 
Apr 2020

1011100112 Posts
Default

YAFU is the fire-and-forget method, or at least it should be, because a bug seems to have crept in; hopefully Ben will fix this soon.

CADO can run SNFS perfectly well. EdH has written a guide 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 tasks.sieve.rels_wanted 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
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.

Last fiddled with by charybdis on 2021-05-30 at 13:33
charybdis is offline   Reply With Quote
Old 2021-05-30, 14:47   #4
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

114048 Posts
Default

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.
VBCurtis is offline   Reply With Quote
Old 2021-05-30, 15:16   #5
charybdis
 
charybdis's Avatar
 
Apr 2020

7×53 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
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).
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.
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.
charybdis is offline   Reply With Quote
Old 2021-05-30, 15:59   #6
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

22×5×72×11 Posts
Default

Quote:
Originally Posted by bur View Post
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?
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+6x2-24x3-120x4+720x5 for all I know.
xilman is offline   Reply With Quote
Old 2021-05-30, 20:36   #7
sean
 
sean's Avatar
 
Aug 2004
New Zealand

DF16 Posts
Default

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.
sean is offline   Reply With Quote
Old 2021-05-31, 03:09   #8
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

22·1,217 Posts
Default

Quote:
Originally Posted by charybdis View Post
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.
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!
VBCurtis is offline   Reply With Quote
Old 2021-05-31, 06:44   #9
bur
 
bur's Avatar
 
Aug 2020

22·3·52 Posts
Default

Thanks for all the information, I'll be back with some questions probably...
bur is offline   Reply With Quote
Old 2021-05-31, 18:02   #10
bur
 
bur's Avatar
 
Aug 2020

22×3×52 Posts
Default

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

1) Using self-created poly, in the example case: 4*(1281979*2^{523}+1) = 1281979*{(2^{105})}^{5}+4, 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.
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?
bur is offline   Reply With Quote
Old 2021-05-31, 19:23   #11
charybdis
 
charybdis's Avatar
 
Apr 2020

5638 Posts
Default

Quote:
Originally Posted by bur View Post
To see if I understood it correctly (that example helped a lot), if I want to factor 1281979*2^{523}+1 with SNFS, I follow EdH's guide, with the following modifications:

1) Using self-created poly, in the example case: 4*(1281979*2^{523}+1) = 1281979*{(2^{105})}^{5}+4, 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.
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 tasks.sieve.sqside = 0 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?
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).
charybdis is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
A new tool to identify aliquot sequence margins and acquisitions garambois Aliquot Sequences 24 2021-02-25 23:31
Comparison of GNFS/SNFS With Quartic (Why not to use SNFS with a Quartic) EdH EdH 14 2020-04-20 16:21
new candidates for M...46 and M48 cochet Miscellaneous Math 4 2008-10-24 14:33
Please identify! Brian-E Lounge 24 2008-08-01 14:13
Easily identify composites using multiplication Nightgamer360 Miscellaneous Math 9 2007-07-09 17:38

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


Sun Aug 1 04:40:41 UTC 2021 up 8 days, 23:09, 0 users, load averages: 0.85, 1.14, 1.41

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.