mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > YAFU

Reply
 
Thread Tools
Old 2012-10-25, 22:58   #1
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

2·3·557 Posts
Default yafu-1.33

Now available.

Mostly "user experience" updates and bug fixes, but enough of them to warrant a new version.

Happy factoring!
bsquared is offline   Reply With Quote
Old 2012-10-26, 00:34   #2
kar_bon
 
kar_bon's Avatar
 
Mar 2006
Germany

2×1,427 Posts
Default

The zip-file is not readable.
kar_bon is offline   Reply With Quote
Old 2012-10-26, 01:03   #3
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

334210 Posts
Default

Things acted a bit funny when I first uploaded it. I re-uploaded, so try it again.

thanks.
bsquared is offline   Reply With Quote
Old 2012-11-07, 03:29   #4
swellman
 
swellman's Avatar
 
Jun 2012

11×263 Posts
Default SNFS # of relations?

When "type: SNFS" is added to the nfs.job file, the estimated required number of relations seems higher than I had been led to expect from SNFS.

What's the formula for this estimate?

Also the # rels/spec_q ratio for my poly drops horribly when changing type from GNFS to SNFS (and the estimated time goes up), despite the usual rule of thumb recommending use of SNFS for my composite. Didn't expect that. Maybe I'm comparing apples and oranges here...
swellman is online now   Reply With Quote
Old 2012-11-07, 03:40   #5
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3×2,399 Posts
Default

Quote:
Originally Posted by swellman View Post
When "type: SNFS" is added to the nfs.job file, the estimated required number of relations seems higher than I had been led to expect from SNFS.
It's case sensitive, and I've seen lowercase from most examples, so that's what YAFU looks for. Thus, it doesn't see the type is SNFS, and the minrels estimate is for a GNFS job of that size, which is why it's so high.
Quote:
Originally Posted by swellman View Post
What's the formula for this estimate?
Code:
(2*fudge * (pow(2.0,(double)lpb) / log(pow(2.0,(double)lpb))))
...where fudge also depends on lpb and is given by a table in the source.
Code:
case 27:
        fudge = 0.70;
        break;
case 28:
        fudge = 0.76;
        break;
case 29:
        fudge = 0.84;
        break;
case 30:
        fudge = 0.89;
        break;
case 31:
        fudge = 0.91;
        break;
Quote:
Originally Posted by swellman View Post
Also the # rels/spec_q ratio for my poly drops horribly when changing type from GNFS to SNFS (and the estimated time goes up), despite the usual rule of thumb recommending use of SNFS for my composite. Didn't expect that. Maybe I'm comparing apples and oranges here...
Perhaps with your poly, sieving on the algebraic side is better...? (YAFU doesn't affect what the siever does other than tell it which side to sieve on.)

Last fiddled with by Dubslow on 2012-11-07 at 03:41 Reason: 2*fudge
Dubslow is offline   Reply With Quote
Old 2012-11-07, 03:50   #6
swellman
 
swellman's Avatar
 
Jun 2012

11×263 Posts
Default

I use snfs in my poly (and Yafu recognizes it as such). It was just all caps here due to my silly iPhone autocorrect.

Will post my example tomorrow to show specifics.

Thanks for the formula.
swellman is online now   Reply With Quote
Old 2012-11-07, 04:00   #7
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

11100000111012 Posts
Default

Quote:
Originally Posted by swellman View Post
I use snfs in my poly (and Yafu recognizes it as such). It was just all caps here due to my silly iPhone autocorrect.

Will post my example tomorrow to show specifics.

Thanks for the formula.
When you first started YAFU with this job, did you have all the job parameters selected and in the file, or did you let YAFU fill them in? If the type was wrong the first time (even if it's correct now), then the parameters chosen would be horribly wrong. In any case, I look forward to the specifics, since it's apparently my code that's derping. (I might need help with figuring out if all the params are decent...)

Actually, do you have the "size: 190" (or whatever) in your job file? If you don't, YAFU assumes the SNFS difficulty is the size of the n: in the job file, and if there are other known factors those two sizes could be significantly different.
Dubslow is offline   Reply With Quote
Old 2012-11-07, 21:01   #8
swellman
 
swellman's Avatar
 
Jun 2012

11·263 Posts
Default

Quote:
Originally Posted by Dubslow View Post
When you first started YAFU with this job, did you have all the job parameters selected and in the file, or did you let YAFU fill them in? If the type was wrong the first time (even if it's correct now), then the parameters chosen would be horribly wrong. In any case, I look forward to the specifics, since it's apparently my code that's derping. (I might need help with figuring out if all the params are decent...)

Actually, do you have the "size: 190" (or whatever) in your job file? If you don't, YAFU assumes the SNFS difficulty is the size of the n: in the job file, and if there are other known factors those two sizes could be significantly different.
I did not have "size:" in my nfs.job file. Once I corrected this, a lot of my issues/confusion went away. Suggest use of "size" and "type" by SNFS within Yafu be more thoroughly documented - I can find nothing in the current docfile.txt (nor the ggnfs and mseive documentation).

As to estimating the number of relations required for SNFS, I had been using models from Kamada's site. For SNFS, they use

4*10^(d/70+4)

where d is the SNFS difficulty. The other parameters for a poly file are also modeled on that page, presumably based on successful factorizations. Anybody have a feel for how accurate the Kamada models are?
swellman is online now   Reply With Quote
Old 2012-11-07, 21:59   #9
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

719710 Posts
Default

Quote:
Originally Posted by swellman View Post
I did not have "size:" in my nfs.job file. Once I corrected this, a lot of my issues/confusion went away. Suggest use of "size" and "type" by SNFS within Yafu be more thoroughly documented - I can find nothing in the current docfile.txt (nor the ggnfs and mseive documentation).
Sorry. That's because these are features I added myself last month, and it didn't occur to anyone to add it to the docfile. (I don't have write access to SVN either.) I'll write up a few notes and send them to b2. In the meantime, the bottom part of this post is the closest there is to documentation.
Quote:
Originally Posted by swellman View Post
As to estimating the number of relations required for SNFS, I had been using models from Kamada's site. For SNFS, they use

4*10^(d/70+4)

where d is the SNFS difficulty. The other parameters for a poly file are also modeled on that page, presumably based on successful factorizations. Anybody have a feel for how accurate the Kamada models are?
Neat! I recognize some of the names, so the figures are probably pretty accurate; for the estimation in YAFU, the rels required are nominally pi(rlim/alim)+1, but the large prime method makes the required rels non-deterministic, though it still depends almost entirely on what lpb is, with some dependence on *lim. The formula I quoted above is related to the density of the primes, though I'm not sure of the details (others can fill in them in; in any case, note that the formula above is the asymptotic approximation of pi(2^lpb), as given in the second link). (Edit: mfb also plays a role in it, or more specifically, the ratio mfb/lpb plays a role.)

As for the regression you quote, that's due to the fact that the choice of lpb is pretty well understood (read: consistent) for difficulties <= ~250 (and in turn the min_rels estimate is consistent).

Last fiddled with by Dubslow on 2012-11-07 at 22:04
Dubslow is offline   Reply With Quote
Old 2012-11-07, 22:59   #10
swellman
 
swellman's Avatar
 
Jun 2012

B4D16 Posts
Default Example

Posting my example, which still has an odd warning message about ignoring the size parameter, even though Yafu appears to use it. But with the size parameter in place, things seem much better.

Composite is C163_145_33 from the xyyx project. It has a SNFS difficulty of 221. My poly is as follows

Code:
n: 8044748335384450433189067533289903349948378898702376138454639872609531665263335556364761169996899460279132119953474639118706796845849163688530204021522714077427337
type: snfs
size: 221
skew: 19.81
c0: 3048625
c5: 1
Y0: -108869005682301795684211705446369982097742753
Y1: 9294114390625
rlim: 34000000
alim: 34000000
lpbr: 29
lpba: 29
mfbr: 58
mfba: 58
rlambda: 2.600000
alambda: 2.600000
Executing Yafu on the rational side results in

Code:
c:>yafu "nfs(8044748335384450
43318906753328990334994837889870237613845463987260953166526333555636476116999689
9460279132119953474639118706796845849163688530204021522714077427337)" -v -r -R -
ns 15000000,15001000
 
11/07/12 17:37:10 v1.33 @ NATINB84202, System/Build Info:
Using GMP-ECM 6.3, Powered by GMP 5.0.1
detected Intel(R) Core(TM)2 Duo CPU     P8700  @ 2.53GHz
detected L1 = 32768 bytes, L2 = 3145728 bytes, CL = 64 bytes
measured cpu frequency ~= 2419.123890
using 20 random witnesses for Rabin-Miller PRP checks
===============================================================
======= Welcome to YAFU (Yet Another Factoring Utility) =======
=======             bbuhrow@gmail.com                   =======
=======     Type help at any time, or quit to quit      =======
===============================================================
cached 78498 primes. pmax = 999983
 
>> nfs: checking for job file - nfs: number in job file matches input
nfs: checking for data file
nfs: no data file found
nfs: commencing nfs on c163: 804474833538445043318906753328990334994837889870237
61384546398726095316652633355563647611699968994602791321199534746391187067968458
49163688530204021522714077427337
nfs: found type: snfs
nfs: found size: 221
nfs: parsed lpbr = 29, lpba = 29, type = snfs, setting lpb = 29
nfs: guessing snfs difficulty 221 is roughly equal to gnfs difficulty 153
nfs: continuing with sieving at user specified special-q 15000000
nfs: commencing rational side lattice sieving over range: 15000500 - 15001000
nfs: commencing rational side lattice sieving over range: 15000000 - 15000500
Warning: Ignoring input line:
size: 221
Warning: Ignoring input line:
size: 221
 Warning:  lowering FB_bound to 15000499.
 Warning:  lowering FB_bound to 14999999.
total yield: 1057, q=15001001 (0.32842 sec/rel)
total yield: 1073, q=15000509 (0.34927 sec/rel)
found 2130 relations, need at least 44869960 (filtering ETA: 2263h 37m), continu
ing with sieving ...
 
***factors found***
 
***co-factor***
C163 = 8044748335384450433189067533289903349948378898702376138454639872609531665
26333555636476116999689946027913211995347463911870679684584916368853020402152271
4077427337
ans = 80447483353844504331890675332899033499483788987023761384546398726095316652
63335556364761169996899460279132119953474639118706796845849163688530204021522714
077427337
swellman is online now   Reply With Quote
Old 2012-11-07, 23:45   #11
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3·2,399 Posts
Default

Quote:
Originally Posted by swellman View Post
Posting my example, which still has an odd warning message about ignoring the size parameter, even though Yafu appears to use it.
That's because the warning is printed by GGNFS' lasieve, not by YAFU.
Dubslow is offline   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-1.34 bsquared YAFU 119 2015-11-05 16:24
Yafu bug. storflyt32 YAFU 2 2015-06-29 05:19
yafu-1.32.1 bsquared YAFU 21 2012-09-04 19:44

All times are UTC. The time now is 03:05.

Sat Nov 28 03:05:35 UTC 2020 up 79 days, 16 mins, 3 users, load averages: 0.97, 1.11, 1.10

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