Binaries for NFS, NFS-DL
=============================
NFS : dup1 -> dup2 -> purge -> merge -> replay
NFS-DL: dup1 -> dup2 -> purge -> merge-dl -> replay-dl
Relations format
================
purge, merge, merge-dl, replay-dl read relations in the following format:
a,b:i1,...,ik
where a and b are in hexa
i1,...,ik are indexes in the renumbering table
all appearances of the same index must be continuous
dup1 (without -abhexa) reads relations in the following format (output of las)
a,b:p1,...,pl:p'1,...,p'r
where a and b are in basis 10
p1,...,pl,p'1,...,p'r are in hexa
dup1 (with -abhexa) reads relations in the following format (output of sieve4ffs)
a,b:p1,...,pl:p'1,...,p'r
where a and b are in hexa
p1,...,pl,p'1,...,p'r are in hexa
dup2 reads relations in two different format (deducted by reading the first line
of the file): either the same as purge, merge, merge-dl, ...; either the same
as dup1 without abhexa
File XXX.renumber
==============
This file is created by the freerels program.
It contains the table that links an ideal (p on rational side, (p,r) on
algebraic side) to its index that is going to be used during filtering.
The first line has the following format:
nbits ratside nbad n_add nonmonic nbpolys lpb0 lpb1
where
- nbits is 32 or 64 (depending on the maximum value of p possible, ie the large
prime bounds).
- ratside is the side of the rational side if it exists.
ratside = 0 means rational side corresponds to side 0.
ratside = 1 means rational side corresponds to side 1.
ratside = -1 means there is no rational side.
- nbad is the number of bad ideals (should be 0 for factorization)
- n_add is between 0 and nbpolys (this field is useful only for DLP; it
should be 0 for factorization). This counts the number of columns
which have been added to the matrix to take into account the logarithm of
the denominator ideal (often denoted J) for DLP problems.
- nonmonic is a bitmask, written in hex, of which polynomials are
not monic.
- nbpolys is the number of polynomials (usually 2)
- lpb0 is the large prime bound on side 0
- lpb1 is the large prime bound on side 1
- ...
- lpbV is the large prime bound on side V=nbpolys-1
nbits, ratside, nbad, add, nbpolys, all lpb's are written in decimal.
Then, the file may contains nbpolys lines, beginning by "# pol$i: ", with
polynomial $i used (polynomials on side 0 is written first).
Then, the file contains nbad lines of the following format:
p,r:s: n
where
- p is a prime and 0 <= r < p such that (p,r) is a bad ideal.
- s is the side (0 or 1) on which this bad ideal may appear.
- n is the number of ideals above this bad ideal.
p and r are written in hexadecimal, side an nb is written in decimal.
At last, the file contains the renumbering table: one hexadecimal number per
line.
File XXX.purged.gz
==================
It is created by purge, and contains a set of relations without
singleton, and where all or almost all the excess has been used.
The first line has the following format:
# nr lc nc
where
- nr is the number of rows (relations)
- lc is the index of the last column (ideal) that has non-zero weight
- nc is the number of columns (ideals)
nr, lc and nc are written in decimal.
Then, each line of the file corresponds to one relation: a,b:h_0,....h_k
where
- a and b give the (a,b) pair of the original relation
- h_i is an index of an ideal appearing in the relation. For factorization, an
ideal appears at most one per relation. For DL, if an ideal more than
once in the relation, all these occurrences are guaranteed to be one after
the other.
a,b and the h_i's are in hexadecimal.
File XXX.rels.deleted.gz
==================
It is created by purge, and contains all the relations that purge deleted.
It has the same format as XXX.purged.gz except the first line which does not
exist in the XXX.rels.deleted.gz file.
Useful only for DL.
File XXX.merge.history
======================
It is created by merge, and contains the sequence of operations that must
be done on the lines to replay the merge and create the matrix given to
linalg.
From time to time, a diagnostic line starting with BWCOST can be found.
It gives hints to replay if it wants to replay only some part of the
merge. (is it still really used ?????)
Otherwise here is the format (taken from a comment in replay.c):
A line is "i i1 ... ik".
If i >= 0 then
row[i] is to be added to rows i1...ik and destroyed at the end of
the process.
Works also is i is alone (hence: destroyed row).
If i < 0 then
row[-i-1] is to be added to rows i1...ik and NOT destroyed.
For DL, the line ends with an additional "#j" entry, where j
is the index of the column that is used for pivoting.
File XXX.ideal
==============
Useful only for DL, as it links the columns of the matrix and the ideals.
It is created by replay. Each line is of the following form:
i h
where i is a column number of the matrix produced by replay (see XXX.small)
and h is the index of the ideal corresponding to the column.
i is written in decimal, h in hexadecimal
File XXX.index
==============
Is is created by replay, and contains the link between the rows of the
small matrix (coming out from merge/replay) and the relation sets to
which they correspond.
The first line gives the number of rows (relation-sets) after the merge/replay
(in decimal).
Then, each line of the file corresponds to a line of the sparse matrix:
the first entry is an integer giving the number of relations in the
relation-set, and the rest of the line gives the indices of the relations
(in hexadecimal). These indices relate to the numbers of the lines in the
purged.gz file.
For DL, each entry is of the form id:e, where id is the index in the
purged.gz file, and e is the exponent of the corresponding relation in
the relation-set.
Files XXX.sparse.{txt|bin} and XXX.sparse.{rw|cw}.{txt|bin}
===========================================================
This is the set of files that describe the "sparse" matrix that is passed
to the linalg machinery. They are created by replay.
They exist in 2 different formats: txt or bin, the latter is more compact.
The "txt" format is human-readable. The main file is XXX.sparse.txt. Its
first line contains the number of rows and columns. Then each line gives
a row in the following format. The first integer is the number of
non-zero entries for this row. Then the list of entries is given. In the
case of factorization, an entry is just a column index, and for DL, it is
accompanied with its positive or negative value.
The files XXX.sparse.rw.txt and XXX.sparse.cw.txt contains the row and
column weights (one weight per row), and have no header (so that the
number of lines of XXX.sparse.rw.txt is exactly the number of rows of the
matrix.
$ wc -l < /tmp/xxx.sparse.rw.txt # number of rows
$ wc -l < /tmp/xxx.sparse.cw.txt # number of columns
The "bin" format is more compact. Recent versions of CADO-NFS only
generate the bin format. It is only made of 32-bit little-endian
integers. The main file has no header, and is just a sequence of rows.
Each row is given as in the txt format: number of non-zero entries, and
column indices for these entries. All are stored as 32-bit little-endian
integers. In the case of DL matrices, the coefficient values are stored
right after the column index, as *signed* 32-bit little-endian integers.
The files XXX.sparse.rw.bin and XXX.sparse.cw.bin, like in the txt case,
have the row and column weights (one weight per row), as 32-bit
little-endian integers.
Conversions between the txt and bin format, as well as generation of the
rw.txt and cw.txt files can be done with the mf_scan binary. For eaxmple,
in order to obtain a xxx.sparse.txt from a xxx.sparse.bin file:
mf_scan --binary-in --mfile xxx.sparse.bin --ascii-out --ofile xxx.sparse.txt --freq
Note that the program will say "Warning: output matrix is headerless",
which is normal. The txt matrix with header can be obtained by adding a
first row to xxx.sparse.txt which contains the number of rows and the
number of columns, for example:
$ wc -l < /tmp/xxx.sparse.rw.txt # number of rows
$ wc -l < /tmp/xxx.sparse.cw.txt # number of columns
7638 7446
11 36 38 89 373 425 689 876 1410 5745 5274 901
11 14 70 107 192 505 1097 4438 6904 4094 1997 2849
10 88 112 170 227 248 399 1365 1329 4749 3056
15 1 8 9 20 24 75 159 169 251 873 2018 1013 4064 2984 2370
12 25 29 36 118 346 387 1026 2930 6995 5591 1719 1605
11 57 65 121 141 390 612 1308 1114 2388 1645 1605
11 28 124 257 348 607 780 815 1097 947 5617 6337
12 33 150 213 217 527 480 576 1323 1261 4570 6374 1723
12 19 60 108 124 789 760 4261 4892 1856 4489 1194 1723
13 11 50 86 148 262 333 528 3382 5961 3234 3412 3534 1723
...
Equivalent shell line:
(echo `wc -l < /tmp/xxx.sparse.rw.txt` `wc -l < /tmp/xxx.sparse.cw.txt` ; cat xxx.sparse.txt) > xxx.sparse.txt.final
Note: The mf_scan binary can also handle DL matrices, but the
--withcoeffs option must be added.
File XXX.dlog
============================
This file is meant to be the most useful form of the log database, for
humans and computer scripts alike. It gives the correspondence between
rational primes, or algebraic prime ideals, and their virtual logarithms.
Files XXX.sparse.* versus XXX.dense.*
=====================================
If the parameter "skip" is non-zero, then the matrix is separated in a
dense and a sparse parts, so that additionnally to the previously
mentioned files, there are also "dense" versions.