% (C) 2007, William Hart, David Harvey
% This file is part of FLINT.
% FLINT is free software; you can redistribute it and/or modify
% it under the terms of the GNU General Public License as published by
% the Free Software Foundation; either version 2 of the License, or
% (at your option) any later version.
% FLINT is distributed in the hope that it will be useful,
% but WITHOUT ANY WARRANTY; without even the implied warranty of
% MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
% GNU General Public License for more details.
% You should have received a copy of the GNU General Public License
% along with FLINT; if not, write to the Free Software
% Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
\documentclass[a4paper,10pt]{article}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{eucal}
\usepackage{amscd}
\usepackage{url}
\usepackage{hyperref}
\usepackage{listings}
\usepackage{wrapfig}
\urlstyle{sf}
\addtolength{\oddsidemargin}{-0.75in}
\addtolength{\evensidemargin}{-0.75in}
\addtolength{\textwidth}{1.5in}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\HH}{\mathcal{H}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\I}{\mathbb{I}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Pee}{\mathbb{P}}
\newcommand{\EuO}{\mathcal{O}}
\newcommand{\Qbar}{\overline{\mathbb{Q}}}
\newcommand{\fn}{\hfill[Function]}
\newcommand{\macro}{\hfill[Macro]}
\newcommand{\gmp}{\hfill[GMP]}
\newcommand{\code}{\lstinline}
\newcommand{\ljk}[2]{\left(\frac{#1}{#2}\right)}
\newcommand{\modulo}[1]{\;\left(\mbox{mod}\;#1\right)}
\newcommand{\fr}{\mathfrak}
\def\notdivides{\mathrel{\kern-3pt\not\!\kern4.5pt\bigm|}}
\def\nmid{\notdivides}
\def\nsubseteq{\mathrel{\kern-3pt\not\!\kern2.5pt\subseteq}}
\parindent=0pt
\parskip 4pt plus 2pt minus 2pt
%\email{w.b.hart@maths.warwick.ac.uk}
\title{FLINT 1.3: Fast Library for Number Theory}
\author{William B. Hart and David Harvey}
\begin{document}
\maketitle
\tableofcontents
\lstset{language=c}
\lstset{basicstyle=\ttfamily}
\lstset{keywordstyle=}
%\lstset{morekeywords={mpz_t,mpz_poly_t,fmpz_poly_t}}
\lstset{escapeinside=\%\%}
\section{Introduction}
FLINT is a C library of functions for doing number theory. It is highly optimised and can be compiled on numerous platforms. FLINT also has the aim of providing support for multicore and multiprocessor computer architectures, though we do not yet provide this facility.
FLINT is currently maintained by William Hart of Warwick University in the UK.
As of version 1.1.0 FLINT supports 32 and 64 bit processors including x86, PPC, Alpha and Itanium processors, though in theory it compiles on any machine with GCC version 3.4 or later and with GMP version 4.2.1 or MPIR 0.9.0 or later.
FLINT is supplied as a set of modules, \code{fmpz}, \code{fmpz_poly}, etc., each of which can be linked to a C program making use of their functionality.
All of the functions in FLINT have a corresponding test function provided in an appropriately named test file, e.g: all the functions in the file \code{fmpz_poly.c} have test functions in the file \code{fmpz_poly-test.c}.
\section{Building and using FLINT}
The easiest way to use FLINT is to build a shared library. Simply download the FLINT tarball and untar it on your system.
FLINT requires GMP version 4.2.1 or later or MPIR version 0.9.0 or later. Set the environment variables \code{FLINT_GMP_LIB_DIR} and \code{FLINT_GMP_INCLUDE_DIR} to point to your GMP or MPIR library and include directories respectively. Alternatively you can set default values for these environment variables in the \code{flint_env} file.
The \code{NTL-interface} module of FLINT requires NTL version 5.4.1 or later. However NTL is not required to build FLINT if this interface module is not required. To build with NTL set the environment variables \code{FLINT_NTL_LIB_DIR} and \code{FLINT_NTL_INCLUDE_DIR} to point to your NTL library and include directories respectively.
By default \code{zn_poly} 0.8 or later is required to build FLINT. In order to use \code{zn_poly} one must set the environment variables \code{FLINT_ZNPOLY_LIB_DIR} and \code{FLINT_ZNPOLY_INCLUDE_DIR} to point to your \code{zn_poly} library and include directories respectively. You must build \code{zn_poly} with the \code{-fPIC} option if you wish to build FLINT as a library. FLINT can be built without \code{zn_poly} by setting \code{HAVE_ZNPOLY=0} in the file \code{flint_env}.
Once the environment variables are set or defaults are set in \code{flint_env} simply type:
\code{source flint_env}
in the main directory of the FLINT directory tree.
Finally type:
\code{make library}
Move the library file \code{libflint.so}, \code{libflint.dll} or \code{libflint.dylib} (depending on your platform) into your library path and move all the .h files in the main directory of FLINT into your include path.
Now to use FLINT, simply include the appropriate header files for the FLINT modules you wish to use in your C program. Then compile your program, linking against the FLINT library, \code{zn_poly} and GMP with the options \code{-lflint -lgmp -lzn_poly}.
If you are using the \code{NTL-interface}, you will also need to link against NTL with the \code{-lntl} linker option.
\section{Test code}
Each module of FLINT has an extensive associated test module. We strongly recommend running the test programs before relying on results from FLINT on your system.
To make and run the test programs, simply type:
\code{make check}
in the main FLINT directory.
To test the \code{NTL-interface} module simply:
\code{make NTL-interface-test}
\code{./NTL-interface-test}
\section{Reporting bugs}
The maintainer wishes to be made aware of any and all bugs. Please send an email with your bug report to hart\_wb@yahoo.com.
If possible please include details of your system, version of gcc, version of GMP and precise details of how to replicate the bug.
Note that FLINT needs to be linked against version 4.2.1 or later of GMP or version 0.9.0 or later of MPIR and must be compiled with gcc version 3.4 or later. In particular the compiler must be c99 compatible.
\section{Example programs}
FLINT comes with a number of example programs to demonstrate current and future FLINT features. To make the example programs, type:
\code{make examples}
The current example programs are:
\code{delta_qexp} Compute the first $n$ terms of the delta function, e.g. \code{delta_qexp 1000000} will compute the first one million terms of the $q$-expansion of delta.
\code{BPTJCubes} Implements the algorithm of Beck, Pine, Tarrant and Jensen for finding solutions to the equation $x^3+y^3+z^3 = k$.
\code{bernoulli_zmod} Compute bernoulli numbers modulo a large number of primes.
\code{expmod} Computes a very large modular exponentiation.
\code{thetaproduct} Computes the product of two very large theta functions and determines the number of zero coefficients.
\section{FLINT macros}
In the file flint.h are various useful macros.
The macro constant \code{FLINT_BITS} is set at compile time to be the number of bits per limb on the machine. FLINT requires it to be either 32 or 64 bits. Other architectures are not currently supported.
The macro constant \code{FLINT_D_BITS} is set at compile time to be the number of bits per double on the machine or the number of bits per limb, whichever is smaller. This will have the value 53 or 32 on currently supported architectures. Numerous functions using precomputed inverses only support operands up to \code{FLINT_D_BITS - 1} bits, hence the macro.
\code{FLINT_ABS(x)} returns the absolute value of a \code{long x}.
\code{FLINT_MIN(x, y)} returns the minimum of two \code{long} or two \code{unsigned long} values \code{x} and \code{y}.
\code{FLINT_MAX(x, y)} returns the maximum of two \code{long} or two \code{unsigned long} values \code{x} and \code{y}.
\code{FLINT_BIT_COUNT(x)} returns the number of binary bits required to represent an \code{unsigned long x}.
\section{The fmpz\_poly module}
The \code{fmpz_poly_t} data type represents elements of $\Z[x]$. The \code{fmpz_poly} module provides routines for memory management, basic arithmetic, and conversions to/from other types.
Each coefficient of an \code{fmpz_poly_t} is an integer of the FLINT \code{fmpz_t} type.
Unless otherwise specified, all functions in this section permit aliasing between their input arguments and between their input and output arguments.
\subsection{Simple example}
The following example computes the square of the polynomial $5x^3 - 1$.
\begin{lstlisting}
#include "fmpz_poly.h"
....
fmpz_poly_t x, y;
fmpz_poly_init(x);
fmpz_poly_init(y);
fmpz_poly_set_coeff_ui(x, 3, 5);
fmpz_poly_set_coeff_si(x, 0, -1);
fmpz_poly_mul(y, x, x);
fmpz_poly_print(x); printf("\n");
fmpz_poly_print(y); printf("\n");
fmpz_poly_clear(x);
fmpz_poly_clear(y);
\end{lstlisting}
The output is:
\begin{lstlisting}
4 -1 0 0 5
7 1 0 0 -10 0 0 25
\end{lstlisting}
\subsection{Definition of the fmpz\_poly\_t polynomial type}
The \code{fmpz_poly_t} type is a typedef for an array of length 1 of \code{fmpz_poly_struct}'s. This permits passing parameters of type \code{fmpz_poly_t} `by reference' in a manner similar to the way GMP integers of type \code{mpz_t} can be passed by reference.
In reality one never deals directly with the struct and simply deals with objects of type \code{fmpz_poly_t}. For simplicity we will think of an \code{fmpz_poly_t} as a struct, though in practice to access fields of this struct, one needs to dereference first, e.g. to access the \code{length} field of an \code{fmpz_poly_t} called \code{poly1} one writes \code{poly1->length}.
An \code{fmpz_poly_t} is said to be \emph{normalised} if either \code{length == 0}, or if the final coefficient is nonzero. All \code{fmpz_poly} functions expect their inputs to be normalised, and unless otherwise specified they produce output that is normalised.
It is recommended that users do not access the fields of an \code{fmpz_poly_t} or its coefficient data directly, but make use of the functions designed for this purpose (detailed below).
Functions in \code{fmpz_poly} do all the memory management for the user. One does not need to specify the maximum length or number of limbs per coefficient in advance before using a polynomial object. FLINT reallocates space automatically as the computation proceeds, if more space is required.
We now describe the functions available in \code{fmpz_poly}.
\subsection{Initialisation and memory management}
\begin{lstlisting}
void fmpz_poly_init(fmpz_poly_t poly)
\end{lstlisting}
\begin{quote}
Initialise an \code{fmpz_poly_t} for use. The length of \code{poly} is set to zero. A corresponding call to \code{fmpz_poly_clear} must be made after finishing with the \code{fmpz_poly_t} to free the memory used by the polynomial.
For efficiency reasons, a call to \code{fmpz_poly_init} does not actually allocate any memory for coefficients. Each of the functions will automatically allocate any space needed for coefficients and in fact the easiest way to use \code{fmpz_poly} is to let FLINT do all the allocation automatically.
To this end, a user need only ever make calls to the \code{fmpz_poly_init} and \code{fmpz_poly_clear} memory management functions if they so wish. Naturally, more efficient code may result if the other memory management functions are also used.
\end{quote}
\begin{lstlisting}
void fmpz_poly_realloc(fmpz_poly_t poly, unsigned long alloc)
\end{lstlisting}
\begin{quote}
Shrink or expand the polynomial so that it has space for precisely \code{alloc} coefficients. If \code{alloc} is less than the current length, the polynomial is truncated (and then normalised), otherwise the coefficients and current length remain unaffected.
If the parameter \code{alloc} is zero, any space currently allocated for coefficients in \code{poly} is free'd. A subsequent call to \code{fmpz_poly_clear} is still permitted and does nothing.
\end{quote}
\begin{lstlisting}
void fmpz_poly_fit_length(fmpz_poly_t poly, unsigned long alloc)
\end{lstlisting}
\begin{quote}
Expand the polynomial (if necessary) so that it has space for at least \code{alloc} coefficients. This function will never shrink the memory allocated for coefficients and the contents of the existing coefficients and the current length remain unaffected.
\end{quote}
\begin{lstlisting}
void fmpz_poly_fit_limbs(fmpz_poly_t poly, unsigned long limbs)
\end{lstlisting}
\begin{quote}
Currently all the coefficients of an \code{fmpz_poly_t} have the same number of limbs of space allocated for them (plus an additional limb for the sign/size limb). This function can be used to increase the space allocated for the coefficients. As all functions in the \code{fmpz_poly} module automatically manage memory allocation for the user, this function should only be used when directly manipulating the coefficients by means of the functions in the \code{fmpz} module (described below). In a later version of FLINT, this function will become defunct, as FLINT will automatically reallocate \code{fmpz_t}'s when there is insufficient space, and this will include polynomial coefficients.
\end{quote}
\begin{lstlisting}
void fmpz_poly_clear(fmpz_poly_t poly)\end{lstlisting}
\begin{quote}
Free all memory used by the coefficients of \code{poly}. The polynomial object \code{poly} cannot be used again until a subsequent call to an initialisation function is made.
\end{quote}
\subsection{Setting/retrieving coefficients}
\begin{lstlisting}
void fmpz_poly_get_coeff_mpz(mpz_t x, const fmpz_poly_t poly,
unsigned long n)
\end{lstlisting}
\begin{quote}
Retrieve coefficient $n$ as an \code{mpz_t}.
Coefficients are numbered from zero, starting with the constant coefficient.
Sets \code{x} to zero when $n >= $ \code{poly->length}.
\end{quote}
\begin{lstlisting}
void fmpz_poly_get_coeff_mpz_read_only(mpz_t x,
const fmpz_poly_t poly, unsigned long n)
\end{lstlisting}
\begin{quote}
Retrieve coefficient $n$ as a read only \code{mpz_t}. The function must be passed an uninitialised \code{mpz_t}. The \code{mpz_t} can then be used as an input to a GMP function, but not as an output. Its contents may be inspected, but not alterered. This function will in general be much faster than the function \code{fmpz_poly_get_coeff_mpz} which makes an extra copy of the data.
Coefficients are numbered from zero, starting with the constant coefficient.
Sets \code{x} to zero when $n >= $ \code{poly->length}.
\end{quote}
\begin{lstlisting}
void fmpz_poly_set_coeff_mpz(fmpz_poly_t poly, unsigned long n,
mpz_t x)
\end{lstlisting}
\begin{quote}
Set coefficient $n$ to the value of the given \code{mpz_t}.
Coefficients are numbered from zero, starting with the constant coefficient. If $n$ represents a coefficient beyond the current length of \code{poly}, zero coefficients are added in between the existing coefficients and the new coefficient, if required.
\end{quote}
\begin{lstlisting}
void fmpz_poly_get_coeff_fmpz(fmpz_t x, const fmpz_poly_t poly,
unsigned long n)
\end{lstlisting}
\begin{quote}
Retrieve coefficient $n$ as an \code{fmpz_t}.
Coefficients are numbered from zero, starting with the constant coefficient.
Sets \code{x} to zero when $n >= $ \code{poly->length}.
\end{quote}
\begin{lstlisting}
void fmpz_poly_set_coeff_fmpz(fmpz_poly_t poly, unsigned long n,
fmpz_t x)
\end{lstlisting}
\begin{quote}
Set coefficient $n$ to the value of the given \code{fmpz_t}.
Coefficients are numbered from zero, starting with the constant coefficient. If $n$ represents a coefficient beyond the current length of \code{poly}, zero coefficients are added in between the existing coefficients and the new coefficient, if required.
\end{quote}
\begin{lstlisting}
unsigned long fmpz_poly_get_coeff_ui(const fmpz_poly_t poly,
unsigned long n)
\end{lstlisting}
\begin{quote}
Return the absolute value of coefficient $n$ as an \code{unsigned long}.
Coefficients are numbered from zero, starting with the constant coefficient. If the coefficient is longer than a single limb, the first limb is returned.
Returns zero when $n >= $ \code{poly->length}.
\end{quote}
\begin{lstlisting}
void fmpz_poly_set_coeff_ui(fmpz_poly_t poly, unsigned long n,
unsigned long x)
\end{lstlisting}
\begin{quote}
Set coefficient $n$ to the value of the given \code{unsigned long}.
Coefficients are numbered from zero, starting with the constant coefficient. If $n$ represents a coefficient beyond the current length of \code{poly}, zero coefficients are added in between the existing coefficients and the new coefficient, if required.
\end{quote}
\begin{lstlisting}
long fmpz_poly_get_coeff_si(const fmpz_poly_t poly,
unsigned long n)
\end{lstlisting}
\begin{quote}
Return the value of coefficient $n$ as a \code{long}.
Coefficients are numbered from zero, starting with the constant coefficient. If the coefficient will not fit into a \code{long}, i.e. if its absolute value takes up more than \code{FLINT_BITS - 1} bits then the result is undefined.
Returns zero when $n >= $ \code{poly->length}.
\end{quote}
\begin{lstlisting}
void fmpz_poly_set_coeff_si(fmpz_poly_t poly, unsigned long n,
long x)
\end{lstlisting}
\begin{quote}
Set coefficient $n$ to the value of the given \code{long}.
Coefficients are numbered from zero, starting with the constant coefficient. If $n$ represents a coefficient beyond the current length of \code{poly}, zero coefficients are added in between the existing coefficients and the new coefficient, if required.
\end{quote}
\begin{lstlisting}
fmpz_t fmpz_poly_get_coeff_ptr(fmpz_poly_t poly, unsigned long n)
\end{lstlisting}
\begin{quote}
Return a reference to coefficient $n$ (as an \code{fmpz_t}). This function is provided so that individual coefficients can be accessed and operated on by functions in the \code{fmpz} module. This function does not make a copy of the data, but returns a reference to the actual coefficient.
Coefficients are numbered from zero, starting with the constant coefficient.
Returns NULL when $n >= $ \code{poly->length}.
\end{quote}
\begin{lstlisting}
fmpz_t fmpz_poly_lead(const fmpz_poly_t poly)
\end{lstlisting}
\begin{quote}
Return a reference to the leading coefficient (as an \code{fmpz_t}) of \code{poly}. This function is provided so that the leading coefficient can be easily accessed and operated on by functions in the \code{fmpz} module. This function does not make a copy of the data, but returns a reference to the actual coefficient.
Returns NULL when the polynomial has length zero.
\end{quote}
\subsection{String conversions and I/O}
The functions in this section are not intended to be particularly fast. They are intended mainly as a debugging aid.
For the string output functions there are two variants. The first uses a simple string representation of polynomials which prints only the length of the polynomial and the integer coefficients, whilst the latter variant (appended with \code{_pretty}) uses a more traditional string representation of polynomials which prints a variable name as part of the representation.
The first string representation is given by a sequence of integers, in decimal notation, separated by whitespace. The first integer gives the length of the polynomial; the remaining \code{length} integers are the coefficients. For example $5x^3 - x + 1$ is represented by the string ``\code{4 1 -1 0 5}'', and the zero polynomial is represented by ``\code{0}''. The coefficients may be signed and arbitrary precision.
The string representation of the functions appended by \code{_pretty} includes only the non-zero terms of the polynomial, starting with the one of highest degree. Each term starts with a coefficient, prepended with a sign (positive or negative), followed by the character \code{*}, followed by a variable name, which must be passed as a string parameter to the function, followed by a carot \code{^} followed by a non-negative exponent.
If the sign of the leading coefficient is positive, it is omitted. Also the exponents of the degree 1 and 0 terms are omitted, as is the variable and the \code{*} character in the case of the degree 0 coefficient. If the coefficient is plus or minus one, the coefficient is omitted, except for the sign.
Some examples of the \code{_pretty} representation are:
\begin{lstlisting}
5*x^3+7*x-4
x^2+3
-x^4+2*x-1
x+1
5
\end{lstlisting}
\begin{lstlisting}
int fmpz_poly_from_string(fmpz_poly_t poly, const char * s)
\end{lstlisting}
\begin{quote}
Import a polynomial from a string. If the string represents a valid polynomial the function returns 1, otherwise it returns 0.
\end{quote}
\begin{lstlisting}
char * fmpz_poly_to_string(const fmpz_poly_t poly)
char * fmpz_poly_to_string_pretty(const fmpz_poly_t poly,
const char * x)
\end{lstlisting}
\begin{quote}
Convert a polynomial to a string and return a pointer to the string. Space is allocated for the string by this function and must be freed when it is no longer used, by a call to \code{free}.
The \code{pretty} version must be supplied with a string \code{x} which represents the variable name to be used when printing the polynomial.
\end{quote}
\begin{lstlisting}
void fmpz_poly_fprint(const fmpz_poly_t poly, FILE * f)
void fmpz_poly_fprint_pretty(const fmpz_poly_t poly, FILE * f,
const char * x)
\end{lstlisting}
\begin{quote}
Convert a polynomial to a string and write it to the given stream.
The \code{pretty} version must be supplied with a string \code{x} which represents the variable name to be used when printing the polynomial.
\end{quote}
\begin{lstlisting}
void fmpz_poly_print(const fmpz_poly_t poly)
void fmpz_poly_print_pretty(const fmpz_poly_t poly, const char * x)
\end{lstlisting}
\begin{quote}
Convert a polynomial to a string and write it to \code{stdout}.
The \code{pretty} version must be supplied with a string \code{x} which represents the variable name to be used when printing the polynomial.
\end{quote}
\begin{lstlisting}
void fmpz_poly_fread(fmpz_poly_t poly, FILE* f)
\end{lstlisting}
\begin{quote}
Read a polynomial from the given stream. Return 1 if the data from the stream represented a valid polynomial, otherwise return 0.
\end{quote}
\begin{lstlisting}
void fmpz_poly_read(fmpz_poly_t poly)
\end{lstlisting}
\begin{quote}
Read a polynomial from \code{stdin}. Return 1 if the data read from \code{stdin} represented a valid polynomial, otherwise return 0.
\end{quote}
\subsection{Polynomial parameters (length, degree, max limbs, etc.)}
\begin{lstlisting}
long fmpz_poly_degree(const fmpz_poly_t poly)
\end{lstlisting}
\begin{quote}
Return \code{poly->length - 1}. The zero polynomial is defined to have degree $-1$.
\end{quote}
\begin{lstlisting}
unsigned long fmpz_poly_length(const fmpz_poly_t poly)
\end{lstlisting}
\begin{quote}
Return \code{poly->length}. The zero polynomial is defined to have length $0$.
\end{quote}
\begin{lstlisting}
unsigned long fmpz_poly_max_limbs(const fmpz_poly_t poly)
\end{lstlisting}
\begin{quote}
Returns the maximum number of limbs required to store the absolute value of coefficients of \code{poly}. \end{quote}
\begin{lstlisting}
long fmpz_poly_max_bits(const fmpz_poly_t poly)
\end{lstlisting}
\begin{quote}
Computes the maximum number of bits $b$ required to store the absolute value of coefficients of \code{poly}. If all the coefficients of \code{poly} are non-negative, $b$ is returned, otherwise $-b$ is returned. \end{quote}
\begin{lstlisting}
long fmpz_poly_max_bits1(const fmpz_poly_t poly)
\end{lstlisting}
\begin{quote}
Computes the maximum number of bits $b$ required to store the absolute value of coefficients of \code{poly}. If all the coefficients of \code{poly} are non-negative, $b$ is returned, otherwise $-b$ is returned.
The assumption is made that the absolute value of each coefficient fits into an unsigned long. This function will be more efficient than the more general \code{fmpz_poly_max_bits} in this situation.
\end{quote}
\subsection{Assignment and basic manipulation}
\begin{lstlisting}
void fmpz_poly_set(fmpz_poly_t output, const fmpz_poly_t poly)
\end{lstlisting}
\begin{quote}
Set polynomial \code{output} equal to the polynomial \code{poly}.
\end{quote}
\begin{lstlisting}
void fmpz_poly_swap(fmpz_poly_t poly1, fmpz_poly_t poly2)
\end{lstlisting}
\begin{quote}
Efficiently swap two polynomials. The coefficients are not moved in memory, pointers are simply switched. \end{quote}
\begin{lstlisting}
void fmpz_poly_zero(fmpz_poly_t poly)
\end{lstlisting}
\begin{quote}
Set the polynomial to the zero polynomial.
\end{quote}
\begin{lstlisting}
void fmpz_poly_zero_coeffs(fmpz_poly_t poly, unsigned long n)
\end{lstlisting}
\begin{quote}
Set the first $n$ coefficients of \code{poly} to zero. If $n$ is greater than or equal to the length of \code{poly} then \code{poly} is set to the zero polynomial.
\end{quote}
\begin{lstlisting}
void fmpz_poly_neg(fmpz_poly_t output, fmpz_poly_t poly)
\end{lstlisting}
\begin{quote}
Negate the polynomial \code{poly}, i.e. set \code{output} to \code{-poly}.
\end{quote}
\begin{lstlisting}
void fmpz_poly_truncate(fmpz_poly_t poly, const unsigned long trunc)
\end{lstlisting}
\begin{quote}
If \code{trunc} is less than the current length of the polynomial, truncate the polynomial to that length. Note that as the function normalises its output, the eventual length of the polynomial may be less than \code{trunc}.
\end{quote}
\begin{lstlisting}
void fmpz_poly_reverse(fmpz_poly_t output,
const fmpz_poly_t poly, unsigned long length)
\end{lstlisting}
\begin{quote}
This function considers the polynomial \code{poly} to be of length $n$, notionally truncating and zero padding if required, and reverses the result. Since this function normalises its result the eventual length of \code{output} may be less than \code{length}.
\end{quote}
\begin{lstlisting}
void _fmpz_poly_normalise(fmpz_poly_t poly)
\end{lstlisting}
\begin{quote}
This function normalises \code{poly} so that the leading coefficient is non-zero (or the polynomial is the zero polynomial). As all functions in \code{fmpz_poly} expect and return normalised polynomials, this function is only used when manipulating the coefficients directly by making use of the functions in the \code{fmpz} module (described below).
\end{quote}
\subsection{Conversions}
\begin{lstlisting}
void fmpz_poly_to_zmod_poly(zmod_poly_t zpol, fmpz_poly_t fpol)
void fmpz_poly_to_zmod_poly_no_red(zmod_poly_t zpol, fmpz_poly_t fpol)
\end{lstlisting}
\begin{quote}
Reduce the coefficients of the \code{fmpz_poly_t fpol} mod the modulus of the \code{zmod_poly_t zpol} and store the result in \code{zpol}.
If the modulus of \code{zpol} is $p$, the \code{no_red} version of this function assumes that the coefficients of \code{fmpz_poly_t fpol} are in the range $[-p, p)$ and the computation is done more efficiently.
These functions are provided to enable the implementation of multimodular algorithms.
\end{quote}
\begin{lstlisting}
void zmod_poly_to_fmpz_poly_unsigned(fmpz_poly_t fpol,
zmod_poly_t zpol)
\end{lstlisting}
\begin{quote}
Convert the \code{zmod_poly_t zpol} to an \code{fmpz_poly_t}. The coefficients of the \code{fmpz_poly_t} will all be unsigned.
\end{quote}
\begin{lstlisting}
void zmod_poly_to_fmpz_poly(fmpz_poly_t fpol, zmod_poly_t zpol)
\end{lstlisting}
\begin{quote}
Convert the \code{zmod_poly_t zpol} to an \code{fmpz_poly_t}. If \code{p} is the modulus of \code{zpol} then coefficients which lie in $[0, p/2]$ are unchanged, however, coefficients $a$ in the range $(p/2, p)$ become $a - p$.
This function is provided to enable the implementation of multimodular algorithms.
\end{quote}
\subsection{Chinese remaindering}
\begin{lstlisting}
int fmpz_poly_CRT_unsigned(fmpz_poly_t res, fmpz_poly_t fpol,
zmod_poly_t zpol, fmpz_t newmod, fmpz_t oldmod)
\end{lstlisting}
\begin{quote}
Performs modular recombination using the Chinese Remainder Theorem. If \code{zpol} has modulus $p$, \code{newmod} is set equal to \code{oldmod*p} and each coefficient of \code{res} is set to the unique value modulo \code{newmod}, in the range $[0, \mbox{newmod})$ which is $a$ modulo \code{oldmod} and $b$ modulo $p$, where $a$ is the coefficient of \code{fpol} and $b$ is the corresponding coefficient of \code{zpol}.
The coefficients of \code{fpol} are assumed to be unsigned.
\end{quote}
\begin{lstlisting}
int fmpz_poly_CRT(fmpz_poly_t res, fmpz_poly_t fpol,
zmod_poly_t zpol, fmpz_t newmod, fmpz_t oldmod)
\end{lstlisting}
\begin{quote}
Performs modular recombination using the Chinese Remainder Theorem. If \code{zpol} has modulus $p$, \code{newmod} is set equal to \code{oldmod*p} and each coefficient of \code{res} is set to the unique value modulo \code{newmod}, in the range $[-(\mbox{newmod} - 1)/2, \mbox{newmod}/2]$ which is $a$ modulo \code{oldmod} and $b$ modulo $p$, where $a$ is the coefficient of \code{fpol} and $b$ is the corresponding coefficient of \code{zpol}.
\end{quote}
\subsection{Comparison}
\begin{lstlisting}
int fmpz_poly_equal(const fmpz_poly_t poly1,
const fmpz_poly_t poly2)
\end{lstlisting}
\begin{quote}
Return 1 if the two polynomials are equal, 0 otherwise.
\end{quote}
\subsection{Shifting}
\begin{lstlisting}
void fmpz_poly_left_shift(fmpz_poly_t output,
const fmpz_poly_t poly, unsigned long n)
\end{lstlisting}
\begin{quote}
Shift poly to the left by $n$ coefficients (multiply by $x^n$) and write the result to \code{output}. Zero coefficients are inserted.
The parameter $n$ must be non-negative, but can be zero.
\end{quote}
\begin{lstlisting}
void fmpz_poly_right_shift(fmpz_poly_t output,
const fmpz_poly_t poly, unsigned long n)
\end{lstlisting}
\begin{quote}
Shift poly to the right by $n$ coefficients (divide by $x^n$ and discard the remainder) and write the result to \code{output}.
The parameter $n$ must be non-negative, but can be zero. Shifting right by greater than or equal to the current length of the polynomial results in the zero polynomial.
\end{quote}
\subsection{Norms}
\begin{lstlisting}
void fmpz_poly_2norm(fmpz_t norm, fmpz_poly_t pol)
\end{lstlisting}
\begin{quote}
Sets \code{norm} to the euclidean norm of \code{pol}, i.e. the integer square root (discarding the remainder) of the sum of the squares of the coefficients of \code{pol}.
\end{quote}
\subsection{Addition/subtraction}
\begin{lstlisting}
void fmpz_poly_add(fmpz_poly_t output, const fmpz_poly_t poly1,
const fmpz_poly_t poly2)
\end{lstlisting}
\begin{quote}
Set the output to the sum of the input polynomials.
Note that if \code{poly1} and \code{poly2} have the same length, cancellation may occur (if the leading coefficients have the same absolute values but opposite signs) and so the result may have less coefficients than either of the inputs.
\end{quote}
\begin{lstlisting}
void fmpz_poly_sub(fmpz_poly_t output, const fmpz_poly_t poly1,
const fmpz_poly_t poly2)
\end{lstlisting}
\begin{quote}
Set the output to \code{poly1 - poly2}.
Note that if \code{poly1} and \code{poly2} have the same length, cancellation may occur (if the leading coefficients have the same values) and so the result may have less coefficients than either of the inputs.
\end{quote}
\subsection{Scalar multiplication and division}
\begin{lstlisting}
void fmpz_poly_scalar_mul_ui(fmpz_poly_t output,
const fmpz_poly_t poly, unsigned long x)
\end{lstlisting}
\begin{quote}
Multiply \code{poly} by the \code{unsigned long x} and write the result to \code{output}.
\end{quote}
\begin{lstlisting}
void fmpz_poly_scalar_mul_si(fmpz_poly_t output,
const fmpz_poly_t poly, long x)
\end{lstlisting}
\begin{quote}
Multiply \code{poly} by the \code{long x} and write the result to \code{output}.
\end{quote}
\begin{lstlisting}
void fmpz_poly_scalar_mul_fmpz(fmpz_poly_t output,
const fmpz_poly_t poly, const fmpz_t x)
\end{lstlisting}
\begin{quote}
Multiply \code{poly} by the \code{fmpz_t x} and write the result to \code{output}.
\end{quote}
\begin{lstlisting}
void fmpz_poly_scalar_mul_mpz(fmpz_poly_t output,
const fmpz_poly_t poly, const mpz_t x)
\end{lstlisting}
\begin{quote}
Multiply \code{poly} by the \code{mpz_t x} and write the result to \code{output}.
\end{quote}
\begin{lstlisting}
void fmpz_poly_scalar_div_ui(fmpz_poly_t output,
const fmpz_poly_t poly, unsigned long x)
\end{lstlisting}
\begin{quote}
Divide \code{poly} by the \code{unsigned long x}, round quotients towards minus infinity, discard remainders and write the result to \code{output}.
\end{quote}
\begin{lstlisting}
void fmpz_poly_scalar_div_si(fmpz_poly_t output,
const fmpz_poly_t poly, long x)
\end{lstlisting}
\begin{quote}
Divide \code{poly} by the \code{long x}, round quotients towards minus infinity, discard remainders and write the result to \code{output}.
\end{quote}
\begin{lstlisting}
void fmpz_poly_scalar_tdiv_ui(fmpz_poly_t output,
const fmpz_poly_t poly, unsigned long x)
\end{lstlisting}
\begin{quote}
Divide \code{poly} by the \code{unsigned long x}, round quotients towards zero, discard remainders and write the result to \code{output}.
\end{quote}
\begin{lstlisting}
void fmpz_poly_scalar_tdiv_si(fmpz_poly_t output,
const fmpz_poly_t poly, long x)
\end{lstlisting}
\begin{quote}
Divide \code{poly} by the \code{long x}, round quotients towards zero, discard remainders and write the result to \code{output}.
\end{quote}
\begin{lstlisting}
void fmpz_poly_scalar_div_exact_ui(fmpz_poly_t output,
const fmpz_poly_t poly, unsigned long x)
\end{lstlisting}
\begin{quote}
Divide \code{poly} by the \code{unsigned long x}. Division is assumed to be exact and the result is undefined otherwise.
\end{quote}
\begin{lstlisting}
void fmpz_poly_scalar_div_exact_si(fmpz_poly_t output,
const fmpz_poly_t poly, long x)
\end{lstlisting}
\begin{quote}
Divide \code{poly} by the \code{long x}. Division is assumed to be exact and the result is undefined otherwise.
\end{quote}
\begin{lstlisting}
void fmpz_poly_scalar_div_fmpz(fmpz_poly_t output,
const fmpz_poly_t poly, const fmpz_t x)
\end{lstlisting}
\begin{quote}
Divide \code{poly} by the \code{fmpz_t x}, round quotients towards minus infinity, discard remainders, and write the result to \code{output}.
\end{quote}
\begin{lstlisting}
void fmpz_poly_scalar_div_mpz(fmpz_poly_t output,
const fmpz_poly_t poly, const mpz_t x)
\end{lstlisting}
\begin{quote}
Divide \code{poly} by the \code{mpz_t x}, round quotients towards minus infinity, discard remainders, and write the result to \code{output}.
\end{quote}
\subsection{Polynomial multiplication}
\begin{lstlisting}
void fmpz_poly_mul(fmpz_poly_t output, const fmpz_poly_t poly1,
const fmpz_poly_t poly2)
\end{lstlisting}
\begin{quote}
Multiply the two given polynomials and return the result in \code{output}.
The length of the output polynomial will be \code{poly1->length + poly2->length - 1}.
\end{quote}
\begin{lstlisting}
void fmpz_poly_mul_modular(fmpz_poly_t output, const fmpz_poly_t poly1,
const fmpz_poly_t poly2, const ulong bits)
\end{lstlisting}
\begin{quote}
Multiply the two given polynomials and return the result in \code{output}. If one has a bound on the number of bits of the output coefficients one can set \code{bits} to this bound (plus one if the coefficients are signed). If \code{bits} is set to zero an automatic bound is computed by the function.
This function is optimised for very long polynomials and makes efficient use of memory, often not thrashing the disk when the ordinary multiplication function would do so.
Note that this function requires \code{zn_poly} to be linked with FLINT.
The length of the output polynomial will be \code{poly1->length + poly2->length - 1}.
\end{quote}
\begin{lstlisting}
void fmpz_poly_mul_trunc_n(fmpz_poly_t output,
const fmpz_poly_t poly1, const fmpz_poly_t poly2, unsigned long n)
\end{lstlisting}
\begin{quote}
Multiply the two given polynomials and truncate the result to $n$ coefficients, storing the result in \code{output}. This is sometimes known as a short product.
The length of the output polynomial will be at most the minimum of $n$ and the value \code{poly1->length + poly2->length - 1}. It is permissible to set $n$ to any non-negative value, however the function is optimised for $n$ about half of \code{poly1->length + poly2->length}.
This function is more efficient than multiplying the two polynomials then truncating. It is the operation used when multiplying power series.
\end{quote}
\begin{lstlisting}
void fmpz_poly_mul_trunc_left_n(fmpz_poly_t output,
const fmpz_poly_t poly1, const fmpz_poly_t poly2, unsigned long n)
\end{lstlisting}
\begin{quote}
Multiply the two given polynomials storing the result in \code{output}. This function guarantees all the coefficients except the first $n$, which may be arbitrary. This is sometimes known as an opposite short product.
The length of the output polynomial will be \code{poly1->length + poly2->length - 1} unless $n$ is greater than or equal to this value, in which case it will return the zero polynomial. It is permissible to set $n$ to any non-negative value, however the function is optimised for $n$ about half of \code{poly1->length + poly2->length}.
For short polynomials, this function is more efficient than computing the full product.
\end{quote}
\subsection{Polynomial division}
\begin{lstlisting}
void fmpz_poly_divrem(fmpz_poly_t Q, fmpz_poly_t R,
const fmpz_poly_t A, const fmpz_poly_t B)
\end{lstlisting}
\begin{quote}
Performs division with remainder in $\Z[x]$. Computes polynomials \code{Q} and \code{R} in $\Z[x]$ such that the equation \code{A = B*Q + R}, holds. All but the final \code{B->length - 1} coefficients of \code{R} will be positive and less than the absolute value of the lead coefficient of \code{B}.
Note that in the special cases where the leading coefficient of \code{B} is $\pm 1$ or \code{A = B*Q} for some polynomial \code{Q}, the result of this function is the same as if the computation had been done over $\Q$.
\end{quote}
\begin{lstlisting}
void fmpz_poly_div(fmpz_poly_t Q, const fmpz_poly_t A,
const fmpz_poly_t B)
\end{lstlisting}
\begin{quote}
Performs division without remainder in $\Z[x]$. The computation returns the same result as \code{fmpz_poly_divrem}, but no remainder is computed. This is in general faster than computing quotient and remainder.
Note that in the special cases where the leading coefficient of \code{B} is $\pm 1$ or \code{A = B*Q} for some polynomial \code{Q}, the result of this function is the same as if the computation had been done over $\Q$.
\end{quote}
\begin{lstlisting}
void fmpz_poly_invert_series(fmpz_poly_t Q_inv,
const fmpz_poly_t Q, const unsigned long n)
\end{lstlisting}
\begin{quote}
Sets \code{Q_inv} to $n$ terms of the inverse of \code{Q}. Calling this function is equivalent to calling the function below, \code{fmpz_poly_div_series}, with \code{A} equal to 1. Assumes that the constant term of $Q$ is 1.
\end{quote}
\begin{lstlisting}
void fmpz_poly_div_series(fmpz_poly_t Q, const fmpz_poly_t A,
const fmpz_poly_t B, unsigned long n)
\end{lstlisting}
\begin{quote}
Performs power series division in $\Z[[x]]$. The function considers the polynomials \code{A} and \code{B} to be power series of length $n$ starting with the constant terms. The function assumes that \code{B} is normalised, i.e. that the constant coefficient is $\pm 1$. The result is truncated to length $n$ regardless of the inputs.
\end{quote}
\begin{lstlisting}
int fmpz_poly_divides(fmpz_poly_t Q, fmpz_poly_t A, fmpz_poly_t B)
\end{lstlisting}
\begin{quote}
If the polynomial \code{A} is divisible by the polynomial \code{B} this function returns 1 and sets \code{Q} to the quotient, otherwise it returns 0.
This function can be used for efficient exact division.
\end{quote}
\subsection{Pseudo division}
\begin{lstlisting}
void fmpz_poly_pseudo_divrem(fmpz_poly_t Q, fmpz_poly_t R,
unsigned long * d, const fmpz_poly_t A, const fmpz_poly_t B)
\end{lstlisting}
\begin{quote}
Performs division with remainder of two polynomials in $\Z[x]$, notionally returning the results in $\Q[x]$ (actually in $\Z[x]$ with a single common denominator).
Computes polynomials \code{Q} and \code{R} such that \code{lead(B)^d*A = B*Q + R} where \code{R} has degree less than that of \code{B}.
This function may be used to do division of polynomials in $\Q[x]$ as follows. Suppose polynomials \code{C} and \code{D} are given in $\Q[x]$.
1) Write \code{C = d1*A} and \code{D = d2*B} for some polynomials \code{A} and \code{B} in $\Z[x]$ and integers \code{d1} and \code{d2}.
2) Use pseudo-division to compute \code{Q} and \code{R} in $\Z[x]$ so that \code{l^d*A = B*Q + R} where \code{l} is the leading coefficient of \code{B}.
3) We can now write \code{C = (d1/d2*D*Q + d1*R)/l^d}.
\end{quote}
\begin{lstlisting}
void fmpz_poly_pseudo_div(fmpz_poly_t Q, unsigned long * d,
const fmpz_poly_t A, const fmpz_poly_t B)
\end{lstlisting}
\begin{quote}
Performs division without remainder of two polynomials in $\Z[x]$, notionally returning the results in $\Q[x]$ (actually in $\Z[x]$ with a single common denominator).
Notionally computes polynomials \code{Q} and \code{R} such that \code{lead(B)^d*A = B*Q + R} where \code{R} has degree less than that of \code{B}, but returns only \code{Q}. This is slightly more efficient than computing the quotient and remainder.
\end{quote}
\begin{lstlisting}
void fmpz_poly_pseudo_rem(fmpz_poly_t R, unsigned long * d,
const fmpz_poly_t A, const fmpz_poly_t B)
\end{lstlisting}
\begin{quote}
Performs division with remainder of two polynomials in $\Z[x]$, without returning the quotient, notionally returning the results in $\Q[x]$ (actually in $\Z[x]$ with a single common denominator).
Notionally computes polynomials \code{Q} and \code{R} such that \code{lead(B)^d*A = B*Q + R} where \code{R} has degree less than that of \code{B}, but returns only \code{R}. This is more efficient than computing the quotient and remainder.
\end{quote}
\subsection{Powering}
\begin{lstlisting}
void fmpz_poly_power(fmpz_poly_t output, const fmpz_poly_t poly,
unsigned long exp)
\end{lstlisting}
\begin{quote}
Raises \code{poly} to the power \code{exp} and writes the result in \code{output}.
\end{quote}
\begin{lstlisting}
void fmpz_poly_power_trunc_n(fmpz_poly_t output,
const fmpz_poly_t poly, unsigned long exp, unsigned long n)
\end{lstlisting}
\begin{quote}
Notionally raises \code{poly} to the power \code{exp}, truncates the result to length $n$ and writes the result in \code{output}. This is computed much more efficiently than simply powering the polynomial and truncating. If \code{exp} is zero then the result will be the constant polynomial equal to 1, unless \code{poly} is zero, in which case the output will be zero.
This function can be used to raise power series to a power in an efficient way.
\end{quote}
\subsection{Gaussian content}
\begin{lstlisting}
void fmpz_poly_content(fmpz_t c, fmpz_poly_t poly)
\end{lstlisting}
\begin{quote}
Set the \code{fmpz_t c} to the Gaussian content of the polynomial \code{poly}, i.e. to the greatest common divisor of its coefficients.
\end{quote}
\begin{lstlisting}
void fmpz_poly_primitive_part(fmpz_poly_t prim, fmpz_poly_t poly)
\end{lstlisting}
\begin{quote}
Set \code{prim} to the primitive part of the polynomial \code{poly}, i.e. to \code{poly} divided by its Gaussian content.
\end{quote}
\subsection{Greatest common divisor and resultant}
\begin{lstlisting}
void fmpz_poly_gcd(fmpz_poly_t res, const fmpz_poly_t poly1,
const fmpz_poly_t poly2)
\end{lstlisting}
\begin{quote}
Sets \code{res} to the greatest common divisor of the polynomials \code{poly1} and \code{poly2}.
\end{quote}
\begin{lstlisting}
unsigned long fmpz_poly_resultant_bound(fmpz_poly_t a,
fmpz_poly_t b)
void fmpz_poly_resultant(fmpz_t r, fmpz_poly_t a, fmpz_poly_t b)
\end{lstlisting}
\begin{quote}
Compute the resultant of the polynomials \code{a} and \code{b}. If \code{a} and \code{b} are monic with $a(x) = \prod_i (x - \alpha_i)$ and $b(x) = \prod_j (x - \beta_j)$, when factored over the complex numbers, then the resultant is given by the expression $r(x) = \prod_{i,j} (\alpha_i - \beta_j)$. If the polynomials are not monic, and \code{a} and \code{b} have leading coefficients $l_1$ and $l_2$ and degrees $d_1$ and $d_2$ respectively, then this quantity is multiplied by $l_1^{d_2-1}l_2^{d_1-1}$.
Note that the resultant is zero iff the polynomials share a root over the algebraic closure of $\Q$.
Currently it is necessary to ensure \code{r} has sufficient space to store the result. The function \code{fmpz_poly_resultant_bound} is used to determine a bit bound on the number of bits \code{b} required and \code{r} must have space for \code{b/FLINT_BITS + 2} limbs.
In a future version of FLINT, this computation will not be necessary.
\end{quote}
\begin{lstlisting}
void fmpz_poly_xgcd(fmpz_t r, fmpz_poly_t s, fmpz_poly_t t,
fmpz_poly_t a, fmpz_poly_t b)
\end{lstlisting}
\begin{quote}
Given coprime polynomials \code{a} and \code{b} this function computes polynomials \code{s} and \code{t} and the resultant \code{r} of the polynomials such that \code{r = a*s + b*t}.
See the function \code{fmpz_poly_resultant} for information on how large \code{r} needs to be to hold the result.
\end{quote}
\subsection{Modular arithmetic}
\begin{lstlisting}
void fmpz_poly_invmod(fmpz_t d, fmpz_poly_t H, fmpz_poly_t poly1,
fmpz_poly_t poly2)
\end{lstlisting}
\begin{quote}
Computes a polynomial \code{H} and a denominator \code{d} such that \code{poly1*H} is \code{d} modulo \code{poly2}.
Assumes that \code{poly1} and \code{poly2} are coprime and that \code{poly2} is monic.
\end{quote}
\subsection{Derivative}
\begin{lstlisting}
void fmpz_poly_derivative(fmpz_poly_t der, fmpz_poly_t poly)
\end{lstlisting}
\begin{quote}
Sets \code{der} to the derivative of \code{poly}.
\end{quote}
\subsection{Evaluation}
\begin{lstlisting}
void fmpz_poly_evaluate(fmpz_t output,
const fmpz_poly_t poly, const fmpz_t val)
\end{lstlisting}
\begin{quote}
Evaluates \code{poly} at the value \code{val} and sets \code{output} to the result.
\end{quote}
\subsection{Polynomial composition}
\begin{lstlisting}
void fmpz_poly_compose(fmpz_poly_t output,
const fmpz_poly_t f, const fmpz_poly_t g)
\end{lstlisting}
\begin{quote}
Sets \code{output} to the polynomial composition of $f$ with $g$, i.e. computes $f(g(x))$.
\end{quote}
\subsection{Polynomial signature}
\begin{lstlisting}
void fmpz_poly_signature(ulong * r1, ulong * r2, fmpz_poly_t poly)
\end{lstlistin}
\begin{quote}
Determines the signature r1, r2 (where r1 + 2*r2 = degree(poly) and r1 is the number of real roots of poly). The input polynomial must be squarefree, otherwise the result is undefined and an exception may be raised. The zero polynomial is allowed, for convenience, and the number of real and complex roots are both set to 0 in that case.
\end{quote}
\subsection{Squarefree}
\begin{lstlisting}
void fmpz_poly_signature(ulong * r1, ulong * r2, fmpz_poly_t poly)
\end{lstlistin}
\begin{quote}
Determines the signature r1, r2 (where r1 + 2*r2 = degree(poly) and r1 is the number of real roots of poly). The input polynomial must be squarefree, otherwise the result is undefined and an exception may be raised. The zero polynomial is allowed, for convenience, and the number of real and complex roots are both set to 0 in that case.
\end{quote}
\subsection{Subpolynomials}
A number of functions are provided for attaching an \code{fmpz_poly_t} object to an existing polynomial or to a range of coefficients of an existing polynomial providing an alias for the original polynomial or part thereof.
Each of the functions in this section normalise the subpolynomials so that they can be used as inputs to \code{fmpz_poly} functions.
As FLINT has no way of reallocating space in subpolynomials, they should not be used for outputs of \code{fmpz_poly} functions, but only for inputs. In a later version of FLINT, this restriction will be lifted.
Note that FLINT may perform suboptimally if a polynomial and an alias of the polynomial are passed as inputs to the same function, as FLINT has no way to tell that it is dealing with aliases of the same polynomial.
\begin{lstlisting}
void _fmpz_poly_attach(fmpz_poly_t output, const fmpz_poly_t poly)
\end{lstlisting}
\begin{quote}
Attach the \code{fmpz_poly_t} object \code{output} to the polynomial \code{poly}. Any changes made to the \code{length} field of \code{output} do not affect \code{poly}.
\end{quote}
\begin{lstlisting}
void _fmpz_poly_attach_shift(fmpz_poly_t output,
const fmpz_poly_t input, unsigned long n)
\end{lstlisting}
\begin{quote}
Attach the \code{fmpz_poly_t} object \code{output} to \code{poly} but shifted to the left by $n$ coefficients. This is equivalent to notionally shifting the original polynomial right (dividing by $x^n$) then attaching to the result without affecting the original polynomial.
\end{quote}
\begin{lstlisting}
void _fmpz_poly_attach_truncate(fmpz_poly_t output,
const fmpz_poly_t input, unsigned long n)
\end{lstlisting}
\begin{quote}
Attach the \code{fmpz_poly_t} object \code{output} to the first $n$ coefficients of the polynomial \code{poly}. This is equivalent to notionally truncating the original polynomial to $n$ coefficients then attaching to the result without affecting the original polynomial.
\end{quote}
\section{The fmpz module}
The \code{fmpz} module is designed for manipulation of the FLINT flat multiprecision integer format \code{fmpz_t}.
Internally, the data for an \code{fmpz_t} has first limb a sign/size limb. If it is 0 the integer represented by the \code{fmpz_t} is 0. The absolute value of the sign/size limb is the number of subsequent limbs that the absolute value of the integer being represented, takes up. The absolute value of the integer is then stored as limbs, least significant limb first, in the subsequent limbs after the sign/size limb. If the sign/size limb is positive, a positive integer is intended and if the sign/size limb is negative the negative integer with the stored absolute value is intended.
The \code{fmpz_t} type is not intended as a standalone integer type. It is intended to be used in composite types such as polynomials and matrices which consist of many integer entries.
Currently the user is responsible for memory management of \code{fmpz_t}'s, i.e. one must ensure that the output of a function in the \code{fmpz} module contains sufficient space to store the result. This will be changed in a later version of FLINT, where automatic memory management will be done for the user.
To ensure that the correct number of limbs are available in each \code{fmpz_t} of an \code{fmpz_poly_t} one must currently call \code{void fmpz_poly_fit_limbs(fmpz_poly_t pol, unsigned long limbs)}, which will then ensure that each coefficient of \code{pol} has space for at least the given number of limbs (referring to the absolute value of the coefficients). Again, in a later version of FLINT, this step will be unnecessary as automatic memory management will be done for all \code{fmpz_t}'s, including coefficients of \code{fmpz_poly_t}'s.
Note that \code{fmpz_t}'s are not currently guaranteed to allow aliasing between inputs or between inputs and outputs. However some optimised inplace functions are provided.
\subsection{A simple example}
We start with a simple example of the use of the \code{fmpz} module.
This example sets $x$ to 3 and adds 5 to it.
\begin{lstlisting}
#include "fmpz.h"
....
fmpz_t x = fmpz_init(1); // Allocate 1 limb of space
fmpz_set_ui(x, 3);
fmpz_add_ui_inplace(x, 5);
printf("3 + 5 is "); fmpz_print(x); printf("\n");
fmpz_clear(x);
\end{lstlisting}
We now discuss the functions available in the \code{fmpz} module.
\subsection{Memory management}
\begin{lstlisting}
fmpz_t fmpz_init(unsigned long limbs)
\end{lstlisting}
\begin{quote}
Allocates space for an \code{fmpz_t} with the given number of limbs (plus an additional limb for the sign/size) on the heap and return a pointer to the space.
\end{quote}
\begin{lstlisting}
fmpz_t fmpz_realloc(fmpz_t f, unsigned long limbs)
\end{lstlisting}
\begin{quote}
Reallocate the space used by the \code{fmpz_t f} so that it has space for the given number of limbs (plus a sign/size limb). The parameter \code{limbs} must be non-negative. The existing contents of \code{f} are not altered if they still fit in the new size.
\end{quote}
\begin{lstlisting}
void fmpz_clear(const fmpz_t f)
\end{lstlisting}
\begin{quote}
Free space used by the \code{fmpz_t f}.
\end{quote}
\subsection{String operations}
\begin{lstlisting}
void fmpz_print(const fmpz_t f)
\end{lstlisting}
\begin{quote}
Print the multiprecision integer \code{f}. A minus sign is prepended if the integer is negative.
\end{quote}
\subsection{fmpz properties}
\begin{lstlisting}
unsigned long fmpz_size(const fmpz_t f)
\end{lstlisting}
\begin{quote}
Return the number of limbs used to store the absolute value of the multiprecision integer \code{f}.
\end{quote}
\begin{lstlisting}
unsigned long fmpz_bits(const fmpz_t f)
\end{lstlisting}
\begin{quote}
Return the number of bits required to store the absolute value of the multiprecision integer \code{f}.
\end{quote}
\begin{lstlisting}
int fmpz_sgn(const fmpz_t f)
\end{lstlisting}
\begin{quote}
Return $1$ if the sign of $f$ is positive, $-1$ if it is negative and $0$ if $f$ is zero.
\end{quote}
\subsection{Assignment}
\begin{lstlisting}
void fmpz_set_ui(fmpz_t res, unsigned long x)
\end{lstlisting}
\begin{quote}
Set the multiprecision integer \code{res} to the \code{unsigned long x}.
\end{quote}
\begin{lstlisting}
void fmpz_set_si(fmpz_t res, long x)
\end{lstlisting}
\begin{quote}
Set the multiprecision integer \code{res} to the \code{long x}.
\end{quote}
\begin{lstlisting}
double fmpz_get_d(fmpz_t x)
\end{lstlisting}
\begin{quote}
Returns a \code{double} floating point approximation to the multiprecision integer $x$. Note that the exponent of a double is limited to strictly less that 1024, thus the absolute value of the integer $x$ must be less than $2^1024$.
\end{quote}
\begin{lstlisting}
void fmpz_set(fmpz_t res, const fmpz_t f)
\end{lstlisting}
\begin{quote}
Set the multiprecision integer \code{res} to equal the multiprecision integer \code{f}.
\end{quote}
\begin{lstlisting}
void fmpz_abs(fmpz_t res, const fmpz_t f)
\end{lstlisting}
\begin{quote}
Set the multiprecision integer \code{res} to the absolute value of the multiprecision integer \code{f}.
\end{quote}
\begin{lstlisting}
void fmpz_neg(fmpz_t res, const fmpz_t f)
\end{lstlisting}
\begin{quote}
Set the multiprecision integer \code{res} to minus the multiprecision integer \code{f}.
\end{quote}
\subsection{Comparison}
\begin{lstlisting}
int fmpz_equal(const fmpz_t f1, const fmpz_t f2)
\end{lstlisting}
\begin{quote}
Return 1 if \code{f1} is equal to \code{f2}, otherwise return 0.
\end{quote}
\begin{lstlisting}
int fmpz_is_one(const fmpz_t f)
\end{lstlisting}
\begin{quote}
Return 1 if \code{f} is one, otherwise return 0.
\end{quote}
\begin{lstlisting}
int fmpz_is_m1(const fmpz_t f)
\end{lstlisting}
\begin{quote}
Return 1 if \code{f} is minus one, otherwise return 0.
\end{quote}
\begin{lstlisting}
int fmpz_is_zero(const fmpz_t f)
\end{lstlisting}
\begin{quote}
Return 1 if \code{f} is zero, otherwise return 0.
\end{quote}
\begin{lstlisting}
int fmpz_cmpabs(const fmpz_t f1, const fmpz_t f2)
\end{lstlisting}
\begin{quote}
Compares the absolute values of \code{f1} and \code{f2}. If the absolute value of \code{f1} is less than that of \code{f2} then a negative value is returned. If the absolute value of \code{f1} is greater than that of \code{f2} then a positive value is returned. If the absolute values are equal, then zero is returned.
\end{quote}
\subsection{Conversions}
\begin{lstlisting}
void mpz_to_fmpz(fmpz_t res, const mpz_t x)
\end{lstlisting}
\begin{quote}
Convert the \code{mpz_t x} to the \code{fmpz_t res}.
\end{quote}
\begin{lstlisting}
void fmpz_to_mpz(mpz_t res, const fmpz_t f)
\end{lstlisting}
\begin{quote}
Convert the \code{fmpz_t f} to the \code{mpz_t res}.
\end{quote}
\subsection{Addition/subtraction}
\begin{lstlisting}
void fmpz_add(fmpz_t res, const fmpz_t f1, const fmpz_t f2)
\end{lstlisting}
\begin{quote}
Set \code{res} to the sum of \code{f1} and \code{f2}.
\end{quote}
\begin{lstlisting}
void fmpz_add_ui_inplace(fmpz_t res, unsigned long x)
\end{lstlisting}
\begin{quote}
Set \code{res} to the sum of \code{res} and the \code{unsigned long x}.
\end{quote}
\begin{lstlisting}
void fmpz_add_ui(fmpz_t res, const fmpz_t f, unsigned long x)
\end{lstlisting}
\begin{quote}
Set \code{res} to the sum of \code{f} and the \code{unsigned long x}.
\end{quote}
\begin{lstlisting}
void fmpz_sub(fmpz_t res, const fmpz_t f1, const fmpz_t f2)
\end{lstlisting}
\begin{quote}
Set \code{res} to \code{f1} minus \code{f2}.
\end{quote}
\begin{lstlisting}
void fmpz_sub_ui_inplace(fmpz_t res, unsigned long x)
\end{lstlisting}
\begin{quote}
Set \code{res} to \code{res} minus the \code{unsigned long x}.
\end{quote}
\begin{lstlisting}
void fmpz_sub_ui(fmpz_t res, const fmpz_t f, unsigned long x)
\end{lstlisting}
\begin{quote}
Set \code{res} to \code{f} minus the \code{unsigned long x}.
\end{quote}
\subsection{Multiplication}
\begin{lstlisting}
void fmpz_mul(fmpz_t res, const fmpz_t f1, const fmpz_t f2)
\end{lstlisting}
\begin{quote}
Set \code{res} to \code{f1} times \code{f2}.
\end{quote}
\begin{lstlisting}
void fmpz_mul_trunc(fmpz_t res, fmpz_t a,
fmpz_t b, unsigned long trunc)
\end{lstlisting}
\begin{quote}
Set \code{res} to \code{f1} times \code{f2} truncated to $trunc$ limbs. This is in general faster than doing a full multiplication then truncating.
\end{quote}
\begin{lstlisting}
void fmpz_mul_ui(fmpz_t res, const fmpz_t f1, unsigned long x)
\end{lstlisting}
\begin{quote}
Set \code{res} to \code{f1} times the \code{unsigned long x}.
\end{quote}
\begin{lstlisting}
void fmpz_mul_2exp(fmpz_t output, fmpz_t x, unsigned long exp)
\end{lstlisting}
\begin{quote}
Set \code{output} to \code{x} multiplied by $2^{\mbox{exp}}$.
\end{quote}
\begin{lstlisting}
void fmpz_addmul(fmpz_t res, const fmpz_t f1, const fmpz_t f2)
\end{lstlisting}
\begin{quote}
Set \code{res} to \code{res + f1 * f2}.
\end{quote}
\subsection{Division}
\begin{lstlisting}
void fmpz_tdiv(fmpz_t res, const fmpz_t f1, const fmpz_t f2)
\end{lstlisting}
\begin{quote}
Set \code{res} to the quotient of \code{f1} by \code{f2}. Round the quotient towards zero and discard the remainder.
\end{quote}
\begin{lstlisting}
void fmpz_fdiv(fmpz_t res, const fmpz_t f1, const fmpz_t f2)
\end{lstlisting}
\begin{quote}
Set \code{res} to the quotient of \code{f1} by \code{f2}. Round the quotient towards minus infinity and discard the remainder.
\end{quote}
\begin{lstlisting}
void fmpz_tdiv_ui(fmpz_t res, const fmpz_t f1, unsigned long x)
\end{lstlisting}
\begin{quote}
Set \code{res} to the quotient of \code{f1} by the unsigned long \code{x}. Round the quotient towards zero and discard the remainder.
\end{quote}
\begin{lstlisting}
void fmpz_div_2exp(fmpz_t output, fmpz_t x, unsigned long exp)
\end{lstlisting}
\begin{quote}
Divide \code{x} by $2^{\mbox{exp}}$, returning the quotient and discarding the remainder. Rounding occurs towards zero.
\end{quote}
\begin{lstlisting}
int fmpz_divides(fmpz_t q, const fmpz_t a, const fmpz_t b)
\end{lstlisting}
\begin{quote}
If $b$ divides $a$ then set $q$ to the quotient and return 1, else return 0.
\end{quote}
\subsection{Modular arithmetic}
\begin{lstlisting}
unsigned long fmpz_mod_ui(const fmpz_t input,
const unsigned long x)
\end{lstlisting}
\begin{quote}
Returns \code{f1} modulo the \code{unsigned long x}. Note that \code{input} may be signed.
\end{quote}
\begin{lstlisting}
void fmpz_mod(fmpz_t res, const fmpz_t input, const fmpz_t x)
\end{lstlisting}
\begin{quote}
Sets \code{res} to \code{input} modulo \code{x}. Note that \code{input} may be signed but \code{x} must be unsigned.
\end{quote}
\begin{lstlisting}
void fmpz_mulmod(fmpz_t res, fmpz_t a, fmpz_t b, fmpz_t m)
\end{lstlisting}
\begin{quote}
Sets \code{res} to $a$ multiplied by $b$ modulo $m$. Note $m$ must be unsigned and both $a$ and $b$ are assumed to be reduced modulo $m$.
\end{quote}
\begin{lstlisting}
void fmpz_invert(fmpz_t res, fmpz_t x, fmpz_t m)
\end{lstlisting}
\begin{quote}
Sets \code{res} to the inverse of $x$ modulo $m$. Note $m$ must be unsigned, $x$ and $m$ must be coprime and $x$ reduced modulo $m$.
\end{quote}
\begin{lstlisting}
void fmpz_divmod(fmpz_t res, fmpz_t a, fmpz_t b, fmpz_t m)
\end{lstlisting}
\begin{quote}
Sets \code{res} to $a$ divided by $b$ modulo $m$. Note $m$ must be unsigned, $b$ and $m$ must be coprime and both $a$ and $b$ are assumed to be reduced modulo $m$.
\end{quote}
\subsection{Powering}
\begin{lstlisting}
void fmpz_pow_ui(fmpz_t res, const fmpz_t f, unsigned long exp)
\end{lstlisting}
\begin{quote}
Set \code{res} to \code{f} raised to the power \code{exp}. This requires \code{exp} to be non-negative.
\end{quote}
\subsection{Root extraction}
\begin{lstlisting}
void fmpz_sqrtrem(fmpz_t sqrt, fmpz_t rem, fmpz_t x)
\end{lstlisting}
\begin{quote}
Computes the square root of \code{x} and returns the integer part of the square root, \code{sqrt}, and the remainder, \code{rem = x - sqrt^2}.
Note that \code{x} must be non-negative, else an exception is raised.
\end{quote}
\subsection{Number theoretical}
\begin{lstlisting}
void fmpz_gcd(fmpz_t output, fmpz_t x1, fmpz_t x2)
\end{lstlisting}
\begin{quote}
Compute the greatest common divisor of \code{x1} and \code{x2}. The result is always non-negative and will be zero if both of the inputs are zero.
\end{quote}
\subsection{Chinese remaindering}
\begin{lstlisting}
void fmpz_CRT_ui_precomp(fmpz_t x, fmpz_t r1, fmpz_t m1,
unsigned long r2, unsigned long m2, unsigned long c,
pre_inv_t pre)
void fmpz_CRT_ui2_precomp(fmpz_t x, fmpz_t r1, fmpz_t m1,
unsigned long r2, unsigned long m2, unsigned long c,
pre_inv2_t pre)
\end{lstlisting}
\begin{quote}
Computes the unique value \code{x} modulo \code{m1*m2} that is \code{r1} modulo \code{m1} and \code{r2} modulo \code{m2}. Requires \code{m1} and \code{m2} to be coprime, \code{c} to be set to the value \code{m1} modulo \code{m2} and \code{pre} to be a precomputed inverse of \code{m2} (computed using \code{z_precompute_inverse(m2)}).
The first version of the function requires that \code{m2} be no more than \code{FLINT_D_BITS} bits, whereas the second version requires \code{m2} to be no more than \code{FLINT_BITS - 1} bits.
\end{quote}
Multiple modular reductions or Chinese remainders can be done at once with the following functions. An \code{fmpz_comb_t} type holds information which is used to speed up the modular reductions and modular recombinations. The first two functions are for initialising and clearing such a structure.
Note all of the functions below require \code{zn_poly} to be linked with FLINT.
\begin{lstlisting}
void fmpz_comb_init(fmpz_comb_t comb, ulong * primes, ulong num_primes)
\end{lstlisting}
\begin{quote}
Initialise a comb structure for multimodular reduction and recombination. The array \code{primes} is assumed to contain \code{num_primes} primes each of \code{FLINT_BITS - 1} bits. Modular reductions and recombinations will be done modulo this list of primes. The \code{primes} array must not be free'd until the comb structure is no longer required and must be cleared by the user.
\end{quote}
\begin{lstlisting}
void fmpz_comb_clear(fmpz_comb_t comb)
\end{lstlisting}
\begin{quote}
Clear the given comb structure, releasing any memory it uses.
\end{quote}
\begin{lstlisting}
void fmpz_multi_mod_ui(unsigned long * out, fmpz_t in, fmpz_comb_t comb)
\end{lstlisting}
\begin{quote}
Reduces the multiprecision integer \code{in} modulo each of the primes stored in the comb structure. The array \code{out} will be filled with the residues modulo these primes.
\end{quote}
\begin{lstlisting}
void fmpz_multi_CRT_ui_unsigned(fmpz_t output,
unsigned long * residues, fmpz_comb_t comb)
\end{lstlisting}
\begin{quote}
This function takes a set of residues modulo the list of primes contained in the comb structure and reconstructs the unique unsigned multiprecision integer modulo the product of the primes which has these residues modulo the corresponding primes.
\end{quote}
\begin{lstlisting}
void fmpz_multi_CRT_ui(fmpz_t output,
unsigned long * residues, fmpz_comb_t comb)
\end{lstlisting}
\begin{quote}
This function takes a set of residues modulo the list of primes contained in the comb structure and reconstructs a signed multiprecision integer modulo the product of the primes which has these residues modulo the corresponding primes. If $N$ is the product of all the primes then \code{output} is normalised to be in the range $[-(N-1)/2, N/2]$.
\end{quote}
\subsection{Montgomery format}
In this section a number of functions are described which deal with numbers in Montgomery format. In cases where multiple multiplicative functions need to be applied, Montgomery format provides a speed increase over manipulating the integers in ordinary multiprecision format.
\begin{lstlisting}
void fmpz_montgomery_init(fmpz_montgomery_t mont, fmpz_t m)
\end{lstlisting}
\begin{quote}
Convert the multiprecision integer to Montgomery format for use with the \code{fmpz_montgomery_redc} function.
\end{quote}
\begin{lstlisting}
void fmpz_montgomery_clear(fmpz_montgomery_t mont)
\end{lstlisting}
\begin{quote}
Clear the Montgomery structure, releasing any memory used.
\end{quote}
\begin{lstlisting}
void fmpz_montgomery_redc(fmpz_t res, fmpz_t x,
fmpz_montgomery_t mont)
\end{lstlisting}
\begin{quote}
Compute the product of \code{x} and the integer stored in Montgomery format in \code{mont} and store the result in Montgomery format in \code{res}.
\end{quote}
\begin{lstlisting}
void fmpz_montgomery_mulmod_init(fmpz_montgomery_t mont,
fmpz_t b, fmpz_t m)
\end{lstlisting}
\begin{quote}
Compute the Montgomery format of a precomputed multiplication by \code{b} modulo \code{m}.
\end{quote}
\begin{lstlisting}
void fmpz_montgomery_mulmod(fmpz_t res, fmpz_t a,
fmpz_montgomery_t mont)
\end{lstlisting}
\begin{quote}
Compute the product of \code{a} by \code{b} modulo \code{m} where the precomputed data \code{b} and \code{m} are stored in the Montgomery structure \code{mont} by the previous function. Set \code{res} to the result, which is in ordinary integer format, not Montgomery format.
\end{quote}
\begin{lstlisting}
void fmpz_montgomery_divmod_init(fmpz_montgomery_t mont,
fmpz_t b, fmpz_t m)
\end{lstlisting}
\begin{quote}
Compute the Montgomery format of a precomputed division by \code{b} modulo \code{m}, assuming \code{b} is coprime with and reduced modulo \code{m}.
\end{quote}
\begin{lstlisting}
void fmpz_montgomery_mulmod(fmpz_t res, fmpz_t a,
fmpz_montgomery_t mont)
\end{lstlisting}
\begin{quote}
Compute \code{a} divided by \code{b} modulo \code{m} where the precomputed data \code{b} and \code{m} are stored in the Montgomery structure \code{mont} by the previous function. Set \code{res} to the result, which is in ordinary integer format, not Montgomery format.
\end{quote}
\begin{lstlisting}
void fmpz_montgomery_mod_init(fmpz_montgomery_t mont, fmpz_t m)
\end{lstlisting}
\begin{quote}
Compute the Montgomery format for a precomputed reduction modulo \code{m}.
\end{quote}
\begin{lstlisting}
void fmpz_montgomery_mod(fmpz_t res, fmpz_t a,
fmpz_montgomery_t mont)
\end{lstlisting}
\begin{quote}
Compute \code{a} modulo \code{m} where the precomputed data \code{m} is stored in the Montgomery structure \code{mont} by the previous function. Set \code{res} to the result, which is in ordinary integer format, not Montgomery format.
\end{quote}
\section{The zmod\_poly module}
The \code{zmod_poly_t} data type represents elements of $\Z/n\Z[x]$ for some word sized integer $n$. Most of the functions work for an arbitrary $n$, however the division functions require the leading coefficient of the divisor polynomial to be invertible modulo $n$ and the gcd and resultant functions require $n$ to be prime.
The \code{zmod_poly} module provides routines for memory management, basic manipulation and basic arithmetic.
Each coefficient of a \code{zmod_poly_t} is stored as an \code{unsigned long} and is assumed to be reduced modulo the modulus $n$.
Unless otherwise specified, all functions in this section permit aliasing between their input arguments and between their input and output arguments.
\subsection{Simple example}
The following example computes the square of the polynomial $5x^3 + 1$, where the coefficients are understood to be in $\Z/7\Z$.
\begin{lstlisting}
#include "zmod_poly.h"
....
zmod_poly_t x, y;
zmod_poly_init(x, 7);
zmod_poly_init(y);
zmod_poly_set_coeff_ui(x, 3, 5);
zmod_poly_set_coeff_ui(x, 0, 1);
zmod_poly_mul(y, x, x);
zmod_poly_print(x); printf("\n");
zmod_poly_print(y); printf("\n");
zmod_poly_clear(x);
zmod_poly_clear(y);
\end{lstlisting}
The output is:
\begin{lstlisting}
4 1 0 0 5
7 1 0 0 3 0 0 4
\end{lstlisting}
\subsection{Definition of the zmod\_poly\_t polynomial type}
The \code{zmod_poly_t} type is a typedef for an array of length 1 of \code{zmod_poly_struct}'s. This permits passing parameters of type \code{zmod_poly_t} `by reference'.
All \code{zmod_poly} functions expect their inputs to be normalised, and unless otherwise specified they produce output that is normalised.
It is recommended that users do not access the fields of a \code{zmod_poly_t} or its coefficient data directly, but make use of the functions designed for this purpose (detailed below). The type has fields for the length of the polynomial, the number of coefficients allocated (the length is always less than or equal to this), a modulus $n$ and possibly a precomputed inverse of $n$.
Functions in \code{zmod_poly} do all the memory management for the user. One does not need to specify the maximum length in advance before using a \code{zmod_poly_t} polynomial object, but it may be more efficient to do so. FLINT reallocates space automatically as the computation proceeds, if more space is required.
We now describe the functions available in \code{zmod_poly}.
\subsection{Memory management}
\begin{lstlisting}
void zmod_poly_init(zmod_poly_t poly, unsigned long p)
\end{lstlisting}
\begin{quote}
Initialise \code{poly} as a polynomial over $\Z/p\Z$.
\end{quote}
\begin{lstlisting}
void zmod_poly_init2(zmod_poly_t poly, unsigned long p,
unsigned long alloc)
\end{lstlisting}
\begin{quote}
Initialise \code{poly} as a polynomial over $\Z/p\Z$, allocating space for at least the given number of coefficients.
\end{quote}
\begin{lstlisting}
void zmod_poly_clear(zmod_poly_t poly)
\end{lstlisting}
\begin{quote}
Release the memory used by \code{poly}, which cannot then be used until it is initialised again.
\end{quote}
\begin{lstlisting}
void zmod_poly_realloc(zmod_poly_t poly, unsigned long alloc)
\end{lstlisting}
\begin{quote}
Reallocate \code{poly} so that it has space for \code{alloc} coefficients. If alloc is greater than the current length of the polynomial, the existing coefficients are retained.
\end{quote}
\begin{lstlisting}
void zmod_poly_fit_length(zmod_poly_t poly, unsigned long alloc)
\end{lstlisting}
\begin{quote}
Reallocate \code{poly} so that it has space for at least \code{alloc} coefficients. This function will not reduce the number of allocated coefficients, so no data will be lost.
\end{quote}
\subsection{Setting/retrieving coefficients}
\begin{lstlisting}
unsigned long zmod_poly_get_coeff_ui(zmod_poly_t poly,
unsigned long n)
\end{lstlisting}
\begin{quote}
Return the $n$-th coefficient as an \code{unsigned long}. Coefficients are numbered from zero, starting with the constant coefficient. If $n$ is greater than or equal to the current length of the polynomial, zero is returned.
\end{quote}
\begin{lstlisting}
void zmod_poly_set_coeff_ui(zmod_poly_t poly, unsigned long n,
unsigned long c)
\end{lstlisting}
\begin{quote}
Set the $n$-th coefficient to the \code{unsigned long c}. It is assumed that \code{c} is already reduced modulo the modulus of the polynomial. Coefficients are number from zero, starting with the constant coefficient. If $n$ is greater than the current length of the polynomial, zeroes are inserted between the new coefficient and the existing coefficients if required.
\end{quote}
\subsection{String conversions and I/O}
The functions in this section read/write a polynomial to/from a string representation. The representation starts with the length of the polynomial, a space and then the modulus of the polynomial. If the length is not zero, this is followed by two spaces and then a space separated list of the coefficients starting from the constant coefficient. Each coefficient is represented as an integer between zero and one less than the modulus.
The polynomial $3*x^2+2$ in $\Z/7\Z[x]$ would be represented:
\begin{lstlisting}
3 7 2 0 3
\end{lstlisting}
\begin{lstlisting}
int zmod_poly_from_string(zmod_poly_t poly, char* s)
\end{lstlisting}
\begin{quote}
Load \code{poly} from the given string \code{s}.
\end{quote}
\begin{lstlisting}
char* zmod_poly_to_string(zmod_poly_t poly)
\end{lstlisting}
\begin{quote}
Return a pointer to a string representing \code{poly}. Space is allocated for the string and must be free'd after use.
\end{quote}
\begin{lstlisting}
void zmod_poly_print(zmod_poly_t poly)
\end{lstlisting}
\begin{quote}
Print the string representation of \code{poly} to \code{stdout}.
\end{quote}
\begin{lstlisting}
void zmod_poly_fprint(zmod_poly_t poly, FILE* f)
\end{lstlisting}
\begin{quote}
Print the string representation of \code{poly} to the given file/stream \code{f}.
\end{quote}
\begin{lstlisting}
int zmod_poly_read(zmod_poly_t poly)
\end{lstlisting}
\begin{quote}
Read a polynomial in string representation from \code{stdin}. The function returns 1 if the string represented a valid polynomial, otherwise it returns 0.
\end{quote}
\begin{lstlisting}
int zmod_poly_fread(zmod_poly_t poly, FILE* f)
\end{lstlisting}
\begin{quote}
Read a polynomial in string representation from the given file/stream \code{f}. The function returns 1 if the string represented a valid polynomial, otherwise it returns 0.
\end{quote}
\subsection{Polynomial parameters (length, degree, modulus, etc.)}
\begin{lstlisting}
unsigned long zmod_poly_length(zmod_poly_t poly)
\end{lstlisting}
\begin{quote}
Return the current length of the polynomial. The zero polynomial has length 0.
\end{quote}
\begin{lstlisting}
long zmod_poly_degree(zmod_poly_t poly)
\end{lstlisting}
\begin{quote}
Return the degree of the polynomial. The zero polynomial is defined to have length $-1$.
\end{quote}
\begin{lstlisting}
unsigned long zmod_poly_modulus(zmod_poly_t poly)
\end{lstlisting}
\begin{quote}
Return the modulus of the polynomial, i.e. if $n$ is returned, the polynomial is an element of $\Z/n\Z$.\end{quote}
\begin{lstlisting}
unsigned long zmod_poly_bits(zmod_poly_t poly)
\end{lstlisting}
\begin{quote}
Return the maximum number of bits used in the coefficients of \code{poly}, i.e. if $n$ is returned, then no coefficient of the polynomial uses more than $n$ bits.\end{quote}
\subsection{Assignment and basic manipulation}
\begin{lstlisting}
void zmod_poly_truncate(zmod_poly_t poly, unsigned long length)
\end{lstlisting}
\begin{quote}
Truncate \code{poly} to the given length and normalise.
\end{quote}
\begin{lstlisting}
void zmod_poly_set(zmod_poly_t res, zmod_poly_t poly)
\end{lstlisting}
\begin{quote}
Set \code{res} to equal \code{poly}.
\end{quote}
\begin{lstlisting}
void zmod_poly_zero(zmod_poly_t poly)
\end{lstlisting}
\begin{quote}
Set \code{poly} to be the zero polynomial.
\end{quote}
\begin{lstlisting}
void zmod_poly_swap(zmod_poly_t poly1, zmod_poly_t poly2)
\end{lstlisting}
\begin{quote}
Efficiently swap \code{poly1} and \code{poly2}. Data is not actually copied in memory. Instead, pointers are swapped.
\end{quote}
\begin{lstlisting}
void zmod_poly_neg(zmod_poly_t res, zmod_poly_t poly)
\end{lstlisting}
\begin{quote}
Negate the polynomial \code{poly}, i.e. set \code{res} to \code{-poly}.
\end{quote}
\begin{lstlisting}
void zmod_poly_reverse(zmod_poly_t output, zmod_poly_t input,
unsigned long length)
\end{lstlisting}
\begin{quote}
Notionally zero padding or truncating if necessary, this function considers \code{input} to be a polynomial of the given length and reverses it, storing the result in \code{output}.
\end{quote}
\begin{lstlisting}
void __zmod_poly_normalise(zmod_poly_t poly)
\end{lstlisting}
\begin{quote}
Normalises the given polynomial. The polynomial will then either be of length zero or its leading coefficient will be non-zero. As all functions in the \code{zmod_poly} module expect and return normalised polynomials, this function is only used when manipulating coefficients directly rather than through the functions provided.
\end{quote}
\subsection{Subpolynomials}
These functions allow one to attach a \code{zmod_poly_t} object to an existing polynomial or subpolynomial thereof. The subpolynomial is normalised if necessary.
Since FLINT cannot reallocate the attached polynomial object, these functions should only be used to construct polynomial objects to be used as inputs to other \code{zmod_poly} functions.
\begin{lstlisting}
void _zmod_poly_attach(zmod_poly_t poly1, zmod_poly_t poly2)
\end{lstlisting}
\begin{quote}
Attach \code{poly2} to the polynomial object \code{poly1}.
\end{quote}
\begin{lstlisting}
void _zmod_poly_attach_shift(zmod_poly_t poly1,
zmod_poly_t poly2, unsigned long n)
\end{lstlisting}
\begin{quote}
This function notionally shifts \code{poly2} to the right by \code{n} coefficients and then attaches the polynomial object \code{poly1} to the result.
\end{quote}
\begin{lstlisting}
void _zmod_poly_attach_truncate(zmod_poly_t output,
zmod_poly_t input, unsigned long n)
\end{lstlisting}
\begin{quote}
This function notionally truncates \code{poly2} to length \code{n} and then attaches the polynomial object \code{poly1} to the result.
\end{quote}
\subsection{Comparison}
\begin{lstlisting}
int zmod_poly_equal(zmod_poly_t poly1, zmod_poly_t poly2)
\end{lstlisting}
\begin{quote}
Returns 1 if the two polynomials are equal, otherwise returns 0.
\end{quote}
\begin{lstlisting}
int zmod_poly_is_one(zmod_poly_t poly1)
\end{lstlisting}
\begin{quote}
Returns 1 if the polynomial is equal to the constant polynomial 1, otherwise returns 0.
\end{quote}
\begin{lstlisting}
int zmod_poly_is_zero(zmod_poly_t poly1)
\end{lstlisting}
\begin{quote}
Returns 1 if the polynomial is the zero polynomial, otherwise returns 0.
\end{quote}
\subsection{Scalar multiplication and division}
\begin{lstlisting}
void zmod_poly_scalar_mul(zmod_poly_t res, zmod_poly_t poly,
unsigned long scalar)
\end{lstlisting}
\begin{quote}
Multiply the polynomial through by the given scalar. It is assumed that \code{scalar} is already reduced modulo the modulus of the polynomial.
\end{quote}
\begin{lstlisting}
void zmod_poly_make_monic(zmod_poly_t output, zmod_poly_t pol)
\end{lstlisting}
\begin{quote}
Divide the polynomial through by the inverse of the leading coefficient of the polynomial. It is assumed that the leading coefficient is invertible modulo the modulus of the polynomial. This function results in a monic polynomial if this condition is met, otherwise the results are undefined.
\end{quote}
\subsection{Addition/subtraction}
\begin{lstlisting}
void zmod_poly_add(zmod_poly_t res, zmod_poly_t poly1,
zmod_poly_t poly2)
\end{lstlisting}
\begin{quote}
Set \code{res} to the sum of \code{poly1} and \code{poly2}. Note that if cancellation occurs, \code{res} may have a lesser length than either of the two input polynomials.
\end{quote}
\begin{lstlisting}
void zmod_poly_sub(zmod_poly_t res, zmod_poly_t poly1,
zmod_poly_t poly2)
\end{lstlisting}
\begin{quote}
Set \code{res} to \code{poly1} minus \code{poly2}. Note that if cancellation occurs, \code{res} may have a lesser length than either of the two input polynomials.
\end{quote}
\subsection{Shifting}
\begin{lstlisting}
void zmod_poly_left_shift(zmod_poly_t res, zmod_poly_t poly,
unsigned long k)
\end{lstlisting}
\begin{quote}
Shift the polynomial \code{poly} left by \code{k} coefficients, i.e. multiply the polynomial by $x^k$ and store the result in \code{res}. The value of $k$ must be non-negative.
\end{quote}
\begin{lstlisting}
void zmod_poly_right_shift(zmod_poly_t res, zmod_poly_t poly,
unsigned long k)
\end{lstlisting}
\begin{quote}
Shift the polynomial \code{poly} right by \code{k} coefficients, i.e. divide the polynomial by $x^k$, ignoring the remainder and store the result in \code{res}. The value of $k$ must be non-negative. If $k$ is greater than or equal to the current length of \code{poly}, \code{res} is set to the zero polynomial.
\end{quote}
\subsection{Polynomial multiplication}
\begin{lstlisting}
void zmod_poly_mul(zmod_poly_t res, zmod_poly_t poly1,
zmod_poly_t poly2)
\end{lstlisting}
\begin{quote}
Set \code{res} to \code{poly1} multiplied by \code{poly2}. The length of \code{res} will be one less than the sum of the lengths of \code{poly1} and \code{poly2}.
\end{quote}
\begin{lstlisting}
void zmod_poly_sqr(zmod_poly_t res, zmod_poly_t poly)
\end{lstlisting}
\begin{quote}
Set \code{res} to \code{poly} squared. The length of \code{res} will be one less than twice the length of \code{poly}.
\end{quote}
\begin{lstlisting}
void zmod_poly_mul_precache_init(zmod_poly_precache_t pre,
zmod_poly_t input2, unsigned long bits_input,
unsigned long length1)
\end{lstlisting}
\begin{quote}
This function precaches an FFT of the polynomial \code{input2} for (usually multiple) subsequent multiplicatons by the polynomial \code{input2}, with up to the given number of bits per output coefficient (0 if this is to be computed automatically). We set \code{length1} to the maximum length of polynomial \code{poly1} which \code{poly2} will be multiplied by.
\end{quote}
\begin{lstlisting}
void zmod_poly_mul_precache(zmod_poly_t output,
zmod_poly_t input1, zmod_poly_precache_t pre)
\end{lstlisting}
\begin{quote}
Multiply the polynomial \code{input1} by the polynomial whose precached FFT has been stored in \code{pre} by \code{zmod_poly_mul_precache_init}, i.e. sets \code{output} to the product of \code{input1} by \code{input2}.
\end{quote}
\begin{lstlisting}
void zmod_poly_mul_precache_clear(zmod_poly_precache_t pre)
\end{lstlisting}
\begin{quote}
Function for clearing a \code{zmod_poly_mul_precache_t}.
\end{quote}
\begin{lstlisting}
void zmod_poly_mul_trunc_n(zmod_poly_t res, zmod_poly_t poly1,
zmod_poly_t poly2, unsigned long n)
\end{lstlisting}
\begin{quote}
Set \code{res} to \code{poly1} multiplied by \code{poly2} and truncate to length \code{n} if this is less than the length of the full product. This function is usually more efficient than simply doing the multiplication and then truncating. The function is tuned for \code{n} about half the length of a full product. This function is sometimes called a short product.
This function can be used for power series multiplication.
\end{quote}
\begin{lstlisting}
void zmod_poly_mul_trunc_left_n(zmod_poly_t res,
zmod_poly_t poly1, zmod_poly_t poly2, unsigned long n)
\end{lstlisting}
\begin{quote}
Set \code{res} to \code{poly1} multiplied by \code{poly2} ignoring the least significant \code{n} terms of the result which may be set to anything. This function is more efficient than doing the full multiplication if the operands are relatively short. It is tuned for \code{n} about half the length of a full product. This function is sometimes called an opposite short product.
\end{quote}
\begin{lstlisting}
void zmod_poly_mul_trunc_n_precache_init(zmod_poly_precache_t pre,
zmod_poly_t input2, unsigned long bits, unsigned long trunc)
\end{lstlisting}
\begin{quote}
This function precaches an FFT of a polynomial \code{input2} to be used (usually multiple times) for truncated multiplicatons by \code{input2}, with up to the given number of bits per output coefficient (0 if this is to be computed automatically), where the output will be truncated to the given length.
This function is also used for initialising a precached middle product.
\end{quote}
\begin{lstlisting}
void zmod_poly_mul_trunc_n_precache(zmod_poly_t output,
zmod_poly_t input1, zmod_poly_precache_t pre, unsigned long trunc)
\end{lstlisting}
\begin{quote}
Performs a truncated multiplication by a polynomial whose FFT has been precached using \code{zmod_poly_mul_trunc_n_precache_init}, i.e. \code{output} is set to \code{input1} multiplied by \code{input2} and truncated to length \code{trunc} (and normalised).
\end{quote}
\begin{lstlisting}
void zmod_poly_mul_middle(zmod_poly_t output,
zmod_poly_t input1, zmod_poly_t input2,
unsigned long trunc)
\end{lstlisting}
\begin{quote}
Performs a middle product of the polynomial \code{input1} by the polynomial \code{input2}.
The middle product is the product of \code{input1} by \code{input2} truncated to length \code{trunc} and with the first \code{trunc/2} coefficients set to zero. Note that for this function to return a correct result one must ensure that if the full product were wrapped around after the first \code{trunc} terms then no more than \code{trunc/2} terms would be affected by the wraparound.
The typical situation to apply this function is when multiplying a polynomial of length $2n$ by one of length $n$. Ordinarily the product would have $3n - 1$ terms, however if \code{trunc} is set to $2n$ the first $n$ terms will be set to zero and the product truncated at $2n$ terms, note that $n - 1$ terms would be wrapped around and $n-1$ is less than the $n$ terms that will be set to zero.
\end{quote}
\begin{lstlisting}
void zmod_poly_mul_middle_precache(zmod_poly_t output,
zmod_poly_t input1, zmod_poly_precache_t pre,
unsigned long trunc)
\end{lstlisting}
\begin{quote}
Performs a middle product of the polynomial \code{input1} by the precached polynomial \code{input2} stored in \code{pre} by the function \code{zmod_poly_mul_trunc_n_precache_init}.
The middle product is the product of \code{input1} by \code{input2} truncated to length \code{trunc} with the first \code{trunc/2} coefficients set to zero. Note that for this function to return a correct result one must ensure that if the full product were wrapped around after the first \code{trunc} terms then no more than \code{trunc/2} terms would be affected by the wraparound.
The typical situation to apply this function is when multiplying a polynomial of length $2n$ by one of length $n$. Ordinarily the product would have $3n - 1$ terms, however if \code{trunc} is set to $2n$ the first $n$ terms will be set to zero and the product truncated at $2n$ terms.
\end{quote}
\subsection{Polynomial division}
\begin{lstlisting}
void zmod_poly_invert_series(zmod_poly_t Q_inv, zmod_poly_t Q,
unsigned long n)
\end{lstlisting}
\begin{quote}
Treat the polynomial \code{Q} as a series of length \code{n} (the constant coefficient of the series is taken to be the constant coefficient of the polynomial, which must be invertible modulo the modulus of \code{Q}) and invert it, yielding a series \code{Q_inv} also given to precision \code{n}.
\end{quote}
\begin{lstlisting}
void zmod_poly_div_series(zmod_poly_t Q, zmod_poly_t A,
zmod_poly_t B, unsigned long n)
\end{lstlisting}
\begin{quote}
Treat the polynomials \code{A} and \code{B} as series of length \code{n} and compute the quotient series \code{Q = A/B}.
\end{quote}
\begin{lstlisting}
void zmod_poly_div(zmod_poly_t Q, zmod_poly_t A, zmod_poly_t B)
\end{lstlisting}
\begin{quote}
Divide the polynomial \code{A} by the polynomial \code{B} and set \code{Q} to the quotient. The leading coefficient of \code{B} must be invertible modulo the modulus of \code{B}.
\end{quote}
\begin{lstlisting}
void zmod_poly_divrem(zmod_poly_t Q, zmod_poly_t R,
zmod_poly_t A, zmod_poly_t B)
\end{lstlisting}
\begin{quote}
Divide the polynomial \code{A} by \code{B} and set \code{Q} to the quotient and \code{R} to the remainder. The leading coefficient of \code{B} must be invertible modulo the modulus of \code{B}.
\end{quote}
\subsection{Greatest common divisor and resultant}
\begin{lstlisting}
unsigned long zmod_poly_resultant(zmod_poly_t a, zmod_poly_t b)
\end{lstlisting}
\begin{quote}
Compute the resultant of the polynomials \code{a} and \code{b}.
If \code{a} and \code{b} are monic with $a(x) = \prod_i (x - \alpha_i)$ and $b(x) = \prod_j (x - \beta_j)$, when factored over an algebraic closure of the field of coefficients, then the resultant is given by the expression $r(x) = \prod_{i,j} (\alpha_i - \beta_j)$. If the polynomials are not monic, and \code{a} and \code{b} have leading coefficients $l_1$ and $l_2$ and degrees $d_1$ and $d_2$ respectively, then this quantity is multiplied by $l_1^{d_2-1}l_2^{d_1-1}$.
Note that the resultant is zero iff the polynomials share a root over an algebraic closure of the coefficient ring.
\end{quote}
\begin{lstlisting}
void zmod_poly_gcd(zmod_poly_t res, zmod_poly_t poly1,
zmod_poly_t poly2)
\end{lstlisting}
\begin{quote}
Conmpute the greatest common divisor of the polynomials \code{poly1} and \code{poly2}.
\end{quote}
\begin{lstlisting}
int zmod_poly_gcd_invert(zmod_poly_t res, zmod_poly_t poly1,
zmod_poly_t poly2)
\end{lstlisting}
\begin{quote}
Compute a polynomial \code{res} such that \code{res*poly1} is a constant modulo \code{poly2}. The two polynomials \code{poly1} and \code{poly2} are assumed to be coprime. If this is not the case, the function returns 0, otherwise it returns 1.
\end{quote}
\begin{lstlisting}
void zmod_poly_xgcd(zmod_poly_t res, zmod_poly_t s, zmod_poly_t t,
zmod_poly_t poly1, zmod_poly_t poly)
\end{lstlisting}
\begin{quote}
Compute polynomials \code{s} and \code{t} such that \code{s*poly1+t*poly2} is the resultant of the polynomials \code{poly1} and \code{poly2}. The polynomials \code{poly1} and \code{poly2} are assumed to be coprime.
\end{quote}
\subsection{Differentiation}
\begin{lstlisting}
void zmod_poly_derivative(zmod_poly_t res, zmod_poly_t poly)
\end{lstlisting}
\begin{quote}
Set \code{res} equal to the derivative of \code{poly} and reduce all the coefficients modulo the modulus of \code{poly}.
\end{quote}
\subsection{Arithmetic modulo a polynomial}
\begin{lstlisting}
void zmod_poly_mulmod(zmod_poly_t res, zmod_poly_t poly1,
zmod_poly_t poly2, zmod_poly_t f)
\end{lstlisting}
\begin{quote}
Set \code{res} equal to the product of \code{poly1} and \code{poly2} modulo \code{f}. Assumes that \code{poly1} and \code{poly2} are reduced modulo \code{f}.
\end{quote}
\begin{lstlisting}
void zmod_poly_powmod(zmod_poly_t res, zmod_poly_t pol,
long exp, zmod_poly_t f)
\end{lstlisting}
\begin{quote}
Sets \code{res} equal to \code{pol} raised to the power \code{exp} modulo \code{f}. Assumes \code{pol} is reduced modulo \code{f}. There are no restrictions on \code{exp}, i.e. it can be zero, positive or negative. The leading coefficient of \code{f} must be invertible modulo the modulus.
\end{quote}
\subsection{Polynomial Factorization}
\begin{lstlisting}
void zmod_poly_factor_init(zmod_poly_factor_t fac)
\end{lstlisting}
\begin{quote}
Initializes an array for storing factors resulting from a factorisation. \end{quote}
\begin{lstlisting}
void zmod_poly_factor_clear(zmod_poly_factor_t fac)
\end{lstlisting}
\begin{quote}
Clear an array of factors, releasing any memory used by the struct.
\end{quote}
\begin{lstlisting}
void zmod_poly_factor_add(zmod_poly_factor_t fac,
zmod_poly_t poly)
\end{lstlisting}
\begin{quote}
Adds an extra element, \code{poly}, to the array of factors, \code{fac}.
\end{quote}
\begin{lstlisting}
void zmod_poly_factor_concat(zmod_poly_factor_t res,
zmod_poly_factor_t fac)
\end{lstlisting}
\begin{quote}
Concatenates the two arrays, \code{res} and \code{fac}, into a single array of factors, \code{res}.
\end{quote}
\begin{lstlisting}
void zmod_poly_factor_print(zmod_poly_factor_t fac)
\end{lstlisting}
\begin{quote}
Prints to stdout each factor in the array \code{fac} each with their corresponding exponent.
\end{quote}
\begin{lstlisting}
void zmod_poly_factor_pow(zmod_poly_factor_t fac,
unsigned long exp)
\end{lstlisting}
\begin{quote}
Raises each factor in the array \code{fac} to the power \code{exp}.
\end{quote}
\begin{lstlisting}
void zmod_poly_factor_square_free(zmod_poly_factor_t res,
zmod_poly_t f)
\end{lstlisting}
\begin{quote}
Sets \code{res} to a square-free factorization of \code{f}.
\end{quote}
\begin{lstlisting}
void zmod_poly_factor_berlekamp(zmod_poly_factor_t factors,
zmod_poly_t f)
\end{lstlisting}
\begin{quote}
Performs the Berlekamp factoring algorithm on \code{f}. Sets \code{factors} to the factors of \code{f}. Assumes \code{f} is squarefree.
\end{quote}
\begin{lstlisting}
unsigned long zmod_poly_factor(zmod_poly_factor_t result,
zmod_poly_t input)
\end{lstlisting}
\begin{quote}
Sets \code{result} to be a complete factorization of \code{input}. There are no restrictions on \code{input}.
\end{quote}
\begin{lstlisting}
int zmod_poly_isirreducible(zmod_poly_t f)
\end{lstlisting}
\begin{quote}
Returns 1 if the polynomial $f$ is irreducible, otherwise it returns 0.
\end{quote}
\section{The long\_extras module}
The \code{long_extras} module contains functions for doing arithmetic with integers which will fit into an \code{unsigned long}, including functions for modular arithmetic.
Many of the functions take a precomputed inverse, which increases performance. Unless otherwise specified, the functions which include 2 in the name support moduli up to \code{FLINT_BITS - 1} bits, i.e. 31 or 63 bits, and the remainder work with moduli up to and including \code{FLINT_D_BITS}.
On 64 bit machines, \code{FLINT_BITS} is 64 and \code{FLINT_D_BITS} is 53 bits. On a 32 bit machine the functions with 2 in the name are in fact macros aliasing the corresponding unadorned version. In this case \code{FLINT_BITS} is 32.
The functions which begin \code{z_ll_} generally take a parameter consisting of two \code{unsigned long}'s thought of as an integer of twice the normal size, e.g. on a 64 bit machine these functions would support an input of 128 bits.
Many of the functions in this module can be used to manipulate the individual coefficients of polynomials of type \code{zmod_poly_t}.
\begin{lstlisting}
pre_inv_t z_precompute_inverse(unsigned long n)
pre_inv2_t z_precompute_inverse2(unsigned long n)
pre_inv_ll_t z_ll_precompute_inverse2(unsigned long n)
\end{lstlisting}
\begin{quote}
Return a precomputed inverse of the integer \code{n}. The first version returns a \code{pre_inv_t}, which is used with functions taking parameters up to \code{FLINT_D_BITS}. The second version returns a \code{pre_inv2_t} for use with function with second versions of functions taking a precomputed inverse, which support parameters up to \code{FLINT_BITS - 1} bits. The third version returns an inverse suitable for use with \code{z_ll_} functions which support an operand consisting of two \code{unsigned long}'s for twice the normal integer precision.
\end{quote}
\begin{lstlisting}
unsigned long z_addmod(unsigned long a, unsigned long b,
unsigned long p)
\end{lstlisting}
\begin{quote}
Return the sum of \code{a} and \code{b} modulo \code{p}. Both \code{a} and \code{b} are assumed to be reduced modulo \code{p} when calling this function.
\end{quote}
\begin{lstlisting}
unsigned long z_submod(unsigned long a, unsigned long b,
unsigned long p)
\end{lstlisting}
\begin{quote}
Return \code{a} minus \code{b} modulo \code{p}. Both \code{a} and \code{b} are assumed to be reduced modulo \code{p} when calling this function.
\end{quote}
\begin{lstlisting}
unsigned long z_negmod(unsigned long a, unsigned long p)
\end{lstlisting}
\begin{quote}
Return minus \code{a} modulo \code{p}. The value \code{a} is assumed to be reduced modulo \code{p} when calling this function.
\end{quote}
\begin{lstlisting}
unsigned long z_div2_precomp(unsigned long a, unsigned long n,
pre_inv2_t ninv)
\end{lstlisting}
\begin{quote}
Return the floor of the quotient of \code{a} by \code{n}. There are no restrictions on the size of \code{a}.
\end{quote}
\begin{lstlisting}
unsigned long z_mod_precomp(unsigned long a, unsigned long n,
pre_inv_t ninv)
unsigned long z_mod2_precomp(unsigned long a, unsigned long n,
pre_inv2_t ninv)
unsigned long z_ll_mod_precomp(unsigned long a_hi,
unsigned long a_lo, unsigned long n, pre_inv_ll_t ninv)
\end{lstlisting}
\begin{quote}
Return \code{a} modulo \code{n}. The first version assumes that \code{a} is less than \code{n^2}. The second and third versions replaces no restrictions on \code{a}.
\end{quote}
\begin{lstlisting}
unsigned long z_mulmod_precomp(unsigned long a, unsigned long b,
unsigned long n, pre_inv_t ninv)
unsigned long z_mulmod2_precomp(unsigned long a, unsigned long b,
unsigned long n, pre_inv2_t ninv)
\end{lstlisting}
\begin{quote}
Return \code{a} times \code{b} modulo \code{n}. The first version assumes that \code{a} and \code{b} have been reduced modulo \code{n} before calling the function. The second version places no restrictions on \code{a} and \code{b}, i.e. their product may be up to two full limbs.
\end{quote}
\begin{lstlisting}
unsigned long z_powmod(unsigned long a, long exp, unsigned long n)
unsigned long z_powmod2(unsigned long a, long exp, unsigned long n)
unsigned long z_powmod_precomp(unsigned long a, long exp,
unsigned long n, pre_inv_t ninv)
unsigned long z_powmod2_precomp(unsigned long a, long exp,
unsigned long n, pre_inv2_t ninv)
\end{lstlisting}
\begin{quote}
Raise \code{a} to the power \code{exp} modulo \code{n}. All versions assume \code{a} is reduced modulo \code{n}, but there are no restrictions on \code{exp}, which may be negative (assuming \code{a} is invertible modulo \code{n}) or zero.
\end{quote}
\begin{lstlisting}
int z_legendre_precomp(unsigned long a, unsigned long p,
pre_inv_t pinv)
\end{lstlisting}
\begin{quote}
Computes the Legendre symbol of \code{a} modulo \code{p} for a prime \code{p}. Assumes that \code{a} is reduced modulo \code{p}.
\end{quote}
\begin{lstlisting}
int z_jacobi(long x, unsigned long y)
\end{lstlisting}
\begin{quote}
Calculates the Jacobi symbol of (\code{x}/\code{y}). Assumes that gcd(\code{x},\code{y})=1 and \code{y} is odd.
\end{quote}
\begin{lstlisting}
int z_ispseudoprime_fermat(unsigned long const n,
unsigned long const i)
\end{lstlisting}
\begin{quote}
Checks to see if \code{n} is a Fermat pseudoprime with base \code{i}. Assumes that \code{n} does not divide \code{i}.
\end{quote}
\begin{lstlisting}
int z_isprime(unsigned long n)
int z_isprime_precomp(unsigned long n, pre_inv_t ninv)
\end{lstlisting}
\begin{quote}
Returns 1 if $n$ is proved prime, otherwise it returns 0 in which case $n$ is composite. In the precomp version of the function it is assumed that \code{n} is greater than 2 and odd. The function takes a precomputed inverse of $n$.
\end{quote}
\begin{lstlisting}
int z_isprobab_prime(unsigned long n)
int z_isprobab_prime_precomp(unsigned long n, pre_inv_t ninv)
\end{lstlisting}
\begin{quote}
This is a deterministic prime test up to $10^16$. Requires \code{n} to be at most \code{FLINT_BITS-1} bits. For numbers greater than $10^16$ there are no known counterexamples to the conjecture that a composite will never be declared prime. Primes are always declared prime by this test.
\end{quote}
\begin{lstlisting}
unsigned long z_nextprime(unsigned long n, int proved)
\end{lstlisting}
\begin{quote}
Returns the next prime after \code{n}. Assumes the result will fit in an unsigned long. If \code{proved} is 0 the prime is not proven prime, otherwise it is.
\end{quote}
\begin{lstlisting}
int z_isprime_pocklington(unsigned long const n,
unsigned long const iterations)
\end{lstlisting}
\begin{quote}
Proves that \code{n} is prime using a Pocklington-Lehmer test returns 0 if composite, 1 if prime and -1 if it failed to prove either way. The number of iterations can be increased for a more thorough check but will take longer. Setting \code{iterations} to \code{-1L} will cause it to continue until the number is proven prime or composite.
\end{quote}
\begin{lstlisting}
int z_ispseudoprime_lucas_ab(unsigned long n, int a, int b)
\end{lstlisting}
\begin{quote}
Tests to see if \code{n} is an \code{a,b-}Lucas pseudoprime. Returns 0 if \code{n} is composite or fails gcd(\code{n}, 2*\code{a}*\code{b}*(\code{a}*\code{a} - 4*\code{b})) = 1. Returns 1 if \code{n} is a Lucas pseudoprime with respect to $x^2 - ax + b$. Returns -1 if the discriminant of the quadratic is square. Assumes \code{n} has been checked for primality using trial factoring up to 256. The absolute values of \code{a} and \code{b} should be $<$ 128. For details of this function see the book ``Primes : a computational perspective'' by Pomerance and Crandall.
\end{quote}
\begin{lstlisting}
int z_ispseudoprime_lucas(unsigned long const n)
\end{lstlisting}
\begin{quote}
Tests if $n$ is a Lucas pseudoprime as per the algorithm of Baillie and Wagstaff (see Math. Comp. vol 35, no. 152, 1980, pp. 1391--1417). Assumes \code{n} has been checked for primality using trial factoring up to 256.
\end{quote}
\begin{lstlisting}
unsigned long z_pow(unsigned long a, unsigned long exp)
\end{lstlisting}
\begin{quote}
Computes \code{a} to the power \code{exp} which must be non-negative. Assumes that the result will fit in an \code{unsigned long}.
\end{quote}
\begin{lstlisting}
unsigned long z_sqrtmod(unsigned long a, unsigned long p)
\end{lstlisting}
\begin{quote}
Returns a square root of \code{a} modulo \code{p}. Assumes \code{a} is reduced modulo \code{p}. The function returns 0 if \code{a} is not a quadratic residue modulo a prime \code{p}.
\end{quote}
\begin{lstlisting}
unsigned long z_cuberootmod(unsigned long * cuberoot1,
unsigned long a, unsigned long p)
\end{lstlisting}
\begin{quote}
Returns a cube root of \code{a} modulo a prime \code{p}. Assumes \code{a} is reduced modulo \code{p}. If \code{a} is not 0, the function also sets \code{cuberoot1} to a cube root of unity modulo \code{p} if the cube roots of \code{a} are distinct, otherwise \code{cuberoot1} is set to 1. If \code{a} is not a cubic residue modulo \code{p} the function returns 0.
\end{quote}
\begin{lstlisting}
unsigned long z_gcd(long x, long y)
\end{lstlisting}
\begin{quote}
Returns the greatest common divisor of \code{x} and \code{y}, which may be signed.
\end{quote}
\begin{lstlisting}
unsigned long z_invert(unsigned long a, unsigned long n)
\end{lstlisting}
\begin{quote}
Returns a multiplicative inverse of \code{a} modulo \code{n}. Assumes \code{a} is reduced modulo \code{p}.
\end{quote}
\begin{lstlisting}
long z_gcd_invert(long* a, long x, long y)
\end{lstlisting}
\begin{quote}
Returns the greatest common divisor \code{d} of \code{x} and \code{y} (which may be signed) and sets \code{a} such that \code{a*x} is \code{d} modulo \code{y}. We ensure \code{a} is reduced modulo \code{y}.
\end{quote}
\begin{lstlisting}
long z_xgcd(long* a, long* b, long x, long y)
\end{lstlisting}
\begin{quote}
Returns the greatest common divisor \code{d} of \code{x} and \code{y} (which may be signed) and sets \code{a} and \code{b} such that \code{d = a*x+b*y}.
\end{quote}
\begin{lstlisting}
unsigned long z_intsqrt(unsigned long r)
\end{lstlisting}
\begin{quote}
Returns the integer part of the square root of \code{r}.
\end{quote}
\begin{lstlisting}
int z_issquare(long x)
\end{lstlisting}
\begin{quote}
The function returns 0 if \code{x} is not a perfect square and 1 otherwise.
\end{quote}
\begin{lstlisting}
unsigned long z_CRT(unsigned long x1, unsigned long n1,
unsigned long x2, unsigned long n2)
\end{lstlisting}
\begin{quote}
Returns the unique integer \code{d} reduced modulo \code{n1*n2} which is \code{x1} modulo \code{n1} and \code{x2} modulo \code{n2}. Assumes \code{x1} is reduced modulo \code{n1} and \code{x2} is reduced modulo \code{n2}. Also assumes \code{n1*n2} is no more than \code{FLINT_BITS - 1} bits and that \code{n1} and \code{n2} are coprime.
\end{quote}
\begin{lstlisting}
int z_remove(unsigned long * n,
unsigned long p)
int z_remove_precomp(unsigned long * n,
unsigned long p, pre_inv_t pinv)
\end{lstlisting}
\begin{quote}
Removes the highest power of \code{p} possible from \code{n} and returns the exponent to which it appeared in \code{n}. In the second function \code{n} can only be up to \code{FLINT_BITS-1} bits.
\end{quote}
\begin{lstlisting}
void z_factor(factor_t * factors, unsigned long n, int proved)
\end{lstlisting}
\begin{quote}
Find the factors of \code{n}. If \code{proved} is set to 0 then the factors are not proved prime, otherwise the result is proved.
\end{quote}
\begin{lstlisting}
unsigned long z_factor_partial(factor_t * factors,
unsigned long n, unsigned long limit, int proved)
\end{lstlisting}
\begin{quote}
Factors \code{n} until the product of the factor found is $>$ \code{limit}. It puts the factors in \code{factors} and returns the cofactor. If \code{proved} is set to 0 then the factors are not proved prime, otherwise the result is proved.
\end{quote}
\begin{lstlisting}
int z_issquarefree(unsigned long n, int proved)
\end{lstlisting}
\begin{quote}
Returns 1 if n is squarefree, otherwise returns 0. If \code{proved} is set to 1 then the result is guaranteed, and if set to 0 then internal factoring may declare some composites prime. Note that \code{n} must be at most \code{FLINT_BITS - 1} bits.
\end{quote}
\begin{lstlisting}
int z_issquare(long n)
\end{lstlisting}
\begin{quote}
Returns 1 if n is a square, otherwise returns 0. There are no restrictions on n, which may be signed and negative numbers will not be declared square.
\end{quote}
\begin{lstlisting}
unsigned long z_randint(unsigned long limit)
\end{lstlisting}
\begin{quote}
Returns a random uniformly distributed integer in the range 0 to \code{limit - 1} inclusive. If \code{limit} is set to 0, the function returns a full random limb.
\end{quote}
\begin{lstlisting}
unsigned long z_randbits(unsigned long bits)
\end{lstlisting}
\begin{quote}
Returns a random uniformly distributed integer with up to the given number of bits. If \code{bits} is set to 0, the function returns a full random limb.
\end{quote}
\begin{lstlisting}
unsigned long (unsigned long bits, int proved)
\end{lstlisting}
\begin{quote}
Returns a random prime integer with up to the given number of bits. Assumes \code{bits} $> 1$. If \code{proved} is 0 then the prime is not proven prime, otherwise it is.
\end{quote}
\section{The mpn\_extras module}
The \code{mpn\_extras} module is designed to supplement the low level \code{mpn} functions provided in GMP. These functions are designed to operate on raw limbs of multiprecision integer data. Each such integer consists of a string of limbs representing an integer, with the least significant limb first. The integers may either be unsigned or signed in twos complement format.
\begin{lstlisting}
void F_mpn_negate(mp_limb_t* dest, mp_limb_t* src,
unsigned long count)
\end{lstlisting}
\begin{quote}
Considering the data at the location \code{src} to be an integer of \code{count} limbs stored in twos complement format, this function negates the integer and stores the result at the location \code{dest}.
\end{quote}
\begin{lstlisting}
void F_mpn_copy(mp_limb_t* dest, const mp_limb_t* src,
unsigned long count)
\end{lstlisting}
\begin{quote}
Copy \code{count} raw limbs at \code{src} to the location \code{dest}. Copying begins with the most significant limb first, thus the destination limbs may overlap the source limbs only if \code{dest > src} in memory.
\end{quote}
\begin{lstlisting}
void F_mpn_copy_forward(mp_limb_t* dest, const mp_limb_t* src,
unsigned long count)
\end{lstlisting}
\begin{quote}
Copy \code{count} raw limbs at \code{src} to the location \code{dest}. Copying begins with the least significant limb first, thus the destination limbs may overlap the source limbs only if \code{dest < src} in memory.
\end{quote}
\begin{lstlisting}
void F_mpn_clear(mp_limb_t* dest, unsigned long count)
\end{lstlisting}
\begin{quote}
Set all bits of the \code{count} limbs starting at \code{dest} to binary zeros.
\end{quote}
\begin{lstlisting}
void F_mpn_set(mp_limb_t* dest, unsigned long count)
\end{lstlisting}
\begin{quote}
Set all bits of the \code{count} limbs starting at \code{dest} to binary ones.
\end{quote}
\begin{lstlisting}
pre_limb_t F_mpn_precompute_inverse(mp_limb_t d)
\end{lstlisting}
\begin{quote}
Returns a precomputed inverse of \code{d} for use in \code{F_mpn} functions which take a \code{pre_limb_t} precomputed inverse \code{dinv} of \code{d}.
One needs to normalise \code{d} before computing the precomputed inverse, however the original value of \code{d} itself is passed to the functions. This computation can be done as follows:
\end{quote}
\begin{lstlisting}
#include "flint.h"
unsigned long norm;
count_lead_zeros(norm, d);
pre_limb_t xinv = F_mpn_precompute_inverse(x<<norm);
\end{lstlisting}
\begin{lstlisting}
mp_limb_t F_mpn_divrem_ui_precomp(mp_limb_t * quot,
mp_limb_t * x, unsigned long xn, mp_limb_t d, pre_limb_t dinv)
\end{lstlisting}
\begin{quote}
Compute the quotient of the unsigned multiprecision integer of \code{xn} limbs at \code{x} by the limb \code{d}, placing the quotient at \code{quot} and returning the remainder. The location \code{quot} needs space for \code{count} limbs. The function takes a precomputed inverse of \code{d}.
\end{quote}
\begin{lstlisting}
mp_limb_t F_mpn_mul(mp_limb_t * rn, mp_limb_t * s1p,
unsigned long s1n, mp_limb_t * s2p, unsigned long s2n)
\end{lstlisting}
\begin{quote}
Set \code{rn} to \code{s1p*s2p) where \code{s1p} has \code{s1n} limbs and \code{s2p} has \code{s2n} limbs. The number of limbs written is \code{s1n + s2n}. The most significant limb of the result (which may be zero) is returned by the function.
This function simply calls the GMP \code{mpn_mul} function for small operands, however for integers of FFT size (larger than about 1300 limbs for multiplication and 1000 limbs for squares) the function is significantly faster than GMP 4.2.2.
\end{quote}
\begin{lstlisting}
mp_limb_t F_mpn_mul_trunc(mp_limb_t * rn, mp_limb_t * s1p,
unsigned long s1n, mp_limb_t * s2p, unsigned long s2n,
unsigned long tn)
\end{lstlisting}
\begin{quote}
Set \code{rn} to \code{s1p*s2p) where \code{s1p} has \code{s1n} limbs and \code{s2p} has \code{s2n} limbs. The output is truncated to \code{tn} limbs, where \code{tn} must be at most \code{s1n+s2n}. The most significant limb of the result (i.e. limb \code{tn}) is returned by the function.
The location \code{rn} must have space for \code{s1n + s2n} limbs, regardless of the value of \code{tn}.
This function simply calls the GMP \code{mpn_mul} function for small operands, however for integers of FFT size the function is significantly faster than GMP 4.2.2. and slightly faster than doing a full multiplication.
\end{quote}
\begin{lstlisting}
void F_mpn_mul_precomp_init(F_mpn_precomp_t precomp,
mp_limb_t * s1p, unsigned long s1n, s2n)
\end{lstlisting}
\begin{quote}
When multiplying a single large integer \code{s1p} of \code{s1n} limbs (usually hundreds or more), by many other integers whose maximum size is \code{s2n} limbs, one can cache the FFT of \code{s1p} to speed up the multiplications. The precomputed data is attached to an \code{F_mpn_precomp_t precomp} by this function for use in the functions below.
\end{quote}
\begin{lstlisting}
void F_mpn_mul_precomp_clear(F_mpn_precomp_t precomp)
\end{lstlisting}
\begin{quote}
Release the memory allocated for the data attached to the \code{F_mpn_precomp_t precomp} once it is finished with.
\end{quote}
\begin{lstlisting}
mp_limb_t F_mpn_mul_precomp(mp_limb_t * rp, mp_limb_t * s2p,
unsigned long s2n, F_mpn_precomp_t precomp)
\end{lstlisting}
\begin{quote}
Multiply the integer \code{s2p} of \code{s2n} limbs by the integer whose FFT has been cached and attached to the \code{F_mpn_precomp_t precomp}, computed previously with \code{F_mpn_mul_precomp_init}.
The total number of limbs written is \code{s1n + s2n} (even if the final limb is zero) where \code{s1n} is the size of the integer whose FFT was cached. The most significant limb of the product is returned by the function.
\end{quote}
\section{NTL interface}
Various functions are provided for converting between FLINT objects and NTL objects. To make use of these functions one must type:
\code{#include "NTL-interface.h"}
In each case the functions provided for conversion expect the output objects, whether NTL or FLINT objects, to be initialised. The first function is unmanaged in that the
user must ensure that sufficient space is allocated in the \code{fmpz_t} to hold the integer contained in the \code{ZZ}.
\begin{lstlisting}
void ZZ_to_fmpz(fmpz_t output, const ZZ& z)
\end{lstlisting}
\begin{quote}
Convert an NTL \code{ZZ} integer object to a FLINT \code{fmpz_t} integer object.
\end{quote}
The following functions are managed, in that a reallocation automatically occurs if insufficient space was allocated by the user.
\begin{lstlisting}
void fmpz_to_ZZ(ZZ& output, const fmpz_t z)
\end{lstlisting}
\begin{quote}
Convert a FLINT \code{fmpz_t} integer object to an NTL \code{ZZ} integer object.
\end{quote}
\begin{lstlisting}
void fmpz_poly_to_ZZX(ZZX& output, const fmpz_poly_t poly)
\end{lstlisting}
\begin{quote}
Convert a FLINT \code{fmpz_poly_t} polynomial object to an NTL \code{ZZX} polynomial object.
\end{quote}
\begin{lstlisting}
void ZZX_to_fmpz_poly(fmpz_poly_t output, const ZZX& poly)
\end{lstlisting}
\begin{quote}
Convert an NTL \code{ZZX} polynomial object to a FLINT \code{fmpz_poly_t} polynomial object.
\end{quote}
\section{The quadratic sieve}
Currently the quadratic sieve is a standalone program which can be built by typing:
\code{make QS}
in the main FLINT directory.
The program is called \code{mpQS}. Upon running it, one enters the number to be factored at the prompt.
The quadratic sieve requires that the number entered not be a prime, not be a perfect power and it must not have very small factors. Trial division and the elliptic curve method should be run before making a call to the quadratic sieve, to remove small factors. The sieve may fail silently if the conditions are not met or if the number is too small to be factored by the quadratic sieve (currently about 20 decimal digits or below).
\section{Large integer multiplication}
In the module \code{mpn_extras} and \code{mpz_extras} are functions \code{F_mpn_mul} and \code{F_mpz_mul} respectively which are drop in replacements for GMP's \code{mpn_mul} and \code{mpz_mul} respectively.
These replacement functions are substantially faster than GMP 4.2.1 when multiplying integers which are thousands of limbs in size. For smaller multiplications these functions call their respective GMP counterparts.
\bibliographystyle{amsalpha}
\bibliography{flint}
\end{document}
distrib
>
Mandriva
>
2010.0
>
i586
>
media
>
contrib-release
>
by-pkgid
>
9f4c189b4ac0d990864b855d532c2b62
>
files
>
3
