Discussion related to cado-nfs

[Jason Parker-Burlingham <jasonp@panix.com>]

Hello,

I started a factorization with yafu and after it crashed in linear algebra I
decided it would be interesting and possibly more productive to try to
complete the factorization using CADO-NFS.

This worked out pretty well as the linear algebra time was significantly
reduced, but it seems that I have probably made an error and the factorization
crashes during quadratic characters.

I should briefly describe what I did to import the relations:

Generally I followed the instructions in README.msieve.  I tried using
convert_poly, but crafted my own after that produced empty output.  Instead
I formatted the CADO-NFS .poly file by hand (it was basically identical) and
ported msieve's parameters to CADO parameters in .params.

I have successfully ported msieve polynomial files to CADO polynomials a
number of times, so I think that's probably good.

misc/check_rels produced a good relations file and I was able to add the "#
Total $nrels reports" line as needed.


===> Poly file:
n: 
7475004291062086064796852645548945815398395080988603287582048859211293436675904190505369623050480927315215248631054338806343718163720876158280613520427996127301554958706294445380591
skew: 45685683.75
c0: -27747437493842532037739444332763684556455552
c1: 10674288309615372368559655715789226248
c2: -1005163640452805980562665477388
c3: -48658444725418682720447
c4: 490190412989734
c5: 2419560
Y0: -79063311904730701812620166921604953
Y1: 33063432183521599027
# f(x) = 
2419560*x^5+490190412989734*x^4-48658444725418682720447*x^3-1005163640452805980562665477388*x^2+10674288309615372368559655715789226248*x-27747437493842532037739444332763684556455552
# g(x) = 33063432183521599027*x-79063311904730701812620166921604953


===> parameters_snapshot.0:
N = 
7475004291062086064796852645548945815398395080988603287582048859211293436675904190505369623050480927315215248631054338806343718163720876158280613520427996127301554958706294445380591
name = 11511_150
slaves.basepath = ./client
tasks.I = 15
tasks.execpath = /pkg/cado/lib/cado-nfs-3.0.0
tasks.lpb0 = 31
tasks.lpb1 = 31
tasks.qmin = 45000000
tasks.threads = 64
tasks.workdir = .
tasks.filter.target_density = 170.0
tasks.filter.purge.keep = 160
tasks.linalg.m = 64
tasks.linalg.n = 64
tasks.linalg.bwc.cpubinding =
/pkg/cado/share/cado-nfs-3.0.0/misc/cpubinding.conf
tasks.linalg.bwc.interleaving = 0
tasks.linalg.bwc.interval = 1000
tasks.linalg.bwc.threads = 32
tasks.linalg.characters.nchar = 50
tasks.polyselect.admax = 0
tasks.polyselect.admin = 0
tasks.polyselect.adrange = 0
tasks.polyselect.import = 11511_150.poly
tasks.polyselect.threads = 2
tasks.sieve.import = relations
tasks.sieve.lim0 = 85600000
tasks.sieve.lim1 = 85600000
tasks.sieve.mfb0 = 62
tasks.sieve.mfb1 = 62
tasks.sieve.qrange = 5000
tasks.sieve.las.threads = 2
tasks.sqrt.threads = 8


===> first 10 and last 10 relations:
-64404483887,3465:4b1,3a9a15,732ded,30390d3,36d45321,2,7,2b,119:10fd,30e5,8c699,b05003,1aac05b,28d13a7,8986a0b,26f899ff,3,3,5,b,3d,10d,139
126618002475,7111:d87,2a83,8eeb,1308e3,45d94f3,4087c805,2,3,3,e5:74b,e3b,1763,7e43,221ef,238e5,33848f,28d13a7,365035f,8ea7361,7,d,11,11,29,c1
338771175207,4505:a099,66a45,1340c9,2121d19,56543f9b,2,2,3,11,25,2b:44f,f0d,60f5,6a3bb,18db9b,1f73bf,d6d6bd,28d13a7,11f06759,5,17,3b,97,119,3b3
-331645508873,13933:529,949,240c7f9,279be01,303e0cc5,2,2,2,2,5,2f,61,2f5:c83,59d1,1e4c1,116059,262bc5,2448455,28d13a7,525b045,2d97cc15,3,b,d,d,1f,3d
-58708058183,4692:4e5f,6929,1ef17fc3,64f8116b,11,df,1bb,2a1,2b3:71fb,1708f,54e7b,69459b,14fabe7,28d13a7,40e70f7,2d76af51,2,2,2,2,3,5,7,b,e5,161
-61887778481,6152:47f,c109,502a5,38010f7,1c6de535,376b8ea3:6bef,3495d,51cb5,4bd54f,87b2af,28d13a7,32762395,73289ed5,2,2,2,3,3,5,7,6b,3c7
-73142709027,13406:7603,12bc8d,1ce5a1f,4c40621,19da98e3,3,3,3,13,35:b03,29e9,8663,20b97,107ecd,1f7a871,28d13a7,10252b91,1430573f,2,2,2,2,5,7,b,d,11,11,67
-350931592839,602:c61,4b7a4d,3a7d1df,9a97141,7bd6edf7,3,7,7:4eb,883,9413,267cd9,2953db,5a98d1,10e96bf,28d13a7,ba6d9db,2,2,2,5,b,d,29,59,24b
-636609463233,1988:c0d9,4b9d0f,27abdf9,be6467b,ea37e91,3,3,5,7:4ad5,9343,2016d,20b97,a34c95,132e477,28d13a7,83d0437,18df3db3,2,2,2,2,2,d,3b,119
4684678376,2707:363f5,c7393,13ef365,91fe9dd,1caa8863,d,3b:ae5,4021,669b,4de3d,b4d49,903223,bd79bb,1b3f9fd,28d13a7,2,2,2,2,2,2,3,5,13,1f,4f
[...]
536893859727,17755:5b3,1837,6c05,4b6cb,36ebb9cb,7f1babbd,2,3,17,43:f3c1,122c9,1394f,65a9f1,a9048d,ce34307,f681743,77d65d29,5,7,7,d,11,59,137,23b
440142804589,4885:551,534e3,e86957,12be2b17,4c1f937d,2,9d,1b1:2047,1f9f7,be615,55055b,7e246d,32d57e3,f681743,18573325,3,5,13,13,17,277,277
-113148842903,17989:4eb,d03,5523e3,1b07847,465da7d,818693b,2,6b:78d9,9aff,c941,1c745,2188f,5308fd,1943377,f681743,6c8d7aff,3,3,5,5,7,b,11,11,17,1d
62756114047,27739:e1667,2fce63,4d8aad,cba27c7,2417358d,2,241:8bd,f6df,1578d9,223985,b06269,585cb75,f681743,345f7c57,3,5,5,7,7,3b,43,97,281
-414543928733,18209:266f,3f80f,4db4f,bbbd3,7d0ab57,10534b35,2,2,2,2,2,2:ed5,373f,2ce8d,2e16b,8175b,2603f11,f681743,24959ca1,2df8db9f,3,3,5,7,d,3b,ad
175411141293,33683:5c9,e1bf,d7fc29,2a820415,6a75a213,2,2,3,3,3,13,1d,1d:e8f,12ee7,cddc9,1116cd,3e6929f,f681743,1043512d,670751f3,5,7,b,d,89,17f,1c1
-619583547309,17495:102b,9af7,6ba47,a5f95,14abf5,2f260f01,2,3,3,1f,2f:8fb9,13e91,5ca3e3,98b04b,28acd1f,2a80383,f681743,21438cd9,5,7,b,13,17,1c1,1eb
2374280317579,19189:3feb,a43ff,14fe37,1eab29,4f9be35,8e58e99,2,2:ac57,4115b,5cdcb,162985,345421,9b9d1d,1045add,9db8d8f,f681743,3,3,5,5,7,b,d,11,11,13
-415271536637,42107:d3d,1d4523,547457,63e587,18686ec9,2,5,1f,a3,2ab:dc9,10a5,16af,94a87,a16b79,2ed3105,3b0d163,7b68b99,f681743,3,7,7,b,d,d,d,13,3d,65
# Total 201646033 reports


===> end of the CADO-NFS logfile:
PID8399 2019-10-24 16:51:10,955 Info:Quadratic Characters: Starting
PID8399 2019-10-24 16:51:10,955 Debug:Quadratic Characters:
characters.run(): Task state: {'stdiocount': 1, 'cputime_characters':
638.7399999983609, 'realtime_characters': 123.21743679046631}
PID8399 2019-10-24 16:51:10,962 Command:Command:
/pkg/cado/lib/cado-nfs-3.0.0/linalg/characters -poly ./11511_150.poly
-purged ./11511_150.purged.gz -index ./11511_150.index.gz -heavyblock
./11511_150.dense.bin -out ./11511_150.kernel -ker ./11511_150.bwc/W
-lpb0 31 -lpb1 31 -nchar 50 -t 64 > ./11511_150.characters.stdout.2 2>
./11511_150.characters.stderr.2
PID8399 2019-10-24 16:53:20,010 Warning:Command: Process with PID 8403
finished with return code 1
PID8399 2019-10-24 16:53:20,021 Error:Quadratic Characters: Program
run on server failed with exit code 1
PID8399 2019-10-24 16:53:20,021 Error:Quadratic Characters: Command
line was: /pkg/cado/lib/cado-nfs-3.0.0/linalg/characters -poly
./11511_150.poly -purged ./11511_150.purged.gz -index
./11511_150.index.gz -heavyblock ./11511_150.dense.bin -out
./11511_150.kernel -ker ./11511_150.bwc/W -lpb0 31 -lpb1 31 -nchar 50
-t 64 > ./11511_150.characters.stdout.2 2>
./11511_150.characters.stderr.2
PID8399 2019-10-24 16:53:20,021 Error:Quadratic Characters: Stderr
output (last 10 lines only) follow (stored in file
./11511_150.characters.stderr.2):
PID8399 2019-10-24 16:53:20,022 Error:Quadratic Characters: done
reading heavy block of size 15286229 x 32 at 128.7
PID8399 2019-10-24 16:53:20,022 Error:Quadratic Characters:
./11511_150.bwc/W: 64 vectors
PID8399 2019-10-24 16:53:20,022 Error:Quadratic Characters: Total: 64
kernel vectors
PID8399 2019-10-24 16:53:20,022 Error:Quadratic Characters: done
reading 64 kernel vectors at 129.0
PID8399 2019-10-24 16:53:20,022 Error:Quadratic Characters: Info:
input kernel vectors reduced to dimension 0
PID8399 2019-10-24 16:53:20,022 Error:Quadratic Characters: done
multiplying matrices at 129.0
PID8399 2019-10-24 16:53:20,023 Error:Quadratic Characters: Computing
left nullspace of 0 x 96 matrix
PID8399 2019-10-24 16:53:20,023 Error:Quadratic Characters: dim of ker = 0
PID8399 2019-10-24 16:53:20,023 Error:Quadratic Characters: Error, all
dependencies are zero !
PID8399 2019-10-24 16:53:20,023 Error:Quadratic Characters:


In searching for the meaning of the "dim of ker = 0" and "input kernel
vectors reduced to dimension 0" errors I found two productive leads, one a
warning about nullspace=right and the other about a case where special-q was
larger than lpb:
https://gforge.inria.fr/tracker/?func=detail&group_id=2065&atid=7442&aid=14649
.

When I ported the params from yafu and msieve to CADO I scratched my head a
little about how to set qmin; I used the same value as the .params file I
cribbed from and figured it was fine when CADO produced a matrix.

I've read README.msieve and scripts/cadofactor/README but I am still not
sure how to determine the right tasks.qmin setting for the relations that I
have, or if I could expect it to have a bearing on the outcome of a second
attempt at krylov and mksol.

I'm also not sure that I preserved tasks.I from msieve to CADO-NFS; I don't
remember if yafu/msieve used I=14 or I=15 and I don't see any sign of that
in the logs I have.


Any and all suggestions would be very welcome.

jason