SNFS Performance

[nivek000]

Does the performance of SNFS vary wildly? I saw a C155 number (a factor of a larger C205 number) factor with SNFS in a little over 2 hours. Now I have a C160 running (a factor of a larger C213 number) that is estimated to run like 35 hours. The stated scaled difficulty is definitely different (167 for the former vs 218 for the latter). I am just surprised that there can be such a longer runtime for just 5 additional digits. Is this an effect of polynomial selection? Is it possible YAFU (version 2.07) made a poor choice for the latter number, or is this par for the course with SNFS?

Thanks!

- Kevin

[bsquared]

Originally Posted by nivek000

Does the performance of SNFS vary wildly? I saw a C155 number (a factor of a larger C205 number) factor with SNFS in a little over 2 hours. Now I have a C160 running (a factor of a larger C213 number) that is estimated to run like 35 hours. The stated scaled difficulty is definitely different (167 for the former vs 218 for the latter). I am just surprised that there can be such a longer runtime for just 5 additional digits. Is this an effect of polynomial selection? Is it possible YAFU (version 2.07) made a poor choice for the latter number, or is this par for the course with SNFS?

Thanks!

- Kevin

Is the C160 a quartic, by chance? The degree of the polynomial matters and degree 4 for a C213 is suboptimal. Unfortunately this is the only way to make a SNFS poly, sometimes. It's better than running GNFS (although this isn't always true!).

[edit]
If you like, post the target number and what yafu picked and we can help figure out if it was the best choice.

[nivek000]

I am running the factor command on the C214:

9204214625221874710952946935076263878608726889174004840754589809679987461484965033357036848408384671559545992781188531318866340573729054722277805831939611797303471658749775441007571889786142040525120939985881393299

This leads to a C160 SNFS:

01/07/22 02:23:41, nfs: commencing nfs on c160: 1094978880991933841557716588685966958370702537417059147514661217327507272995782570163478397553503222964719677999983911694855297094453016882804532233693251575823
01/07/22 02:23:41, nfs: input divides 43^131 - 42^131
01/07/22 02:23:41, nfs: using supplied cofactor: 1094978880991933841557716588685966958370702537417059147514661217327507272995782570163478397553503222964719677999983911694855297094453016882804532233693251575823
01/07/22 02:23:41, nfs: commencing snfs on c160: 1094978880991933841557716588685966958370702537417059147514661217327507272995782570163478397553503222964719677999983911694855297094453016882804532233693251575823
01/07/22 02:23:41, gen: best 3 polynomials:
n: 1094978880991933841557716588685966958370702537417059147514661217327507272995782570163478397553503222964719677999983911694855297094453016882804532233693251575823
# 43^131-42^131, difficulty: 213.98, anorm: -8.04e+28, rnorm: 7.89e+48
# scaled difficulty: 217.98, suggest sieving rational side
# size = 6.194e-15, alpha = 0.995, combined = 3.414e-12, rroots = 1
type: snfs
size: 213
skew: 0.9953
c5: 43
c0: -42
Y1: -1601332619247764283850260201342556799238144
Y0: 2952431600795587633717359131697109546569049
n: 1094978880991933841557716588685966958370702537417059147514661217327507272995782570163478397553503222964719677999983911694855297094453016882804532233693251575823
# 43^131-42^131, difficulty: 218.86, anorm: -3.54e+35, rnorm: 2.01e+42
# scaled difficulty: 220.21, suggest sieving rational side
# size = 6.444e-11, alpha = 0.798, combined = 2.431e-12, rroots = 2
type: snfs
size: 218
skew: 1.0039
c6: 42
c0: -43
Y1: -514617308132852400700537649353457664
Y0: 863586854220408743801513785592407849
n: 1094978880991933841557716588685966958370702537417059147514661217327507272995782570163478397553503222964719677999983911694855297094453016882804532233693251575823
# 43^131-42^131, difficulty: 233.50, anorm: -3.01e+33, rnorm: 3.35e+50
# scaled difficulty: 236.91, suggest sieving rational side
# size = 8.786e-17, alpha = -1.236, combined = 2.748e-13, rroots = 1
type: snfs
size: 233
skew: 1.0190
c5: 3111696
c0: -3418801
Y1: -67255970008406099921710928456387385568002048
Y0: 126954558834210268249846442662975710502469107
01/07/22 02:23:46, test: fb generation took 3.9993 seconds
01/07/22 02:23:46, test: commencing test sieving of polynomial 0 on the rational side over range 27800000-27801000
skew: 1.1247
c5: 43
c0: -42
Y1: -1601332619247764283850260201342556799238144
Y0: 2952431600795587633717359131697109546569049
rlim: 27800000
alim: 27800000
mfbr: 58
mfba: 58
lpbr: 29
lpba: 29
rlambda: 2.60
alambda: 2.60
01/07/22 02:23:46, test: estimated total sieving time = 11574 days 1h 46m 39s (with 40 threads)
01/07/22 02:23:52, test: fb generation took 6.5770 seconds
01/07/22 02:23:52, test: commencing test sieving of polynomial 1 on the rational side over range 29200000-29201000
skew: 1.0742
c6: 42
c0: -43
Y1: -514617308132852400700537649353457664
Y0: 863586854220408743801513785592407849
rlim: 29200000
alim: 29200000
mfbr: 58
mfba: 58
lpbr: 29
lpba: 29
rlambda: 2.60
alambda: 2.60
01/07/22 02:23:53, test: estimated total sieving time = 11574 days 1h 46m 39s (with 40 threads)
01/07/22 02:23:59, test: fb generation took 6.2644 seconds
01/07/22 02:23:59, test: commencing test sieving of polynomial 2 on the rational side over range 43600000-43601000
skew: 1.1311
c5: 3111696
c0: -3418801
Y1: -67255970008406099921710928456387385568002048
Y0: 126954558834210268249846442662975710502469107
rlim: 43600000
alim: 43600000
mfbr: 60
mfba: 60
lpbr: 30
lpba: 30
rlambda: 2.60
alambda: 2.60
01/07/22 02:23:59, test: estimated total sieving time = 11574 days 1h 46m 39s (with 40 threads)
01/07/22 02:23:59, gen: selected polynomial:
n: 1094978880991933841557716588685966958370702537417059147514661217327507272995782570163478397553503222964719677999983911694855297094453016882804532233693251575823
# 43^131-42^131, difficulty: 213.98, anorm: -8.04e+28, rnorm: 7.89e+48
# scaled difficulty: 217.98, suggest sieving rational side
# size = 6.194e-15, alpha = 0.995, combined = 3.414e-12, rroots = 1
type: snfs
size: 213
skew: 1.1247
c5: 43
c0: -42
Y1: -1601332619247764283850260201342556799238144
Y0: 2952431600795587633717359131697109546569049
01/07/22 02:23:59, nfs: commencing lattice sieving with 40 threads

[bsquared]

The estimated total sieving time looks like it isn't being printed correctly, but other than that it all looks fine and the best poly was chosen. Note that this number isn't 5 digits larger, it is 10 digits larger than your previous one. Unless there are algebraic factors that can be pulled out, SNFS difficulty is proportional to the full input size, not the cofactor size. That's why it is sometimes better to run GNFS on SNFSable numbers.

[nivek000]

Thanks for the explanation. I did not realize the SNFS time was based on the original number and not the smaller factor. It's just so much easier when ECM finds all the factors :)

And, yes, I have noticed in the runs that I have done that the estimated total sieving times consistently do not print correctly for some reason. I just wait for the first sieving round to complete to get an estimate of the time.