20130301, 12:11  #23 
Romulan Interpreter
Jun 2011
Thailand
21701_{8} Posts 
I would really like to, unfortunately I have many reasons not to: all my cores are busy with different other tasks right now, my knowledge of factoring is quite weak on the gnfs/snfs area, and (beside of gimps) I am only factoring aliquots, where the new snfsimproved yafu is no help either... (I mean comparing with the former version, without snfs, for me they are the same: aliquots are glued to gnfs. I however enjoy other small improvements, new libraries built in, etc, as BB said before!)
Last fiddled with by LaurV on 20130301 at 12:14 
20130302, 05:00  #24 
"Ben"
Feb 2007
6441_{8} Posts 
1.34.4
YAFU should now pick intelligently between gnfs and snfs. And there is a new option (gnfs) if you believe it chose poorly and want to force it .

20130302, 14:15  #25  
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
2·2,897 Posts 
Quote:
Also there is behavior in the poly selector that I don't understand. For 1203193^171 the output provided by yafu is: Code:
nfs: checking x^17 +/ 1 nfs: input divides 1203193^17  1 gen: rank 1 terms: 17 gen: base exponent multiplier: 1 gen: multiplying by 1203193^17  1 = 23211330856125181758611942029710729411469446850296907 240025641387259558140884031084400673727546433187192 gen: dividing by 1203193^1  1 = 1203192 gen: ======================================================== gen: considering the following polynomials: gen: ======================================================== Error: M=2521601667296103324157241199193 is not a root of f(x) n = 34657538708223790272810989413434436772507088972811377041848153893539630852567521108538 805271 f(x) = + 1*x^4 + 0*x^3 + 0*x^2 + 0*x^1  1681576704*x^0 Remainder is 1741830493768253353 n: 346575387082237902728109894134344367725070889728113770418481538935396308525675211085388 05271 # 1203193^171, difficulty: 109.45, anorm: 7.34e+021, rnorm: 1.21e+031 # size = 2.079e011, alpha = 0.733, combined = 1.520e007, rroots = 2 type: snfs size: 109 skew: 0.0302 c4: 1203193 c0: 1 Y1: 1 Y0: 2095758259311767375772001 m: 2095758259311767375772001 Error: M=2095758259311767375772001 is not a root of f(x) n = 34657538708223790272810989413434436772507088972811377041848153893539630852567521108538 805271 f(x) = + 1*x^5 + 0*x^4 + 0*x^3 + 0*x^2 + 0*x^1  1681576704*x^0 Remainder is 1741830493768253353 Error: M=1741830495449830057 is not a root of f(x) n = 34657538708223790272810989413434436772507088972811377041848153893539630852567521108538 805271 f(x) = + 269416497*x^5 + 0*x^4 + 0*x^3 + 0*x^2 + 0*x^1  1*x^0 Remainder is 28242215676366881854729500894620392177126928325191207712379555020886481574606 936993316483026 gen: anorm: 7.34e+021, rnorm: 1.21e+031, ratio: 1.64e+009, log10(ratio) = 9.22 nfs: guessing snfs difficulty 109 is roughly equal to gnfs difficulty 91 gen: ======================================================== gen: selected polynomial: gen: ======================================================== n: 346575387082237902728109894134344367725070889728113770418481538935396308525675211085388 05271 # 1203193^171, difficulty: 109.45, anorm: 7.34e+021, rnorm: 1.21e+031 # scaled difficulty: 110.98, suggest sieving rational side # size = 2.079e011, alpha = 0.733, combined = 1.520e007, rroots = 2 type: snfs size: 109 skew: 0.0302 c4: 1203193 c0: 1 Y1: 1 Y0: 2095758259311767375772001 m: 2095758259311767375772001 The obvious polys for something of the form x^171 to try are surely: (x^6)^31 x*(x^4)^41 (which it finds and uses) x^2*(x^3)^51 (x^3)^6x x*(x^4)^41 is the only one of these polys it finds. I can't understand what it is attempting to do with the other failed polys. Where did the number 1681576704 come from? Personally for this size number the degree 3 looks tempting although you are then factoring x*N which might be too much of a slowdown over making the norms more equal. 

20130302, 16:38  #26 
"Ben"
Feb 2007
D21_{16} Posts 
It doesn't consider degree 3 at all. For this size input it also doesn't consider degree 6 (way unbalanced norms). And the squared coefficient apparently overflows a int64.
An expression parser is not on my todo list. Possibily it isn't as hard as i think it will be, but i have other things i want to work on. 
20130302, 18:19  #27 
"Ben"
Feb 2007
3,361 Posts 
Actually, the overflow happens when it tries to make (x^4)^5  x^3. x^2*(x^3)^5  1 should have worked... and it does for me (on linux64). The errors are expected  I knew that occasionally stuff would overflow, but never got around to implementing everything in gmp. Usually it can find a poly that works... and in this case it found the best one.

20130302, 21:43  #28 
Basketry That Evening!
"Bunslow the Bold"
Jun 2011
40<A<43 89<O<88
16065_{8} Posts 
Would you say that snfs(number, knownfactors) is better than snfs(number, cofactor)? It's trivial to do it either way (and perhaps there should be a flag to do it either way...).

20130303, 00:05  #29 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
2×2,897 Posts 
An overflow would make sense.
I suggested detecting the factors in the way I did as it should be relatively easy to parse that specific form. It wouldn't be perfect but you could check whether everything after the / is an expression on it's own and whether it divides the other bit of the expression. Dubslow's suggestion is probably better than current. I would like to be able to copy a a list of snfsable candidates from the factordb and have yafu run a bit of ecm on them and then pass them to snfs automatically. Last fiddled with by henryzz on 20130303 at 00:06 
20130304, 00:33  #30 
Jun 2012
3^{3}·109 Posts 

20130304, 00:52  #31  
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2·11·421 Posts 
Quote:
size < 0.56*S_{nfsdiff}+30 ad hoc decision boundary. For a better boundary, you could obtain the Evalue (internally for the snfs poly) and search a gnfs poly for a short time while comparing the best gnfs Evalues and using some heuristics to abandon the gnfs search early or not (i.e. if early gnfs E is way above snfs E, then definitely carry on along the gnfs track; if it is way below, then abandon early; and if it is, say, 2 times lower, then expect gnfs E to overcome snfs E  here, you will need some heuristic from experimentation) 

20130304, 01:32  #32 
"Ben"
Feb 2007
110100100001_{2} Posts 
The adhoc decision threshold is what I implemented. Your gnfs testpoly approach probably makes sense to do, especially as N grows, but this works for now.
Also, looks like we'll need one more patch version. A couple people have now reported crashes from the new 6.4.2 ECM library (this), so I'll test 6.4.4, and if that's no better, revert to 6.3. I'll post here when it's ready. 
20130307, 00:21  #33 
"Mark"
Apr 2003
Between here and the
6178_{10} Posts 
I ran into one issue building yafu on OS X. In include/types.h, I had to make this change:
#ifdef __APPLE__ #include <malloc/malloc.h> #else #include <malloc.h> #endif although I doubt that malloc.h is even required. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Yafu  bsquared  YAFU  1276  20190112 04:46 
Running YAFU via Aliqueit doesn't find yafu.ini  EdH  YAFU  8  20180314 17:22 
Yafu bug.  storflyt32  YAFU  2  20150629 05:19 
yafu1.33  bsquared  YAFU  12  20121108 04:12 
yafu1.32.1  bsquared  YAFU  21  20120904 19:44 