YAFU 2.0

[bsquared]

New version 2.04 is now available.

Includes two improvements to yafu's QS:

1) Now using the poly formulation Q(x) = (2ax + b)^2 - kN whenever possible (if kN == 1 mod 8). For ~85% of inputs this gives about a 10% speedup.
2) Found some new AVX512 optimizations to the bucket sort: linux systems (and WSL2 windows systems) that are AVX-512 capable should be about 15-20% faster (!)

With those two improvements my benchmark numbers now run from 21 to 30% faster. Including a c80 in well under a minute! (46 seconds, down from 62 seconds, on my i7-7800X)

The windows version doesn't get all of these improvements yet because visual studio doesn't like the compressstoreu instruction. I may need to update visual studio or file a bug report or something.

Anyway, happy factoring!

[Plutie]

I recently compiled a fresh build of YAFU, but am having issues when trying to factor via SNFS with a pre-made polynomial.

Log:

YAFU Version 2.03
Built with GCC 9
Using GMP-ECM 7.0.5-dev, Powered by GMP 6.2.1
Detected AMD Ryzen 5 5600X 6-Core Processor
Detected L1 = 32768 bytes, L2 = 33554432 bytes, CL = 64 bytes
Using 1 random witness for Rabin-Miller PRP checks
Cached 664579 primes; max prime is 9999991

===============================================================
======= Welcome to YAFU (Yet Another Factoring Utility) =======
=======             bbuhrow@gmail.com                   =======
=======     Type help at any time, or quit to quit      =======
===============================================================

>> nfs(508155924947538816161101635487366611969955965840021547875500594140402111454201939923927956969296837060051327267616455978442987911081313892049188185868241575553249)
nfs: checking for job file - job file found, testing for matching input
input from file = 508155924947538816161101635487366611969955965840021547875500594140402111454201939923927956969296837060051327267616455978442987911081313892049188185868241575553249
input to yafu = 508155924947538816161101635487366611969955965840021547875500594140402111454201939923927956969296837060051327267616455978442987911081313892049188185868241575553249
input matches with multiple of 1
nfs: number in job file matches input
nfs: checking for data file
nfs: no data file found
nfs: commencing nfs on c162: 508155924947538816161101635487366611969955965840021547875500594140402111454201939923927956969296837060051327267616455978442987911081313892049188185868241575553249
nfs: resumesieve; last_spq = 0, nfs_phases = 0
nfs: found m: 50000000000000000000000000000000000000
nfs: found c[5]: 196
nfs: found c[0]: -5
nfs: found skew: 0.480000
nfs: found type: snfs
nfs: initializing snfs poly
nfs: parsed lpbr = 28, lpba = 28
nfs: detected snfs job but no snfs difficulty
nfs: using m and poly coefficients to compute difficulty
nfs: snfs difficulty: 39.991226
nfs: checking degree 5 poly
nfs: analyzing poly:
Segmentation fault

Content of nfs.job:

n: 508155924947538816161101635487366611969955965840021547875500594140402111454201939923927956969296837060051327267616455978442987911081313892049188185868241575553249
m: 50000000000000000000000000000000000000
deg: 5
c5: 196
c0: -5
skew: 0.48
# Murphy_E = 3.279e-11
type: snfs
lss: 1
rlim: 10600000
alim: 10600000
lpbr: 28
lpba: 28
mfbr: 54
mfba: 54
rlambda: 2.5
alambda: 2.5

Another thing to note is that the SNFS difficulty calculation seems to be wrong when missing some coefficients.

[bsquared]

I can take a look at where it's going wrong. In the meantime, if I comment out m: and put in the rational coefficients instead it works:

n: 508155924947538816161101635487366611969955965840021547875500594140402111454201939923927956969296837060051327267616455978442987911081313892049188185868241575553249
# m: 50000000000000000000000000000000000000
deg: 5
c5: 196
c0: -5
Y1: -1
Y0: 50000000000000000000000000000000000000
skew: 0.48
type: snfs
lss: 1
rlim: 10600000
alim: 10600000
lpbr: 28
lpba: 28
mfbr: 54
mfba: 54
rlambda: 2.5
alambda: 2.5

nfs: commencing nfs on c162: 508155924947538816161101635487366611969955965840021547875500594140402111454201939923927956969296837060051327267616455978442987911081313892049188185868241575553249
nfs: resumesieve; last_spq = 0, nfs_phases = 0
nfs: found c[5]: 196
nfs: found c[0]: -5
nfs: found Y1: -1
nfs: found Y0: 50000000000000000000000000000000000000
nfs: found skew: 0.480000
nfs: found type: snfs
nfs: initializing snfs poly
nfs: parsed lpbr = 28, lpba = 28
nfs: detected snfs job but no snfs difficulty
nfs: using m and poly coefficients to compute difficulty
nfs: snfs difficulty: 39.991226
nfs: checking degree 5 poly
nfs: analyzing poly:
nfs: anorm = -2.388308e+32, rnorm = 4.180462e+44, size: 2.193000e-13, alpha = 1.196000e+00, murphyE = 3.279000e-11
gen: anorm: -2.39e+32, rnorm: 4.18e+44, ratio: 1.75e+12, log10(ratio) = 12.24
nfs: snfs skewed difficulty: 42.439853
nfs: optimizing skew
nfs: found better skew: 0.484800 with murphy score 3.281000e-11
nfs: found better skew: 0.489600 with murphy score 3.282000e-11
nfs: found better skew: 0.494400 with murphy score 3.284000e-11
nfs: found better skew: 0.499200 with murphy score 3.285000e-11
nfs: found better skew: 0.504000 with murphy score 3.286000e-11
nfs: found better skew: 0.508800 with murphy score 3.287000e-11
nfs: found better skew: 0.513600 with murphy score 3.289000e-11
nfs: found better skew: 0.518400 with murphy score 3.290000e-11
nfs: found better skew: 0.523200 with murphy score 3.291000e-11
nfs: found better skew: 0.528000 with murphy score 3.292000e-11
nfs: found better skew: 0.532800 with murphy score 3.293000e-11
nfs: found better skew: 0.537600 with murphy score 3.294000e-11
nfs: found better skew: 0.547200 with murphy score 3.295000e-11
nfs: found better skew: 0.552000 with murphy score 3.296000e-11
nfs: found better skew: 0.556800 with murphy score 3.297000e-11
nfs: found better skew: 0.561600 with murphy score 3.298000e-11
nfs: found better skew: 0.571200 with murphy score 3.299000e-11
nfs: found better skew: 0.580800 with murphy score 3.300000e-11
nfs: found better skew: 0.585600 with murphy score 3.301000e-11
nfs: found better skew: 0.600000 with murphy score 3.302000e-11
nfs: found better skew: 0.609600 with murphy score 3.303000e-11
nfs: found better skew: 0.624000 with murphy score 3.304000e-11
nfs: found better skew: 0.643200 with murphy score 3.305000e-11
nfs: guessing snfs difficulty 42 is roughly equal to gnfs difficulty 53
nfs: creating ggnfs job parameters for input of size 53
nfs: job file is missing params, filling them
nfs: continuing with sieving - could not determine last special q; using default startq
nfs: commencing rational side lattice sieving over range: 5300000 - 5302000
syscmd: ../../ggnfs-bin/gnfs-lasieve4I11e -v -f 5300000 -c 2000 -o rels0.dat -n 0 -r nfs.job
gnfs-lasieve4I11e (with asm64): L1_BITS=15, SVN $Revision: 399 $
Warning:  lowering FB_bound to 5299999.
FBsize 702099+0 (deg 5), 367899+0 (deg 1)
total yield: 353, q=5300857 (0.03694 sec/rel) ^C

Clearly having issues figuring out difficulty, but since the parameters are in there already that mostly doesn't matter. You can just tell it which siever to use and I think it will work, e.g.:

./yafu "nfs(508155924947538816161101635487366611969955965840021547875500594140402111454201939923927956969296837060051327267616455978442987911081313892049188185868241575553249)" -v -v -siever 13