mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > YAFU

Reply
 
Thread Tools
Old 2021-02-16, 06:07   #1
jyb
 
jyb's Avatar
 
Aug 2005
Seattle, WA

110100010002 Posts
Default Yafu SNFS difficulty calculation

Can anybody help me understand the values Yafu is claiming for the difficulty in this example?
Code:
n: 401721424383720426137324949508336187045848565417289917430550907056665790265814883369879394476169080075318675151956526421358049691930517872710129161972339727160629599769770122149882863
# 7^307+6^307, difficulty: 260.29, anorm: 1.30e+037, rnorm: 1.27e+049
# scaled difficulty: 262.29, suggest sieving rational side
# size = 1.218e-012, alpha = 0.000, combined = 1.324e-013, rroots = 0
type: snfs
size: 260
skew: 0.9746
c6: 7
c0: 6
Y1: -4849687664788584363858837602739217760256
Y0: 12589255298531885026341962383987545444758743
...
The actual SNFS difficulty given by these polynomials is 259.445, according to every definition of SNFS difficulty that I've ever seen. So what are "difficulty", "scaled difficulty" and "size" (the second one) supposed to represent here?
jyb is offline   Reply With Quote
Old 2021-02-16, 14:55   #2
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

337110 Posts
Default

Quote:
Originally Posted by jyb View Post
Can anybody help me understand the values Yafu is claiming for the difficulty in this example?
Code:
n: 401721424383720426137324949508336187045848565417289917430550907056665790265814883369879394476169080075318675151956526421358049691930517872710129161972339727160629599769770122149882863
# 7^307+6^307, difficulty: 260.29, anorm: 1.30e+037, rnorm: 1.27e+049
# scaled difficulty: 262.29, suggest sieving rational side
# size = 1.218e-012, alpha = 0.000, combined = 1.324e-013, rroots = 0
type: snfs
size: 260
skew: 0.9746
c6: 7
c0: 6
Y1: -4849687664788584363858837602739217760256
Y0: 12589255298531885026341962383987545444758743
...
The actual SNFS difficulty given by these polynomials is 259.445, according to every definition of SNFS difficulty that I've ever seen. So what are "difficulty", "scaled difficulty" and "size" (the second one) supposed to represent here?




Difficulty is computed in the normal way, except here it looks like I may have included the contribution of the leading coefficient twice. Thanks for that report. As for scaled difficulty, quoting here from the code:

Quote:
Originally Posted by snfs.c
// poly degrees yielding very unbalanced norms are less desirable for sieving.
// reflect this by scaling the difficulty of these polys. Since special-q can
// bring the norm down on one side or another (at the expense of the other side),
// we add one to the difficulty for every order of magnitude imbalance beyond 6
// between the two sides (until we figure out something more accurate)
i.e., it's an attempt to call attention to polynomials that are very unbalanced (of undesirable degree). If the scaled difficulty is sufficiently bigger than the normal difficulty, yafu will try to compensate by increasing the factor base, large prime bounds, and trial factoring bounds. This happens in skew_snfs_params(). Looks like the scaled difficulty needs to be at least 4 bigger than normal (corresponding to 24 orders of magnitude difference in norms) before any parameters are altered.

Size is rounded difficulty. IIRC ggnfs doesn't use size for anything.

p.s.
I'm happy to consider alternatives if you have any suggestions! As indicated above, scaled difficulty was a mix of numerology and experience from back when I was actively performing snfs work.

Last fiddled with by bsquared on 2021-02-16 at 15:08 Reason: more details
bsquared is offline   Reply With Quote
Old 2021-02-16, 18:08   #3
charybdis
 
Apr 2020

2×5×19 Posts
Default

Quote:
Originally Posted by jyb View Post
Code:
anorm: 1.30e+037, rnorm: 1.27e+049
These are a bit small, especially anorm; the code uses a = 1e6*sqrt(skew), b=1e6/sqrt(skew) which might work well for small jobs but for numbers this large 1e6 is a big underestimate.

Really it should be something like a = sqrt(2^(2I-1)*Q*skew)*const, b = sqrt(2^(2I-1)*Q/skew)*const where Q is a realistic average special-q; smaller a and b give more relations so const should maybe be around 0.2? Not sure how it would be best to code this, given that the scaled difficulty informs the choice of I and Q. Perhaps use some function of difficulty that's a reasonable approximation of sqrt(2^(2I-1)*Q)?

And really anorm ought to be multiplied by exp(alpha) to account for root properties of the algebraic polynomial, but if you're doing a job large enough that this matters, then you ought to be test-sieving anyway.
charybdis is offline   Reply With Quote
Old 2021-02-16, 19:33   #4
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

D2B16 Posts
Default

Quote:
Originally Posted by charybdis View Post
...

Not sure how it would be best to code this, given that the scaled difficulty informs the choice of I and Q. Perhaps use some function of difficulty that's a reasonable approximation of sqrt(2^(2I-1)*Q)?
...
Thanks for the suggestions! Using the siever area is simple and straightforward and by itself gets the estimates much closer to actual norm sizes. So I'm tempted to just use
sqrt(2^(2I-1)*1e6*skew) and sqrt(2^(2I-1)*1e6/skew) as I think finer adjustments to Q or using alpha would be in the noise of what this estimate is used for.
bsquared is offline   Reply With Quote
Old 2021-02-24, 16:23   #5
jyb
 
jyb's Avatar
 
Aug 2005
Seattle, WA

23×11×19 Posts
Default

Here's another one, though perhaps with the opposite cause. The correct difficulty is 255.99. It looks like in this case Yafu didn't add the leading coefficient at all (255.14 ≈ 245*log_10(11)).
Code:
n: 7384049810391587250211352363287406947175960642669013845450189424529816242856745368078260733462087073764724231472029401134928725306986130695481851831787933178814661362606610448657133293018573723301486442995118362671069447396748839101553572591556351201
# 11^244+7^244, difficulty: 255.14, anorm: 1.75e+031, rnorm: 1.02e+057
# scaled difficulty: 259.44, suggest sieving rational side
# size = 1.944e-017, alpha = 0.000, combined = 7.014e-014, rroots = 1
type: snfs
size: 255
skew: 1.0946
c5: 7
c0: 11
Y1: -256923577521058878088611477224235621321607
Y0: 1067189571633593786424240872639621090354383081702091
jyb is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Difficulty of SNFS polynomials StrongestStrike Factoring 6 2020-09-16 22:40
HOW TO BYPASS RSA DIFFICULTY... not! Alberico Lepore Alberico Lepore 3 2020-04-29 16:28
Running YAFU via Aliqueit doesn't find yafu.ini EdH YAFU 8 2018-03-14 17:22
Better measures of SNFS difficulty fivemack Factoring 4 2007-06-30 09:20
Difficulty Running Prime with DSL Rosenfeld Lounge 16 2004-07-31 22:15

All times are UTC. The time now is 10:34.

Mon Mar 1 10:34:26 UTC 2021 up 88 days, 6:45, 0 users, load averages: 1.22, 1.24, 1.32

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.