yafu-1.33

[bsquared]

Now available.

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

Happy factoring!

[kar_bon]

The zip-file is not readable.

[bsquared]

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

thanks.

[swellman]

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...

[Dubslow]

Originally Posted by swellman

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.

Originally Posted by swellman

What's the formula for this estimate?

(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.

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;

Originally Posted by swellman

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.)

[swellman]

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.

[Dubslow]

Originally Posted by swellman

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.

[swellman]

Originally Posted by Dubslow

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?

[Dubslow]

Originally Posted by swellman

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 b². In the meantime, the bottom part of this post is the closest there is to documentation.

Originally Posted by swellman

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).

[swellman]

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

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

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

[Dubslow]

Originally Posted by swellman

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.