mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > YAFU

Reply
 
Thread Tools
Old 2022-01-07, 13:39   #1
nivek000
 
Dec 2021

17 Posts
Default SNFS Performance

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
nivek000 is offline   Reply With Quote
Old 2022-01-07, 13:57   #2
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

3×17×73 Posts
Default

Quote:
Originally Posted by nivek000 View Post
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.

Last fiddled with by bsquared on 2022-01-07 at 13:59
bsquared is offline   Reply With Quote
Old 2022-01-07, 14:18   #3
nivek000
 
Dec 2021

218 Posts
Default

I am running the factor command on the C214:

Code:
9204214625221874710952946935076263878608726889174004840754589809679987461484965033357036848408384671559545992781188531318866340573729054722277805831939611797303471658749775441007571889786142040525120939985881393299
This leads to a C160 SNFS:

Code:
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
nivek000 is offline   Reply With Quote
Old 2022-01-07, 14:56   #4
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

3×17×73 Posts
Default

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.
bsquared is offline   Reply With Quote
Old 2022-01-07, 15:13   #5
nivek000
 
Dec 2021

17 Posts
Default

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.

Last fiddled with by nivek000 on 2022-01-07 at 15:22
nivek000 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Odd GMP Performance prime Programming 11 2021-03-12 04:39
Comparison of GNFS/SNFS With Quartic (Why not to use SNFS with a Quartic) EdH EdH 14 2020-04-20 16:21
fun with snfs masser Sierpinski/Riesel Base 5 36 2008-04-18 02:39
LLR performance on k and n robert44444uk 15k Search 1 2006-02-09 01:43
Performance battlemaxx Prime Sierpinski Project 4 2005-06-29 20:32

All times are UTC. The time now is 23:41.


Sat Nov 26 23:41:20 UTC 2022 up 100 days, 21:09, 0 users, load averages: 1.53, 1.29, 1.13

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔