POLYNOMIALS README
------------------
This file describes the different polynomial implementations present in the
utils/ directory.
GENERAL DESCRIPTION
-------------------
There are currently six families of files: cado_poly, fpoly, modul_poly,
mpz_poly, plain_poly and poly.
The cado_poly library implements operations on cado_poly structs, which
function is to stock the polynomial pair used for sieving as well as the
factor base parameters.
The fpoly library implements root refining by dichotomy, on polynomials with
floating-point coefficients. It is used in the sieve, both in sieve.c
(computation of lognorms of prime products) and in las.c (norms of
polynomials). We also use it in polynomial selection, in auxiliary.c (in the
computation of the optimal skewness).
The modul_poly files implement arithmetic on modular polynomials, with
coefficients of a generic TYPEDEFined type, which by now is an unsigned long.
These files are used in rootfinder.c, in the computation of polynomial roots
modulo p of the algebraic polynomial.
Polynomials on mpz_poly are implicit (there is no struct), and they have gmp
integers as coefficients. The mpz_poly files are used in the making of the
factor base, in makefb.c (which builds the factor base).
The plain_poly polynomials have a custom coefficient type, which is actually a
64-bit integer. They are used in utils/rootfinder.c (to find roots of the
algebraic polynomial), and in sqrt/algsqrt.c (to find a suitable modulus).
The poly files implement polynomials with multiprecision integers as
coefficients. We use them in sqrt/algsqrt.c to represent rings of integers.
and in fast_rootsieve.c, to represent the involved polynomials.
TODO
----
- Write a SPECIFIC DESCRIPTION of the capabilities of the previous
implementations.
- Evaluate overlap and simplify the polynomial implementations as much as
possible.