mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > YAFU

Reply
 
Thread Tools
Old 2013-03-01, 12:11   #23
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

217018 Posts
Default

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
LaurV is offline   Reply With Quote
Old 2013-03-02, 05:00   #24
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

64418 Posts
Default 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 .
bsquared is offline   Reply With Quote
Old 2013-03-02, 14:15   #25
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

2·2,897 Posts
Default

Quote:
Originally Posted by bsquared View Post
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.
henryzz is online now   Reply With Quote
Old 2013-03-02, 16:38   #26
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

D2116 Posts
Default

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.
bsquared is offline   Reply With Quote
Old 2013-03-02, 18:19   #27
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

3,361 Posts
Default

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.
bsquared is offline   Reply With Quote
Old 2013-03-02, 21:43   #28
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

160658 Posts
Default

Would you say that snfs(number, known-factors) 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...).
Dubslow is offline   Reply With Quote
Old 2013-03-03, 00:05   #29
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

2×2,897 Posts
Default

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
henryzz is online now   Reply With Quote
Old 2013-03-04, 00:33   #30
swellman
 
swellman's Avatar
 
Jun 2012

33·109 Posts
Default

Quote:
Originally Posted by bsquared View Post
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.
swellman is online now   Reply With Quote
Old 2013-03-04, 00:52   #31
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2·11·421 Posts
Default

Quote:
Originally Posted by bsquared View Post
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)
Batalov is offline   Reply With Quote
Old 2013-03-04, 01:32   #32
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

1101001000012 Posts
Default

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.
bsquared is offline   Reply With Quote
Old 2013-03-07, 00:21   #33
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

617810 Posts
Default

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.
rogue is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Yafu bsquared YAFU 1276 2019-01-12 04:46
Running YAFU via Aliqueit doesn't find yafu.ini EdH YAFU 8 2018-03-14 17:22
Yafu bug. storflyt32 YAFU 2 2015-06-29 05:19
yafu-1.33 bsquared YAFU 12 2012-11-08 04:12
yafu-1.32.1 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

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.