Version 2.04 uploaded
 

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!

Segfault upon starting SNFS
 

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

Log: [CODE]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[/CODE]

Content of nfs.job:
[CODE]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[/CODE]

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

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:

[CODE]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


[/CODE]


[CODE]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
[/CODE]

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

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

Windows Ver 2.04 SIQS Bug
 

Using Windows executable ver. 2.04, SIQS has problems:

[CODE]08/09/21 08:21:19, ****************************
08/09/21 08:21:19, Starting factorization of 105393989787970375262364798207451884611473765049956049673829221285271966197423217847983687608092010532144015094441669842637319335236412609289116384759967578759
08/09/21 08:21:19, using pretesting plan: normal
08/09/21 08:21:19, using tune info for qs/gnfs crossover
08/09/21 08:21:19, ****************************
08/09/21 08:21:19, rho: x^2 + 3, starting 1000 iterations on C159
08/09/21 08:21:19, rho: x^2 + 2, starting 1000 iterations on C159
08/09/21 08:21:19, rho: x^2 + 1, starting 1000 iterations on C159
08/09/21 08:21:20, pm1: starting B1 = 150K, B2 = gmp-ecm default on C159
08/09/21 08:21:20, current ECM pretesting depth: 0.00
08/09/21 08:21:20, scheduled 30 curves at B1=2000 toward target pretesting depth of 48.92
08/09/21 08:21:20, Finished 30 curves using GMP-ECM method on C159 input, B1=2k, B2=gmp-ecm default
08/09/21 08:21:20, current ECM pretesting depth: 15.18
08/09/21 08:21:20, scheduled 74 curves at B1=11000 toward target pretesting depth of 48.92
08/09/21 08:21:26, Finished 74 curves using GMP-ECM method on C159 input, B1=11k, B2=gmp-ecm default
08/09/21 08:21:26, current ECM pretesting depth: 20.24
08/09/21 08:21:26, scheduled 214 curves at B1=50000 toward target pretesting depth of 48.92
08/09/21 08:22:29, Finished 214 curves using GMP-ECM method on C159 input, B1=50k, B2=gmp-ecm default
08/09/21 08:22:29, pm1: starting B1 = 3750K, B2 = gmp-ecm default on C159
08/09/21 08:22:31, current ECM pretesting depth: 25.33
08/09/21 08:22:31, scheduled 430 curves at B1=250000 toward target pretesting depth of 48.92
08/09/21 08:32:02, Finished 430 curves using GMP-ECM method on C159 input, B1=250k, B2=gmp-ecm default
08/09/21 08:32:02, pm1: starting B1 = 15M, B2 = gmp-ecm default on C159
08/09/21 08:32:09, current ECM pretesting depth: 30.45
08/09/21 08:32:09, scheduled 904 curves at B1=1000000 toward target pretesting depth of 48.92
08/09/21 08:51:40, prp32 = 81818626235929905372894171191449 (curve 222 stg2 B1=1000000 sigma=3833225760 thread=0)
08/09/21 08:51:40, Finished 221 curves using GMP-ECM method on C159 input, B1=1M, B2=gmp-ecm default
08/09/21 08:51:40, current ECM pretesting depth: 31.68
08/09/21 08:51:40, scheduled 683 curves at B1=1000000 toward target pretesting depth of 39.08
08/09/21 09:06:41, prp30 = 287063003181080966701377441473 (curve 222 stg2 B1=1000000 sigma=2084237989 thread=0)
08/09/21 09:06:41, Finished 221 curves using GMP-ECM method on C127 input, B1=1M, B2=gmp-ecm default
08/09/21 09:06:41, final ECM pretested depth: 32.90
08/09/21 09:06:41, scheduler: switching to sieve method
08/09/21 09:06:42, starting SIQS on c97: 4487313770523153739495208002033098434359404539272558781592283264158439136945627929018162116601567
08/09/21 09:06:42, random seed: 380728400
08/09/21 09:06:42, ==== sieve params ====
08/09/21 09:06:42, n = 99 digits, 328 bits
08/09/21 09:06:42, factor base: 102912 primes (max prime = 2823973)
08/09/21 09:06:42, single large prime cutoff: 409476085 (145 * pmax)
08/09/21 09:06:42, double large prime range from 7974823504729 to 8562938075287819
08/09/21 09:06:42, DLP MFB = 1.85
08/09/21 09:06:42, allocating 9 large prime slices of factor base
08/09/21 09:06:42, buckets hold 2048 elements
08/09/21 09:06:42, large prime hashtables have 1622016 bytes
08/09/21 09:06:42, using AVX2 enabled 32k sieve core
08/09/21 09:06:42, sieve interval: 11 blocks of size 32768
08/09/21 09:06:42, polynomial A has ~ 13 factors
08/09/21 09:06:42, using multiplier of 103
08/09/21 09:06:42, using multiplier of 103
08/09/21 09:06:42, using Q2(x) polynomials for kN mod 8 = 1
08/09/21 09:06:42, using SPV correction of 21 bits, starting at offset 36
08/09/21 09:06:42, trial factoring cutoff at 98 bits
08/09/21 09:06:42, ==== sieving started ( 6 threads) ====
08/09/21 09:31:29, trial division touched 164355364 sieve locations out of 1512672657408
08/09/21 09:31:29, total reports = 164355364, total surviving reports = 43553883
08/09/21 09:31:29, total blocks sieved = 46163106, avg surviving reports per block = 0.94
08/09/21 09:31:29, dlp-ecm: 131 failures, 1685998 attempts, 34424793 outside range, 7038997 prp, 1342823 useful
08/09/21 09:31:29, 103416 relations found: 26955 full + 76461 from 1719963 partial, using 2098323 polys (1900 A polys)
08/09/21 09:31:29, on average, sieving found 0.83 rels/poly and 1174.44 rels/sec
08/09/21 09:31:29, trial division touched 164355364 sieve locations out of 1512672657408
08/09/21 09:31:29, ==== post processing stage (msieve-1.38) ====
08/09/21 09:31:29, QS elapsed time = 1487.4595 seconds.
08/09/21 09:31:30, begin singleton removal with 1746918 relations
08/09/21 09:31:31, reduce to 266460 relations in 12 passes
08/09/21 09:31:31, failed to read relation 8
08/09/21 09:31:31, failed to read relation 190

** numerous failed to read relation lines

08/09/21 09:31:35, failed to read relation 266199
08/09/21 09:31:35, recovered 263590 relations
08/09/21 09:31:35, recovered 247915 polynomials
08/09/21 09:31:35, attempting to build 100566 cycles
08/09/21 09:31:35, found 100566 cycles from 263590 relations in 6 passes
08/09/21 09:31:35, distribution of cycle lengths:
08/09/21 09:31:35, length 1 : 26563
08/09/21 09:31:35, length 2 : 18090
08/09/21 09:31:35, length 3 : 16887
08/09/21 09:31:35, length 4 : 13215
08/09/21 09:31:35, length 5 : 9817
08/09/21 09:31:35, length 6 : 6261
08/09/21 09:31:35, length 7 : 4166
08/09/21 09:31:35, length 9+: 5567
08/09/21 09:31:35, largest cycle: 25 relations
08/09/21 09:31:35, matrix is 102912 x 100566 (29.1 MB) with weight 6836076 (67.98/col)
08/09/21 09:31:35, sparse part has weight 6836076 (67.98/col)
08/09/21 09:31:36, filtering completed in 2 passes
08/09/21 09:31:36, matrix is 96687 x 94802 (28.1 MB) with weight 6606297 (69.69/col)
08/09/21 09:31:36, sparse part has weight 6606297 (69.69/col)
08/09/21 09:31:36, matrix must have more columns than rows
08/09/21 09:31:38, begin singleton removal with 1746918 relations
08/09/21 09:31:39, reduce to 266460 relations in 12 passes
08/09/21 09:31:39, failed to read relation 8
08/09/21 09:31:39, failed to read relation 190
[/CODE]

SIQS then repeats over and over until the process is killed.

Thanks, it was a very silly mistake on my part. I didn't do enough testing.

2.05 is now available.

Yafu bug?
 

I downloaded the most recent version 2.05 for Windows. That version is still crashing for me. When I try to run it as yafu-x64.exe, it will open to ">>" where you can enter a command such as factor(123456) but it crashes before I can enter anything.

Ver. 2.05 works fine (so far) on my Windows 10 i7 laptop where I had the SIQS bug with ver. 2.04.

[QUOTE=bsquared;585347]Thanks, it was a very silly mistake on my part. I didn't do enough testing.

2.05 is now available.[/QUOTE]I am being especially dumb today.

The sourceforge version is stuck at 1.34.

Where is 2.05 to be found?

Thanks, Paul

[URL="http://github.com/bbuhrow/yafu/blob/master/yafu-x64.exe"]Here[/URL] it is. :smile:

[QUOTE=johnadam74;585381]I downloaded the most recent version 2.05 for Windows. That version is still crashing for me. When I try to run it as yafu-x64.exe, it will open to ">>" where you can enter a command such as factor(123456) but it crashes before I can enter anything.[/QUOTE]

Can you give me any more info about your cpu (intel/amd model number)? If you can run with -v or -vproc that output would help.

[QUOTE=kruoli;585405][URL="http://github.com/bbuhrow/yafu/blob/master/yafu-x64.exe"]Here[/URL] it is. :smile:[/QUOTE]

Hey that's my line! :smile:

Hi Ben

I spent some time today aligning all the constituent parts of the YAFU Visual Studio 2019 build for windows X64 to use the Microsoft static runtime libraries and I now have a successful build of YAFU. I have tested it on Windows 11 (beta) with the Quadro T2000 GPU on my laptop and all seems to work as expected.

It is available here (yafu, ysieve and ytools):

[url]https://github.com/BrianGladman?tab=repositories[/url]

The build is in the build.vs subdirectory, not build.vc19 (which does not build), as I am in the process of moving it to Visual Studio 2022.

Sadly the build for the siqs_demo project fails because it cannot find these symbols:

1>calc.obj : error LNK2001: unresolved external symbol siqsbench
1>calc.obj : error LNK2001: unresolved external symbol smallmpqs
1>calc.obj : error LNK2001: unresolved external symbol SIQS
1>siqs_demo.obj : error LNK2001: unresolved external symbol get_computer_info

I would be grateful for your advice on where these should be available.