How I install YAFU onto my Ubuntu Machines

[bsquared]

Originally Posted by RedGolpe

Actually it didn't as the seg fault reappeared with new factorizations: see the following messages. As I said, it even fails with factor(2) which should be a good target for debugging: if I can help in any way, please let me know.

Oh, sorry. Didn't refresh the page before responding. I will take a look.

[EdH]

This is repeatable:

If I uninstall GMP 6.1.2 and install 6.2.0, YAFU fails:

$ ./yafu -v -v

03/24/20 14:48:31 v1.34.5 @ math20, System/Build Info: 
Using GMP-ECM 7.0.5-dev, Powered by GMP 6.2.0
detected Intel(R) Core(TM) i5-4570S CPU @ 2.90GHz
detected L1 = 32768 bytes, L2 = 6291456 bytes, CL = 64 bytes
measured cpu frequency ~= 2893.258220
using 1 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

>> factor(33727095233132290409342213138708322681737322487170896778164145844669592994743377)

fac: factoring 33727095233132290409342213138708322681737322487170896778164145844669592994743377
fac: using pretesting plan: normal
fac: no tune info: using qs/gnfs crossover of 95 digits
div: primes less than 10000
rho: x^2 + 3, starting 1000 iterations on C80 
rho: x^2 + 2, starting 1000 iterations on C80 
rho: x^2 + 1, starting 1000 iterations on C80 
pm1: starting B1 = 150K, B2 = gmp-ecm default on C80
fac: setting target pretesting digits to 24.62
fac: estimated sum of completed work is t0.00
fac: work done at B1=2000: 0 curves, max work = 30 curves
fac: 30 more curves at B1=2000 needed to get to t24.62
ecm: 32/32 curves on C80, B1=2K, B2=gmp-ecm default
fac: setting target pretesting digits to 24.62
fac: t15: 1.07
fac: t20: 0.04
fac: estimated sum of completed work is t15.19
fac: work done at B1=11000: 0 curves, max work = 74 curves
fac: 74 more curves at B1=11000 needed to get to t24.62
ecm: 76/76 curves on C80, B1=11K, B2=gmp-ecm default
fac: setting target pretesting digits to 24.62
fac: t15: 7.40
fac: t20: 1.06
fac: t25: 0.05
fac: estimated sum of completed work is t20.25
fac: work done at B1=50000: 0 curves, max work = 214 curves
fac: 187 more curves at B1=50000 needed to get to t24.62
ecm: 188/188 curves on C80, B1=50K, B2=gmp-ecm default, ETA: 0 sec 
fac: setting target pretesting digits to 24.62
fac: t15: 34.26
fac: t20: 10.02
fac: t25: 0.93
fac: t30: 0.06
fac: estimated sum of completed work is t24.64

starting SIQS on c80: 33727095233132290409342213138708322681737322487170896778164145844669592994743377
fb bounds: 85%
    small: 1024
    SPV: 35
    10bit: 96
    11bit: 168
    12bit: 304
    13bit: 536
    32k div 3: 688
    14bit: 960
    15bit: 1752
    med: 2512
    large: 14096
    all: 47184
start primes
    SPV: 241
    10bit: 1033
    11bit: 2089
    12bit: 4261
    13bit: 8317
    32k div 3: 10987
    14bit: 16451
    15bit: 32789
    med: 49307
    large: 327571

==== sieve params ====
n = 80 digits, 265 bits
factor base: 47184 primes (max prime = 1218601)
single large prime cutoff: 109674090 (90 * pmax)
double large prime range from 41 to 49 bits
double large prime range from 1484988397201 to 296611012458251
allocating 7 large prime slices of factor base
buckets hold 2048 elements
using SSE2 enabled 32k sieve core
sieve interval: 10 blocks of size 32768
polynomial A has ~ 10 factors
using multiplier of 1
using SPV correction of 21 bits, starting at offset 35
trial factoring cutoff at 87 bits

==== sieving in progress ( 4 threads):   47248 relations needed ====
====            Press ctrl-c to abort and save state            ====
Segmentation fault (core dumped)

If I uninstall 6.2.0 and reinstall 6.1.2, YAFU succeeds:

$ ./yafu -v -v

03/24/20 14:54:44 v1.34.5 @ math20, System/Build Info: 
Using GMP-ECM 7.0.5-dev, Powered by GMP 6.1.2
detected Intel(R) Core(TM) i5-4570S CPU @ 2.90GHz
detected L1 = 32768 bytes, L2 = 6291456 bytes, CL = 64 bytes
measured cpu frequency ~= 2893.276310
using 1 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

>> factor(33727095233132290409342213138708322681737322487170896778164145844669592994743377)

fac: factoring 33727095233132290409342213138708322681737322487170896778164145844669592994743377
fac: using pretesting plan: normal
fac: no tune info: using qs/gnfs crossover of 95 digits
div: primes less than 10000
rho: x^2 + 3, starting 1000 iterations on C80 
rho: x^2 + 2, starting 1000 iterations on C80 
rho: x^2 + 1, starting 1000 iterations on C80 
pm1: starting B1 = 150K, B2 = gmp-ecm default on C80
fac: setting target pretesting digits to 24.62
fac: estimated sum of completed work is t0.00
fac: work done at B1=2000: 0 curves, max work = 30 curves
fac: 30 more curves at B1=2000 needed to get to t24.62
ecm: 32/32 curves on C80, B1=2K, B2=gmp-ecm default
fac: setting target pretesting digits to 24.62
fac: t15: 1.07
fac: t20: 0.04
fac: estimated sum of completed work is t15.19
fac: work done at B1=11000: 0 curves, max work = 74 curves
fac: 74 more curves at B1=11000 needed to get to t24.62
ecm: 76/76 curves on C80, B1=11K, B2=gmp-ecm default
fac: setting target pretesting digits to 24.62
fac: t15: 7.40
fac: t20: 1.06
fac: t25: 0.05
fac: estimated sum of completed work is t20.25
fac: work done at B1=50000: 0 curves, max work = 214 curves
fac: 187 more curves at B1=50000 needed to get to t24.62
ecm: 188/188 curves on C80, B1=50K, B2=gmp-ecm default, ETA: 0 sec 
fac: setting target pretesting digits to 24.62
fac: t15: 34.26
fac: t20: 10.02
fac: t25: 0.93
fac: t30: 0.06
fac: estimated sum of completed work is t24.64

starting SIQS on c80: 33727095233132290409342213138708322681737322487170896778164145844669592994743377
fb bounds: 85%
    small: 1024
    SPV: 35
    10bit: 96
    11bit: 168
    12bit: 304
    13bit: 536
    32k div 3: 688
    14bit: 960
    15bit: 1752
    med: 2512
    large: 14096
    all: 47184
start primes
    SPV: 241
    10bit: 1033
    11bit: 2089
    12bit: 4261
    13bit: 8317
    32k div 3: 10987
    14bit: 16451
    15bit: 32789
    med: 49307
    large: 327571

==== sieve params ====
n = 80 digits, 265 bits
factor base: 47184 primes (max prime = 1218601)
single large prime cutoff: 109674090 (90 * pmax)
double large prime range from 41 to 49 bits
double large prime range from 1484988397201 to 296611012458251
allocating 7 large prime slices of factor base
buckets hold 2048 elements
using SSE2 enabled 32k sieve core
sieve interval: 10 blocks of size 32768
polynomial A has ~ 10 factors
using multiplier of 1
using SPV correction of 21 bits, starting at offset 35
trial factoring cutoff at 87 bits

==== sieving in progress ( 4 threads):   47248 relations needed ====
====            Press ctrl-c to abort and save state            ====
36150 rels found: 16473 full + 19677 from 343453 partial, (13629.81 rels/sec)

sieving required 64261 total polynomials
trial division touched 6551746 sieve locations out of 42114088960
squfof: 0 failures, 218488 attempts, 1769438 outside range, 1239973 prp, 207029 useful
total reports = 6551746, total surviving reports = 4092848
total blocks sieved = 1285220,avg surviving reports per block = 3.18
QS elapsed time = 30.9348 seconds.

==== post processing stage (msieve-1.38) ====
begin with 424829 relations
reduce to 90315 relations in 9 passes
attempting to read 90315 relations
recovered 90315 relations
recovered 48552 polynomials
attempting to build 48489 cycles
found 48489 cycles in 4 passes
distribution of cycle lengths:
   length 1 : 19202
   length 2 : 14652
   length 3 : 8320
   length 4 : 3749
   length 5 : 1543
   length 6 : 660
   length 7 : 251
   length 9+: 112
largest cycle: 12 relations
matrix is 47184 x 48489 (8.7 MB) with weight 1892112 (39.02/col)
sparse part has weight 1892112 (39.02/col)
filtering completed in 4 passes
matrix is 36883 x 36947 (6.8 MB) with weight 1474089 (39.90/col)
sparse part has weight 1474089 (39.90/col)
saving the first 48 matrix rows for later
matrix is 36835 x 36947 (5.7 MB) with weight 1235125 (33.43/col)
sparse part has weight 1114954 (30.18/col)
matrix includes 64 packed rows
using block size 14778 for processor cache size 6144 kB
commencing Lanczos iteration
memory use: 4.9 MB
lanczos halted after 584 iterations (dim = 36831)
recovered 14 nontrivial dependencies
Lanczos elapsed time = 2.7926 seconds.
Sqrt elapsed time = 0.0323 seconds.
SIQS elapsed time = 33.7602 seconds.
pretesting / qs ratio was 0.19
Total factoring time = 40.3479 seconds

***factors found***

P40 = 3104758941649954796179093599696620654807
P41 = 10863031838216972467057273004441996191511

ans = 1

>>

I did not reinstall GMP-ECM or recompile msieve. Both are latest (7.0.5 and 1030), though they were compiled with GMP 6.1.2 installed.

I compiled YAFU with no options; (make x86_64).

I didn't try the wip branch today, but I haven't been able to compile it at all on this machine for quite some time. I will try to play with this some more soon.

[bsquared]

Originally Posted by EdH

This is repeatable:

If I uninstall GMP 6.1.2 and install 6.2.0, YAFU fails:

I did not reinstall GMP-ECM or recompile msieve. Both are latest (7.0.5 and 1030), though they were compiled with GMP 6.1.2 installed.

I compiled YAFU with no options; (make x86_64).

I didn't try the wip branch today, but I haven't been able to compile it at all on this machine for quite some time. I will try to play with this some more soon.

Thank you very much. Looks like something is incompatible with gmp 6.2.0. I would imagine whatever this is, is there no matter the yafu version. So until I figure out what changed, going back to gmp 6.1.2 would probably be the way to go.

[RedGolpe]

Originally Posted by bsquared

Thank you very much. Looks like something is incompatible with gmp 6.2.0. I would imagine whatever this is, is there no matter the yafu version. So until I figure out what changed, going back to gmp 6.1.2 would probably be the way to go.

Does factor(2) even invoke GMP?

[bsquared]

Originally Posted by RedGolpe

Does factor(2) even invoke GMP?

All inputs get converted into mpz_t's (GMP's signed-integer data type). And it has no way of knowing the input is a '2' except by running trial division (on the mpt_z) or is_probab_prime_p() (on the mpz_t).

So, yes.

[RedGolpe]

I tried factor(p) on primes of various size on my almost-working build. It apparently segfaults for all primes below 10000 and succeeds for all primes above. It also seems to segfault for all factorizations whose input factors in such small primes, and not otherwise. That would explain why "tune" succeeds, that being focused on products of two large primes. This hypothesis is also consistent with my previous segfaults, including the C89 divisible by 5.

[bsquared]

Originally Posted by RedGolpe

I tried factor(p) on primes of various size on my almost-working build. It apparently segfaults for all primes below 10000 and succeeds for all primes above. It also seems to segfault for all factorizations whose input factors in such small primes, and not otherwise. That would explain why "tune" succeeds, that being focused on products of two large primes. This hypothesis is also consistent with my previous segfaults, including the C89 divisible by 5.

Thank you, this is extremely helpful! It seems to isolate the problem to when trial division succeeds.

[RedGolpe]

I just discovered that factor(2^308+97) also fails but has no factors below 10000. However, it fails with

>> factor(2^308+97)
fac: factoring 521481209941628438084722096232800809229175908778479680162851955034721612739414196782949728353
fac: using pretesting plan: normal
fac: using specified qs/gnfs crossover of 93 digits
fac: using specified qs/snfs crossover of 75 digits
div: primes less than 10000
fmt: 1000000 iterations
rho: x^2 + 3, starting 200 iterations on C93
rho: found prp6 factor = 785033
rho: x^2 + 3, starting 200 iterations on C87
rho: x^2 + 2, starting 200 iterations on C87
rho: x^2 + 1, starting 200 iterations on C87
nfs: searching for brent special forms...
nfs: input divides 2^308 + 97
Segmentation fault (core dumped)

while factor(2) fails with

>> factor(2)
fac: factoring 2
fac: using pretesting plan: normal
fac: using specified qs/gnfs crossover of 93 digits
fac: using specified qs/snfs crossover of 75 digits
div: primes less than 10000
Segmentation fault (core dumped)

[EdH]

For the wip branch I have to change the "CC = gcc-7.3.0" to "CC = gcc" since my gcc is "gcc version 7.5.0 (Ubuntu 7.5.0-3ubuntu1~18.04)."

With the wip branch I get the following with either version of GMP:

factor/rho.o: In function `_trail_zcnt64':
/home/math20/Math/yafuwip2/include/arith.h:102: undefined reference to `_BitScanForward64'
/home/math20/Math/yafuwip2/include/arith.h:102: undefined reference to `_BitScanForward64'
factor/squfof.o: In function `_lead_zcnt64':
/home/math20/Math/yafuwip2/include/arith.h:110: undefined reference to `_BitScanReverse64'
arith/arith3.o: In function `_trail_zcnt64':
/home/math20/Math/yafuwip2/include/arith.h:102: undefined reference to `_BitScanForward64'
/home/math20/Math/yafuwip2/include/arith.h:102: undefined reference to `_BitScanForward64'
/home/math20/Math/yafuwip2/include/arith.h:102: undefined reference to `_BitScanForward64'
arith/monty.o: In function `mulmod128':
/home/math20/Math/yafuwip2/arith/monty.c:416: undefined reference to `_umul128'
/home/math20/Math/yafuwip2/arith/monty.c:423: undefined reference to `_umul128'
/home/math20/Math/yafuwip2/arith/monty.c:423: undefined reference to `_addcarry_u64'
/home/math20/Math/yafuwip2/arith/monty.c:424: undefined reference to `_addcarry_u64'
/home/math20/Math/yafuwip2/arith/monty.c:428: undefined reference to `_umul128'
/home/math20/Math/yafuwip2/arith/monty.c:428: undefined reference to `_addcarry_u64'
/home/math20/Math/yafuwip2/arith/monty.c:429: undefined reference to `_umul128'
/home/math20/Math/yafuwip2/arith/monty.c:429: undefined reference to `_addcarry_u64'
/home/math20/Math/yafuwip2/arith/monty.c:430: undefined reference to `_addcarry_u64'
/home/math20/Math/yafuwip2/arith/monty.c:431: undefined reference to `_addcarry_u64'
/home/math20/Math/yafuwip2/arith/monty.c:440: undefined reference to `_umul128'
/home/math20/Math/yafuwip2/arith/monty.c:440: undefined reference to `_addcarry_u64'
/home/math20/Math/yafuwip2/arith/monty.c:441: undefined reference to `_addcarry_u64'
/home/math20/Math/yafuwip2/arith/monty.c:449: undefined reference to `_umul128'
/home/math20/Math/yafuwip2/arith/monty.c:449: undefined reference to `_addcarry_u64'
/home/math20/Math/yafuwip2/arith/monty.c:450: undefined reference to `_addcarry_u64'
/home/math20/Math/yafuwip2/arith/monty.c:455: undefined reference to `_umul128'
/home/math20/Math/yafuwip2/arith/monty.c:455: undefined reference to `_addcarry_u64'
/home/math20/Math/yafuwip2/arith/monty.c:456: undefined reference to `_umul128'
/home/math20/Math/yafuwip2/arith/monty.c:456: undefined reference to `_addcarry_u64'
/home/math20/Math/yafuwip2/arith/monty.c:457: undefined reference to `_addcarry_u64'
/home/math20/Math/yafuwip2/arith/monty.c:458: undefined reference to `_addcarry_u64'
top/eratosthenes/primes.o: In function `_trail_zcnt64':
/home/math20/Math/yafuwip2/include/arith.h:102: undefined reference to `_BitScanForward64'
collect2: error: ld returned 1 exit status
Makefile:359: recipe for target 'all' failed
make: *** [all] Error 1

If I compile the trunk branch of YAFU with USE_AVX2=1, I also get a segfault in SIQS:

$ ./yafu -v -v


03/24/20 16:47:09 v1.34.5 @ math20, System/Build Info: 
Using GMP-ECM 7.0.5-dev, Powered by GMP 6.1.2
detected Intel(R) Core(TM) i5-4570S CPU @ 2.90GHz
detected L1 = 32768 bytes, L2 = 6291456 bytes, CL = 64 bytes
measured cpu frequency ~= 2893.255040
using 1 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


>> factor(33727095233132290409342213138708322681737322487170896778164145844669592994743377)

fac: factoring 33727095233132290409342213138708322681737322487170896778164145844669592994743377
fac: using pretesting plan: normal
fac: no tune info: using qs/gnfs crossover of 95 digits
div: primes less than 10000
rho: x^2 + 3, starting 1000 iterations on C80 
rho: x^2 + 2, starting 1000 iterations on C80 
rho: x^2 + 1, starting 1000 iterations on C80 
pm1: starting B1 = 150K, B2 = gmp-ecm default on C80
fac: setting target pretesting digits to 24.62
fac: estimated sum of completed work is t0.00
fac: work done at B1=2000: 0 curves, max work = 30 curves
fac: 30 more curves at B1=2000 needed to get to t24.62
ecm: 32/32 curves on C80, B1=2K, B2=gmp-ecm default
fac: setting target pretesting digits to 24.62
fac: t15: 1.07
fac: t20: 0.04
fac: estimated sum of completed work is t15.19
fac: work done at B1=11000: 0 curves, max work = 74 curves
fac: 74 more curves at B1=11000 needed to get to t24.62
ecm: 76/76 curves on C80, B1=11K, B2=gmp-ecm default
fac: setting target pretesting digits to 24.62
fac: t15: 7.40
fac: t20: 1.06
fac: t25: 0.05
fac: estimated sum of completed work is t20.25
fac: work done at B1=50000: 0 curves, max work = 214 curves
fac: 187 more curves at B1=50000 needed to get to t24.62
ecm: 188/188 curves on C80, B1=50K, B2=gmp-ecm default, ETA: 0 sec 
fac: setting target pretesting digits to 24.62
fac: t15: 34.26
fac: t20: 10.02
fac: t25: 0.93
fac: t30: 0.06
fac: estimated sum of completed work is t24.64

starting SIQS on c80: 33727095233132290409342213138708322681737322487170896778164145844669592994743377
fb bounds: 85%
    small: 1024
    SPV: 35
    10bit: 96
    11bit: 168
    12bit: 304
    13bit: 536
    32k div 3: 688
    14bit: 960
    15bit: 1752
    med: 2512
    large: 14096
    all: 47184
start primes
    SPV: 241
    10bit: 1033
    11bit: 2089
    12bit: 4261
    13bit: 8317
    32k div 3: 10987
    14bit: 16451
    15bit: 32789
    med: 49307
    large: 327571

==== sieve params ====
n = 80 digits, 265 bits
factor base: 47184 primes (max prime = 1218601)
single large prime cutoff: 109674090 (90 * pmax)
double large prime range from 41 to 49 bits
double large prime range from 1484988397201 to 296611012458251
allocating 7 large prime slices of factor base
buckets hold 2048 elements
using AVX2 enabled 32k sieve core
sieve interval: 10 blocks of size 32768
polynomial A has ~ 10 factors
using multiplier of 1
using SPV correction of 21 bits, starting at offset 35
trial factoring cutoff at 87 bits

==== sieving in progress ( 4 threads):   47248 relations needed ====
====            Press ctrl-c to abort and save state            ====
Segmentation fault (core dumped)

USE_SSE41=1 works fine.

[bsquared]

gmp-6.2.0 has a new lazy allocation strategy that makes it even more dangerous to access mpz_t internals directly (like _mp_d). I was bad and had some code accessing internals... that's what was causing the problem.

Should be fixed now in /branches/wip r382. I tested the following makes in gcc 7.3.0

NFS=1 USE_SSE41=1
NFS=1 USE_AVX2=1
NFS=1 USE_AVX2=1 USE_BMI2=1
NFS=1 USE_AVX2=1 SKYLAKEX=1

[RedGolpe]

I tried again but I can't manage "make" to work, apparently with any combination of the flags NFS=1 SKYLAKEX=1 USE_BMI2=1 USE_AVX2=1. At least, all tries with various flags seem to produce the same error:

redgolpe@c2018:~/yafu$ make NFS=1 SKYLAKEX=1 USE_BMI2=1 USE_AVX2=1
gcc -g -DUSE_BMI2 -DUSE_AVX2 -DUSE_AVX512F -DUSE_AVX512BW -march=skylake-avx512  -mbmi2 -mbmi -DUSE_BMI2 -DUSE_AVX2 -DUSE_SSE41  -mavx2  -DUSE_SSE41 -m64 -msse4.1 -DUSE_NFS -O2 -fomit-frame-pointer -Wall  -I. -Iinclude -Itop/aprcl -Itop/ -I../msieve/zlib -I../gmp/include -I../gmp-ecm/include/ -c -o factor/qs/msieve/lanczos.o factor/qs/msieve/lanczos.c
In file included from include/qs.h:30:0,
                 from factor/qs/msieve/lanczos.c:20:
include/cofactorize.h:1:1: error: version control conflict marker in file
 <<<<<<< .mine
 ^~~~~~~
include/cofactorize.h:228:1: error: expected identifier or ‘(’ before ‘||’ token
 ||||||| .r0
 ^~
In file included from factor/qs/msieve/lanczos.c:20:0:
include/qs.h:182:3: warning: data definition has no type or storage class
 } qs_params;
   ^~~~~~~~~
include/qs.h:182:3: warning: type defaults to ‘int’ in declaration of ‘qs_params’ [-Wimplicit-int]
include/qs.h:824:1: error: unknown type name ‘qs_params’; did you mean ‘tiny_qs_params’?
 qs_params sieve_params;
 ^~~~~~~~~
 tiny_qs_params
factor/qs/msieve/lanczos.c: In function ‘yafu_block_lanczos_core’:
factor/qs/msieve/lanczos.c:1245:5: warning: null argument where non-null required (argument 1) [-Wnonnull]
     fprintf(NULL, "linear algebra completed %u "
     ^~~~~~~
factor/qs/msieve/lanczos.c: In function ‘yafu_read_lanczos_state’:
factor/qs/msieve/lanczos.c:854:2: warning: ignoring return value of ‘fread’, declared with attribute warn_unused_result [-Wunused-result]
  fread(&read_n, sizeof(uint32), (size_t)1, dump_fp);
  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Makefile:369: recipe for target 'factor/qs/msieve/lanczos.o' failed
make: *** [factor/qs/msieve/lanczos.o] Error 1