mersenneforum.org > YAFU YAFU-1.34
 Register FAQ Search Today's Posts Mark Forums Read

 2013-03-01, 12:11 #23 LaurV Romulan Interpreter     Jun 2011 Thailand 217018 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 snfs-improved 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 2013-03-01 at 12:14
 2013-03-02, 05:00 #24 bsquared     "Ben" Feb 2007 64418 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 .
2013-03-02, 14:15   #25
henryzz
Just call me Henry

"David"
Sep 2007
Cambridge (GMT/BST)

2·2,897 Posts

Quote:
 Originally Posted by bsquared 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 .
Would it be possible for YAFU to parse something of the form (number)/(known factors) and recognize the known factors automatically. Currently if there are known factors for a snfs it is necessary to do snfs(number,(number)/(known factors)). Number and known factors can be an expression but not necessarily.

Also there is behavior in the poly selector that I don't understand. For 1203193^17-1 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^17-1, difficulty: 109.45, anorm: -7.34e+021, rnorm: 1.21e+031
# size = 2.079e-011, alpha = 0.733, combined = 1.520e-007, 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^17-1, difficulty: 109.45, anorm: -7.34e+021, rnorm: 1.21e+031
# scaled difficulty: 110.98, suggest sieving rational side
# size = 2.079e-011, alpha = 0.733, combined = 1.520e-007, rroots = 2
type: snfs
size: 109
skew: 0.0302
c4: 1203193
c0: -1
Y1: -1
Y0: 2095758259311767375772001
m: 2095758259311767375772001
I can't understand how it is trying to find a good polynomial.
The obvious polys for something of the form x^17-1 to try are surely:
(x^6)^3-1
x*(x^4)^4-1 (which it finds and uses)
x^2*(x^3)^5-1
(x^3)^6-x

x*(x^4)^4-1 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.

 2013-03-02, 16:38 #26 bsquared     "Ben" Feb 2007 D2116 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.
 2013-03-02, 18:19 #27 bsquared     "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.
 2013-03-02, 21:43 #28 Dubslow Basketry That Evening!     "Bunslow the Bold" Jun 2011 40
 2013-03-03, 00:05 #29 henryzz 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 2013-03-03 at 00:06
2013-03-04, 00:33   #30
swellman

Jun 2012

33·109 Posts

Quote:
 Originally Posted by bsquared 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 .
Works great! Thanks for the quick fix.

Running a GNFS poly search now for a C164.

2013-03-04, 00:52   #31
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2·11·421 Posts

Quote:
 Originally Posted by bsquared That... is not a dumb question at all. In fact it seems I've overlooked that possibility At least, nothing is occurring to me as to a way to force it to use gnfs. I guess we'll have at least one more patch to 1.34 at some point. I'll try to get it done tomorrow.
Ben, if you don't have a better estimate, you could use a
size < 0.56*Snfs-diff+30
ad hoc decision boundary. For a better boundary, you could obtain the E-value (internally for the snfs poly) and search a gnfs poly for a short time while comparing the best gnfs E-values 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)

 2013-03-04, 01:32 #32 bsquared     "Ben" Feb 2007 1101001000012 Posts The ad-hoc decision threshold is what I implemented. Your gnfs test-poly 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.
 2013-03-07, 00:21 #33 rogue     "Mark" Apr 2003 Between here and the 617810 Posts I ran into one issue building yafu on OS X. In include/types.h, I had to make this change: #ifdef __APPLE__ #include #else #include #endif although I doubt that malloc.h is even required.

 Similar Threads Thread Thread Starter Forum Replies Last Post bsquared YAFU 1276 2019-01-12 04:46 EdH YAFU 8 2018-03-14 17:22 storflyt32 YAFU 2 2015-06-29 05:19 bsquared YAFU 12 2012-11-08 04:12 bsquared YAFU 21 2012-09-04 19:44

All times are UTC. The time now is 13:56.

Fri Jan 22 13:56:50 UTC 2021 up 50 days, 10:08, 0 users, load averages: 2.32, 2.62, 2.71