Discussion related to cado-nfs

[hermann@stamm-wilbrandt.de]

I did factor RSA-110
https://en.wikipedia.org/wiki/RSA_numbers#RSA-110

with cado-nfs.py on AMD 7600X CPU with 64bit Ubuntu 22.04 Desktop in 
less than 16 minutes:
./cado-nfs.py 
35794234179725868774991807832568455403003778024228226193532908190484670252364677411513516111204504060317568667

Here is the part corresponding to failing part further below:
...
Linear Algebra: mksol: N=4517 ; ETA (N=4608): Wed Jul 12 08:49:33 2023 
[0.005 s/iter]
Complete Factorization / Discrete logarithm: Linear Algebra
Linear Algebra: Total cpu/real time for bwc: 378.89/69.72
Linear Algebra: Aggregate statistics:
Linear Algebra: Krylov: CPU time 225.9, WCT time 40.3, iteration CPU 
time 0, COMM 0.0, cpu-wait 0.0, comm-wait 0.0 (9088 iterations)
Linear Algebra: Lingen CPU time 15.91, WCT time 3.3
Linear Algebra: Mksol: CPU time 126.28,  WCT time 22.67, iteration CPU 
time 0, COMM 0.0, cpu-wait 0.0, comm-wait 0.0 (4608 iterations)
Quadratic Characters: Starting
Complete Factorization / Discrete logarithm: Quadratic Characters
Quadratic Characters: Total cpu/real time for characters: 5.85/1.47769
Square Root: Starting
...


On my Raspberry Pi400 (Cortex A72 CPU with 4 cores) with Debian based 
64bit PiOS it fails. Here the failing part corresponding to previous 
part:
...
Info:Linear Algebra: mksol: N=4578 ; ETA (N=4608): Wed Jul 12 03:58:54 
2023 [0.285 s/iter]
Info:Complete Factorization / Discrete logarithm: Linear Algebra
Info:Linear Algebra: Total cpu/real time for bwc: 14758.9/4147.33
Info:Linear Algebra: Aggregate statistics:
Info:Linear Algebra: Krylov: CPU time 9499.3, WCT time 2539.2, iteration 
CPU time 0.26, COMM 0.01, cpu-wait 0.01, comm-wait 0.0 (9216 iterations)
Info:Linear Algebra: Lingen CPU time 251.83, WCT time 261.01
Info:Linear Algebra: Mksol: CPU time 4889.58,  WCT time 1305.59, 
iteration CPU time 0.27, COMM 0.01, cpu-wait 0.01, comm-wait 0.0 (4608 
iterations)
Info:Quadratic Characters: Starting
Warning:Command: Process with PID 27034 finished with return code -6
Error:Quadratic Characters: Program run on server failed with exit code 
-6
Error:Quadratic Characters: Command line was: 
/home/pi/cado-nfs/build/pi400-64/linalg/characters -poly 
/tmp/cado.z59qan9o/c110.poly -purged /tmp/cado.z59qan9o/c110.purged.gz 
-index /tmp/cado.z59qan9o/c110.index.gz -heavyblock 
/tmp/cado.z59qan9o/c110.dense.bin -out /tmp/cado.z59qan9o/c110.kernel 
-ker /tmp/cado.z59qan9o/c110.bwc/W -lpb0 25 -lpb1 26 -nchar 50 -t 4 > 
/tmp/cado.z59qan9o/c110.characters.stdout.1 2> 
/tmp/cado.z59qan9o/c110.characters.stderr.1
Error:Quadratic Characters: Stderr output (last 10 lines only) follow 
(stored in file /tmp/cado.z59qan9o/c110.characters.stderr.1):
Error:Quadratic Characters:     
/home/pi/cado-nfs/build/pi400-64/linalg/characters.re9cc3be15 -poly 
/tmp/cado.z59qan9o/c110.poly -purged /tmp/cado.z59qan9o/c110.purged.gz 
-index /tmp/cado.z59qan9o/c110.index.gz -heavyblock 
/tmp/cado.z59qan9o/c110.dense.bin -out /tmp/cado.z59qan9o/c110.kernel 
-ker /tmp/cado.z59qan9o/c110.bwc/W -lpb0 25 -lpb1 26 -nchar 50 -t 4
Error:Quadratic Characters:     # Warning: parameter nratchars is 
checked by this program but is undocumented.
Error:Quadratic Characters:     Note: total 64 characters, including 14 
trivial padding characters
Error:Quadratic Characters:     Reading 1469231 (a,b) pairs from 
/tmp/cado.z59qan9o/c110.purged.gz
Error:Quadratic Characters:     Computing 64 characters for 1469231 
(a,b) pairs
Error:Quadratic Characters:     Error, Jacobi symbol is 0 for a = 0, b = 
0, p = 67108879, r = 28784789
Error:Quadratic Characters:     Please check lpb0/lpb1 are large enough
Error:Quadratic Characters:     terminate called after throwing an 
instance of 'std::runtime_error'
Error:Quadratic Characters:       what():  code BUG() : condition res != 
0 failed at /home/pi/cado-nfs/linalg/characters.cpp:194
Error:Quadratic Characters:
...



On "Please check lpb0/lpb1 are large enough":
How can that be for same computation with just different CPU?

OK, my 7600X PC has 32GB RAM, while the Pi400 has only 4GB RAM.
Can that be the problem?


In README.md `lpb0` and `lpb1` are only mentioned in section "Big 
factorization (200 digits and more)", and here we factor only 110-digit 
number.


Btw, factoring 59-digit and 79-digit numbers on Pi400 worked without 
issues:
https://github.com/Hermann-SW/RSA_numbers_factored/blob/main/python/RSA_numbers_factored.py#L880-L903



Regards,

Hermann Stamm-Wilbrandt.



P.S:
cado-nfs.py is really cool. While 7600X CPU bought for high single 
thread performance (rank 18 of >3100 CPUs PassMark list) did factor 
RSA-100 in 1.5h only with msieve sequentially, it did factor RSA-100 in 
less than 8min with cado-nfs.py(!), and RSA-140 in 11.1h only!
https://github.com/Hermann-SW/RSA_numbers_factored/blob/main/cado-nfs/README.md#cado-nfs