The main page of the Cado-NFS source code is
[https://gitlab.inria.fr/cado-nfs/cado-nfs](https://gitlab.inria.fr/cado-nfs/cado-nfs).
If you're accessing the cado-nfs source from a different link, it may be
an outdated fork.

[![pipeline status](https://gitlab.inria.fr/cado-nfs/cado-nfs/badges/master/pipeline.svg)](https://gitlab.inria.fr/cado-nfs/cado-nfs/-/pipelines?ref=master)
[![coverage report](https://gitlab.inria.fr/cado-nfs/cado-nfs/badges/master/coverage.svg)](https://gitlab.inria.fr/cado-nfs/cado-nfs/-/jobs/artifacts/master/file/coverage/index.html?job=merge+coverage+tests)
[![coverity scan](https://scan.coverity.com/projects/23184/badge.svg)](https://scan.coverity.com/projects/cado-nfs)

Quick install:
==============

in most cases the following should work to factor the number 903...693
using all cores on the local machine

1. `make`
2. `./cado-nfs.py 90377629292003121684002147101760858109247336549001090677693`

More details follow.

Important note: For a larger factorization (distributed on several
machines), the command line to be used is a priori more involved. Please
refer to [`scripts/cadofactor/README.md`](scripts/cadofactor/README.md).
Documented example parameter files are in
[`parameters/factor/params.c90`](parameters/factor/params.c90) and
[`scripts/cadofactor/parameters*`](scripts/cadofactor/).

Supported platforms
===================

The primary development platform is `x86_64` linux with gcc 5 or newer,
the most common processor being Intel core2-like or more recent.

Other architectures are checked regularly, and should work. Please refer
to the gitlab-ci page for the list of regularly tested platforms, and their
current status. The overall pipeline status for the master branch is
[![pipeline
status](https://gitlab.inria.fr/cado-nfs/cado-nfs/badges/master/pipeline.svg)](https://gitlab.inria.fr/cado-nfs/cado-nfs/-/pipelines?ref=master),
and details can be obtained by clicking on the badges.  Note however that
a failing pipeline might mean that a bug affects only one platform in
particular, or could be caused by one runner encountering difficulties.
Such things do happen.

Since we use gitlab-ci pipelines, the authoritative source as to what
gets tested on a routine basis is of course the [`.gitlab-ci.yml`
file](.gitlab-ci.yml). In plain english, the configurations that we test,
or that we at least used to test at some point, are as follows.
Anything beyond the set of regularly tested machines perhaps works,
perhaps does not.

 * The primary development platform is `x86_64` Debian GNU/Linux, latest
   version, with gcc. If it doesn't work, we have a problem.

 * A few recent versions of Debian or Fedora are also tested. CentOS
   distributions (or derivatives) that have been EOL'd for some time, or
   are deemed to be shortly because they have vastly out-of-date
   software, are not tested.

 * `x86_64` with icc 14, 15, 16, 17, and 18 did work once, but are not checked
   regularly (cado-nfs uses C++11, which is not available with icc <=
   14). Compilation with icc 19 has undergone more testing. Routine
   checks use the ICC version that is provided by Intel's
   [`intel/oneapi-hpckit:latest` docker
   image](https://hub.docker.com/r/intel/oneapi-hpckit).

 * Mac OS X is used for CI routine compilation checks, using the
   default compiler from XCode. All version from 10.5 onwards were part
   of the CI routine checks at some point in time, and worked
   successfully. However we do not commit to continued support for old
   versions. As of cado-nfs 2.3.0, Mac OS X 10.8+ should work. As of
   cado-nfs 3.0.0, we expect that Mac OS X 10.12+ should work.

 * Windows used to be partly supported, but this has been abandoned for
   some time now (see a longer note
   [there](#using-cado-nfs-under-windows) at the end of this file).

Those machines, compared to the base install, are equipped with the
necessary dependencies (see below). The console outputs for the different
builds contain information related to the compiler versions being used.


Required software tools
=======================

 * [GMP](http://gmplib.org/), version 5 or newer: usually installed in
   most Linux distributions (on some Linux distributions you need to
   install the `libgmp*-dev` or `gmp-devel` package that includes
   `gmp.h`. It is often not installed by default). Note: make sure to
   configure GMP with `--enable-shared` so that a shared library is
   installed (`libgmp.so` under Linux) otherwise CADO-NFS might not
   compile.
 * As of `cado-nfs-3.0.0`, a C/C++ compiler and C/C++ standard library that
   conform to the C99 and C++11 standards are required. (cado-nfs-2.3.0
   only needed C99 and C++98).  The dependency on C++11 is now
   substantial enough that an "almost conformant" compiler is not
   guaranteed to work.  The minimal required versions for various
   compilers are as follows.  Not all old compiler versions are part of
   our routine checks, so that a break for an old compiler is possible.
   The only thing that we're quite certain of is that versions _older_
   than below are a no-go.
   * GCC: the minimal required version is >= 5
   * LLVM Clang: the minimal required version is >= 4.0.0
   * Apple Clang: the minimal required version is >= 6.0.0
   * Intel ICC: the minimal required version is >= 14
 * GNU make and CMake (`cmake 3.4` or later) for building (CMake is
   installed on the fly if missing. This feature requires an Internet
   connection.)
 * Support for POSIX threads.
 * The main `cado-nfs.py` script uses a lot of unix tools: Python, Python3,
   `ssh`, `rsync`, `gzip` to mention but a few.
 * On MacOS X, the cado-nfs client script needs an alternative to the
   system-provided curl binary, which it doesn't like. The simplest way
   to deal with this issue is to install the wget downloader (e.g. via
   homebrew).
 * For a large computation, MySQL is recommended.

Optionally, cado-nfs can use the following additional software.

* Support for OpenMP (at least version 3.0)
* Support for MPI (see [`local.sh.example`](local.sh.example) and [`linalg/bwc/README`](linalg/bwc/README))
* Support for hwloc (see [`parameters/misc/cpubinding.conf`](parameters/misc/cpubinding.conf))
* Support for GMP-ECM. Define the environment variable GMPECM if it is
  installed in a non-standard place.
* A system [`fmt`](https://fmt.dev/) is used is found, otherwise a
  snapshot is embedded in the cado-nfs code anyway.

Configure
=========

Normally you have nothing to do to configure cado-nfs.

However if your site needs tweaks, set such tweaks using environment variables,
or via the shell script local.sh ; you may start with

```
cp local.sh.example local.sh
```

Edit according to your local settings and your taste: local.sh.example
gives documentation on the recognized environment variables and their effect.

Note that tweaks in local.sh are global (relevant to all sub-directories
of the cado-nfs tree, not to a particular directory).

As a rule of thumb, whenever you happen to modify the `local.sh` script, it
is advised to trigger re-configuration of the build system, by the
special command `make cmake`. Another way to achieve the same goal is
to remove the build tree, which is below `build/` (normally named as the
hostname of the current machine): `make tidy` should do it.
Then, of course, you must recompile with `make`, since `make cmake`
is just the equivalent of `./configure` in a classical build system.

Optional (alternative): configure using cmake directly
======================================================

cado-nfs includes a top-level `Makefile` which builds the binary objects in
a special build directory which is below `build/` (normally named as the
hostname of the current machine). This way, parallel builds for different
machines may coexist in one shared directory. This is sort of a magic
`out-of-source` build.

Another way to do `out-of-source` build is to create a separate build
directory and build from there, by calling cmake directly for the
configuration. This proceeds as follows:

```
mkdir /some/build/directory
cd /some/build/directory
cmake /path/to/cado-nfs/source/tree
```

Note however that in this case, the `local.sh` file found in the source
tree is not read (but you may elect to do so before calling cmake).

Compile:
========

```
make
```

Install:
========

The relevance of the `make install` step depends on the platform.
Cado-nfs binaries link to shared libraries, and some do so dynamically.
For this to work, we rely on some control logic by cmake and cooperation
with the operating system's dynamic linker.

* if `make` is directly called from the source directory `$SRCDIR`,
  then `make install` installs all programs and binaries in `$SRCDIR/installed`.

* otherwise programs and binaries will be installed in
  `/usr/local/share/cado-nfs-x.y.z`, and this default installation prefix
  can be changed by one of the following commands:

```
cmake .../cado-nfs -DCMAKE_INSTALL_PREFIX=/tmp/install
export PREFIX=/tmp/install ; cmake .../cado-nfs
```

There are several ways to call cado-nfs scripts (e.g., `cado-nfs.py`).
Here we assume that `$SRCDIR` is the source directory, that `$BUILDDIR`
is the build tree for the local machine (typically `$SRCDIR/$(hostname)`),
and that `$PREFIX` is the installation prefix (see above).  We refer to
these different ways, and later discuss how they work on different
systems (which is mostly impacted by the shared library mechanism).

* `$SRCDIR/cado-nfs.py`
  This deduces `$BUILDDIR` from the machine hostname, and amounts to
  calling binaries from there. Parameter files are obtained from
  $SRCDIR/parameters/

* `$PREFIX/bin/cado-nfs.py`
  This calls binaries from `$PREFIX/bin`, and loads parameter files from
  `$PREFIX/share/cado-nfs-x.y.z/`

* `$BUILDDIR/cado-nfs.py`
  This is not supported. Might work, might not. You've been warned.

Linux, BSD: the first two choices above should work ok.
MacOS X:
    For any invocation to work, the `LD_LIBRARY_PATH` or `DYLD_LIBRARY_PATH`
    variable must be set up properly. The easiest method is to do make
    install, and include in these environment variables the directory
    `$PREFIX/lib/cado-nfs-x.y.z`.

Run a factorization on the current machine:
===========================================

```
./cado-nfs.py 90377629292003121684002147101760858109247336549001090677693 -t 2
```

where the option `-t 2` tells how many cores (via threads) to use on the
current machine (for polynomial selection, sieving, linear algebra, among
others).  It is possible to set `-t all` (which, in fact, is the default)
to use all threads on the current machine.

CADO-NFS is optimized only for numbers above 85 digits, and no support will
be provided for numbers of less than 60 digits (for very large numbers,
no support is promised). Note that it is a good idea to remove small prime
factors using special-purpose algorithms such as trial division, P-1, P+1,
or ECM, and use CADO-NFS only for the remaining composite factor.

Parts of the Number Field Sieve computation are massively distributed. In
this mode, client scripts (namely, `cado-nfs-client.py`) are run on many
nodes, connect to a central server, and run programs according to which
computations need to be done.  The programs (for the polynomial selection
and sieving steps) can run multithreaded. It is better to have them
run with a capped number of threads (say, 2), and run several clients per
node. By default, programs in this step are limited to 2 threads. When
running the computation on the local machine, the number of clients is
set so that the number of cores specified by `-t` are kept busy.

Run a larger factorization on several machines:
===============================================

CADO-NFS has several ways of operation, which can be roughly split into
three modes as follows.

 * For small computations, or for tests where it is important to have a
   single command line, the strategy
   [above](#run-a-factorization-on-the-current-machine) works. The
   `cado-nfs.py` script can arrange so that the binaries for all steps of
   the computation are run on the current machine, or possibly on other
   machines, via SSH. Some of the documentation here is specific to this
   mode of operation (see in particular
   [there](#check-that-your-network-configuration-is-correct) or
   [there](#check-that-your-ssh-configuration-is-correct)). If you get it
   right, you may manage to run factorizations as follows. However be
   aware that this mode of operation is fragile, and we advise not to use
   it beyond trivial testing.

   ```
   ./cado-nfs.py 353493749731236273014678071260920590602836471854359705356610427214806564110716801866803409 slaves.hostnames=hostname1,hostname2,hostname3 --slaves 4 --client-threads 2
   ```

   This starts 4 clients per host on the hosts `hostname1`, `hostname2`,
   and `hostname3`, and each client uses two cpus (threads). For
   hostnames that are not `localhost`, ssh is used to connect to the host
   and start a client there.  To configure ssh, see the [next
   section](#check-that-your-ssh-configuration-is-correct). For tasks
   that use the local machine only (not massively distributed tasks), the
   number of threads used is the one given by `-t` (which defaults to all
   threads on the local machine).

 * For larger computations where work distribution is an important point
   (distribution on several machines, possibly with different parameters
   for different machines), it is considerably more flexible to let the
   server be _just_ a server, and start clients separately, that will be
   used to offload the distributed tasks (polynomial selection and
   relation collection). Clients can come and go. The server has plenty
   of timeout provisions to deal with such events.

   This is called the `--server` mode (see
   [`scripts/cadofactor/README.md`](scripts/cadofactor/README.md) and
   [`scripts/cadofactor/parameters`](scripts/cadofactor/parameters)).
   See also [this thread](https://lists.gforge.inria.fr/pipermail/cado-nfs-discuss/2020-March/001168.html) on the old `cado-nfs-discuss` list (it's been [replaced](#contact-links)). If you want to use cado-nfs even to a little extent, we recomment that you familiarize with this mode of operation.

 * For much larger computations, the `cado-nfs.py` is only of moderate
   use. The individual cado-nfs binaries and internal scripts are the
   most flexible entry points, and should be used in order to adapt to
   the specificities of the platform being used (e.g. to deal with
   various requirements such as memory for filtering, interconnect for
   linear algebra, and so on).

Check that your network configuration is correct:
=================================================

In case you run a factorization on the local machine, the clients should be able
to connect to the server. Under Linux, CADO-NFS uses 'localhost' to identify the
server, thus you should have the following line in your /etc/hosts file:

```
127.0.0.1   localhost
```

Check that your SSH configuration is correct:
=============================================

The master script (unless in `--server` mode) uses SSH to connect to
available computing resources.  In order to avoid the script asking your
password or passphrase, you must have public-key authentication and an
agent.

The SSH keys are usually installed in the files `~/.ssh/id_rsa` and
`~/.ssh/id_rsa.pub`; if you don't have them yet, you can create them with the
`ssh-keygen` command. See the man page `ssh-keygen(1)` for details. The private
key should be protected with a passphrase, which you can enter when you
create the keys. Normally ssh will ask for the key's passphrase when you log
on to a machine, but this can be avoided by using ssh-agent, see the man
page `ssh-agent(1)`, and providing the passphrase to the agent with `ssh-add`.
Public-key authenticaton together with an ssh-agent will allow `cadofactor`
to use ssh to run commands on slave machines automatically.

Most of the recent Linux distributions will run an `ssh-agent` for you. But
if this is not the case with your distribution, or if you are running
`cado-nfs.py` inside a `screen` in order to logout from your desktop, you
will need to run the `ssh-agent` by hand. As a short recipe, you can type:
```
eval `ssh-agent`
ssh-add
```

You should also copy your public key, i.e., the contents of the file
`~/.ssh/id_rsa.pub`, into `$HOME/.ssh/authorized_keys` on the slave machines, to
allow logging in with public-key authentication.

Also, since localhost has an IP and key that varies, you should have
those 3 lines in your `$HOME/.ssh/config`:

```
Host    localhost
        StrictHostKeyChecking no
        UserKnownHostsFile /dev/null
```

If everything is correctly configured, when you type

ssh localhost

you should end up with a new shell on your machine, without having to
type any password/passphrase.


Restarting an interrupted factorization:
========================================

If you have started a factorization with the `cado-nfs.py` script, and it was
interrupted (for example because of a power failure) you can restart in
any of these two ways:

 * with the same `cado-nfs.py` command line if a work directory was
   explicitly provided on the command line:

   ```
   $ cado-nfs.py ... workdir=/path/to/workdir
   ```

 * with a single argument as in:

   ```
   $ cado-nfs.py     [[work directory]]/XXX.parameters_snapshot.YYY
   ```

   where `[[work directory]]` is the directory which has been chosen
   automatically, `XXX` is the "name" of the running factorisation, and `YYY`
   is the largest possible integer value for which such a file exists.

Factoring with SNFS:
====================

It is possible to take advantage of the special form of an integer and
use the Special Number Field Sieve. See
[`parameters/factor/parameters.F9`](parameters/factor/parameters.F9)
for that:

```
$ cado-nfs.py parameters/factor/parameters.F9 slaves.hostnames=localhost
```

Note in particular that you can force the special-q to be on the rational
side if this is more appropriate for your number, with
`tasks.sieve.sqside=0` on the `cado-nfs.py` command line or in the
parameter file (assuming side 0 is the rational side).

The default square root algorithm does not work in some very rare cases
that could possibly occur with SNFS polynomials (a degree 4 polynomial
with Galois group $Z/2 \times Z/2$ is the only reasonable example, next
case is for degree 8). The CRT approach is a workaround. See
[`sqrt/crtaglsqrt.c`](sqrt/crtaglsqrt.c) .

Big factorization (200 digits and more):
========================================

By default, to decrease memory usage, it is assumed that less than $2^32$
(~ four billion) relations or ideals are needed and that the ideals will
be less than $2^32$ (i.e., the `lpb0` and `lpb1` parameters are less or
equal to 32). In the case of factorizations of numbers of 200 digits and
more, these assumptions may not hold. In this case, you have to set some
variables in your `local.sh` script (see Configure section above for more
information on `local.sh` and section on big factorizations in
`local.sh.example`).

Factoring with two non-linear polynomials:
==========================================

You can find a bit of information on this topic in the development
version, in the GIT repository (see file
[`README.nonlinear`](README.nonlinear)).

Importing polynomials or relations:
===================================

If you have already computed a good polynomial and/or relations, you can
tell CADO-NFS to use them, see
[`scripts/cadofactor/README.md`](scripts/cadofactor/README.md).

Using CADO-NFS under Windows:
=============================

Portability of CADO-NFS on Windows was not an initial goal of that project,
however we give here some hints that might help people wanting to use CADO-NFS
under Windows. We hope that the following information can be useful to
some extent, but the general message is that you're on your own.

* Cado-NFS uses the POSIX interface all over the place, which means that
  in one form of the other, you need to have the corresponding
  functionality. If you don't, you're out of luck. (e.g., cado-nfs cannot
  build as a "pure" visual studio project.)

* if you only need the siever to run on Windows, then you only need to compile
  the `las` program on Windows.

* [Cygwin](http://www.cygwin.com/) provides a Unix-like environment,
  where compilation should be easy.  However the binary requires a
  `cygwin.dll` file. We have been told of problems with shared libraries,
  which the following seems to address:
  ```
  PATH="installed/lib/cado-nfs-x.y.z:$PATH" ./cado-nfs.py [...]
  ```

* if you want a binary without any dependency, you might try
  [MinGW](http://www.mingw.org/). The INSTALL file from GNU MPFR contains
  detailed instructions on how to compile MPFR under Windows. Those
  instructions should work for CADO-NFS too.  See
  [`dev_docs/howto-MinGW.txt`](dev_docs/howto-MinGW.txt).

* you might try to use MPIR (<http://mpir.org/>) instead of GMP. MPIR
  is a fork of GMP, which claims to be more portable under Windows.
  Alternatively, Windows ports of GMP shouldn't be too hard to find.

* you might succeed in compiling the cado-nfs binaries with a
  cross-compiler for Windows (which does not waive the runtime
  requirements for `cado-nfs.py`, notably on unix-like utilities). See
  [`dev_docs/README.cross`](dev_docs/README.cross) in the source code
  repository for information on how to cross-compile.

Examples of basic usage:
========================

* Run a full factorization on the local machine, using all available
  cores:

```
./cado-nfs.py 90377629292003121684002147101760858109247336549001090677693
```

* Run a full factorization on the local machine, using all available
  cores, but with a slightly modified set of default parameters.

  The difficulty here is that when `cado-nfs.py` uses a parameter file
  supplied on the command line, it does not automatically insert into the
  parameter set the options that are necessary for running jobs.
  Therefore, we need to add these options:

```
./cado-nfs.py --parameters ./parameters/factor/params.c60 90377629292003121684002147101760858109247336549001090677693 slaves.hostnames=localhost slaves.nrclients=2
```

* Run a full factorization on the local machine, using 8 threads for the
  server (this includes the linear algebra), and 4 jobs of 2 threads
  each for the polynomial selection and the sieving:

```
./cado-nfs.py 90377629292003121684002147101760858109247336549001090677693 --slaves 4 --client-threads 2 --server-threads 8
```

* Run a factorization in the given directory, interrupt it (with Ctrl-C,
  or whatever unexpected event), and resume the computation:

```
./cado-nfs.py 90377629292003121684002147101760858109247336549001090677693 workdir=/tmp/myfacto
[Ctrl-C]
./cado-nfs.py /tmp/myfacto/c60.parameters_snapshot.0
```

* Run a server on `machine1`, and a slave on `machine2`, disabling ssl:

```
machine1$ ./cado-nfs.py --server 90377629292003121684002147101760858109247336549001090677693 server.port=4242 server.ssl=no server.whitelist=machine2
machine2$ ./cado-nfs-client.py --server=http://machine1:4242 --bindir=...
```

Note: if you are on an insecure network, you'll have to activate ssl, and
then pass the appropriate sha1 certificate to the client (the server
prints the appropriate command-line to be copy-pasted on `machine2`).

* Run a factorization on `machine1`, and have it start automatically a
  slave on `machine2` via SSH:

```
./cado-nfs.py 90377629292003121684002147101760858109247336549001090677693
slaves.hostnames=machine1,machine2
```

Note that, in that case, you have to specify `machine1` as well in the list
of `hostnames` if you want it to contribute to the polynomial selection and
the sieving.


Stopping the factorization during a specific step:
==================================================
It is possible to stop the factorization:

```
./cado-nfs.py 90377629292003121684002147101760858109247336549001090677693 tasks.xxxx.run=false
```

This command works with: xxxx = polyselect, sieve, filter, linalg


Known problems:
===============

(some of these problems refer to versions or operating systems that are
no longer supported by cado-nfs anyway)

* when running the square root step in multi-thread mode (tasks.sqrt.threads=2
  or larger) with GMP <= 6.0, you might encounter an issue due to a "buglet"
  in GMP (<https://gmplib.org/list-archives/gmp-bugs/2015-March/003607.html>).
  Workaround: use tasks.sqrt.threads=1 or GMP >= 6.1.0.
* GCC 4.1.2 is known to miscompile CADO-NFS (see
  <http://cado-nfs.gforge.inria.fr/bug.php?14490>),
  GCC 4.2.0, 4.2.1 and 4.2.2 are also affected.
* under NetBSD 5.1 amd64, Pthreads in the linear algebra step seem not to
  work, please use `-t 1` option in `cado-nfs.py` or `tasks.linalg.threads=1x1`.
* under AIX, if GMP is compiled in 64-bit mode, you should set the
  environment variable `OBJECT_MODE`, for example:
  export `OBJECT_MODE=64`
* if you encounter the error "Exceeded maximum number of failed workunits,
  maxfailed=100", you can restart the factorization with
  `tasks.maxfailed=200`.   But it would be wise, first, to try to
  understand _why_ workunits are failing. This should not appear. It
  might be that all your workunits are timing out, because your `adrange`
  and `qrange` parameters are too large.  Or it's a bug in cado-nfs, and
  then it should definitely be reported.


Contact, links:
===============

The website of the project is hosted at:
   <http://cado-nfs.gforge.inria.fr/>

You can get the latest development version with:
```
git clone https://gitlab.inria.fr/cado-nfs/cado-nfs.git
```
or
```
git clone git@gitlab.inria.fr:cado-nfs/cado-nfs.git
```
(use the latter if you have an account on Inria gitlab, and commit access
to cado-nfs)

There is now a unique mailing-list associated to Cado-nfs
[cado-nfs@inria.fr](https://sympa.inria.fr/sympa/info/cado-nfs). Please
do not use the old `cado-nfs-discuss` mailing list, the infrastructure
that hosts this mailing list is set for removal in 2021.

If you find a bug, if you have a problem compiling cado-nfs, if you want to
factor a large number and seek for advice for tuning the parameters, then
the cado-nfs-discuss list is the right place to ask.

On the <https://gitlab.inria.fr/cado-nfs/cado-nfs> web page you can also
find the cado-nfs bug tracker (a.k.a project issues). The bug tracker is
an important piece of the cado-nfs development cycle.  Submitting bugs
and merge requests there is welcome (you need an Inria gitlab account),
although if you are unsure, it might be better to speak up on the
cado-nfs-discuss mailing list first.

This file describes some problems that can occur with the cado-nfs.py
script in relation to various distributions' Python installations.


1. Python 3

Python 3, version 3.3 or greater, is required for cado-nfs.py. If you
do not wish to use cado-nfs.py, maybe because you plan to run all
commands by hand, you can disable the Python check in CMake by setting
NO_PYTHON_CHECK to any non-empty string in local.sh. See local.sh.example
for a template.

Some operating systems don't have a Python 3 interpreter installed by
default. The safest bet is to install a distribution-supplied package
for Python 3. If no such package is available, you can download the
Python source code, compile and and install it by yourself. For a good
introduction to installing Python from source, see
https://www.digitalocean.com/community/articles/how-to-set-up-python-2-7-6-and-3-3-3-on-centos-6-4


2. Sqlite 3

The Python cado-nfs.py script requires sqlite3. Unfortunately, not all
distributions install the Python sqlite3 module by default.

In fact, two things are required: the binary sqlite3 library, and the Python
module called "sqlite3" which provides a Python interface to the sqlite3
library.

The binary sqlite3 library is installed by default on most systems, but it
is worthwhile to check that it is. Use your distribution's package manager,
and look for a package called "sqlite", "sqlite3", or "libsqlite3", which
should contain a file "libsqlite3.so.*"

The Python sqlite3 module unfortunately is not installed by default by some
distributions, known culprits include Gentoo.

Gentoo:
For Gentoo, the Python 3 package by default does not include the sqlite3
module. This link to a forum post briefly describes the situation:
<http://forums.gentoo.org/viewtopic-t-876737-start-0.html>
The sqlite3 module can be included in the Python installation by adding
the sqlite USE flag to /etc/portage/make.conf as shown in this example:

# These are the USE flags that were used in addition to what is provided by the
# profile used for building.
USE="bindist mmx sse sse2 sqlite"

and then running
emerge  --deep --newuse world


If you compile Python 3 yourself from source code, be aware that the sqlite3
development package with the header files for the sqlite3 library must be
installed on the system; without them, the Python 3 build will seem to
succeed but will not include the sqlite3 interface. When compiling Python 3,
be sure that the "make" output does NOT include a warning of the form:

The necessary bits to build these optional modules were not found:
_sqlite3


3. SSL

The workunit server and clients use SSL for communication to prevent an
attacker on the same network from injecting text into workunits which could
be used to execute arbitrary commands on the client machines. Generating a
server certificate requires that OpenSSL is installed on the computer
running the server.

4. MySQL

If you wish to use MySQL you first need to install the Python MySQL connector library available at
https://dev.mysql.com/get/Downloads/Connector-Python/mysql-connector-python-py3_2.1.3-1ubuntu14.04_all.deb
You then pass the -mysql flag to ./cado-nfs.py

Using CADO-NFS for DLP in large characteristic fields.
------------------------------------------------------

**** Basic usage: DLP in GF(p)

The cado-nfs.py script can be used to compute discrete logarithms in a
prime field GF(p). For example, to compute the discrete logarithm in GF(p)
modulo the factor 101538509534246169632617439 of p-1 of the target
92800609832959449330691138186 with p=191907783019725260605646959711:

$ ./cado-nfs.py -dlp -ell 101538509534246169632617439 target=92800609832959449330691138186 191907783019725260605646959711

In principle, just typing
  ./cado-nfs.py -dlp -ell <ell> target=<target> <p>
should compute the discrete logarithm of <target> modulo <ell> in
GF(<p>). Right now, there are parameters only for primes p of around 30,
60, 100 or 155 digits (to be checked in params_dl/ subdirectory). If no
target is given, then the output is a file containing the virtual
logarithms of all the factor base elements.

More flexibility is possible. An example of parameter file is given in
parameters/dlp/param.p60. Compared to parameter files for integer
factorization, the main difference is that the lines related
to characters and sqrt disappear and that there is an additional block of
parameters related to individual logarithms.

After the computation is finished, it is possible to run again the
cado-nfs.py script, with a different target: only the last step will be
run. For ensuring that the precomputed data is really used, copy-paste
the command-line indicated in the output of the first computation that
contains "If you want to compute a new target…", and set the new target at the
end.

Important note: the logarithms are given in an arbitrary (unknown) base.
If you want to define them with respect to a specific generator g, then
you'll have to compute the logarithm of g and then divide all the logs by
this value. See https://lists.gforge.inria.fr/pipermail/cado-nfs-discuss/2018-November/000939.html and
https://lists.gforge.inria.fr/pipermail/cado-nfs-discuss/2018-November/000942.html.

**** Using Joux-Lercier polynomial selection

By default, the same polynomial selection algorithm as for factoring is
used. In some (many ?) cases, it can be much better to use Joux-Lercier's
polynomial selection as implemented in polyselect/dlpolyselect. In order
to use it, it is necessary to add the parameter
  jlpoly = true
and to give the additional parameters:
  tasks.polyselect.degree = 3
  tasks.polyselect.bound = 5
  tasks.polyselect.modm = 5

Here, polynomial.degree is the degree of the polynomial with small
coefficients. The other one will have degree one less. Therefore, on this
example, this is a selection for degrees (3,2). The polynomial.bound
and the polynomial.modm parameters are passed directly to dlpolyselect.
The search is parallelized with the client/server mechanism as for the
classical polynomial selection. Each task does one value "modr" between 0
and modm-1 (again, this is dlpolyselect terminology). The number of tried
polynomials is roughly (2*bound+1)^(degree+1), thus here 14641 (the larger
the better, but then polynomial selection will last longer).

For instance, the 30-digit example above can be done with JL polynomial
selection with the following command-line:

$ ./cado-nfs.py -dlp -ell 101538509534246169632617439 191907783019725260605646959711 jlpoly=true tasks.polyselect.bound=5 tasks.polyselect.modm=7 tasks.polyselect.degree=3 tasks.reconstructlog.checkdlp=false

In that case, the individual logarithm phase implementation is based on
GMP-ECM, so this is available only if this library is installed and
detected by the configuration script (see local.sh.example for indicating
non-standard locations).

Note that tasks.reconstructlog.checkdlp=false is there to disable some
consistency checks that can not be made in JL mode.

This is still experimental, but parameters optimized for the JL
polynomial selection can be found in parameters/dlp/Joux-Lercier/ .
Copying
  parameters/dlp/Joux-Lercier/params.p30
to
  parameters/dlp/params.p30
will automatically activate the JL polynomial selection (but will crash
if GMP-ECM failed to be detected at compile time) for primes of this
size. For instance,

$ ./cado-nfs.py -dlp -ell 101538509534246169632617439 target=92800609832959449330691138186 191907783019725260605646959711

should then work and compute the log of the given target using JL.


**** Using non-linear polynomials

Just like for factorization, it is possible to use two non-linear
polynomials for DLP. Apart from Joux-Lercier polynomial selection (see above),
the user must provide the polynomial file. Also, the current descent script
will not work.

See README.nonlinear for an example of importing a polynomial file with 2
non-linear polynomials.

An important issue is that since the descent is not yet functional
for this case, the script has no way to check the results if there is no
linear polynomial. A good idea is to set
  tasks.reconstructlog.partial = false
so that many consistency checks are performed while using all the
relations that were deleted during the filter.

**** Discrete logarithms in GF(p^k) for small k

The algorithm works "mutatis mutandis" for discrete logarithm computations
in GF(p^k). The only difference is that the two polynomials must have a
common irreducible factor of degree k over GF(p). Polynomial selection
for this case is not yet included, so you must build them by yourself,
based on constructions available in the literature, and import it as
indicated in scripts/cadofactor/README. Also the individual
logarithm has to be implemented for that case.

For DLP in GF(p^2), things are sligthly more integrated:
  ./cado-nfs.py <p> -dlp -ell <ell> -gfpext 2
should work for p = 7 mod 8, provided that a parameter file is available
for the size of p (at the time of writing this doc, only p of 20 decimal
digits is supported).

The main page of the Cado-NFS source code is
[https://gitlab.inria.fr/cado-nfs/cado-nfs](https://gitlab.inria.fr/cado-nfs/cado-nfs).
If you're accessing the cado-nfs source from a different link, it may be
an outdated fork.

[![pipeline status](https://gitlab.inria.fr/cado-nfs/cado-nfs/badges/master/pipeline.svg)](https://gitlab.inria.fr/cado-nfs/cado-nfs/-/pipelines?ref=master)
[![coverage report](https://gitlab.inria.fr/cado-nfs/cado-nfs/badges/master/coverage.svg)](https://gitlab.inria.fr/cado-nfs/cado-nfs/-/jobs/artifacts/master/file/coverage/index.html?job=merge+coverage+tests)
[![coverity scan](https://scan.coverity.com/projects/23184/badge.svg)](https://scan.coverity.com/projects/cado-nfs)

Quick install:
==============

in most cases the following should work to factor the number 903...693
using all cores on the local machine

1. `make`
2. `./cado-nfs.py 90377629292003121684002147101760858109247336549001090677693`

More details follow.

Important note: For a larger factorization (distributed on several
machines), the command line to be used is a priori more involved. Please
refer to [`scripts/cadofactor/README.md`](scripts/cadofactor/README.md).
Documented example parameter files are in
[`parameters/factor/params.c90`](parameters/factor/params.c90) and
[`scripts/cadofactor/parameters*`](scripts/cadofactor/).

Supported platforms
===================

The primary development platform is `x86_64` linux with gcc 5 or newer,
the most common processor being Intel core2-like or more recent.

Other architectures are checked regularly, and should work. Please refer
to the gitlab-ci page for the list of regularly tested platforms, and their
current status. The overall pipeline status for the master branch is
[![pipeline
status](https://gitlab.inria.fr/cado-nfs/cado-nfs/badges/master/pipeline.svg)](https://gitlab.inria.fr/cado-nfs/cado-nfs/-/pipelines?ref=master),
and details can be obtained by clicking on the badges.  Note however that
a failing pipeline might mean that a bug affects only one platform in
particular, or could be caused by one runner encountering difficulties.
Such things do happen.

Since we use gitlab-ci pipelines, the authoritative source as to what
gets tested on a routine basis is of course the [`.gitlab-ci.yml`
file](.gitlab-ci.yml). In plain english, the configurations that we test,
or that we at least used to test at some point, are as follows.
Anything beyond the set of regularly tested machines perhaps works,
perhaps does not.

 * The primary development platform is `x86_64` Debian GNU/Linux, latest
   version, with gcc. If it doesn't work, we have a problem.

 * A few recent versions of Debian or Fedora are also tested. CentOS
   distributions (or derivatives) that have been EOL'd for some time, or
   are deemed to be shortly because they have vastly out-of-date
   software, are not tested.

 * `x86_64` with icc 14, 15, 16, 17, and 18 did work once, but are not checked
   regularly (cado-nfs uses C++11, which is not available with icc <=
   14). Compilation with icc 19 has undergone more testing. Routine
   checks use the ICC version that is provided by Intel's
   [`intel/oneapi-hpckit:latest` docker
   image](https://hub.docker.com/r/intel/oneapi-hpckit).

 * Mac OS X is used for CI routine compilation checks, using the
   default compiler from XCode. All version from 10.5 onwards were part
   of the CI routine checks at some point in time, and worked
   successfully. However we do not commit to continued support for old
   versions. As of cado-nfs 2.3.0, Mac OS X 10.8+ should work. As of
   cado-nfs 3.0.0, we expect that Mac OS X 10.12+ should work.

 * Windows used to be partly supported, but this has been abandoned for
   some time now (see a longer note
   [there](#using-cado-nfs-under-windows) at the end of this file).

Those machines, compared to the base install, are equipped with the
necessary dependencies (see below). The console outputs for the different
builds contain information related to the compiler versions being used.


Required software tools
=======================

 * [GMP](http://gmplib.org/), version 5 or newer: usually installed in
   most Linux distributions (on some Linux distributions you need to
   install the `libgmp*-dev` or `gmp-devel` package that includes
   `gmp.h`. It is often not installed by default). Note: make sure to
   configure GMP with `--enable-shared` so that a shared library is
   installed (`libgmp.so` under Linux) otherwise CADO-NFS might not
   compile.
 * As of `cado-nfs-3.0.0`, a C/C++ compiler and C/C++ standard library that
   conform to the C99 and C++11 standards are required. (cado-nfs-2.3.0
   only needed C99 and C++98).  The dependency on C++11 is now
   substantial enough that an "almost conformant" compiler is not
   guaranteed to work.  The minimal required versions for various
   compilers are as follows.  Not all old compiler versions are part of
   our routine checks, so that a break for an old compiler is possible.
   The only thing that we're quite certain of is that versions _older_
   than below are a no-go.
   * GCC: the minimal required version is >= 5
   * LLVM Clang: the minimal required version is >= 4.0.0
   * Apple Clang: the minimal required version is >= 6.0.0
   * Intel ICC: the minimal required version is >= 14
 * GNU make and CMake (`cmake 3.4` or later) for building (CMake is
   installed on the fly if missing. This feature requires an Internet
   connection.)
 * Support for POSIX threads.
 * The main `cado-nfs.py` script uses a lot of unix tools: Python, Python3,
   `ssh`, `rsync`, `gzip` to mention but a few.
 * On MacOS X, the cado-nfs client script needs an alternative to the
   system-provided curl binary, which it doesn't like. The simplest way
   to deal with this issue is to install the wget downloader (e.g. via
   homebrew).
 * For a large computation, MySQL is recommended.

Optionally, cado-nfs can use the following additional software.

* Support for OpenMP (at least version 3.0)
* Support for MPI (see [`local.sh.example`](local.sh.example) and [`linalg/bwc/README`](linalg/bwc/README))
* Support for hwloc (see [`parameters/misc/cpubinding.conf`](parameters/misc/cpubinding.conf))
* Support for GMP-ECM. Define the environment variable GMPECM if it is
  installed in a non-standard place.
* A system [`fmt`](https://fmt.dev/) is used is found, otherwise a
  snapshot is embedded in the cado-nfs code anyway.

Configure
=========

Normally you have nothing to do to configure cado-nfs.

However if your site needs tweaks, set such tweaks using environment variables,
or via the shell script local.sh ; you may start with

```
cp local.sh.example local.sh
```

Edit according to your local settings and your taste: local.sh.example
gives documentation on the recognized environment variables and their effect.

Note that tweaks in local.sh are global (relevant to all sub-directories
of the cado-nfs tree, not to a particular directory).

As a rule of thumb, whenever you happen to modify the `local.sh` script, it
is advised to trigger re-configuration of the build system, by the
special command `make cmake`. Another way to achieve the same goal is
to remove the build tree, which is below `build/` (normally named as the
hostname of the current machine): `make tidy` should do it.
Then, of course, you must recompile with `make`, since `make cmake`
is just the equivalent of `./configure` in a classical build system.

Optional (alternative): configure using cmake directly
======================================================

cado-nfs includes a top-level `Makefile` which builds the binary objects in
a special build directory which is below `build/` (normally named as the
hostname of the current machine). This way, parallel builds for different
machines may coexist in one shared directory. This is sort of a magic
`out-of-source` build.

Another way to do `out-of-source` build is to create a separate build
directory and build from there, by calling cmake directly for the
configuration. This proceeds as follows:

```
mkdir /some/build/directory
cd /some/build/directory
cmake /path/to/cado-nfs/source/tree
```

Note however that in this case, the `local.sh` file found in the source
tree is not read (but you may elect to do so before calling cmake).

Compile:
========

```
make
```

Install:
========

The relevance of the `make install` step depends on the platform.
Cado-nfs binaries link to shared libraries, and some do so dynamically.
For this to work, we rely on some control logic by cmake and cooperation
with the operating system's dynamic linker.

* if `make` is directly called from the source directory `$SRCDIR`,
  then `make install` installs all programs and binaries in `$SRCDIR/installed`.

* otherwise programs and binaries will be installed in
  `/usr/local/share/cado-nfs-x.y.z`, and this default installation prefix
  can be changed by one of the following commands:

```
cmake .../cado-nfs -DCMAKE_INSTALL_PREFIX=/tmp/install
export PREFIX=/tmp/install ; cmake .../cado-nfs
```

There are several ways to call cado-nfs scripts (e.g., `cado-nfs.py`).
Here we assume that `$SRCDIR` is the source directory, that `$BUILDDIR`
is the build tree for the local machine (typically `$SRCDIR/$(hostname)`),
and that `$PREFIX` is the installation prefix (see above).  We refer to
these different ways, and later discuss how they work on different
systems (which is mostly impacted by the shared library mechanism).

* `$SRCDIR/cado-nfs.py`
  This deduces `$BUILDDIR` from the machine hostname, and amounts to
  calling binaries from there. Parameter files are obtained from
  $SRCDIR/parameters/

* `$PREFIX/bin/cado-nfs.py`
  This calls binaries from `$PREFIX/bin`, and loads parameter files from
  `$PREFIX/share/cado-nfs-x.y.z/`

* `$BUILDDIR/cado-nfs.py`
  This is not supported. Might work, might not. You've been warned.

Linux, BSD: the first two choices above should work ok.
MacOS X:
    For any invocation to work, the `LD_LIBRARY_PATH` or `DYLD_LIBRARY_PATH`
    variable must be set up properly. The easiest method is to do make
    install, and include in these environment variables the directory
    `$PREFIX/lib/cado-nfs-x.y.z`.

Run a factorization on the current machine:
===========================================

```
./cado-nfs.py 90377629292003121684002147101760858109247336549001090677693 -t 2
```

where the option `-t 2` tells how many cores (via threads) to use on the
current machine (for polynomial selection, sieving, linear algebra, among
others).  It is possible to set `-t all` (which, in fact, is the default)
to use all threads on the current machine.

CADO-NFS is optimized only for numbers above 85 digits, and no support will
be provided for numbers of less than 60 digits (for very large numbers,
no support is promised). Note that it is a good idea to remove small prime
factors using special-purpose algorithms such as trial division, P-1, P+1,
or ECM, and use CADO-NFS only for the remaining composite factor.

Parts of the Number Field Sieve computation are massively distributed. In
this mode, client scripts (namely, `cado-nfs-client.py`) are run on many
nodes, connect to a central server, and run programs according to which
computations need to be done.  The programs (for the polynomial selection
and sieving steps) can run multithreaded. It is better to have them
run with a capped number of threads (say, 2), and run several clients per
node. By default, programs in this step are limited to 2 threads. When
running the computation on the local machine, the number of clients is
set so that the number of cores specified by `-t` are kept busy.

Run a larger factorization on several machines:
===============================================

CADO-NFS has several ways of operation, which can be roughly split into
three modes as follows.

 * For small computations, or for tests where it is important to have a
   single command line, the strategy
   [above](#run-a-factorization-on-the-current-machine) works. The
   `cado-nfs.py` script can arrange so that the binaries for all steps of
   the computation are run on the current machine, or possibly on other
   machines, via SSH. Some of the documentation here is specific to this
   mode of operation (see in particular
   [there](#check-that-your-network-configuration-is-correct) or
   [there](#check-that-your-ssh-configuration-is-correct)). If you get it
   right, you may manage to run factorizations as follows. However be
   aware that this mode of operation is fragile, and we advise not to use
   it beyond trivial testing.

   ```
   ./cado-nfs.py 353493749731236273014678071260920590602836471854359705356610427214806564110716801866803409 slaves.hostnames=hostname1,hostname2,hostname3 --slaves 4 --client-threads 2
   ```

   This starts 4 clients per host on the hosts `hostname1`, `hostname2`,
   and `hostname3`, and each client uses two cpus (threads). For
   hostnames that are not `localhost`, ssh is used to connect to the host
   and start a client there.  To configure ssh, see the [next
   section](#check-that-your-ssh-configuration-is-correct). For tasks
   that use the local machine only (not massively distributed tasks), the
   number of threads used is the one given by `-t` (which defaults to all
   threads on the local machine).

 * For larger computations where work distribution is an important point
   (distribution on several machines, possibly with different parameters
   for different machines), it is considerably more flexible to let the
   server be _just_ a server, and start clients separately, that will be
   used to offload the distributed tasks (polynomial selection and
   relation collection). Clients can come and go. The server has plenty
   of timeout provisions to deal with such events.

   This is called the `--server` mode (see
   [`scripts/cadofactor/README.md`](scripts/cadofactor/README.md) and
   [`scripts/cadofactor/parameters`](scripts/cadofactor/parameters)).
   See also [this thread](https://lists.gforge.inria.fr/pipermail/cado-nfs-discuss/2020-March/001168.html) on the old `cado-nfs-discuss` list (it's been [replaced](#contact-links)). If you want to use cado-nfs even to a little extent, we recomment that you familiarize with this mode of operation.

 * For much larger computations, the `cado-nfs.py` is only of moderate
   use. The individual cado-nfs binaries and internal scripts are the
   most flexible entry points, and should be used in order to adapt to
   the specificities of the platform being used (e.g. to deal with
   various requirements such as memory for filtering, interconnect for
   linear algebra, and so on).

Check that your network configuration is correct:
=================================================

In case you run a factorization on the local machine, the clients should be able
to connect to the server. Under Linux, CADO-NFS uses 'localhost' to identify the
server, thus you should have the following line in your /etc/hosts file:

```
127.0.0.1   localhost
```

Check that your SSH configuration is correct:
=============================================

The master script (unless in `--server` mode) uses SSH to connect to
available computing resources.  In order to avoid the script asking your
password or passphrase, you must have public-key authentication and an
agent.

The SSH keys are usually installed in the files `~/.ssh/id_rsa` and
`~/.ssh/id_rsa.pub`; if you don't have them yet, you can create them with the
`ssh-keygen` command. See the man page `ssh-keygen(1)` for details. The private
key should be protected with a passphrase, which you can enter when you
create the keys. Normally ssh will ask for the key's passphrase when you log
on to a machine, but this can be avoided by using ssh-agent, see the man
page `ssh-agent(1)`, and providing the passphrase to the agent with `ssh-add`.
Public-key authenticaton together with an ssh-agent will allow `cadofactor`
to use ssh to run commands on slave machines automatically.

Most of the recent Linux distributions will run an `ssh-agent` for you. But
if this is not the case with your distribution, or if you are running
`cado-nfs.py` inside a `screen` in order to logout from your desktop, you
will need to run the `ssh-agent` by hand. As a short recipe, you can type:
```
eval `ssh-agent`
ssh-add
```

You should also copy your public key, i.e., the contents of the file
`~/.ssh/id_rsa.pub`, into `$HOME/.ssh/authorized_keys` on the slave machines, to
allow logging in with public-key authentication.

Also, since localhost has an IP and key that varies, you should have
those 3 lines in your `$HOME/.ssh/config`:

```
Host    localhost
        StrictHostKeyChecking no
        UserKnownHostsFile /dev/null
```

If everything is correctly configured, when you type

ssh localhost

you should end up with a new shell on your machine, without having to
type any password/passphrase.


Restarting an interrupted factorization:
========================================

If you have started a factorization with the `cado-nfs.py` script, and it was
interrupted (for example because of a power failure) you can restart in
any of these two ways:

 * with the same `cado-nfs.py` command line if a work directory was
   explicitly provided on the command line:

   ```
   $ cado-nfs.py ... workdir=/path/to/workdir
   ```

 * with a single argument as in:

   ```
   $ cado-nfs.py     [[work directory]]/XXX.parameters_snapshot.YYY
   ```

   where `[[work directory]]` is the directory which has been chosen
   automatically, `XXX` is the "name" of the running factorisation, and `YYY`
   is the largest possible integer value for which such a file exists.

Factoring with SNFS:
====================

It is possible to take advantage of the special form of an integer and
use the Special Number Field Sieve. See
[`parameters/factor/parameters.F9`](parameters/factor/parameters.F9)
for that:

```
$ cado-nfs.py parameters/factor/parameters.F9 slaves.hostnames=localhost
```

Note in particular that you can force the special-q to be on the rational
side if this is more appropriate for your number, with
`tasks.sieve.sqside=0` on the `cado-nfs.py` command line or in the
parameter file (assuming side 0 is the rational side).

The default square root algorithm does not work in some very rare cases
that could possibly occur with SNFS polynomials (a degree 4 polynomial
with Galois group $Z/2 \times Z/2$ is the only reasonable example, next
case is for degree 8). The CRT approach is a workaround. See
[`sqrt/crtaglsqrt.c`](sqrt/crtaglsqrt.c) .

Big factorization (200 digits and more):
========================================

By default, to decrease memory usage, it is assumed that less than $2^32$
(~ four billion) relations or ideals are needed and that the ideals will
be less than $2^32$ (i.e., the `lpb0` and `lpb1` parameters are less or
equal to 32). In the case of factorizations of numbers of 200 digits and
more, these assumptions may not hold. In this case, you have to set some
variables in your `local.sh` script (see Configure section above for more
information on `local.sh` and section on big factorizations in
`local.sh.example`).

Factoring with two non-linear polynomials:
==========================================

You can find a bit of information on this topic in the development
version, in the GIT repository (see file
[`README.nonlinear`](README.nonlinear)).

Importing polynomials or relations:
===================================

If you have already computed a good polynomial and/or relations, you can
tell CADO-NFS to use them, see
[`scripts/cadofactor/README.md`](scripts/cadofactor/README.md).

Using CADO-NFS under Windows:
=============================

Portability of CADO-NFS on Windows was not an initial goal of that project,
however we give here some hints that might help people wanting to use CADO-NFS
under Windows. We hope that the following information can be useful to
some extent, but the general message is that you're on your own.

* Cado-NFS uses the POSIX interface all over the place, which means that
  in one form of the other, you need to have the corresponding
  functionality. If you don't, you're out of luck. (e.g., cado-nfs cannot
  build as a "pure" visual studio project.)

* if you only need the siever to run on Windows, then you only need to compile
  the `las` program on Windows.

* [Cygwin](http://www.cygwin.com/) provides a Unix-like environment,
  where compilation should be easy.  However the binary requires a
  `cygwin.dll` file. We have been told of problems with shared libraries,
  which the following seems to address:
  ```
  PATH="installed/lib/cado-nfs-x.y.z:$PATH" ./cado-nfs.py [...]
  ```

* if you want a binary without any dependency, you might try
  [MinGW](http://www.mingw.org/). The INSTALL file from GNU MPFR contains
  detailed instructions on how to compile MPFR under Windows. Those
  instructions should work for CADO-NFS too.  See
  [`dev_docs/howto-MinGW.txt`](dev_docs/howto-MinGW.txt).

* you might try to use MPIR (<http://mpir.org/>) instead of GMP. MPIR
  is a fork of GMP, which claims to be more portable under Windows.
  Alternatively, Windows ports of GMP shouldn't be too hard to find.

* you might succeed in compiling the cado-nfs binaries with a
  cross-compiler for Windows (which does not waive the runtime
  requirements for `cado-nfs.py`, notably on unix-like utilities). See
  [`dev_docs/README.cross`](dev_docs/README.cross) in the source code
  repository for information on how to cross-compile.

Examples of basic usage:
========================

* Run a full factorization on the local machine, using all available
  cores:

```
./cado-nfs.py 90377629292003121684002147101760858109247336549001090677693
```

* Run a full factorization on the local machine, using all available
  cores, but with a slightly modified set of default parameters.

  The difficulty here is that when `cado-nfs.py` uses a parameter file
  supplied on the command line, it does not automatically insert into the
  parameter set the options that are necessary for running jobs.
  Therefore, we need to add these options:

```
./cado-nfs.py --parameters ./parameters/factor/params.c60 90377629292003121684002147101760858109247336549001090677693 slaves.hostnames=localhost slaves.nrclients=2
```

* Run a full factorization on the local machine, using 8 threads for the
  server (this includes the linear algebra), and 4 jobs of 2 threads
  each for the polynomial selection and the sieving:

```
./cado-nfs.py 90377629292003121684002147101760858109247336549001090677693 --slaves 4 --client-threads 2 --server-threads 8
```

* Run a factorization in the given directory, interrupt it (with Ctrl-C,
  or whatever unexpected event), and resume the computation:

```
./cado-nfs.py 90377629292003121684002147101760858109247336549001090677693 workdir=/tmp/myfacto
[Ctrl-C]
./cado-nfs.py /tmp/myfacto/c60.parameters_snapshot.0
```

* Run a server on `machine1`, and a slave on `machine2`, disabling ssl:

```
machine1$ ./cado-nfs.py --server 90377629292003121684002147101760858109247336549001090677693 server.port=4242 server.ssl=no server.whitelist=machine2
machine2$ ./cado-nfs-client.py --server=http://machine1:4242 --bindir=...
```

Note: if you are on an insecure network, you'll have to activate ssl, and
then pass the appropriate sha1 certificate to the client (the server
prints the appropriate command-line to be copy-pasted on `machine2`).

* Run a factorization on `machine1`, and have it start automatically a
  slave on `machine2` via SSH:

```
./cado-nfs.py 90377629292003121684002147101760858109247336549001090677693
slaves.hostnames=machine1,machine2
```

Note that, in that case, you have to specify `machine1` as well in the list
of `hostnames` if you want it to contribute to the polynomial selection and
the sieving.


Stopping the factorization during a specific step:
==================================================
It is possible to stop the factorization:

```
./cado-nfs.py 90377629292003121684002147101760858109247336549001090677693 tasks.xxxx.run=false
```

This command works with: xxxx = polyselect, sieve, filter, linalg


Known problems:
===============

(some of these problems refer to versions or operating systems that are
no longer supported by cado-nfs anyway)

* when running the square root step in multi-thread mode (tasks.sqrt.threads=2
  or larger) with GMP <= 6.0, you might encounter an issue due to a "buglet"
  in GMP (<https://gmplib.org/list-archives/gmp-bugs/2015-March/003607.html>).
  Workaround: use tasks.sqrt.threads=1 or GMP >= 6.1.0.
* GCC 4.1.2 is known to miscompile CADO-NFS (see
  <http://cado-nfs.gforge.inria.fr/bug.php?14490>),
  GCC 4.2.0, 4.2.1 and 4.2.2 are also affected.
* under NetBSD 5.1 amd64, Pthreads in the linear algebra step seem not to
  work, please use `-t 1` option in `cado-nfs.py` or `tasks.linalg.threads=1x1`.
* under AIX, if GMP is compiled in 64-bit mode, you should set the
  environment variable `OBJECT_MODE`, for example:
  export `OBJECT_MODE=64`
* if you encounter the error "Exceeded maximum number of failed workunits,
  maxfailed=100", you can restart the factorization with
  `tasks.maxfailed=200`.   But it would be wise, first, to try to
  understand _why_ workunits are failing. This should not appear. It
  might be that all your workunits are timing out, because your `adrange`
  and `qrange` parameters are too large.  Or it's a bug in cado-nfs, and
  then it should definitely be reported.


Contact, links:
===============

The website of the project is hosted at:
   <http://cado-nfs.gforge.inria.fr/>

You can get the latest development version with:
```
git clone https://gitlab.inria.fr/cado-nfs/cado-nfs.git
```
or
```
git clone git@gitlab.inria.fr:cado-nfs/cado-nfs.git
```
(use the latter if you have an account on Inria gitlab, and commit access
to cado-nfs)

There is now a unique mailing-list associated to Cado-nfs
[cado-nfs@inria.fr](https://sympa.inria.fr/sympa/info/cado-nfs). Please
do not use the old `cado-nfs-discuss` mailing list, the infrastructure
that hosts this mailing list is set for removal in 2021.

If you find a bug, if you have a problem compiling cado-nfs, if you want to
factor a large number and seek for advice for tuning the parameters, then
the cado-nfs-discuss list is the right place to ask.

On the <https://gitlab.inria.fr/cado-nfs/cado-nfs> web page you can also
find the cado-nfs bug tracker (a.k.a project issues). The bug tracker is
an important piece of the cado-nfs development cycle.  Submitting bugs
and merge requests there is welcome (you need an Inria gitlab account),
although if you are unsure, it might be better to speak up on the
cado-nfs-discuss mailing list first.

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.

This file explains how to factor a number with two non linear polynomials.
This is currently experimental in CADO-NFS.

Assume for example we want to factor the following 59-digit number:

n = 71641520761751435455133616475667090434063332228247871795429

with the two quadratics below (found by Thomas Prest using Montgomery's two
quadratics method, see polyselect/twoquadratics.c):

f = 215609964539787*x^2 + 75006949764904*x + 44337721223995
g = -205964131819700*x^2 - 71651332635517*x + 1199051061668898
skew = 1.29196058385
m = 14849204829709953721577291784724593124898329527333780861554
(m is the common root of f and g mod n.)

1) you first have to create a polynomial file, see for example the one in
   tests/misc/c59_nonlinear.poly:

$ cat tests/misc/c59_nonlinear.poly
n: 71641520761751435455133616475667090434063332228247871795429
skew: 1.29196058385
c0: 44337721223995
c1: 75006949764904
c2: 215609964539787
Y0: 1199051061668898
Y1: -71651332635517
Y2: -205964131819700

2) run cado-nfs.py with importing this polynomial:

$ ./cado-nfs.py 71641520761751435455133616475667090434063332228247871795429 tasks.polyselect.import=tests/misc/c59_nonlinear.poly