https://gitlab.inria.fr/cado-nfs/cado-nfs
Revision 6615ac369b8eb2750088c33cd9667c971132f8c5 authored by Emmanuel Thomé on 19 March 2021, 14:24:16 UTC, committed by Emmanuel Thomé on 19 March 2021, 14:24:16 UTC
Bucket sieve projective primes; fix attempt for #30012 See merge request cado-nfs/cado-nfs!27
Tip revision: 6615ac369b8eb2750088c33cd9667c971132f8c5 authored by Emmanuel Thomé on 19 March 2021, 14:24:16 UTC
Merge branch 'bucket_sieve_projective_primes' into 'master'
Merge branch 'bucket_sieve_projective_primes' into 'master'
Tip revision: 6615ac3
README.msieve
Instructions on how to use CADO-NFS with msieve
===============================================
Summary:
I) Using CADO-NFS with relations computed with msieve (or ggnfs)
II) Using msieve filtering and linear algebra with relations in CADO format
III) Using msieve linear algebra after CADO-NFS filtering
==============================================================================
I) Using CADO-NFS with relations computed with msieve (or ggnfs)
The format of relations used by CADO-NFS is the same as the one used by ggnfs
or msieve.
IMPORTANT NOTE: free relations should not be included. To remove them,
first do: $ egrep -v '^[0-9]+,0$' relations > relations_fixed
0) You need to work with a git checkout of CADO-NFS, as it contains
utility code that is not present in tarballs (see main README for the
git clone command line).
1) First, convert the polynomial from Msieve format to CADO format using:
$ make convert_poly
$ build/<hostname>/misc/convert_poly -if msieve < input.poly > output.poly
2) Since ggnfs doesn't print prime factors under 10000, and CADO-NFS requires
all prime factors, you will need to complete all relations files that are in
ggnfs or msieve format using:
$ build/<hostname>/misc/check_rels -complete rels.out.gz -poly <polyfile> file0 file1 ... filen
or
$ build/<hostname>/misc/check_rels -complete rels.out.gz -poly <polyfile> -filelsit <filelist>
where <filelist> is a name of a file containing the list of all
relations files
See check_rels -h for others options.
3) Create a parameter file for the Python script: in the scripts/cadofactor
directory, see the files 'parameters' and 'README'. In the README file, read
thoroughly the section on importing polynomial file and importing relations.
You can also look in the 'params' directory for examples of parameter files
depending on the size of the input.
4) run the cado-nfs.py script (where $CADO is the CADO-NFS directory):
$ $CADO/cado-nfs.py <parameterfile>
If the parameter file is correctly configured, the script will skip the
polyselect step and the sieving. It will run all the remaining step of the
factorization until the factors are found.
NB: If you only want to do the filtering step, add the following command-line
arguments:
$ $CADO/cado-nfs.py <parameterfile> 'tasks.linalg.run = false' 'tasks.sqrt.run = false'
==============================================================================
II) Using msieve filtering and linear algebra with relations in CADO format
1) Create a file msieve.fb, which contains:
N <number to be factored>
R0 <coeff of x^0, rational side>
R1 <coeff of x^1, rational side>
A0 <coeff of x^0, algebraic side>
A1 <etc>
A2 <etc>
A3 <etc>
A4 <etc>
A5 <etc>
This can be done with:
$ ./convert_poly -of msieve < cxxx.poly > msieve.fb
2) create a file msieve.dat, which contains:
N <number to be factored>
<all the relations in GGNFS/CADO format>
(Do not include free relations, since the CADO-NFS format is not
recognized by msieve, and msieve includes them in the filtering.)
3) then run "msieve -nc -v <number to be factored>"
The msieve output goes into msieve.log.
You can add the "-t 4" option to use 4 threads.
==============================================================================
III) Using msieve linear algebra after CADO-NFS filtering
[should work with CADO-NFS revision aca5658]
up from msieve (svn) revision 891, msieve can read a cycle file produced by
CADO-NFS. To use it, you will have to:
- use CADO-NFS for the filtering. In what follows, let 'prefix' be
the prefix used for all the CADO filenames
- use the CADO 'replay' binary with --for_msieve to produce
a file <prefix>.cyc
- concatenate all the relation files specified by purge.log in
the order specified, and name the file <prefix> in the same
directory as all the other CADO intermediate files. If Msieve was
compiled with zlib support, the files do not have to be uncompressed
- create a <prefix>.fb file with the polynomials in Msieve format
- create worktodo.ini with a single line containing N
- run Msieve LA with
-v -nf <prefix>.fb -s <prefix> -nc2 "cado_filter=1"
The string at the end may get extra options depending on whether
the LA has more tweaking, like using MPI. The .cyc file gets
overwritten during the LA, so re-running the LA does not require
cado_filter=1.
Computing file changes ...