\deg b$.
Assumes that $p$ is prime.
\fun{GEN}{Flx_halfgcd_pre}{GEN a, GEN b, ulong p}
\fun{GEN}{Flx_extgcd}{GEN a, GEN b, ulong p, GEN *ptu, GEN *ptv},
here $p$ must be prime.
\fun{GEN}{Flx_extgcd_pre}{GEN a, GEN b, ulong p, ulong pi, GEN *ptu, GEN *ptv}
\fun{GEN}{Flx_roots}{GEN f, ulong p} returns the vector of roots
of $f$ (without multiplicity, as a \typ{VECSMALL}). Assumes that $p$ is
prime.
\fun{GEN}{Flx_roots_pre}{GEN f, ulong p, ulong pi}
\fun{ulong}{Flx_oneroot}{GEN f, ulong p} returns one root $0 \leq r < p$ of
the \kbd{Flx}~\kbd{f} in \kbd{\Z/p\Z}. Return $p$ if no root exists.
Assumes that $p$ is prime.
\fun{GEN}{Flx_oneroot_pre}{GEN f, ulong p}, as \kbd{Flx\_oneroot}
\fun{ulong}{Flx_oneroot_split}{GEN f, ulong p} as \kbd{Flx\_oneroot} but
assume $f$ is totally split. Assumes that $p$ is prime.
\fun{ulong}{Flx_oneroot_split_pre}{GEN f, ulong p, ulong pi}
\fun{long}{Flx_ispower}{GEN f, ulong k, ulong p, GEN *pt}
return $1$ if the \kbd{Flx} $f$ is a $k$-th power, $0$ otherwise.
If \kbd{pt} is not \kbd{NULL}, set it to $g$ such that $g^k = f$.
\fun{GEN}{Flx_factor}{GEN f, ulong p} Assumes that $p$ is prime.
\fun{GEN}{Flx_ddf}{GEN f, ulong p} Assumes that $p$ is prime.
\fun{GEN}{Flx_ddf_pre}{GEN f, ulong p, ulong pi}
\fun{GEN}{Flx_factor_squarefree}{GEN f, ulong p} returns the squarefree
factorization of $f$ modulo $p$. This is a vector $[u_1,\dots,u_k]$
of pairwise coprime \kbd{Flx} such that $u_k \neq 1$ and $f = \prod u_i^i$.
Shallow function. Assumes that $p$ is prime.
\fun{GEN}{Flx_factor_squarefree_pre}{GEN f, ulong p, ulong pi}
\fun{GEN}{Flx_mod_Xn1}{GEN T, ulong n, ulong p} return $T$ modulo
$(X^n + 1, p)$. Shallow function.
\fun{GEN}{Flx_mod_Xnm1}{GEN T, ulong n, ulong p} return $T$ modulo
$(X^n - 1, p)$. Shallow function.
\fun{GEN}{Flx_degfact}{GEN f, ulong p} as \tet{FpX_degfact}. Assumes that $p$
is prime.
\fun{GEN}{Flx_factorff_irred}{GEN P, GEN Q, ulong p} as
\tet{FpX_factorff_irred}. Assumes that $p$ is prime.
\fun{GEN}{Flx_rootsff}{GEN P, GEN T, ulong p} as \tet{FpX_rootsff}.
Assumes that $p$ is prime.
\fun{GEN}{Flx_factcyclo}{ulong n, ulong p, ulong m} returns the factors
of the $n$-th cyclotomic polynomial over \kbd{Fp}. if $m=1$ returns
a single factor.
\fun{GEN}{Flx_ffisom}{GEN P,GEN Q,ulong l} as \tet{FpX_ffisom}.
Assumes that $p$ is prime.
\subsubsec{Miscellaneous operations}
\fun{GEN}{pol0_Flx}{long sv} returns a zero \kbd{Flx} in variable $v$.
\fun{GEN}{zero_Flx}{long sv} alias for \kbd{pol0\_Flx}
\fun{GEN}{pol1_Flx}{long sv} returns the unit \kbd{Flx} in variable $v$.
\fun{GEN}{polx_Flx}{long sv} returns the variable $v$ as degree~1~\kbd{Flx}.
\fun{GEN}{polxn_Flx}{long n, long sv} Returns the monomial of degree $n$ as
a \kbd{Flx} in variable $v$; assume that $n \geq 0$.
\fun{GEN}{monomial_Flx}{ulong a, long d, long sv} returns the \kbd{Flx}
$a\*X^d$ in variable $v$.
\fun{GEN}{init_Flxq}{ulong p, long n, long sv} returns an irreducible
polynomial of degree $\kbd{n} > 0$ over $\F_p$, in variable \kbd{v}.
\fun{GEN}{Flx_normalize}{GEN z, ulong p}, as \kbd{FpX\_normalize}.
\fun{GEN}{Flx_rescale}{GEN P, ulong h, ulong p} returns $h^{\deg(P)} P(x/h)$,
\kbd{P} is a \kbd{Flx} and \kbd{h} is a nonzero integer.
\fun{GEN}{random_Flx}{long d, long sv, ulong p} returns a random \kbd{Flx}
in variable \kbd{v}, of degree less than~\kbd{d}.
\fun{GEN}{Flx_recip}{GEN x}, returns the reciprocal polynomial
\fun{ulong}{Flx_resultant}{GEN a, GEN b, ulong p}, returns the resultant
of \kbd{a} and \kbd{b}. Assumes that $p$ is prime.
\fun{ulong}{Flx_resultant_pre}{GEN a, GEN b, ulong p, ulong pi}
\fun{ulong}{Flx_extresultant}{GEN a, GEN b, ulong p, GEN *ptU, GEN *ptV}
given two \kbd{Flx} \kbd{a} and \kbd{b},
returns their resultant and sets Bezout coefficients (if the resultant is 0,
the latter are not set). Assumes that $p$ is prime.
\fun{GEN}{Flx_invBarrett}{GEN T, ulong p}, returns the Barrett inverse
$M$ of $T$ defined by $M(x)\*x^n\*T(1/x)\equiv 1\pmod{x^{n-1}}$ where $n$ is
the degree of $T$. Assumes that $p$ is prime.
\fun{GEN}{Flx_renormalize}{GEN x, long l}, as \kbd{FpX\_renormalize}, where
$\kbd{l} = \kbd{lg(x)}$, in place.
\fun{GEN}{Flx_shift}{GEN T, long n} returns $\kbd{T} * x^n$ if $n\geq 0$,
and $\kbd{T} \bs x^{-n}$ otherwise.
\fun{long}{Flx_val}{GEN x} returns the valuation of \kbd{x}, i.e. the
multiplicity of the $0$ root.
\fun{long}{Flx_valrem}{GEN x, GEN *Z} as \kbd{RgX\_valrem}, returns the
valuation of \kbd{x}. In particular, if the valuation is $0$, set \kbd{*Z}
to $x$, not a copy.
\fun{GEN}{Flx_div_by_X_x}{GEN A, ulong a, ulong p, ulong *rem}, returns the
Euclidean quotient of the \kbd{Flx}~\kbd{A} by $X - \kbd{a}$, and sets
\kbd{rem} to the remainder $ \kbd{A}(\kbd{a})$.
\fun{ulong}{Flx_eval}{GEN x, ulong y, ulong p}, as \kbd{FpX\_eval}.
\fun{ulong}{Flx_eval_pre}{GEN x, ulong y, ulong p, ulong pi}
\fun{ulong}{Flx_eval_powers_pre}{GEN P, GEN y, ulong p, ulong pi}. Let $y$ be
the \typ{VECSMALL} $(1,a,\dots,a^n)$, where $n$ is the degree of the
\kbd{Flx} $P$, return $P(a)$.
\fun{GEN}{Flx_Flv_multieval}{GEN P, GEN v, ulong p} returns the vector
$[P(v[1]),\ldots,P(v[n])]$ as a \kbd{Flv}.
\fun{ulong}{Flx_dotproduct}{GEN x, GEN y, ulong p} returns the scalar product
of the coefficients of $x$ and $y$.
\fun{ulong}{Flx_dotproduct_pre}{GEN x, GEN y, ulong p, ulong pi}.
\fun{GEN}{Flx_deflate}{GEN P, long d} assuming $P$ is a polynomial of the
form $Q(X^d)$, return $Q$.
\fun{GEN}{Flx_inflate}{GEN P, long d} returns $P(X^d)$.
\fun{GEN}{Flx_splitting}{GEN P, long k}, as \tet{RgX_splitting}.
\fun{GEN}{Flx_blocks}{GEN P, long n, long m}, as \tet{RgX_blocks}.
\fun{int}{Flx_is_squarefree}{GEN z, ulong p}. Assumes that $p$ is prime.
\fun{int}{Flx_is_irred}{GEN f, ulong p}, as \kbd{FpX\_is\_irred}.
Assumes that $p$ is prime.
\fun{int}{Flx_is_totally_split}{GEN f, ulong p} returns $1$ if the
\kbd{Flx}~\kbd{f} splits into a product of distinct linear factors, $0$
otherwise. Assumes that \kbd{p} is prime.
\fun{int}{Flx_is_smooth}{GEN f, long r, ulong p} return $1$ if all
irreducible factors of $f$ are of degree at most $r$, $0$ otherwise.
Assumes that $p$ is prime.
\fun{int}{Flx_is_smooth_pre}{GEN f, long r, ulong p, ulong pi}
\fun{long}{Flx_nbroots}{GEN f, ulong p}, as \kbd{FpX\_nbroots}.
Assumes that $p$ is prime.
\fun{long}{Flx_nbfact}{GEN z, ulong p}, as \kbd{FpX\_nbfact}.
Assumes that $p$ is prime.
\fun{long}{Flx_nbfact_pre}{GEN z, ulong p, ulong pi}
\fun{long}{Flx_nbfact_Frobenius}{GEN f, GEN XP, ulong p},
as \kbd{FpX\_nbfact\_Frobenius}. Assumes that $p$ is prime.
\fun{long}{Flx_nbfact_Frobenius_pre}{GEN f, GEN XP, ulong p, ulong pi}
\fun{GEN}{Flx_degfact}{GEN f, ulong p}, as \kbd{FpX\_degfact}.
Assumes that $p$ is prime.
\fun{GEN}{Flx_nbfact_by_degree}{GEN z, long *nb, ulong p} Assume
that the \kbd{Flx} $z$ is squarefree mod the prime $p$. Returns a
\typ{VECSMALL} $D$ with $\deg z$ entries, such that $D[i]$ is the number of
irreducible factors of degree $i$. Set \kbd{nb} to the total number of
irreducible factors (the sum of the $D[i]$).
Assumes that $p$ is prime.
\fun{void}{Flx_ffintersect}{GEN P,GEN Q, long n, ulong p, GEN*SP, GEN*SQ, GEN
MA,GEN MB},\hfil\break
as \kbd{FpX\_ffintersect}. Assumes that $p$ is prime.
\fun{GEN}{Flx_Laplace}{GEN x, ulong p}
\fun{GEN}{Flx_invLaplace}{GEN x, ulong p}
\fun{GEN}{Flx_Newton}{GEN x, long n, ulong p}
\fun{GEN}{Flx_fromNewton}{GEN x, ulong p}
\fun{GEN}{Flx_Teichmuller}{GEN P, ulong p, long n}
Return a \kbd{ZX} $Q$ such that $P\equiv Q\pmod{p}$ and
$Q(X^p)=0\pmod{Q,p^n}$. Assumes that $p$ is prime.
\fun{GEN}{Flv_polint}{GEN x, GEN y, ulong p, long sv} as \kbd{FpV\_polint},
returning an \kbd{Flx} in variable $v$. Assumes that $p$ is prime.
\fun{GEN}{Flv_Flm_polint}{GEN x, GEN V, ulong p, long sv} equivalent (but
faster) to applying \kbd{Flv\_polint(x,$\ldots$)} to all the elements of the
vector $V$ (thus, returns a \kbd{FlxV}). Assumes that $p$ is prime.
\fun{GEN}{Flv_invVandermonde}{GEN L, ulong d, ulong p} $L$ being a \kbd{Flv}
of length $n$, return the inverse $M$ of the Vandermonde matrix attached to
the elements of $L$, multiplied by \kbd{d}.
If $A$ is a \kbd{Flv} and $B=M\*A$, then the polynomial
$P=\sum_{i=1}^n B[i]\*X^{i-1}$ verifies $P(L[i])=d\*A[i]$ for
$1 \leq i \leq n$. Assumes that $p$ is prime.
\fun{GEN}{Flv_roots_to_pol}{GEN a, ulong p, long sv} as
\kbd{FpV\_roots\_to\_pol} returning an \kbd{Flx} in variable $v$.
\subsec{\kbd{FlxV}} See \kbd{FpXV} operations.
\fun{GEN}{FlxV_Flc_mul}{GEN V, GEN W, ulong p}, as \kbd{FpXV\_FpC\_mul}.
\fun{GEN}{FlxV_red}{GEN V, ulong p} reduces each components with \kbd{Flx\_red}.
\fun{GEN}{FlxV_prod}{GEN V, ulong p}, \kbd{V} being a vector of \kbd{Flx},
returns their product.
\fun{ulong}{FlxC_eval_powers_pre}{GEN x, GEN y, ulong p, ulong pi}
apply \kbd{Flx\_eval\_powers\_pre} to all elements of \kbd{x}.
\fun{GEN}{FlxV_Flv_multieval}{GEN F, GEN v, ulong p} assuming $F$ is a
vector of \kbd{Flx} with $m$ entries and $v$ is a \kbd{Flv} with $m$ entries,
returns the $n$-components vector (\kbd{FlvV}) whose $j$-th entry is
$[F_j(v[1]),\ldots,F_j(v[n])]$, with $F_j = F[j]$.
\fun{GEN}{FlxC_neg}{GEN x, ulong p}
\fun{GEN}{FlxC_sub}{GEN x, GEN y, ulong p}
\fun{GEN}{zero_FlxC}{long n, long sv}
\subsec{\kbd{FlxM}} See \kbd{FpXM} operations.
\fun{ulong}{FlxM_eval_powers_pre}{GEN M, GEN y, ulong p, ulong pi}
this function applies \kbd{FlxC\_eval\_powers\_pre} to all entries of \kbd{M}.
\fun{GEN}{FlxM_neg}{GEN x, ulong p}
\fun{GEN}{FlxM_sub}{GEN x, GEN y, ulong p}
\fun{GEN}{zero_FlxM}{long r, long c, long sv}
\subsec{\kbd{FlxT}} See \kbd{FpXT} operations.
\fun{GEN}{FlxT_red}{GEN V, ulong p} reduces each leaf with \kbd{Flx\_red}.
\subsec{\kbd{Flxn}} See \kbd{FpXn} operations.
In this section, \var{pi} is the pseudoinverse of $p$, or $0$ in which case
we assume \kbd{SMALL\_ULONG}$(p)$.
\fun{GEN}{Flxn_mul}{GEN a, GEN b, long n, ulong p}
returns $a\*b$ modulo $X^n$.
\fun{GEN}{Flxn_mul_pre}{GEN a, GEN b, long n, ulong p, ulong pi}
\fun{GEN}{Flxn_sqr}{GEN a, long n, ulong p}
returns $a^2$ modulo $X^n$.
\fun{GEN}{Flxn_sqr_pre}{GEN a, long n, ulong p, ulong pi}
\fun{GEN}{Flxn_inv}{GEN a, long n, ulong p}
returns $1/a$ modulo $X^n$.
\fun{GEN}{Flxn_div}{GEN a, GEN b, long n, ulong p}
returns $a/b$ modulo $X^n$.
\fun{GEN}{Flxn_div_pre}{GEN a, GEN b, long n, ulong p, ulong pi}
\fun{GEN}{Flxn_red}{GEN a, long n}
returns $a$ modulo $X^n$.
\fun{GEN}{Flxn_exp}{GEN x, long n, ulong p} return $\exp(x)$
as a composition of formal power series.
It is required that the valuation of $x$ is positive and that $p>n$.
\fun{GEN}{Flxn_expint}{GEN f, long n, ulong p} return $\exp(F)$
where $F$ is the primitive of $f$ that vanishes at $0$.
It is required that $p>n$.
\subsec{\kbd{Flxq}} See \kbd{FpXQ} operations. In this section, \var{pi} is
the pseudoinverse of $p$, or $0$ in which case we assume
\kbd{SMALL\_ULONG}$(p)$.
\fun{GEN}{Flxq_add}{GEN x, GEN y, GEN T, ulong p}
\fun{GEN}{Flxq_sub}{GEN x, GEN y, GEN T, ulong p}
\fun{GEN}{Flxq_mul}{GEN x, GEN y, GEN T, ulong p}
\fun{GEN}{Flxq_mul_pre}{GEN x, GEN y, GEN T, ulong p, ulong pi}
\fun{GEN}{Flxq_sqr}{GEN y, GEN T, ulong p}
\fun{GEN}{Flxq_sqr_pre}{GEN y, GEN T, ulong p}
\fun{GEN}{Flxq_inv}{GEN x, GEN T, ulong p}
\fun{GEN}{Flxq_inv_pre}{GEN x, GEN T, ulong p, ulong pi}
\fun{GEN}{Flxq_invsafe}{GEN x, GEN T, ulong p}
\fun{GEN}{Flxq_invsafe_pre}{GEN x, GEN T, ulong p, ulong pi}
\fun{GEN}{Flxq_div}{GEN x, GEN y, GEN T, ulong p}
\fun{GEN}{Flxq_div_pre}{GEN x, GEN y, GEN T, ulong p, ulong pi}
\fun{GEN}{Flxq_pow}{GEN x, GEN n, GEN T, ulong p}
\fun{GEN}{Flxq_pow_pre}{GEN x, GEN n, GEN T, ulong p, ulong pi}
\fun{GEN}{Flxq_powu}{GEN x, ulong n, GEN T, ulong p}
\fun{GEN}{Flxq_powu_pre}{GEN x, ulong n, GEN T, ulong p}
\fun{GEN}{FlxqV_factorback}{GEN L, GEN e, GEN Tp, ulong p}
\fun{GEN}{Flxq_pow_init}{GEN x, GEN n, long k, GEN T, ulong p}
\fun{GEN}{Flxq_pow_init_pre}{GEN x, GEN n, long k, GEN T, ulong p, ulong pi}
\fun{GEN}{Flxq_pow_table}{GEN R, GEN n, GEN T, ulong p}
\fun{GEN}{Flxq_pow_table_pre}{GEN R, GEN n, GEN T, ulong p, ulong pi}
\fun{GEN}{Flxq_powers}{GEN x, long n, GEN T, ulong p}
\fun{GEN}{Flxq_powers_pre}{GEN x, long n, GEN T, ulong p, ulong pi}
\fun{GEN}{Flxq_matrix_pow}{GEN x, long m, long n, GEN T, ulong p},
see \kbd{FpXQ\_matrix\_pow}.
\fun{GEN}{Flxq_matrix_pow_pre}{GEN x, long m, long n, GEN T, ulong p, ulong pi}
\fun{GEN}{Flxq_autpow}{GEN a, long n, GEN T, ulong p}
see \kbd{FpXQ\_autpow}.
\fun{GEN}{Flxq_autpow_pre}{GEN a, long n, GEN T, ulong p, ulong pi}
\fun{GEN}{Flxq_autpowers}{GEN a, long n, GEN T, ulong p}
return $[X,\sigma(X),\ldots,\sigma^n(X)]$,
assuming $a=\sigma(X)$ where $\sigma$ is an automorphism of the algebra
$\F_p[X]/T(X)$.
\fun{GEN}{Flxq_autsum}{GEN a, long n, GEN T, ulong p}
see \kbd{FpXQ\_autsum}.
\fun{GEN}{Flxq_auttrace}{GEN a, ulong n, GEN T, ulong p}
see \kbd{FpXQ\_auttrace}.
\fun{GEN}{Flxq_auttrace_pre}{GEN a, ulong n, GEN T, ulong p, ulong pi}
\fun{GEN}{Flxq_ffisom_inv}{GEN S, GEN T, ulong p}, as \kbd{FpXQ\_ffisom\_inv}.
\fun{GEN}{Flx_Flxq_eval}{GEN f, GEN x, GEN T, ulong p} returns
$\kbd{f}(\kbd{x})$.
\fun{GEN}{Flx_Flxq_eval_pre}{GEN f, GEN x, GEN T, ulong p, ulong pi}
\fun{GEN}{Flx_FlxqV_eval}{GEN f, GEN x, GEN T, ulong p},
see \kbd{FpX\_FpXQV\_eval}.
\fun{GEN}{Flx_FlxqV_eval_pre}{GEN f, GEN x, GEN T, ulong p, ulong pi}
\fun{GEN}{FlxC_Flxq_eval}{GEN C, GEN x, GEN T, ulong p},
see \kbd{FpXC\_FpXQ\_eval}.
\fun{GEN}{FlxC_Flxq_eval_pre}{GEN C, GEN x, GEN T, ulong p, ulong pi}
\fun{GEN}{FlxC_FlxqV_eval}{GEN C, GEN V, GEN T, ulong p}
see \kbd{FpXC\_FpXQV\_eval}.
\fun{GEN}{FlxC_FlxqV_eval_pre}{GEN C, GEN V, GEN T, ulong p, ulong pi}
\fun{GEN}{FlxqV_roots_to_pol}{GEN V, GEN T, ulong p, long v} as
\kbd{FqV\_roots\_to\_pol} returning an \kbd{FlxqX} in variable $v$.
\fun{int}{Flxq_issquare}{GEN x, GEN T, ulong p} returns $1$ if $x$ is a square
and $0$ otherwise. Assume that \kbd{T} is irreducible mod \kbd{p}.
\fun{int}{Flxq_is2npower}{GEN x, long n, GEN T, ulong p} returns $1$ if $x$ is
a $2^n$-th power and $0$ otherwise. Assume that \kbd{T} is irreducible mod
\kbd{p}.
\fun{GEN}{Flxq_order}{GEN a, GEN ord, GEN T, ulong p}
as \tet{FpXQ_order}.
\fun{GEN}{Flxq_log}{GEN a, GEN g, GEN ord, GEN T, ulong p}
as \tet{FpXQ_log}
\fun{GEN}{Flxq_sqrtn}{GEN x, GEN n, GEN T, ulong p, GEN *zn} as
\tet{FpXQ_sqrtn}.
\fun{GEN}{Flxq_sqrt}{GEN x, GEN T, ulong p} returns a square root of \kbd{x}.
Return \kbd{NULL} if \kbd{x} is not a square.
\fun{GEN}{Flxq_lroot}{GEN a, GEN T, ulong p} returns $x$ such that $x^p = a$.
\fun{GEN}{Flxq_lroot_pre}{GEN a, GEN T, ulong p, ulong pi}
\fun{GEN}{Flxq_lroot_fast}{GEN a, GEN V, GEN T, ulong p} assuming that
\kbd{V=Flxq\_powers(s,p-1,T,p)} where $s(x)^p \equiv x\pmod{T(x),p}$,
returns $b$ such that $b^p=a$. Only useful if $p$ is less than the degree of
$T$.
\fun{GEN}{Flxq_lroot_fast_pre}{GEN a, GEN V, GEN T, ulong p, ulong pi}
\fun{GEN}{Flxq_charpoly}{GEN x, GEN T, ulong p} returns the characteristic
polynomial of \kbd{x}
\fun{GEN}{Flxq_minpoly}{GEN x, GEN T, ulong p} returns the minimal polynomial
of \kbd{x}
\fun{GEN}{Flxq_minpoly_pre}{GEN x, GEN T, ulong p, ulong pi}
\fun{ulong}{Flxq_norm}{GEN x, GEN T, ulong p} returns the norm of \kbd{x}
\fun{ulong}{Flxq_trace}{GEN x, GEN T, ulong p} returns the trace of \kbd{x}
\fun{GEN}{Flxq_conjvec}{GEN x, GEN T, ulong p} returns the conjugates
$[x,x^p,x^{p^2},\ldots,x^{p^{n-1}}]$ where $n$ is the degree of $T$.
\fun{GEN}{gener_Flxq}{GEN T, ulong p, GEN *po} returns a primitive root modulo
$(T,p)$. $T$ is an \kbd{Flx} assumed to be irreducible modulo the prime
$p$. If \kbd{po} is not \kbd{NULL} it is set to $[o,\var{fa}]$, where $o$ is the
order of the multiplicative group of the finite field, and \var{fa} is
its factorization.
\subsec{\kbd{FlxX}} See \kbd{FpXX} operations.
In this section, we assume \var{pi} is the pseudoinverse of $p$, or $0$ in
which case we assume \kbd{SMALL\_ULONG}$(p)$.
\fun{GEN}{pol1_FlxX}{long vX, long sx} returns the unit \kbd{FlxX} as a
\typ{POL} in variable \kbd{vX} which only coefficient is \kbd{pol1\_Flx(sx)}.
\fun{GEN}{polx_FlxX}{long vX, long sx} returns the variable $X$ as a
degree~1~\typ{POL} with \kbd{Flx} coefficients in the variable $x$.
\fun{long}{FlxY_degreex}{GEN P} return the degree of $P$ with respect to
the secondary variable.
\fun{GEN}{FlxX_add}{GEN P, GEN Q, ulong p}
\fun{GEN}{FlxX_sub}{GEN P, GEN Q, ulong p}
\fun{GEN}{FlxX_Fl_mul}{GEN x, ulong y, ulong p}
\fun{GEN}{FlxX_double}{GEN x, ulong p}
\fun{GEN}{FlxX_triple}{GEN x, ulong p}
\fun{GEN}{FlxX_neg}{GEN x, ulong p}
\fun{GEN}{FlxX_Flx_add}{GEN x, GEN y, ulong p}
\fun{GEN}{FlxX_Flx_sub}{GEN x, GEN y, ulong p}
\fun{GEN}{FlxX_Flx_mul}{GEN x, GEN y, ulong p}
\fun{GEN}{FlxY_Flx_div}{GEN x, GEN y, ulong p} divides the coefficients of $x$
by $y$ using \kbd{Flx\_div}.
\fun{GEN}{FlxX_deriv}{GEN P, ulong p} returns the derivative of \kbd{P} with
respect to the main variable.
\fun{GEN}{FlxX_Laplace}{GEN x, ulong p}
\fun{GEN}{FlxX_invLaplace}{GEN x, ulong p}
\fun{GEN}{FlxY_evalx}{GEN P, ulong z, ulong p} $P$ being an \kbd{FlxY}, returns
the \kbd{Flx} $P(z,Y)$, where $Y$ is the main variable of $P$.
\fun{GEN}{FlxY_evalx_pre}{GEN P, ulong z, ulong p, ulong pi}
\fun{GEN}{FlxX_translate1}{GEN P, ulong p, long n} $P$ being an \kbd{FlxX} with
all coefficients of degree at most $n$, return $(P(x,Y+1)$, where $Y$ is the
main variable of $P$.
\fun{GEN}{zlxX_translate1}{GEN P, ulong p, long e, long n}
$P$ being an \kbd{zlxX} with all coefficients of degree at most $n$, return
$(P(x,Y+1)$ modulo $p^e$ for prime $p$ , where $Y$ is the main variable of
$P$.
\fun{GEN}{FlxY_Flx_translate}{GEN P, GEN f, ulong p} $P$ being an \kbd{FlxY}
and $f$ being an \kbd{Flx}, return $(P(x,Y+f(x))$, where $Y$ is the main
variable of $P$.
\fun{ulong}{FlxY_evalx_powers_pre}{GEN P, GEN xp, ulong p, ulong pi}, \kbd{xp}
being the vector $[1,x,\dots,x^n]$, where $n$ is larger or equal to the degree
of $P$ in $X$, return $P(x,Y)$, where $Y$ is the main variable of $Q$.
\fun{ulong}{FlxY_eval_powers_pre}{GEN P, GEN xp, GEN yp, ulong p, ulong pi},
\kbd{xp} being the vector $[1,x,\dots,x^n]$, where $n$ is larger or equal to
the degree of $P$ in $X$ and \kbd{yp} being the vector $[1,y,\dots,y^m]$,
where $m$ is larger or equal to the degree of $P$ in $Y$ return $P(x,y)$.
\fun{GEN}{FlxY_Flxq_evalx}{GEN x, GEN y, GEN T, ulong p} as
\kbd{FpXY\_FpXQ\_evalx}.
\fun{GEN}{FlxY_Flxq_evalx_pre}{GEN x, GEN y, GEN T, ulong p, ulong pi}
\fun{GEN}{FlxY_FlxqV_evalx}{GEN x, GEN V, GEN T, ulong p} as
\kbd{FpXY\_FpXQV\_evalx}.
\fun{GEN}{FlxY_FlxqV_evalx_pre}{GEN x, GEN V, GEN T, ulong p, ulong pi}
\fun{GEN}{FlxX_renormalize}{GEN x, long l}, as \kbd{normalizepol}, where
$\kbd{l} = \kbd{lg(x)}$, in place.
\fun{GEN}{FlxX_resultant}{GEN u, GEN v, ulong p, long sv} Returns
$\text{Res}_X(u, v)$, which is an \kbd{Flx}. The coefficients of \kbd{u}
and \kbd{v} are assumed to be in the variable $v$.
\fun{GEN}{Flx_FlxY_resultant}{GEN a, GEN b, ulong p}
Returns $\text{Res}_x(a, b)$, which is an \kbd{Flx}
in the main variable of \kbd{b}.
\fun{GEN}{FlxX_blocks}{GEN P, long n, long m, long sv}, as \tet{RgX_blocks},
where $v$ is the secondary variable.
\fun{GEN}{FlxX_shift}{GEN a, long n, long sv}, as \kbd{RgX\_shift\_shallow},
where $v$ is the secondary variable.
\fun{GEN}{FlxX_swap}{GEN x, long n, long ws}, as \kbd{RgXY\_swap}.
\fun{GEN}{FlxYqq_pow}{GEN x, GEN n, GEN S, GEN T, ulong p}, as
\kbd{FpXYQQ\_pow}.
\subsec{\kbd{FlxXV, FlxXC, FlxXM}} See \kbd{FpXX} operations.
\fun{GEN}{FlxXC_sub}{GEN x, GEN y, ulong p}
\subsec{\kbd{FlxqX}} See \kbd{FpXQX} operations.
\subsubsec{Preconditioned reduction}
For faster reduction, the modulus \kbd{S} can be replaced by an extended
modulus, which is an \kbd{FlxqXT}, in all \kbd{FlxqXQ}-classes
functions, and in \kbd{FlxqX\_rem} and \kbd{FlxqX\_divrem}.
\fun{GEN}{FlxqX_get_red}{GEN S, GEN T, ulong p} returns the extended modulus
\kbd{eS}.
\fun{GEN}{FlxqX_get_red_pre}{GEN S, GEN T, ulong p, ulong pi}, where \var{pi}
is a pseudoinverse of $p$, or $0$ in which case we assume
\kbd{SMALL\_ULONG}$(p)$.
To write code that works both with plain and extended moduli, the following
accessors are defined:
\fun{GEN}{get_FlxqX_mod}{GEN eS} returns the underlying modulus \kbd{S}.
\fun{GEN}{get_FlxqX_var}{GEN eS} returns the variable number of the modulus.
\fun{GEN}{get_FlxqX_degree}{GEN eS} returns the degree of the modulus.
\subsubsec{basic functions}
In this section, \var{pi} is a pseudoinverse of $p$, or $0$ in which case we
assume \kbd{SMALL\_ULONG}$(p)$.
\fun{GEN}{random_FlxqX}{long d, long v, GEN T, ulong p} returns a random
\kbd{FlxqX} in variable \kbd{v}, of degree less than~\kbd{d}.
\fun{GEN}{zxX_to_Kronecker}{GEN P, GEN Q} assuming $P(X,Y)$ is a polynomial
of degree in $X$ strictly less than $n$, returns $P(X,X^{2*n-1})$, the
Kronecker form of $P$.
\fun{GEN}{Kronecker_to_FlxqX}{GEN z, GEN T, ulong p}. Let $n = \deg T$ and let
$P(X,Y)\in \Z[X,Y]$ lift a polynomial in $K[Y]$, where $K := \F_p[X]/(T)$ and
$\deg_X P < 2n-1$ --- such as would result from multiplying minimal degree
lifts of two polynomials in $K[Y]$. Let $z = P(t,t^{2*n-1})$ be a Kronecker
form of $P$, this function returns $Q\in \Z[X,t]$ such that $Q$ is congruent to
$P(X,t)$ mod $(p, T(X))$, $\deg_X Q < n$, and all coefficients are in $[0,p[$.
Not stack-clean. Note that $t$ need not be the same variable as $Y$!
\fun{GEN}{Kronecker_to_FlxqX_pre}{GEN z, GEN T, ulong p, ulong pi}
\fun{GEN}{FlxqX_red}{GEN z, GEN T, ulong p}
\fun{GEN}{FlxqX_red_pre}{GEN z, GEN T, ulong p, ulong pi}
\fun{GEN}{FlxqX_normalize}{GEN z, GEN T, ulong p}
\fun{GEN}{FlxqX_normalize_pre}{GEN z, GEN T, ulong p, ulong pi}
\fun{GEN}{FlxqX_mul}{GEN x, GEN y, GEN T, ulong p}
\fun{GEN}{FlxqX_mul_pre}{GEN x, GEN y, GEN T, ulong p, ulong pi}
\fun{GEN}{FlxqX_Flxq_mul}{GEN P, GEN U, GEN T, ulong p}
\fun{GEN}{FlxqX_Flxq_mul_pre}{GEN P, GEN U, GEN T, ulong p, ulong pi}
\fun{GEN}{FlxqX_Flxq_mul_to_monic}{GEN P, GEN U, GEN T, ulong p}
returns $P*U$ assuming the result is monic of the same degree as $P$ (in
particular $U\neq 0$).
\fun{GEN}{FlxqX_Flxq_mul_to_monic_pre}{GEN P, GEN U, GEN T, ulong p, ulong pi}
\fun{GEN}{FlxqX_sqr}{GEN x, GEN T, ulong p}
\fun{GEN}{FlxqX_sqr_pre}{GEN x, GEN T, ulong p, ulong pi}
\fun{GEN}{FlxqX_powu}{GEN x, ulong n, GEN T, ulong p}
\fun{GEN}{FlxqX_powu_pre}{GEN x, ulong n, GEN T, ulong p, ulong pi}
\fun{GEN}{FlxqX_divrem}{GEN x, GEN y, GEN T, ulong p, GEN *pr}
\fun{GEN}{FlxqX_divrem_pre}{GEN x, GEN y, GEN T, ulong p, ulong pi, GEN *pr}
\fun{GEN}{FlxqX_div}{GEN x, GEN y, GEN T, ulong p}
\fun{GEN}{FlxqX_div_pre}{GEN x, GEN y, GEN T, ulong p, ulong pi}
\fun{GEN}{FlxqX_rem}{GEN x, GEN y, GEN T, ulong p}
\fun{GEN}{FlxqX_rem_pre}{GEN x, GEN y, GEN T, ulong p, ulong pi}
\fun{GEN}{FlxqX_invBarrett}{GEN T, GEN Q, ulong p}
\fun{GEN}{FlxqX_invBarrett_pre}{GEN T, GEN Q, ulong p, ulong pi}
\fun{GEN}{FlxqX_gcd}{GEN x, GEN y, ulong p} returns a (not necessarily monic)
greatest common divisor of $x$ and $y$.
\fun{GEN}{FlxqX_gcd_pre}{GEN x, GEN y, ulong p, ulong pi}
\fun{GEN}{FlxqX_extgcd}{GEN x, GEN y, GEN T, ulong p, GEN *ptu, GEN *ptv}
\fun{GEN}{FlxqX_extgcd_pre}{GEN x, GEN y, GEN T, ulong p, ulong pi, GEN *ptu, GEN *ptv}
\fun{GEN}{FlxqX_halfgcd}{GEN x, GEN y, GEN T, ulong p}, see \kbd{FpX\_halfgcd}.
\fun{GEN}{FlxqX_halfgcd_pre}{GEN x, GEN y, GEN T, ulong p, ulong pi}
\fun{GEN}{FlxqX_resultant}{GEN x, GEN y, GEN T, ulong p}
\fun{GEN}{FlxqX_saferesultant}{GEN P, GEN Q, GEN T, ulong p} Returns the
resultant of $P$ and $Q$ if Euclid's algorithm succeeds and \kbd{NULL} otherwise.
In particular, if $p$ is not prime or $T$ is not irreducible over $\F_p[X]$, the
routine may still be used (but will fail if noninvertible leading terms
occur).
\fun{GEN}{FlxqX_disc}{GEN x, GEN T, ulong p}
\fun{GEN}{FlxqXV_prod}{GEN V, GEN T, ulong p}
\fun{GEN}{FlxqX_safegcd}{GEN P, GEN Q, GEN T, ulong p} Returns the \emph{monic}
GCD of $P$ and $Q$ if Euclid's algorithm succeeds and \kbd{NULL} otherwise. In
particular, if $p$ is not prime or $T$ is not irreducible over $\F_p[X]$, the
routine may still be used (but will fail if noninvertible leading terms
occur).
\fun{GEN}{FlxqX_dotproduct}{GEN x, GEN y, GEN T, ulong p} returns the scalar
product of the coefficients of $x$ and $y$.
\fun{GEN}{FlxqX_Newton}{GEN x, long n, GEN T, ulong p}
\fun{GEN}{FlxqX_Newton_pre}{GEN x, long n, GEN T, ulong p, ulong pi}
\fun{GEN}{FlxqX_fromNewton}{GEN x, GEN T, ulong p}
\fun{GEN}{FlxqX_fromNewton_pre}{GEN x, GEN T, ulong p, ulong pi}
We assume \var{pi} is a pseudoinverse of $p$, or $0$ in which case we assume
\kbd{SMALL\_ULONG}$(p)$.
\fun{long}{FlxqX_is_squarefree}{GEN S, GEN T, ulong p}, as
\kbd{FpX\_is\_squarefree}.
\fun{long}{FlxqX_ispower}{GEN f, ulong k, GEN T, ulong p, GEN *pt}
return $1$ if the \kbd{FlxqX} $f$ is a $k$-th power, $0$ otherwise.
If \kbd{pt} is not \kbd{NULL}, set it to $g$ such that $g^k = f$.
\fun{GEN}{FlxqX_Frobenius}{GEN S, GEN T, ulong p}, as \kbd{FpXQX\_Frobenius}
\fun{GEN}{FlxqX_Frobenius_pre}{GEN S, GEN T, ulong p, ulong pi}
\fun{GEN}{FlxqX_roots}{GEN f, GEN T, ulong p} return the roots of \kbd{f} in
$\F_p[X]/(T)$. Assumes \kbd{p} is prime and \kbd{T} irreducible in $\F_p[X]$.
\fun{GEN}{FlxqX_factor}{GEN f, GEN T, ulong p} return the factorization of
\kbd{f} over $\F_p[X]/(T)$. Assumes \kbd{p} is prime and \kbd{T} irreducible
in $\F_p[X]$.
\fun{GEN}{FlxqX_factor_squarefree}{GEN f, GEN T, ulong p} returns the squarefree
factorization of $f$, see \kbd{FpX\_factor\_squarefree}.
\fun{GEN}{FlxqX_factor_squarefree_pre}{GEN f, GEN T, ulong p, ulong pi}
\fun{GEN}{FlxqX_ddf}{GEN f, GEN T, ulong p} as \kbd{FpX\_ddf}.
\fun{long}{FlxqX_ddf_degree}{GEN f, GEN XP, GEN T, GEN p},
as \kbd{FpX\_ddf\_degree}.
\fun{GEN}{FlxqX_degfact}{GEN f, GEN T, ulong p}, as \kbd{FpX\_degfact}.
\fun{long}{FlxqX_nbroots}{GEN S, GEN T, ulong p}, as \kbd{FpX\_nbroots}.
\fun{long}{FlxqX_nbfact}{GEN S, GEN T, ulong p}, as \kbd{FpX\_nbfact}.
\fun{long}{FlxqX_nbfact_Frobenius}{GEN S, GEN Xq, GEN T, ulong p},
as \kbd{FpX\_nbfact\_Frobenius}.
\fun{GEN}{FlxqX_nbfact_by_degree}{GEN z, long *nb, GEN T, ulong p} Assume
that the \kbd{FlxqX} $z$ is squarefree mod the prime $p$. Returns a
\typ{VECSMALL} $D$ with $\deg z$ entries, such that $D[i]$ is the number of
irreducible factors of degree $i$. Set \kbd{nb} to the total number of
irreducible factors (the sum of the $D[i]$).
\fun{GEN}{FlxqX_FlxqXQ_eval}{GEN Q, GEN x, GEN S, GEN T, ulong p} as
\kbd{FpX\_FpXQ\_eval}.
\fun{GEN}{FlxqX_FlxqXQ_eval_pre}{GEN Q, GEN x, GEN S, GEN T, ulong p, ulong pi}
\fun{GEN}{FlxqX_FlxqXQV_eval}{GEN P, GEN V, GEN S, GEN T, ulong p} as
\kbd{FpX\_FpXQV\_eval}.
\fun{GEN}{FlxqX_FlxqXQV_eval_pre}{GEN P, GEN V, GEN S, GEN T, ulong p,
ulong pi}
\fun{GEN}{FlxqXC_FlxqXQ_eval}{GEN Q, GEN x, GEN S, GEN T, ulong p} as
\kbd{FpXC\_FpXQ\_eval}.
\fun{GEN}{FlxqXC_FlxqXQ_eval_pre}{GEN Q, GEN x, GEN S, GEN T, ulong p,
ulong pi}
\fun{GEN}{FlxqXC_FlxqXQV_eval}{GEN P, GEN V, GEN S, GEN T, ulong p} as
\kbd{FpXC\_FpXQV\_eval}.
\fun{GEN}{FlxqXC_FlxqXQV_eval_pre}{GEN P, GEN V, GEN S, GEN T, ulong p, ulong
pi}
\subsec{\kbd{FlxqXQ}} See \kbd{FpXQXQ} operations.
In this section, \var{pi} is a pseudoinverse of $p$, or $0$ in which case we
assume \kbd{SMALL\_ULONG}$(p)$.
\fun{GEN}{FlxqXQ_mul}{GEN x, GEN y, GEN S, GEN T, ulong p}
\fun{GEN}{FlxqXQ_mul_pre}{GEN x, GEN y, GEN S, GEN T, ulong p, ulong pi}
\fun{GEN}{FlxqXQ_sqr}{GEN x, GEN S, GEN T, ulong p}
\fun{GEN}{FlxqXQ_sqr_pre}{GEN x, GEN S, GEN T, ulong p, ulong pi}
\fun{GEN}{FlxqXQ_inv}{GEN x, GEN S, GEN T, ulong p}
\fun{GEN}{FlxqXQ_inv_pre}{GEN x, GEN S, GEN T, ulong p, ulong pi}
\fun{GEN}{FlxqXQ_invsafe}{GEN x, GEN S, GEN T, ulong p}
\fun{GEN}{FlxqXQ_invsafe_pre}{GEN x, GEN S, GEN T, ulong p, ulong pi}
\fun{GEN}{FlxqXQ_div}{GEN x, GEN y, GEN S, GEN T, ulong p}
\fun{GEN}{FlxqXQ_div_pre}{GEN x, GEN y, GEN S, GEN T, ulong p, ulong pi}
\fun{GEN}{FlxqXQ_pow}{GEN x, GEN n, GEN S, GEN T, ulong p}
\fun{GEN}{FlxqXQ_pow_pre}{GEN x, GEN n, GEN S, GEN T, ulong p, ulong pi}
\fun{GEN}{FlxqXQ_powu}{GEN x, ulong n, GEN S, GEN T, ulong p}
\fun{GEN}{FlxqXQ_powu_pre}{GEN x, ulong n, GEN S, GEN T, ulong p, ulong pi}
\fun{GEN}{FlxqXQ_powers}{GEN x, long n, GEN S, GEN T, ulong p}
\fun{GEN}{FlxqXQ_powers_pre}{GEN x, long n, GEN S, GEN T, ulong p, ulong pi}
\fun{GEN}{FlxqXQ_matrix_pow}{GEN x, long n, long m, GEN S, GEN T, ulong p}
\fun{GEN}{FlxqXQ_autpow}{GEN a, long n, GEN S, GEN T, ulong p}
as \kbd{FpXQXQ\_autpow}
\fun{GEN}{FlxqXQ_autpow_pre}{GEN a, long n, GEN S, GEN T, ulong p, ulong pi}
\fun{GEN}{FlxqXQ_autsum}{GEN a, long n, GEN S, GEN T, ulong p}
as \kbd{FpXQXQ\_autsum}
\fun{GEN}{FlxqXQ_autsum_pre}{GEN a, long n, GEN S, GEN T, ulong p, ulong pi}
\fun{GEN}{FlxqXQ_auttrace}{GEN a, long n, GEN S, GEN T, ulong p}
as \kbd{FpXQXQ\_auttrace}
\fun{GEN}{FlxqXQ_auttrace_pre}{GEN a, long n, GEN S, GEN T, ulong p, ulong pi}
\fun{GEN}{FlxqXQ_halfFrobenius}{GEN A, GEN S, GEN T, ulong p}, as
\kbd{FpXQXQ\_halfFrobenius}
\fun{GEN}{FlxqXQ_minpoly}{GEN x, GEN S, GEN T, ulong p}, as
\kbd{FpXQ\_minpoly}
\fun{GEN}{FlxqXQ_minpoly_pre}{GEN x, GEN S, GEN T, ulong p, ulong pi}
\subsec{\kbd{FlxqXn}} See \kbd{FpXn} operations.
In this section, we assume \var{pi} is the pseudoinverse of $p$, or $0$ in
which case we assume \kbd{SMALL\_ULONG}$(p)$.
\fun{GEN}{FlxXn_red}{GEN a, long n} returns $a$ modulo $X^n$.
\fun{GEN}{FlxqXn_mul}{GEN a, GEN b, long n, GEN T, ulong p}
\fun{GEN}{FlxqXn_mul_pre}{GEN a, GEN b, long n, GEN T, ulong p, ulong pi}
\fun{GEN}{FlxqXn_sqr}{GEN a, long n, GEN T, ulong p}
\fun{GEN}{FlxqXn_sqr_pre}{GEN a, long n, GEN T, ulong p, ulong pi}
\fun{GEN}{FlxqXn_inv}{GEN a, long n, GEN T, ulong p}
\fun{GEN}{FlxqXn_inv_pre}{GEN a, long n, GEN T, ulong p, ulong pi}
\fun{GEN}{FlxqXn_expint}{GEN a, long n, GEN T, ulong p}
\fun{GEN}{FlxqXn_expint_pre}{GEN a, long n, GEN T, ulong p, ulong pi}
\subsec{\kbd{F2x}} An \kbd{F2x}~\kbd{z} is a \typ{VECSMALL}
representing a polynomial over $\F_2[X]$. Specifically
\kbd{z[0]} is the usual codeword, \kbd{z[1] = evalvarn($v$)} for some
variable $v$ and the coefficients are given by the bits of remaining
words by increasing degree.
\subsubsec{Preconditioned reduction}
For faster reduction, the modulus \kbd{T} can be replaced by an extended
modulus (\kbd{FlxT}) in all \kbd{Flxq}-classes functions, and in
\kbd{Flx\_divrem}.
\fun{GEN}{F2x_get_red}{GEN T} returns the extended modulus \kbd{eT}.
To write code that works both with plain and extended moduli, the following
accessors are defined:
\fun{GEN}{get_F2x_mod}{GEN eT} returns the underlying modulus \kbd{T}.
\fun{GEN}{get_F2x_var}{GEN eT} returns the variable number of the modulus.
\fun{GEN}{get_F2x_degree}{GEN eT} returns the degree of the modulus.
\subsubsec{Basic operations}
\fun{ulong}{F2x_coeff}{GEN x, long i} returns the coefficient $i\ge 0$ of $x$.
\fun{void}{F2x_clear}{GEN x, long i} sets the coefficient $i\ge 0$ of $x$ to
$0$.
\fun{void}{F2x_flip}{GEN x, long i} adds $1$ to the coefficient $i\ge 0$ of $x$.
\fun{void}{F2x_set}{GEN x, long i} sets the coefficient $i\ge 0$ of $x$ to $1$.
\fun{GEN}{F2x_copy}{GEN x}
\fun{GEN}{Flx_to_F2x}{GEN x}
\fun{GEN}{Z_to_F2x}{GEN x, long sv}
\fun{GEN}{ZX_to_F2x}{GEN x}
\fun{GEN}{F2v_to_F2x}{GEN x, long sv}
\fun{GEN}{F2x_to_Flx}{GEN x}
\fun{GEN}{F2x_to_F2xX}{GEN x, long sv}
\fun{GEN}{F2x_to_ZX}{GEN x}
\fun{GEN}{pol0_F2x}{long sv} returns a zero \kbd{F2x} in variable $v$.
\fun{GEN}{zero_F2x}{long sv} alias for \kbd{pol0\_F2x}.
\fun{GEN}{pol1_F2x}{long sv} returns the \kbd{F2x} in variable $v$ constant to
$1$.
\fun{GEN}{polx_F2x}{long sv} returns the variable $v$ as degree~1~\kbd{F2x}.
\fun{GEN}{monomial_F2x}{long d, long sv} returns the \kbd{F2x}
$X^d$ in variable $v$.
\fun{GEN}{random_F2x}{long d, long sv} returns a random \kbd{F2x}
in variable \kbd{v}, of degree less than~\kbd{d}.
\fun{long}{F2x_degree}{GEN x} returns the degree of the \kbd{F2x x}. The
degree of $0$ is defined as $-1$.
\fun{GEN}{F2x_recip}{GEN x}
\fun{int}{F2x_equal1}{GEN x}
\fun{int}{F2x_equal}{GEN x, GEN y}
\fun{GEN}{F2x_1_add}{GEN y} returns \kbd{y+1} where \kbd{y} is a \kbd{Flx}.
\fun{GEN}{F2x_add}{GEN x, GEN y}
\fun{GEN}{F2x_mul}{GEN x, GEN y}
\fun{GEN}{F2x_sqr}{GEN x}
\fun{GEN}{F2x_divrem}{GEN x, GEN y, GEN *pr}
\fun{GEN}{F2x_rem}{GEN x, GEN y}
\fun{GEN}{F2x_div}{GEN x, GEN y}
\fun{GEN}{F2x_renormalize}{GEN x, long lx}
\fun{GEN}{F2x_deriv}{GEN x}
\fun{GEN}{F2x_deflate}{GEN x, long d}
\fun{ulong}{F2x_eval}{GEN P, ulong u} returns $P(u)$.
\fun{void}{F2x_shift}{GEN x, long d} as \tet{RgX_shift}
\fun{void}{F2x_even_odd}{GEN P, GEN *pe, GEN *po} as \tet{RgX_even_odd}
\fun{long}{F2x_valrem}{GEN x, GEN *Z}
\fun{GEN}{F2x_extgcd}{GEN a, GEN b, GEN *ptu, GEN *ptv}
\fun{GEN}{F2x_gcd}{GEN a, GEN b}
\fun{GEN}{F2x_halfgcd}{GEN a, GEN b}
\fun{int}{F2x_issquare}{GEN x} returns $1$ if $x$ is a square of a \kbd{F2x}
and $0$ otherwise.
\fun{int}{F2x_is_irred}{GEN f}, as \tet{FpX_is_irred}.
\fun{GEN}{F2x_degfact}{GEN f} as \tet{FpX_degfact}.
\fun{GEN}{F2x_sqrt}{GEN x} returns the squareroot of $x$, assuming $x$ is a
square of a \kbd{F2x}.
\fun{GEN}{F2x_Frobenius}{GEN T}
\fun{GEN}{F2x_matFrobenius}{GEN T}
\fun{GEN}{F2x_factor}{GEN f}
\fun{GEN}{F2x_factor_squarefree}{GEN f}
\fun{GEN}{F2x_ddf}{GEN f}
\fun{GEN}{F2x_Teichmuller}{GEN P, long n}
Return a \kbd{ZX} $Q$ such that $P\equiv Q\pmod{2}$ and
$Q(X^p)=0\pmod{Q,2^n}$.
\subsec{\kbd{F2xq}} See \kbd{FpXQ} operations.
\fun{GEN}{F2xq_mul}{GEN x, GEN y, GEN T}
\fun{GEN}{F2xq_sqr}{GEN x, GEN T}
\fun{GEN}{F2xq_div}{GEN x,GEN y,GEN T}
\fun{GEN}{F2xq_inv}{GEN x, GEN T}
\fun{GEN}{F2xq_invsafe}{GEN x, GEN T}
\fun{GEN}{F2xq_pow}{GEN x, GEN n, GEN T}
\fun{GEN}{F2xq_powu}{GEN x, ulong n, GEN T}
\fun{GEN}{F2xq_pow_init}{GEN x, GEN n, long k, GEN T}
\fun{GEN}{F2xq_pow_table}{GEN R, GEN n, GEN T}
\fun{ulong}{F2xq_trace}{GEN x, GEN T}
\fun{GEN}{F2xq_conjvec}{GEN x, GEN T} returns the vector of conjugates
$[x,x^2,x^{2^2},\ldots,x^{2^{n-1}}]$ where $n$ is the degree of $T$.
\fun{GEN}{F2xq_log}{GEN a, GEN g, GEN ord, GEN T}
\fun{GEN}{F2xq_order}{GEN a, GEN ord, GEN T}
\fun{GEN}{F2xq_Artin_Schreier}{GEN a, GEN T} returns a solution of $x^2+x=a$,
assuming it exists.
\fun{GEN}{F2xq_sqrt}{GEN a, GEN T}
\fun{GEN}{F2xq_sqrt_fast}{GEN a, GEN s, GEN T} assuming that
$s^2 \equiv x\pmod{T(x)}$, computes $b \equiv a(s)\pmod{T}$ so that $b^2=a$.
\fun{GEN}{F2xq_sqrtn}{GEN a, GEN n, GEN T, GEN *zeta}
\fun{GEN}{gener_F2xq}{GEN T, GEN *po}
\fun{GEN}{F2xq_powers}{GEN x, long n, GEN T}
\fun{GEN}{F2xq_matrix_pow}{GEN x, long m, long n, GEN T}
\fun{GEN}{F2x_F2xq_eval}{GEN f, GEN x, GEN T}
\fun{GEN}{F2x_F2xqV_eval}{GEN f, GEN x, GEN T}, see \kbd{FpX\_FpXQV\_eval}.
\fun{GEN}{F2xq_autpow}{GEN a, long n, GEN T} computes $\sigma^n(X)$ assuming
$a=\sigma(X)$ where $\sigma$ is an automorphism of the algebra $\F_2[X]/T(X)$.
\subsec{\kbd{F2xn}} See \kbd{FpXn} operations.
\fun{GEN}{F2xn_red}{GEN a, long n}
\fun{GEN}{F2xn_div}{GEN x, GEN y, long e}
\fun{GEN}{F2xn_inv}{GEN x, long e}
\subsec{\kbd{F2xqV}, \kbd{F2xqM}}. See \kbd{FqV}, \kbd{FqM} operations.
\fun{GEN}{F2xqM_F2xqC_gauss}{GEN a, GEN b, GEN T}
\fun{GEN}{F2xqM_F2xqC_invimage}{GEN a, GEN b, GEN T}
\fun{GEN}{F2xqM_F2xqC_mul}{GEN a, GEN b, GEN T}
\fun{GEN}{F2xqM_deplin}{GEN x, GEN T}
\fun{GEN}{F2xqM_det}{GEN a, GEN T}
\fun{GEN}{F2xqM_gauss}{GEN a, GEN b, GEN T}
\fun{GEN}{F2xqM_image}{GEN x, GEN T}
\fun{GEN}{F2xqM_indexrank}{GEN x, GEN T}
\fun{GEN}{F2xqM_inv}{GEN a, GEN T}
\fun{GEN}{F2xqM_invimage}{GEN a, GEN b, GEN T}
\fun{GEN}{F2xqM_ker}{GEN x, GEN T}
\fun{GEN}{F2xqM_mul}{GEN a, GEN b, GEN T}
\fun{long}{F2xqM_rank}{GEN x, GEN T}
\fun{GEN}{F2xqM_suppl}{GEN x, GEN T}
\fun{GEN}{matid_F2xqM}{long n, GEN T}
\subsec{\kbd{F2xX}}. See \kbd{FpXX} operations.
\fun{GEN}{ZXX_to_F2xX}{GEN x, long v}
\fun{GEN}{FlxX_to_F2xX}{GEN x}
\fun{GEN}{F2xX_to_FlxX}{GEN B}
\fun{GEN}{F2xX_to_F2xC}{GEN B, long N, long sv}
\fun{GEN}{F2xXV_to_F2xM}{GEN B, long N, long sv}
\fun{GEN}{F2xX_to_ZXX}{GEN B}
\fun{GEN}{F2xX_renormalize}{GEN x, long lx}
\fun{long}{F2xY_degreex}{GEN P} return the degree of $P$ with respect to
the secondary variable.
\fun{GEN}{pol1_F2xX}{long v, long sv}
\fun{GEN}{polx_F2xX}{long v, long sv}
\fun{GEN}{F2xX_add}{GEN x, GEN y}
\fun{GEN}{F2xX_F2x_add}{GEN x, GEN y}
\fun{GEN}{F2xX_F2x_mul}{GEN x, GEN y}
\fun{GEN}{F2xX_deriv}{GEN P} returns the derivative of \kbd{P} with respect to
the main variable.
\fun{GEN}{Kronecker_to_F2xqX}{GEN z, GEN T}
\fun{GEN}{F2xX_to_Kronecker}{GEN z, GEN T}
\fun{GEN}{F2xY_F2xq_evalx}{GEN x, GEN y, GEN T} as \kbd{FpXY\_FpXQ\_evalx}.
\fun{GEN}{F2xY_F2xqV_evalx}{GEN x, GEN V, GEN T} as \kbd{FpXY\_FpXQV\_evalx}.
\subsec{\kbd{F2xXV/F2xXC}}. See \kbd{FpXXV} operations.
\fun{GEN}{FlxXC_to_F2xXC}{GEN B}
\fun{GEN}{F2xXC_to_ZXXC}{GEN B}
\subsec{\kbd{F2xqX}}. See \kbd{FlxqX} operations.
\subsubsec{Preconditioned reduction}
For faster reduction, the modulus \kbd{S} can be replaced by an extended
modulus, which is an \kbd{F2xqXT}, in all \kbd{F2xqXQ}-classes
functions, and in \kbd{F2xqX\_rem} and \kbd{F2xqX\_divrem}.
\fun{GEN}{F2xqX_get_red}{GEN S, GEN T} returns the extended modulus
\kbd{eS}.
To write code that works both with plain and extended moduli, the following
accessors are defined:
\fun{GEN}{get_F2xqX_mod}{GEN eS} returns the underlying modulus \kbd{S}.
\fun{GEN}{get_F2xqX_var}{GEN eS} returns the variable number of the modulus.
\fun{GEN}{get_F2xqX_degree}{GEN eS} returns the degree of the modulus.
\subsubsec{basic functions}
\fun{GEN}{random_F2xqX}{long d, long v, GEN T, ulong p} returns a random
\kbd{F2xqX} in variable \kbd{v}, of degree less than~\kbd{d}.
\fun{GEN}{F2xqX_red}{GEN z, GEN T}
\fun{GEN}{F2xqX_normalize}{GEN z, GEN T}
\fun{GEN}{F2xqX_F2xq_mul}{GEN P, GEN U, GEN T}
\fun{GEN}{F2xqX_F2xq_mul_to_monic}{GEN P, GEN U, GEN T}
\fun{GEN}{F2xqX_mul}{GEN x, GEN y, GEN T}
\fun{GEN}{F2xqX_sqr}{GEN x, GEN T}
\fun{GEN}{F2xqX_powu}{GEN x, ulong n, GEN T}
\fun{GEN}{F2xqX_rem}{GEN x, GEN y, GEN T}
\fun{GEN}{F2xqX_div}{GEN x, GEN y, GEN T}
\fun{GEN}{F2xqX_divrem}{GEN x, GEN y, GEN T, GEN *pr}
\fun{GEN}{F2xqXQ_inv}{GEN x, GEN S, GEN T}
\fun{GEN}{F2xqXQ_invsafe}{GEN x, GEN S, GEN T}
\fun{GEN}{F2xqX_invBarrett}{GEN T, GEN Q}
\fun{GEN}{F2xqX_extgcd}{GEN x, GEN y, GEN T, GEN *ptu, GEN *ptv}
\fun{GEN}{F2xqX_gcd}{GEN x, GEN y, GEN T}
\fun{GEN}{F2xqX_halfgcd}{GEN x, GEN y, GEN T}
\fun{GEN}{F2xqX_resultant}{GEN x, GEN y, GEN T}
\fun{GEN}{F2xqX_disc}{GEN x, GEN T}
\fun{long}{F2xqX_ispower}{GEN f, ulong k, GEN T, GEN *pt}
\fun{GEN}{F2xqX_F2xqXQ_eval}{GEN Q, GEN x, GEN S, GEN T} as
\kbd{FpX\_FpXQ\_eval}.
\fun{GEN}{F2xqX_F2xqXQV_eval}{GEN P, GEN V, GEN S, GEN T} as
\kbd{FpX\_FpXQV\_eval}.
\fun{GEN}{F2xqX_roots}{GEN f, GEN T} return the roots of \kbd{f} in
$\F_2[X]/(T)$. Assumes \kbd{T} irreducible in $\F_2[X]$.
\fun{GEN}{F2xqX_factor}{GEN f, GEN T} return the factorization of \kbd{f} over
$\F_2[X]/(T)$. Assumes \kbd{T} irreducible in $\F_2[X]$.
\fun{GEN}{F2xqX_factor_squarefree}{GEN f, GEN T} as
\kbd{FlxqX\_factor\_squarefree}.
\fun{GEN}{F2xqX_ddf}{GEN f, GEN T} as \kbd{FpX\_ddf}.
\fun{GEN}{F2xqX_degfact}{GEN f, GEN T} as \kbd{FpX\_degfact}.
\subsec{\kbd{F2xqXQ}}. See \kbd{FlxqXQ} operations.
\fun{GEN}{FlxqXQ_inv}{GEN x, GEN S, GEN T}
\fun{GEN}{FlxqXQ_invsafe}{GEN x, GEN S, GEN T}
\fun{GEN}{F2xqXQ_mul}{GEN x, GEN y, GEN S, GEN T}
\fun{GEN}{F2xqXQ_sqr}{GEN x, GEN S, GEN T}
\fun{GEN}{F2xqXQ_pow}{GEN x, GEN n, GEN S, GEN T}
\fun{GEN}{F2xqXQ_powers}{GEN x, long n, GEN S, GEN T}
\fun{GEN}{F2xqXQ_autpow}{GEN a, long n, GEN S, GEN T}
as \kbd{FpXQXQ\_autpow}
\fun{GEN}{F2xqXQ_auttrace}{GEN a, long n, GEN S, GEN T}. Let
$\sigma$ be the automorphism defined by $\sigma(X)=a[1]\pmod{T(X)}$ and
$\sigma(Y)=a[2]\pmod{S(X,Y),T(X)}$; returns the vector
$[\sigma^n(X),\sigma^n(Y),b+\sigma(b)+\ldots+\sigma^{n-1}(b)]$
where $b=a[3]$.
\fun{GEN}{F2xqXQV_red}{GEN x, GEN S, GEN T}
\subsec{Functions returning objects with \typ{INTMOD} coefficients}
Those functions are mostly needed for interface reasons: \typ{INTMOD}s should
not be used in library mode since the modular kernel is more flexible and more
efficient, but GP users do not have access to the modular kernel.
We document them for completeness:
\fun{GEN}{Fp_to_mod}{GEN z, GEN p}, \kbd{z} a \typ{INT}. Returns \kbd{z *
Mod(1,p)}, normalized. Hence the returned value is a \typ{INTMOD}.
\fun{GEN}{FpX_to_mod}{GEN z, GEN p}, \kbd{z} a \kbd{ZX}. Returns \kbd{z *
Mod(1,p)}, normalized. Hence the returned value has \typ{INTMOD} coefficients.
\fun{GEN}{FpC_to_mod}{GEN z, GEN p}, \kbd{z} a \kbd{ZC}. Returns \kbd{Col(z) *
Mod(1,p)}, a \typ{COL} with \typ{INTMOD} coefficients.
\fun{GEN}{FpV_to_mod}{GEN z, GEN p}, \kbd{z} a \kbd{ZV}. Returns \kbd{Vec(z) *
Mod(1,p)}, a \typ{VEC} with \typ{INTMOD} coefficients.
\fun{GEN}{FpVV_to_mod}{GEN z, GEN p}, \kbd{z} a \kbd{ZVV}. Returns \kbd{Vec(z) *
Mod(1,p)}, a \typ{VEC} of \typ{VEC} with \typ{INTMOD} coefficients.
\fun{GEN}{FpM_to_mod}{GEN z, GEN p}, \kbd{z} a \kbd{ZM}. Returns \kbd{z *
Mod(1,p)}, with \typ{INTMOD} coefficients.
\fun{GEN}{F2c_to_mod}{GEN x}
\fun{GEN}{F3c_to_mod}{GEN x}
\fun{GEN}{F2m_to_mod}{GEN x}
\fun{GEN}{F3m_to_mod}{GEN x}
\fun{GEN}{Flc_to_mod}{GEN z}
\fun{GEN}{Flm_to_mod}{GEN z}
\fun{GEN}{FqC_to_mod}{GEN z, GEN T, GEN p}
\fun{GEN}{FqM_to_mod}{GEN z, GEN T, GEN p}
\fun{GEN}{FpXC_to_mod}{GEN V, GEN p}
\fun{GEN}{FpXM_to_mod}{GEN V, GEN p}
\fun{GEN}{FpXQC_to_mod}{GEN V, GEN T, GEN p} $V$ being a vector of \kbd{FpXQ},
converts each entry to a \typ{POLMOD} with \typ{INTMOD} coefficients, and return
a \typ{COL}.
\fun{GEN}{FpXQX_to_mod}{GEN P, GEN T, GEN p}
$P$ being a \kbd{FpXQX}, converts each coefficient to a \typ{POLMOD} with
\typ{INTMOD} coefficients.
\fun{GEN}{FqX_to_mod}{GEN P, GEN T, GEN p} same but allow
$\kbd{T} = \kbd{NULL}$.
\fun{GEN}{FqXC_to_mod}{GEN P, GEN T, GEN p}
\fun{GEN}{FqXM_to_mod}{GEN P, GEN T, GEN p}
\fun{GEN}{QXQ_to_mod_shallow}{GEN x, GEN T} $x$ a \kbd{QXQ}, which is
a lifted representative of elements of $\Q[X]/(T)$ (number field elements
in most applications) and $T$ is in $\Z[X]$. Convert it to a \typ{POLMOD}
modulo $T$; no reduction mod $T$ is attempted: the representatives should be
already reduced. Shallow function.
\fun{GEN}{QXQV_to_mod}{GEN V, GEN T} $V$ a vector of \kbd{QXQ}, which
are lifted representatives of elements of $\Q[X]/(T)$ (number field elements
in most applications) and $T$ is in $\Z[X]$. Return a vector where all
nonrational entries are converted to \typ{POLMOD} modulo $T$; no reduction
mod $T$ is attempted: the representatives should be already reduced. Used to
normalize the output of \kbd{nfroots}.
\fun{GEN}{QXQX_to_mod_shallow}{GEN P, GEN T} $P$ a polynomial with \kbd{QXQ}
coefficients; replace them by \kbd{mkpolmod(.,T)}. Shallow function.
\fun{GEN}{QXQC_to_mod_shallow}{GEN V, GEN T} $V$ a vector with \kbd{QXQ}
coefficients; replace them by \kbd{mkpolmod(.,T)}. Shallow function.
\fun{GEN}{QXQM_to_mod_shallow}{GEN M, GEN T} $M$ a matrix with \kbd{QXQ}
coefficients; replace them by \kbd{mkpolmod(.,T)}. Shallow function.
\fun{GEN}{QXQXV_to_mod}{GEN V, GEN T} $V$ a vector of polynomials whose
coefficients are \kbd{QXQ}. Analogous to \kbd{QXQV\_to\_mod}.
Used to normalize the output of \kbd{nffactor}.
The following functions are obsolete and should not be used: they receive a
polynomial with arbitrary coefficients, apply a conversion function to map
them to a finite field, a function from the modular kernel, then
\kbd{*\_to\_mod}:
\fun{GEN}{rootmod}{GEN f, GEN p}, applies \kbd{FpX\_roots}.
\fun{GEN}{rootmod2}{GEN f, GEN p}, (now) identical to \kbd{rootmod}.
\fun{GEN}{rootmod0}{GEN f, GEN p, long flag}, (now) identical to
\kbd{rootmod}; ignores \fl.
\fun{GEN}{factmod}{GEN f, GEN p} applies \kbd{*\_factor}.
\fun{GEN}{simplefactmod}{GEN f, GEN p} applies \kbd{*\_degfact}.
\subsec{Slow Chinese remainder theorem over $\Z$}
The routines in this section have quadratic time complexity with respect to
the input size; see the routines in the next two sections for quasi-linear
time variants.
\fun{GEN}{Z_chinese}{GEN a, GEN b, GEN A, GEN B} returns the integer
in $[0, \lcm(A,B)[$ congruent to $a$ mod $A$ and $b$ mod $B$, assuming it
exists; in other words, that $a$ and $b$ are congruent mod $\gcd(A,B)$.
\fun{GEN}{Z_chinese_all}{GEN a, GEN b, GEN A, GEN B, GEN *pC} as
\kbd{Z\_chinese}, setting \kbd{*pC} to the lcm of $A$ and $B$.
\fun{GEN}{Z_chinese_coprime}{GEN a, GEN b, GEN A, GEN B, GEN C}, as
\kbd{Z\_chinese}, assuming that $\gcd(A,B) = 1$ and that $C = \lcm(A,B) = AB$.
\fun{ulong}{u_chinese_coprime}{ulong a, ulong b, ulong A, ulong B, ulong C}, as
\kbd{Z\_chinese\_coprime} for \kbd{ulong} inputs and output.
\fun{void}{Z_chinese_pre}{GEN A, GEN B, GEN *pC, GEN *pU, GEN *pd}
initializes chinese remainder computations modulo $A$ and $B$. Sets
\kbd{*pC} to $\lcm(A,B)$, \kbd{*pd} to $\gcd(A,B)$,
\kbd{*pU} to an integer congruent to $0$ mod $(A/d)$ and $1$ mod $(B/d)$.
It is allowed to set \kbd{pd = NULL}, in which case, $d$ is still
computed, but not saved.
\fun{GEN}{Z_chinese_post}{GEN a, GEN b, GEN C, GEN U, GEN d} returns
the solution to the chinese remainder problem $x$ congruent
to $a$ mod $A$ and $b$ mod $B$, where $C, U, d$ were set in
\kbd{Z\_chinese\_pre}. If $d$ is \kbd{NULL}, assume the problem has a
solution. Otherwise, return \kbd{NULL} if it has no solution.
\medskip
The following pair of functions is used in homomorphic imaging schemes,
when reconstructing an integer from its images modulo pairwise coprime
integers. The idea is as follows: we want to discover an integer $H$ which
satisfies $|H| < B$ for some known bound $B$; we are given pairs $(H_p, p)$
with $H$ congruent to $H_p$ mod $p$ and all $p$ pairwise coprime.
Given \kbd{H} congruent to $H_p$ modulo a number of $p$, whose product is
$q$, and a new pair $(\kbd{Hp}, \kbd{p})$, \kbd{p} coprime to $q$, the
following incremental functions use the chinese remainder theorem (CRT) to
find a new \kbd{H}, congruent to the preceding one modulo $q$, but also to
\kbd{Hp} modulo \kbd{p}. It is defined uniquely modulo $qp$, and we choose
the centered representative. When $P$ is larger than $2B$, we have $\kbd{H} =
H$, but of course, the value of \kbd{H} may stabilize sooner. In many
applications it is possible to directly check that such a partial result is
correct.
\fun{GEN}{Z_init_CRT}{ulong Hp, ulong p} given a \kbd{Fl} \kbd{Hp} in
$[0, p-1]$, returns the centered representative \kbd{H} congruent to \kbd{Hp}
modulo \kbd{p}.
\fun{int}{Z_incremental_CRT}{GEN *H, ulong Hp, GEN *q, ulong p}
given a \typ{INT} \kbd{*H}, centered modulo \kbd{*q}, a new pair $(\kbd{Hp},
\kbd{p})$ with \kbd{p} coprime to \kbd{q}, this function updates \kbd{*H} so
that it also becomes congruent to $(\kbd{Hp}, \kbd{p})$, and \kbd{*q} to the
product$\kbd{qp} = \kbd{p} \cdot \kbd{*q}$. It returns $1$ if the new value
is equal to the old one, and $0$ otherwise.
\fun{GEN}{chinese1_coprime_Z}{GEN v} an alternative divide-and-conquer
implementation: $v$ is a vector of \typ{INTMOD} with pairwise coprime moduli.
Return the \typ{INTMOD} solving the corresponding chinese remainder problem.
This is a streamlined version of
\fun{GEN}{chinese1}{GEN v}, which solves a general chinese remainder problem
(not necessarily over $\Z$, moduli not assumed coprime).
As above, for $H$ a \kbd{ZM}: we assume that $H$ and all \kbd{Hp} have
dimension $> 0$. The original \kbd{*H} is destroyed.
\fun{GEN}{ZM_init_CRT}{GEN Hp, ulong p}
\fun{int}{ZM_incremental_CRT}{GEN *H, GEN Hp, GEN *q, ulong p}
As above for $H$ a \kbd{ZX}: note that the degree may increase or decrease.
The original \kbd{*H} is destroyed.
\fun{GEN}{ZX_init_CRT}{GEN Hp, ulong p, long v}
\fun{int}{ZX_incremental_CRT}{GEN *H, GEN Hp, GEN *q, ulong p}
As above, for $H$ a matrix whose coefficient are \kbd{ZX}.
The original \kbd{*H} is destroyed.
The entries of $H$ are not normalized, use \kbd{ZX\_renormalize}
for this.
\fun{GEN}{ZXM_init_CRT}{GEN Hp, long deg, ulong p} where \kbd{deg}
is the maximal degree of all the \kbd{Hp}
\fun{int}{ZXM_incremental_CRT}{GEN *H, GEN Hp, GEN *q, ulong p}
\subsec{Fast remainders}
The routines in these section are asymptotically fast (quasi-linear time in
the input size).
\fun{GEN}{Z_ZV_mod}{GEN A, GEN P} given a \typ{INT} $A$ and a vector $P$ of
positive pairwise coprime integers of length $n\ge 1$, return a vector $B$ of
the same length such that $B[i] = A\pmod{P[i]}$ and $0\leq B[i] < P[i]$ for
all $1\leq i\leq n$. The vector $P$ may be a \typ{VEC} or a \typ{VECSMALL}
(treated as \kbd{ulong}s) and $B$ has the same type as $P$.
\fun{GEN}{Z_nv_mod}{GEN A, GEN P} given a \typ{INT} $A$ and a \typ{VECSMALL}
$P$ of positive pairwise coprime integers of length $n\ge 1$, return a
\typ{VECSMALL} $B$ of the same length such that $B[i]=A\pmod{P[i]}$ and
$0\leq B[i] < P[i]$ for all $1\leq i\leq n$. The entries of $P$ and $B$ are
treated as \kbd{ulong}s.
The following low level functions allow precomputations:
\fun{GEN}{ZV_producttree}{GEN P} where $P$ is a vector of integers (or
\typ{VECSMALL}) of length $n\ge 1$, return the vector of \typ{VEC}s
$[f(P),f^2(P),\ldots,f^k(P)]$ where $f$ is the transformation
$[p_1,p_2,\ldots,p_m] \mapsto [p_1\*p_2,p_3\*p_4,\ldots,p_{m-1}\*p_m]$ if $m$
is even and $[p_1\*p_2,p_3\*p_4,\ldots,p_{m-2}\*p_{m-1},p_m]$ if $m$ is odd,
and $k = O(\log m)$ is minimal so that $f^k(P)$ has length $1$; in other
words, $f^k(P) = [p_1\*p_2\*\ldots\*p_m]$.
\fun{GEN}{Z_ZV_mod_tree}{GEN A, GEN P, GEN T}
as \kbd{Z\_ZV\_mod} where $T$ is the tree \kbd{ZV\_producttree(P)}.
\fun{GEN}{ZV_nv_mod_tree}{GEN A, GEN P, GEN T} $A$ being a \kbd{ZV}
and $P$ a \typ{VECSMALL} of length $n\ge 1$, the elements of $P$ being
pairwise coprime, return the vector of \kbd{Flv}
$[A \pmod{P[1]},\ldots,A \pmod{P[n]}]$,
where $T$ is the tree \kbd{ZV\_producttree(P)}.
\fun{GEN}{ZM_nv_mod_tree}{GEN A, GEN P, GEN T} $A$ being a \kbd{ZM}
and $P$ a \typ{VECSMALL} of length $n\ge 1$, the elements of $P$ being
pairwise coprime, return the vector of \kbd{Flm}
$[A \pmod{P[1]},\ldots,A \pmod{P[n]}]$,
where $T$ is the tree \kbd{ZV\_producttree(P)}.
\fun{GEN}{ZX_nv_mod_tree}{GEN A, GEN P, GEN T} $A$ being a \kbd{ZX}
and $P$ a \typ{VECSMALL} of length $n\ge 1$, the elements of $P$ being
pairwise coprime, return the vector of \kbd{Flx} polynomials
$[A \pmod{P[1]},\ldots,A \pmod{P[n]}]$,
where $T$ is the tree \kbd{ZV\_producttree(P)}.
\fun{GEN}{ZXC_nv_mod_tree}{GEN A, GEN P, GEN T} $A$ being a \kbd{ZXC}
and $P$ a \typ{VECSMALL} of length $n\ge 1$, the elements of $P$ being
pairwise coprime, return the vector of \kbd{FlxC}
$[A \pmod{P[1]},\ldots,A \pmod{P[n]}]$,
where $T$ is the tree \kbd{ZV\_producttree(P)}.
\fun{GEN}{ZXM_nv_mod_tree}{GEN A, GEN P, GEN T} $A$ being a \kbd{ZXM}
and $P$ a \typ{VECSMALL} of length $n\ge 1$, the elements of $P$ being
pairwise coprime, return the vector of \kbd{FlxM}
$[A \pmod{P[1]},\ldots,A \pmod{P[n]}]$,
where $T$ is the tree \kbd{ZV\_producttree(P)}.
\fun{GEN}{ZXX_nv_mod_tree}{GEN A, GEN P, GEN T, long v} $A$ being a \kbd{ZXX},
and $P$ a \typ{VECSMALL} of length $n\ge 1$, the elements of $P$ being
pairwise coprime, return the vector of \kbd{FlxX}
$[A \pmod{P[1]},\ldots,A \pmod{P[n]}]$,
where $T$ is assumed to be the tree created by \kbd{ZV\_producttree(P)}.
\medskip
\subsec{Fast Chinese remainder theorem over $\Z$}
The routines in these section are asymptotically fast (quasi-linear time in
the input size) and should be used whenever the moduli are known from
the start.
The simplest function is
\fun{GEN}{ZV_chinese}{GEN A, GEN P, GEN *pM}
let $P$ be a vector of positive pairwise coprime integers, let $A$ be a
vector of integers of the same length $n\ge 1$ such that $0 \leq A[i] < P[i]$
for all $i$, and let $M$ be the product of the elements of $P$. Returns the
integer in $[0, M[$ congruent to $A[i]$ mod $P[i]$ for all $1\leq i\leq n$.
If \kbd{pM} is not \kbd{NULL}, set \kbd{*pM} to $M$. We also allow
\typ{VECSMALL}s for $A$ and $P$ (seen as vectors of unsigned integers).
\fun{GEN}{ZV_chinese_center}{GEN A, GEN P, GEN *pM}
As \kbd{ZV\_chinese} but return integers in $[-M/2, M/2[$ instead.
The following functions allow to solve many Chinese remainder problems
simultaneously, for a given set of moduli:
\fun{GEN}{nxV_chinese_center}{GEN A, GEN P, GEN *pt_mod}
where $A$ is a vector of \kbd{nx}
and $P$ a \typ{VECSMALL} of the same length $n\ge 1$, the elements of $P$
being pairwise coprime, and $M$ being the product of the elements of $P$,
returns the \typ{POL} whose entries are integers in $[-M/2, M/2[$ congruent to $A[i]$
mod $P[i]$ for all $1\leq i\leq n$.
If \kbd{pt\_mod} is not \kbd{NULL}, set \kbd{*pt\_mod} to $M$.
\fun{GEN}{ncV_chinese_center}{GEN A, GEN P, GEN *pM} where $A$ is a
vector of \kbd{VECSMALL}s (seen as vectors of unsigned integers) and $P$ a
\typ{VECSMALL} of the same length $n\ge 1$, the elements of $P$ being
pairwise coprime, and $M$ being the product of the elements of $P$, returns
the \typ{COL} whose entries are integers in $[-M/2, M/2[$ congruent to $A[i]$
mod $P[i]$ for all $1\leq i\leq n$. If \kbd{pM} is not \kbd{NULL}, set
\kbd{*pt\_mod} to $M$.
\fun{GEN}{nmV_chinese_center}{GEN A, GEN P, GEN *pM} where $A$ is a
vector of \kbd{MATSMALL}s (seen as matrices of unsigned integers) and $P$ a
\typ{VECSMALL} of the same length $n\ge 1$, the elements of $P$ being
pairwise coprime, and $M$ being the product of the elements of $P$, returns
the matrix whose entries are integers in $[-M/2, M/2[$ congruent to $A[i]$
mod $P[i]$ for all $1\leq i\leq n$. If \kbd{pM} is not \kbd{NULL}, set
\kbd{*pM} to $M$. N.B.: this function uses the parallel GP interface.
\fun{GEN}{nxCV_chinese_center}{GEN A, GEN P, GEN *pM} where $A$ is a
vector of \kbd{nxC}s and $P$ a
\typ{VECSMALL} of the same length $n\ge 1$, the elements of $P$ being
pairwise coprime, and $M$ being the product of the elements of $P$, returns
the \typ{COL} whose entries are integers in $[-M/2, M/2[$ congruent to $A[i]$
mod $P[i]$ for all $1\leq i\leq n$. If \kbd{pM} is not \kbd{NULL}, set
\kbd{*pt\_mod} to $M$.
\fun{GEN}{nxMV_chinese_center}{GEN A, GEN P, GEN *pM} where $A$ is a
vector of \kbd{nxM}s and $P$ a
\typ{VECSMALL} of the same length $n\ge 1$, the elements of $P$ being
pairwise coprime, and $M$ being the product of the elements of $P$, returns
the matrix whose entries are integers in $[-M/2, M/2[$ congruent to $A[i]$
mod $P[i]$ for all $1\leq i\leq n$. If \kbd{pM} is not \kbd{NULL}, set
\kbd{*pM} to $M$. N.B.: this function uses the parallel GP interface.
The other routines allow for various precomputations :
\fun{GEN}{ZV_chinesetree}{GEN P, GEN T} given $P$ a vector of integers
(or \typ{VECSMALL}) and a product tree $T$ from \tet{ZV_producttree}$(P)$
for the same $P$, return a ``chinese remainder tree'' $R$, preconditionning
the solution of Chinese remainder problems modulo the $P[i]$.
\fun{GEN}{ZV_chinese_tree}{GEN A, GEN P, GEN T, GEN R}
return \kbd{ZV\_chinese}$(A,P,\kbd{NULL})$, where $T$ is created by
\kbd{ZV\_producttree}$(P)$ and $R$ by \kbd{ZV\_chinesetree}$(P,T)$.
\fun{GEN}{ncV_chinese_center_tree}{GEN A, GEN P, GEN T, GEN R}
as \kbd{ncV\_chinese\_center} where $T$ is assumed to be the tree created by
\kbd{ZV\_producttree(P)} and $R$ by \kbd{ZV\_chinesetree}$(P,T)$.
\fun{GEN}{nmV_chinese_center_tree}{GEN A, GEN P, GEN T, GEN R}
as \kbd{nmV\_chinese\_center} where $T$ is assumed to be the tree created by
\kbd{ZV\_producttree(P)} and $R$ by \kbd{ZV\_chinesetree}$(P,T)$.
\fun{GEN}{nxV_chinese_center_tree}{GEN A, GEN P, GEN T, GEN R}
as \kbd{nxV\_chinese\_center} where $T$ is assumed to be the tree created by
\kbd{ZV\_producttree(P)} and $R$ by \kbd{ZV\_chinesetree}$(P,T)$.
\fun{GEN}{nxCV_chinese_center_tree}{GEN A, GEN P, GEN T, GEN R}
as \kbd{nxCV\_chinese\_center} where $T$ is assumed to be the tree created by
\kbd{ZV\_producttree(P)} and $R$ by \kbd{ZV\_chinesetree}$(P,T)$.
\subsec{Rational reconstruction}
\fun{int}{Fp_ratlift}{GEN x, GEN m, GEN amax, GEN bmax, GEN *a, GEN *b}.
Assuming that $0 \leq x < m$, $\kbd{amax} \geq 0$, and
$\kbd{bmax} > 0$ are \typ{INT}s, and that $2 \kbd{amax} \kbd{bmax} < m$,
attempts to recognize $x$ as a rational $a/b$, i.e. to find \typ{INT}s $a$
and $b$ such that
\item $a \equiv b x$ modulo $m$,
\item $|a| \leq \kbd{amax}$, $0 < b \leq \kbd{bmax}$,
\item $\gcd(m,b) = \gcd(a,b)$.
\noindent If unsuccessful, the routine returns $0$ and leaves $a$, $b$
unchanged; otherwise it returns $1$ and sets $a$ and $b$.
In almost all applications, we actually know that a solution exists, as well
as a nonzero multiple $B$ of $b$, and $m = p^\ell$ is a prime power, for a
prime $p$ chosen coprime to $B$ hence to $b$. Under the single assumption
$\gcd(m,b) = 1$, if a solution $a,b$ exists satisfying the three conditions
above, then it is unique.
\fun{GEN}{FpM_ratlift}{GEN M, GEN m, GEN amax, GEN bmax, GEN denom}
given an \kbd{FpM} modulo $m$ with reduced or \kbd{Fp\_center}-ed entries,
reconstructs a matrix with rational coefficients by applying \kbd{Fp\_ratlift}
to all entries. Assume that all preconditions for \kbd{Fp\_ratlift} are
satisfied, as well $\gcd(m,b) = 1$ (so that the solution is unique if it
exists). Return \kbd{NULL} if the reconstruction fails, and the rational
matrix otherwise. If \kbd{denom} is not \kbd{NULL} check further that all
denominators divide \kbd{denom}.
The function is not stack clean if one of the coefficients of $M$ is negative
(centered residues), but still suitable for \kbd{gerepileupto}.
\fun{GEN}{FpX_ratlift}{GEN P, GEN m, GEN amax, GEN bmax, GEN denom} as
\kbd{FpM\_ratlift}, where $P$ is an \kbd{FpX}.
\fun{GEN}{FpC_ratlift}{GEN P, GEN m, GEN amax, GEN bmax, GEN denom} as
\kbd{FpM\_ratlift}, where $P$ is an \kbd{FpC}.
\subsec{Zp}
\fun{GEN}{Zp_invlift}{GEN b, GEN a, GEN p, long e} let
$p$ be a prime \typ{INT}, $a$ be a \typ{INT} and
$b$ a \typ{INT} such that $a\*b \equiv 1 \mod p$.
Returns an \typ{INT} $A$ such that $A \equiv a \pmod{p}$ and
$A\*b \equiv 1 \mod p^e$.
\fun{GEN}{Zp_inv}{GEN b, GEN p, long e} let
$p$ be a prime \typ{INT} and $b$ be a \typ{INT}
Returns an \typ{INT} $A$ such that $A\*b \equiv 1 \mod p^e$.
\fun{GEN}{Zp_div}{GEN a, GEN b, GEN p, long e} let
$p$ be a prime \typ{INT} and $a$ and $b$ be a \typ{INT}
Returns an \typ{INT} $c$ such that $c\*b \equiv a \mod p^e$.
\fun{GEN}{Zp_sqrt}{GEN b, GEN p, long e} $b$ and $p$ being \typ{INT}s, with $p$
a prime (possibly $2$), returns a \typ{INT} $a$ such that $a^2 \equiv b \mod
p^e$.
\fun{GEN}{Z2_sqrt}{GEN b, long e} $b$ being a \typ{INT}s
returns a \typ{INT} $a$ such that $a^2 \equiv b \mod 2^e$.
\fun{GEN}{Zp_sqrtlift}{GEN b, GEN a, GEN p, long e} let
$a,b,p$ be \typ{INT}s, with $p > 2$, such that $a^2\equiv b\mod p$.
Returns a \typ{INT} $A$ such that $A^2 \equiv b \mod p^e$. Special case
of \tet{Zp_sqrtnlift}.
\fun{GEN}{Zp_sqrtnlift}{GEN b, GEN n, GEN a, GEN p, long e} let
$a,b,n,p$ be \typ{INT}s, with $n,p > 1$, and $p$ coprime to $n$,
such that $a^n \equiv b \mod p$. Returns a \typ{INT} $A$ such that
$A^n \equiv b \mod p^e$. Special case of \tet{ZpX_liftroot}.
\fun{GEN}{Zp_teichmuller}{GEN x, GEN p, long e, GEN pe} for $p$ an odd prime,
$x$ a \typ{INT} coprime to $p$, and $pe = p^e$, returns the $(p-1)$-th root of
$1$ congruent to $x$ modulo $p$, modulo $p^e$. For convenience, $p = 2$ is
also allowed and we return $1$ ($x$ is $1$ mod $4$) or $2^e - 1$ ($x$ is $3$
mod $4$).
\fun{GEN}{teichmullerinit}{long p, long n} returns the values of
\tet{Zp_teichmuller} at all $x = 1, \dots, p-1$.
\fun{GEN}{Zp_exp}{GEN z, GEN p, ulong e} given a \typ{INT} $z$ (preferably
reduced mod $p^e$), return $\exp_p(a)$ mod $p^e$ (\typ{INT}).
\fun{GEN}{Zp_log}{GEN z, GEN p, ulong e} given a \typ{INT} $z$ (preferably
reduced mod $p^e$), such that $a \equiv 1 \pmod{p}$, return
$\log_p(a)$ mod $p^e$ (\typ{INT}).
\subsec{ZpM}
\fun{GEN}{ZpM_invlift}{GEN M, GEN Np, GEN p, long e} let
$p$ be a prime \typ{INT}, $Np$ be a \kbd{FpM} (modulo $p$) and
$M$ a \kbd{ZpM} such that $M\*Np \equiv 1 \mod p$.
Returns an \kbd{ZpM} $N$ such that $N \equiv Np \pmod{p}$ and
$M\*N \equiv 1 \mod p^e$.
\subsec{ZpX}
\fun{GEN}{ZpX_roots}{GEN f, GEN p, long e} $f$ a \kbd{ZX} with leading
term prime to $p$, and without multiple roots mod $p$. Return a vector
of \typ{INT}s which are the roots of $f$ mod $p^e$.
\fun{GEN}{ZpX_liftroot}{GEN f, GEN a, GEN p, long e} $f$ a \kbd{ZX} with
leading term prime to $p$, and $a$ a root mod $p$ such that
$v_p(f'(a))=0$. Return a \typ{INT} which is the root of $f$ mod $p^e$
congruent to $a$ mod $p$.
\fun{GEN}{ZX_Zp_root}{GEN f, GEN a, GEN p, long e} same as \tet{ZpX_liftroot}
without the assumption $v_p(f'(a)) = 0$. Return a \typ{VEC} of \typ{INT}s,
which are the $p$-adic roots of $f$ congruent to $a$ mod $p$ (given modulo
$p^e$). Assume that $0 \leq a < p$.
\fun{GEN}{ZpX_liftroots}{GEN f, GEN S, GEN p, long e} $f$ a \kbd{ZX} with
leading term prime to $p$, and $S$ a vector of simple roots mod $p$. Return a
vector of \typ{INT}s which are the root of $f$ mod $p^e$ congruent to the
$S[i]$ mod $p$.
\fun{GEN}{ZpX_liftfact}{GEN A, GEN B, GEN pe, GEN p, long e} is
the routine underlying \tet{polhensellift}. Here, $p$ is prime
defines a finite field $\F_p$. $A$ is a polynomial in
$\Z[X]$, whose leading coefficient is nonzero in $\F_q$. $B$ is a vector of
monic \kbd{FpX}, pairwise coprime in $\F_p[X]$, whose product is congruent to
$A/\text{lc}(A)$ in $\F_p[X]$. Lifts the elements of $B$ mod $\kbd{pe} = p^e$.
\fun{GEN}{ZpX_Frobenius}{GEN T, GEN p, ulong e} returns the $p$-adic lift
of the Frobenius automorphism of $\F_p[X]/(T)$ to precision $e$.
\fun{long}{ZpX_disc_val}{GEN f, GEN p} returns the valuation at $p$ of the
discriminant of $f$. Assume that $f$ is a monic \emph{separable} \kbd{ZX}
and that $p$ is a prime number. Proceeds by dynamically increasing the
$p$-adic accuracy; infinite loop if the discriminant of $f$ is
$0$.
\fun{long}{ZpX_resultant_val}{GEN f, GEN g, GEN p, long M} returns the
valuation at $p$ of $\text{Res}(f,g)$. Assume $f,g$ are both \kbd{ZX},
and that $p$ is a prime number coprime to the leading coefficient of $f$.
Proceeds by dynamically increasing the $p$-adic accuracy.
To avoid an infinite loop when the resultant is $0$, we return $M$ if
the Sylvester matrix mod $p^M$ still does not have maximal rank.
\fun{GEN}{ZpX_gcd}{GEN f,GEN g, GEN p, GEN pm} $f$ a monic \kbd{ZX},
$g$ a \kbd{ZX}, $\kbd{pm} = p^m$ a prime power. There is a unique integer
$r\geq 0$ and a monic $h\in \Q_p[X]$ such that
$$p^rh\Z_p[X] + p^m\Z_p[X] = f\Z_p[X] + g\Z_p[X] + p^m\Z_p[X].$$
Return the $0$ polynomial if $r\geq m$ and a monic $h\in\Z[1/p][X]$ otherwise
(whose valuation at $p$ is $> -m$).
\fun{GEN}{ZpX_reduced_resultant}{GEN f, GEN g, GEN p, GEN pm} $f$ a monic
\kbd{ZX}, $g$ a \kbd{ZX}, $\kbd{pm} = p^m$ a prime power. The $p$-adic
\emph{reduced resultant}\varsidx{resultant (reduced)} of $f$ and $g$ is
$0$ if $f$, $g$ not coprime in $\Z_p[X]$, and otherwise the generator of the
form $p^d$ of
$$ (f\Z_p[X] + g\Z_p[X])\cap \Z_p. $$
Return the reduced resultant modulo $p^m$.
\fun{GEN}{ZpX_reduced_resultant_fast}{GEN f, GEN g, GEN p, long M} $f$
a monic \kbd{ZX}, $g$ a \kbd{ZX}, $p$ a prime. Returns
the $p$-adic reduced resultant of $f$ and $g$ modulo $p^M$. This function
computes resultants for a sequence of increasing $p$-adic accuracies
(up to $M$ $p$-adic digits), returning as soon as it obtains a nonzero
result. It is very inefficient when the resultant is $0$, but otherwise
usually more efficient than computations using a priori bounds.
\fun{GEN}{ZpX_monic_factor}{GEN f, GEN p, long M} $f$ a monic
\kbd{ZX}, $p$ a prime, return the $p$-adic factorization of $f$, modulo
$p^M$. This is the underlying low-level recursive function behind
\kbd{factorpadic} (using a combination of Round 4 factorization and Hensel
lifting); the factors are not sorted and the function is not
\kbd{gerepile}-clean.
\fun{GEN}{ZpX_primedec}{GEN T, GEN p} $T$ a monic separable \kbd{ZX}, $p$ a
prime, return as a factorization matrix the shape of the prime ideal
decomposition of $(p)$ in $\Q[X]/(T)$: the first column contains inertia
degrees, the second columns contains ramification degrees.
\subsec{ZpXQ}
\fun{GEN}{ZpXQ_invlift}{GEN b, GEN a, GEN T, GEN p, long e} let
$p$ be a prime \typ{INT}, $a$ be a \kbd{FpXQ} (modulo $(p, T)$) and
$b$ a \kbd{ZpXQ} such that $a\*b \equiv 1 \mod (p, T)$.
Returns an \kbd{ZpXQ} $A$ such that $A \equiv a \pmod{p}$ and
$A\*b \equiv 1 \mod (p^e, T)$.
\fun{GEN}{ZpXQ_inv}{GEN b, GEN T, GEN p, long e} let
$p$ be a prime \typ{INT} and $b$ be a \kbd{FpXQ} (modulo $T, p^e$).
Returns an \kbd{FpXQ} $A$ such that $A\*b \equiv 1 \mod (p^e, T)$.
\fun{GEN}{ZpXQ_div}{GEN a, GEN b, GEN T, GEN q, GEN p, long e} let
$p$ be a prime \typ{INT} and $a$ and $b$ be a \kbd{FpXQ} (modulo $T, p^e$).
Returns an \kbd{FpXQ} $c$ such that $c\*b \equiv a \mod (p^e, T)$.
The parameter $q$ must be equal to $p^e$.
\fun{GEN}{ZpXQ_sqrtnlift}{GEN b, GEN n, GEN a, GEN T, GEN p, long e} let
$n,p$ be \typ{INT}s, with $n,p > 1$ and $p$ coprime to $n$, and $a,b$
be \kbd{FpXQ}s (modulo $T$) such that $a^n \equiv b \mod (p,T)$.
Returns an \kbd{Fq} $A$ such that $A^n \equiv b \mod (p^e, T)$.
\fun{GEN}{ZpXQ_sqrt}{GEN b, GEN T, GEN p, long e} let
$p$ being a odd prime and $b$ be a \kbd{FpXQ} (modulo $T, p^e$),
returns $a$ such that $a^2 \equiv b \mod (p^e, T)$.
\fun{GEN}{ZpX_ZpXQ_liftroot}{GEN f, GEN a, GEN T, GEN p, long e}
as \tet{ZpXQX_liftroot}, but $f$ is a polynomial in $\Z[X]$.
\fun{GEN}{ZpX_ZpXQ_liftroot_ea}{GEN f, GEN a, GEN T, GEN p, long e,
void *E, GEN early(void *E, GEN x, GEN q)}
as \tet{ZpX_ZpXQ_liftroot} with early abort: the function \kbd{early(E,x,q)}
will be called with $x$ is a root of $f$ modulo $q=p^n$ for some $n$. If
\kbd{early} returns a non-\kbd{NULL} value $z$, the function returns $z$
immediately.
\fun{GEN}{ZpXQ_log}{GEN a, GEN T, GEN p, long e} $T$ being a \kbd{ZpX}
irreducible modulo $p$, return the logarithm of $a$ in $\Z_p[X]/(T)$ to
precision $e$, assuming that $a\equiv 1 \pmod{p\Z_p[X]}$ if $p$ odd or
$a\equiv 1 \pmod{4\Z_2[X]}$ if $p=2$.
\subsec{Zq}
\fun{GEN}{Zq_sqrtnlift}{GEN b, GEN n, GEN a, GEN T, GEN p, long e}
\subsec{ZpXQM}
\fun{GEN}{ZpXQM_prodFrobenius}{GEN M, GEN T, GEN p, long e}
returns the product of matrices $M\*\sigma(M)\*\sigma^2(M)\ldots\sigma^{n-1}(M)$
to precision $e$ where $\sigma$ is the lift of the Frobenius automorphism
over $\Z_p[X]/(T)$ and $n$ is the degree of $T$.
\subsec{ZpXQX}
\fun{GEN}{ZpXQX_liftfact}{GEN A, GEN B, GEN T, GEN pe, GEN p, long e} is the
routine underlying \tet{polhensellift}. Here, $p$ is prime, $T(Y)$ defines a
finite field $\F_q$. $A$ is a polynomial in $\Z[X,Y]$, whose leading
coefficient is nonzero in $\F_q$. $B$ is a vector of monic or \kbd{FqX},
pairwise coprime in $\F_q[X]$, whose product is congruent to $A/\text{lc}(A)$
in $\F_q[X]$. Lifts the elements of $B$ mod $\kbd{pe} = p^e$, such that the
congruence now holds mod $(T,p^e)$.
\fun{GEN}{ZpXQX_liftroot}{GEN f, GEN a, GEN T, GEN p, long e} as
\tet{ZpX_liftroot}, but $f$ is now a polynomial in $\Z[X,Y]$ and lift the
root $a$ in the unramified extension of $\Q_p$ with residue field $\F_p[Y]/(T)$,
assuming $v_p(f(a))>0$ and $v_p(f'(a))=0$.
\fun{GEN}{ZpXQX_liftroot_vald}{GEN f, GEN a, long v, GEN T, GEN p, long e}
returns the foots of $f$ as \tet{ZpXQX_liftroot}, where $v$ is the valuation
of the content of $f'$ and it is required that $v_p(f(a))>v$ and
$v_p(f'(a))=v$.
\fun{GEN}{ZpXQX_roots}{GEN F, GEN T, GEN p, long e}
\fun{GEN}{ZpXQX_liftroots}{GEN F, GEN S, GEN T, GEN p, long e}
\fun{GEN}{ZpXQX_divrem}{GEN x, GEN Sp, GEN T,GEN q,GEN p,long e, GEN *pr}
as \kbd{FpXQX\_divrem}. The parameter $q$ must be equal to $p^e$.
\fun{GEN}{ZpXQX_digits}{GEN x, GEN B, GEN T, GEN q, GEN p, long e}
As \kbd{FpXQX\_digits}. The parameter $q$ must be equal to $p^e$.
\fun{GEN}{ZpXQX_ZpXQXQ_liftroot}{GEN f, GEN a, GEN S, GEN T, GEN p, long e}
as \tet{ZpXQX_liftroot}, except that $a$ is an element of
$\Z_p[X,Y]/(S(X,Y),T(X))$.
\subsec{ZqX}
\kbd{ZqX} are either \kbd{ZpX} or \kbd{ZpXQX} depending whether \kbd{T} is \kbd{NULL} or not.
\fun{GEN}{ZqX_roots}{GEN F, GEN T, GEN p, long e}
\fun{GEN}{ZqX_liftfact}{GEN A, GEN B, GEN T, GEN pe, GEN p, long e}
\fun{GEN}{ZqX_liftroot}{GEN f, GEN a, GEN T, GEN p, long e}
\fun{GEN}{ZqX_ZqXQ_liftroot}{GEN f, GEN a, GEN P, GEN T, GEN p, long e}
\subsec{Other $p$-adic functions}
\fun{GEN}{ZpM_echelon}{GEN M, long early_abort, GEN p, GEN pm} given a
\kbd{ZM} $M$, a prime $p$ and $\kbd{pm} = p^m$, returns an echelon form
$E$ for $M$ mod $p^m$. I.e. there exist a square integral matrix $U$ with
$\det U$ coprime to $p$ such that $E = MU$ modulo $p^m$. I
\kbd{early\_abort} is nonzero, return NULL as soon as one pivot in
the echelon form is divisible by $p^m$. The echelon form is an upper
triangular HNF, we do not waste time to reduce it to Gauss-Jordan form.
\fun{GEN}{zlm_echelon}{GEN M, long early_abort, ulong p, ulong pm}
variant of \kbd{ZpM\_echelon}, for a \kbd{Zlm} $M$.
\fun{GEN}{ZlM_gauss}{GEN a, GEN b, ulong p, long e, GEN C} as \kbd{gauss}
with the following peculiarities: $a$ and $b$ are \kbd{ZM}, such that $a$ is
invertible modulo $p$. Optional $C$ is an \kbd{Flm} that is an inverse of
$a\mod p$ or \kbd{NULL}. Return the matrix $x$ such that $ax=b\mod p^e$ and
all elements of $x$ are in $[0,p^e-1]$. For efficiency, it is better
to reduce $a$ and $b$ mod $p^e$ first.
\fun{GEN}{padic_to_Q}{GEN x} truncate the \typ{PADIC} to a \typ{INT} or
\typ{FRAC}.
\fun{GEN}{padic_to_Q_shallow}{GEN x} shallow version of \tet{padic_to_Q}
\fun{GEN}{QpV_to_QV}{GEN v} apply \tet{padic_to_Q_shallow}
\fun{long}{padicprec}{GEN x, GEN p} returns the absolute $p$-adic precision of
the object $x$, by definition the minimum precision of the components of $x$.
For a nonzero \typ{PADIC}, this returns \kbd{valp(x) + precp(x)}.
\fun{long}{padicprec_relative}{GEN x} returns the relative $p$-adic
precision of the \typ{INT}, \typ{FRAC}, or \typ{PADIC} $x$ (minimum precision
of the components of $x$ for \typ{POL} or vector/matrices).
For a \typ{PADIC}, this returns \kbd{precp(x)} if $x\neq0$, and $0$ for $x=0$.
\subsubsec{low-level}
The following technical function returns an optimal sequence of $p$-adic
accuracies, for a given target accuracy:
\fun{ulong}{quadratic_prec_mask}{long n} we want to reach accuracy
$n\geq 1$, starting from accuracy 1, using a quadratically convergent,
self-correcting, algorithm; in other words, from inputs correct to accuracy
$l$ one iteration outputs a result correct to accuracy $2l$.
For instance, to reach $n = 9$, we want to use accuracies
$[1,2,3,5,9]$ instead of $[1,2,4,8,9]$. The idea is to essentially double
the accuracy at each step, and not overshoot in the end.
Let $a_0$ = 1, $a_1 = 2, \ldots, a_k = n$, be the desired sequence of
accuracies. To obtain it, we work backwards and set
$$ a_k = n,\quad a_{i-1} = (a_i + 1)\,\bs\, 2.$$
This is in essence what the function returns.
But we do not want to store the $a_i$ explicitly, even as a \typ{VECSMALL},
since this would leave an object on the stack. Instead, we store $a_i$
implicitly in a bitmask \kbd{MASK}: let $a_0 = 1$, if the $i$-th bit of the
mask is set, set $a_{i+1} = 2a_i - 1$, and $2a_i$ otherwise; in short the
bits indicate the places where we do something special and do not quite
double the accuracy (which would be the straightforward thing to do).
In fact, to avoid returning separately the mask and the sequence length
$k+1$, the function returns $\kbd{MASK} + 2^{k+1}$, so the highest bit of
the mask indicates the length of the sequence, and the following ones give
an algorithm to obtain the accuracies. This is much simpler than it sounds,
here is what it looks like in practice:
\bprog
ulong mask = quadratic_prec_mask(n);
long l = 1;
while (mask > 1) { /* here, the result is known to accuracy l */
l = 2*l; if (mask & 1) l--; /* new accuracy l for the iteration */
mask >>= 1; /* pop low order bit */
/* ... lift to the new accuracy ... */
}
/* we are done. At this point l = n */
@eprog\noindent We just pop the bits in \kbd{mask} starting from the low
order bits, stop when \kbd{mask} is $1$ (that last bit corresponds to the
$2^{k+1}$ that we added to the mask proper). Note that there is nothing
specific to Hensel lifts in that function: it would work equally well for
an Archimedean Newton iteration.
Note that in practice, we rather use an infinite loop, and insert an
\bprog
if (mask == 1) break;
@eprog\noindent in the middle of the loop: the loop body usually includes
preparations for the next iterations (e.g. lifting Bezout coefficients
in a quadratic Hensel lift), which are costly and useless in the \emph{last}
iteration.
\subsec{Conversions involving single precision objects}
\subsubsec{To single precision}
\fun{ulong}{Rg_to_Fl}{GEN z, ulong p}, \kbd{z} which can be mapped to
$\Z/p\Z$: a \typ{INT}, a \typ{INTMOD} whose modulus is divisible by $p$,
a \typ{FRAC} whose denominator is coprime to $p$, or a \typ{PADIC} with
underlying prime $\ell$ satisfying $p = \ell^n$ for some $n$ (less than the
accuracy of the input). Returns \kbd{lift(z * Mod(1,p))}, normalized, as an
\kbd{Fl}.
\fun{ulong}{Rg_to_F2}{GEN z}, as \tet{Rg_to_Fl} for $p = 2$.
\fun{ulong}{padic_to_Fl}{GEN x, ulong p} special case of \tet{Rg_to_Fl},
for a $x$ a \typ{PADIC}.
\fun{GEN}{RgX_to_F2x}{GEN x}, \kbd{x} a \typ{POL}, returns the
\kbd{F2x} obtained by applying \kbd{Rg\_to\_Fl} coefficientwise.
\fun{GEN}{RgX_to_Flx}{GEN x, ulong p}, \kbd{x} a \typ{POL}, returns the
\kbd{Flx} obtained by applying \kbd{Rg\_to\_Fl} coefficientwise.
\fun{GEN}{RgXV_to_FlxV}{GEN x, ulong p}, \kbd{x} a vector, returns the
\kbd{FlxV} obtained by applying \kbd{RgX\_to\_Flx} coefficientwise.
\fun{GEN}{Rg_to_F2xq}{GEN z, GEN T}, \kbd{z} a \kbd{GEN} which can be
mapped to $\F_2[X]/(T)$: anything \kbd{Rg\_to\_Fl} can be applied to,
a \typ{POL} to which \kbd{RgX\_to\_F2x} can be applied to, a \typ{POLMOD}
whose modulus is divisible by $T$ (once mapped to a \kbd{F2x}), a suitable
\typ{RFRAC}. Returns \kbd{z} as an \kbd{F2xq}, normalized.
\fun{GEN}{Rg_to_Flxq}{GEN z, GEN T, ulong p}, \kbd{z} a \kbd{GEN} which can be
mapped to $\F_p[X]/(T)$: anything \kbd{Rg\_to\_Fl} can be applied to,
a \typ{POL} to which \kbd{RgX\_to\_Flx} can be applied to, a \typ{POLMOD}
whose modulus is divisible by $T$ (once mapped to a \kbd{Flx}), a suitable
\typ{RFRAC}. Returns \kbd{z} as an \kbd{Flxq}, normalized.
\fun{GEN}{RgX_to_FlxqX}{GEN z, GEN T, ulong p}, \kbd{z} a \kbd{GEN} which can be
mapped to $\F_p[x]/(T)[X]$: anything \kbd{Rg\_to\_Flxq} can be applied to,
a \typ{POL} to which \kbd{RgX\_to\_Flx} can be applied to, a \typ{POLMOD}
whose modulus is divisible by $T$ (once mapped to a \kbd{Flx}), a suitable
\typ{RFRAC}. Returns \kbd{z} as an \kbd{FlxqX}, normalized.
\fun{GEN}{ZX_to_Flx}{GEN x, ulong p} reduce \kbd{ZX}~\kbd{x} modulo \kbd{p}
(yielding an \kbd{Flx}). Faster than \kbd{RgX\_to\_Flx}.
\fun{GEN}{ZV_to_Flv}{GEN x, ulong p} reduce \kbd{ZV}~\kbd{x} modulo \kbd{p}
(yielding an \kbd{Flv}).
\fun{GEN}{ZXV_to_FlxV}{GEN v, ulong p}, as \kbd{ZX\_to\_Flx}, repeatedly
called on the vector's coefficients.
\fun{GEN}{ZXT_to_FlxT}{GEN v, ulong p}, as \kbd{ZX\_to\_Flx}, repeatedly
called on the tree leaves.
\fun{GEN}{ZXX_to_FlxX}{GEN B, ulong p, long v}, as \kbd{ZX\_to\_Flx},
repeatedly called on the polynomial's coefficients.
\fun{GEN}{zxX_to_FlxX}{GEN z, ulong p} as \kbd{zx\_to\_Flx},
repeatedly called on the polynomial's coefficients.
\fun{GEN}{ZXXV_to_FlxXV}{GEN V, ulong p, long v}, as \kbd{ZXX\_to\_FlxX},
repeatedly called on the vector's coefficients.
\fun{GEN}{ZXXT_to_FlxXT}{GEN V, ulong p, long v}, as \kbd{ZXX\_to\_FlxX},
repeatedly called on the tree leaves.
\fun{GEN}{RgV_to_Flv}{GEN x, ulong p} reduce the \typ{VEC}/\typ{COL}
$x$ modulo $p$, yielding a \typ{VECSMALL}.
\fun{GEN}{RgM_to_Flm}{GEN x, ulong p} reduce the \typ{MAT} $x$ modulo $p$.
\fun{GEN}{ZM_to_Flm}{GEN x, ulong p} reduce \kbd{ZM}~$x$ modulo $p$
(yielding an \kbd{Flm}).
\fun{GEN}{ZXC_to_FlxC}{GEN x, ulong p, long sv} reduce \kbd{ZXC}~$x$ modulo $p$
(yielding an \kbd{FlxC}). Assume that \kbd{sv = evalvarn(v)} where $v$ is
the variable number of the entries of $x$. It is allowed for the entries of
$x$ to be \typ{INT}.
\fun{GEN}{ZXM_to_FlxM}{GEN x, ulong p, long sv} reduce \kbd{ZXM}~$x$ modulo $p$
(yielding an \kbd{FlxM}). Assume that \kbd{sv = evalvarn(v)} where $v$ is
the variable number of the entries of $x$. It is allowed for the entries of $x$
to be \typ{INT}.
\fun{GEN}{ZV_to_zv}{GEN z}, converts coefficients using \kbd{itos}
\fun{GEN}{ZV_to_nv}{GEN z}, converts coefficients using \kbd{itou}
\fun{GEN}{ZM_to_zm}{GEN z}, converts coefficients using \kbd{itos}
\subsubsec{From single precision}
\fun{GEN}{Flx_to_ZX}{GEN z}, converts to \kbd{ZX} (\typ{POL} of nonnegative
\typ{INT}s in this case)
\fun{GEN}{Flx_to_FlxX}{GEN z}, converts to \kbd{FlxX} (\typ{POL} of constant
\kbd{Flx} in this case).
\fun{GEN}{Flx_to_ZX_inplace}{GEN z}, same as \kbd{Flx\_to\_ZX}, in place
(\kbd{z} is destroyed).
\fun{GEN}{FlxX_to_ZXX}{GEN B}, converts an \kbd{FlxX} to a polynomial with
\kbd{ZX} or \typ{INT} coefficients (repeated calls to \kbd{Flx\_to\_ZX}).
\fun{GEN}{FlxXC_to_ZXXC}{GEN B}, converts an \kbd{FlxXC} to a \typ{COL} with
\kbd{ZXX} coefficients (repeated calls to \kbd{FlxX\_to\_ZXX}).
\fun{GEN}{FlxXM_to_ZXXM}{GEN B}, converts an \kbd{FlxXM} to a \typ{MAT} with
\kbd{ZXX} coefficients (repeated calls to \kbd{FlxX\_to\_ZXX}).
\fun{GEN}{FlxC_to_ZXC}{GEN x}, converts a vector of \kbd{Flx} to a column
vector of polynomials with \typ{INT} coefficients (repeated calls to
\kbd{Flx\_to\_ZX}).
\fun{GEN}{FlxV_to_ZXV}{GEN x}, as above but return a \typ{VEC}.
\fun{void}{F2xV_to_FlxV_inplace}{GEN v} v is destroyed.
\fun{void}{F2xV_to_ZXV_inplace}{GEN v} v is destroyed.
\fun{void}{FlxV_to_ZXV_inplace}{GEN v} v is destroyed.
\fun{GEN}{FlxM_to_ZXM}{GEN z}, converts a matrix of \kbd{Flx} to a matrix of
polynomials with \typ{INT} coefficients (repeated calls to \kbd{Flx\_to\_ZX}).
\fun{GEN}{zx_to_ZX}{GEN z}, as \kbd{Flx\_to\_ZX}, without assuming
the coefficients to be nonnegative.
\fun{GEN}{zx_to_Flx}{GEN z, ulong p} as \kbd{Flx\_red} without assuming
the coefficients to be nonnegative.
\fun{GEN}{Flc_to_ZC}{GEN z}, converts to \kbd{ZC} (\typ{COL} of nonnegative
\typ{INT}s in this case)
\fun{GEN}{Flc_to_ZC_inplace}{GEN z}, same as \kbd{Flc\_to\_ZC}, in place
(\kbd{z} is destroyed).
\fun{GEN}{Flv_to_ZV}{GEN z}, converts to \kbd{ZV} (\typ{VEC} of nonnegative
\typ{INT}s in this case)
\fun{GEN}{Flm_to_ZM}{GEN z}, converts to \kbd{ZM} (\typ{MAT} with
nonnegative \typ{INT}s coefficients in this case)
\fun{GEN}{Flm_to_ZM_inplace}{GEN z}, same as \kbd{Flm\_to\_ZM}, in place
(\kbd{z} is destroyed).
\fun{GEN}{zc_to_ZC}{GEN z} as \kbd{Flc\_to\_ZC}, without assuming
coefficients are nonnegative.
\fun{GEN}{zv_to_ZV}{GEN z} as \kbd{Flv\_to\_ZV}, without assuming
coefficients are nonnegative.
\fun{GEN}{zm_to_ZM}{GEN z} as \kbd{Flm\_to\_ZM}, without assuming
coefficients are nonnegative.
\fun{GEN}{zv_to_Flv}{GEN z, ulong p}
\fun{GEN}{zm_to_Flm}{GEN z, ulong p}
\subsubsec{Mixed precision linear algebra} Assumes dimensions are compatible.
Multiply a multiprecision object by a single-precision one.
\fun{GEN}{RgM_zc_mul}{GEN x, GEN y}
\fun{GEN}{RgMrow_zc_mul}{GEN x, GEN y, long i}
\fun{GEN}{RgM_zm_mul}{GEN x, GEN y}
\fun{GEN}{RgV_zc_mul}{GEN x, GEN y}
\fun{GEN}{RgV_zm_mul}{GEN x, GEN y}
\fun{GEN}{ZM_zc_mul}{GEN x, GEN y}
\fun{GEN}{zv_ZM_mul}{GEN x, GEN y}
\fun{GEN}{ZV_zc_mul}{GEN x, GEN y}
\fun{GEN}{ZM_zm_mul}{GEN x, GEN y}
\fun{GEN}{ZC_z_mul}{GEN x, long y}
\fun{GEN}{ZM_nm_mul}{GEN x, GEN y} the entries of $y$ are \kbd{ulong}s.
\fun{GEN}{nm_Z_mul}{GEN y, GEN c} the entries of $y$ are \kbd{ulong}s.
\subsubsec{Miscellaneous involving Fl}
\fun{GEN}{Fl_to_Flx}{ulong x, long evx} converts a \kbd{unsigned long} to a
scalar \kbd{Flx}. Assume that \kbd{evx = evalvarn(vx)} for some variable
number \kbd{vx}.
\fun{GEN}{Z_to_Flx}{GEN x, ulong p, long sv} converts a \typ{INT} to a scalar
\kbd{Flx} polynomial. Assume that \kbd{sv = evalvarn(v)} for some variable
number \kbd{v}.
\fun{GEN}{Flx_to_Flv}{GEN x, long n} converts from \kbd{Flx} to \kbd{Flv}
with \kbd{n} components (assumed larger than the number of coefficients of
\kbd{x}).
\fun{GEN}{zx_to_zv}{GEN x, long n} as \kbd{Flx\_to\_Flv}.
\fun{GEN}{Flv_to_Flx}{GEN x, long sv} converts from vector (coefficient
array) to (normalized) polynomial in variable $v$.
\fun{GEN}{zv_to_zx}{GEN x, long n} as \kbd{Flv\_to\_Flx}.
\fun{GEN}{Flm_to_FlxV}{GEN x, long sv} converts the columns of
\kbd{Flm}~\kbd{x} to an array of \kbd{Flx} in the variable $v$
(repeated calls to \kbd{Flv\_to\_Flx}).
\fun{GEN}{FlxM_to_FlxXV}{GEN V, long v} see \kbd{RgM\_to\_RgXV}
\fun{GEN}{zm_to_zxV}{GEN x, long n} as \kbd{Flm\_to\_FlxV}.
\fun{GEN}{Flm_to_FlxX}{GEN x, long sw, long sv} same as
\kbd{Flm\_to\_FlxV(x,sv)} but returns the result as a (normalized) polynomial
in variable $w$.
\fun{GEN}{FlxV_to_Flm}{GEN v, long n} reverse \kbd{Flm\_to\_FlxV}, to obtain
an \kbd{Flm} with \kbd{n} rows (repeated calls to \kbd{Flx\_to\_Flv}).
\fun{GEN}{FlxX_to_Flx}{GEN P} Let $P(x,X)$ be a \kbd{FlxX}, return $P(0,X)$
as a \kbd{Flx}.
\fun{GEN}{FlxX_to_Flm}{GEN v, long n} reverse \kbd{Flm\_to\_FlxX}, to obtain
an \kbd{Flm} with \kbd{n} rows (repeated calls to \kbd{Flx\_to\_Flv}).
\fun{GEN}{FlxX_to_FlxC}{GEN B, long n, long sv} see \kbd{RgX\_to\_RgV}.
The coefficients of \kbd{B} are assumed to be in the variable $v$.
\fun{GEN}{FlxV_to_FlxX}{GEN x, long v} see \kbd{RgV\_to\_RgX}.
\fun{GEN}{FlxXV_to_FlxM}{GEN V, long n, long sv} see \kbd{RgXV\_to\_RgM}.
The coefficients of \kbd{V[i]} are assumed to be in the variable $v$.
\fun{GEN}{Fly_to_FlxY}{GEN a, long sv} convert coefficients of \kbd{a} to
constant \kbd{Flx} in variable $v$.
\subsubsec{Miscellaneous involving \kbd{F2x}}
\fun{GEN}{F2x_to_F2v}{GEN x, long n} converts from \kbd{F2x} to \kbd{F2v}
with \kbd{n} components (assumed larger than the number of coefficients of
\kbd{x}).
\fun{GEN}{F2xC_to_ZXC}{GEN x}, converts a vector of \kbd{F2x} to a column
vector of polynomials with \typ{INT} coefficients (repeated calls to
\kbd{F2x\_to\_ZX}).
\fun{GEN}{F2xC_to_FlxC}{GEN x}
\fun{GEN}{FlxC_to_F2xC}{GEN x}
\fun{GEN}{F2xV_to_F2m}{GEN v, long n} \kbd{F2x\_to\_F2v} to each polynomial
to get an \kbd{F2m} with \kbd{n} rows.
\section{Higher arithmetic over $\Z$: primes, factorization}
\subsec{Pure powers}
\fun{long}{Z_issquare}{GEN n} returns $1$ if the \typ{INT} $n$ is
a square, and $0$ otherwise. This is tested first modulo small prime
powers, then \kbd{sqrtremi} is called.
\fun{long}{Z_issquareall}{GEN n, GEN *sqrtn} as \kbd{Z\_issquare}. If
$n$ is indeed a square, set \kbd{sqrtn} to its integer square root.
Uses a fast congruence test mod $64\times 63\times 65\times 11$ before
computing an integer square root.
\fun{long}{Z_ispow2}{GEN x} returns $1$ if the \typ{INT} $x$ is a power of
$2$, and $0$ otherwise.
\fun{long}{uissquare}{ulong n} as \kbd{Z\_issquare},
for an \kbd{ulong} operand \kbd{n}.
\fun{long}{uissquareall}{ulong n, ulong *sqrtn} as \kbd{Z\_issquareall},
for an \kbd{ulong} operand \kbd{n}.
\fun{ulong}{usqrt}{ulong a} returns the floor of the square root of $a$.
\fun{ulong}{usqrtn}{ulong a, ulong n} returns the floor of the $n$-th root
of $a$.
\fun{long}{Z_ispower}{GEN x, ulong k} returns $1$ if the \typ{INT} $n$ is a
$k$-th power, and $0$ otherwise; assume that $k > 1$.
\fun{long}{Z_ispowerall}{GEN x, ulong k, GEN *pt} as \kbd{Z\_ispower}. If
$n$ is indeed a $k$-th power, set \kbd{*pt} to its integer $k$-th root.
\fun{long}{Z_isanypower}{GEN x, GEN *ptn} returns the maximal $k\geq 2$ such
that the \typ{INT} $x = n^k$ is a perfect power, or $0$ if no such $k$ exist;
in particular \kbd{ispower(1)}, \kbd{ispower(0)}, \kbd{ispower(-1)} all
return 0. If the return value $k$ is not $0$ (so that $x = n^k$) and
\kbd{ptn} is not \kbd{NULL}, set \kbd{*ptn} to $n$.
The following low-level functions are called by \tet{Z_isanypower} but can
be directly useful:
\fun{int}{is_357_power}{GEN x, GEN *ptn, ulong *pmask} tests whether the
integer $x > 0$ is a $3$-rd, $5$-th or $7$-th power. The bits of \kbd{*mask}
initially indicate which test is to be performed;
bit $0$: $3$-rd,
bit $1$: $5$-th,
bit $2$: $7$-th (e.g.~$\kbd{*pmask} = 7$ performs all tests). They are
updated during the call: if the ``$i$-th power'' bit is set to $0$
then $x$ is not a $k$-th power. The function returns $0$
(not a
$3$-rd,
$5$-th or
$7$-th power),
$3$
($3$-rd power,
not a $5$-th or
$7$-th power),
$5$
($5$-th power,
not a $7$-th power),
or $7$
($7$-th power); if an $i$-th power bit is initially set to $0$, we take it
at face value and assume $x$ is not an $i$-th power without performing any
test. If the return value $k$ is nonzero, set \kbd{*ptn} to $n$ such that $x
= n^k$.
\fun{int}{is_pth_power}{GEN x, GEN *ptn, forprime_t *T, ulong cutoff}
let $x > 0$ be an integer, $\kbd{cutoff} > 0$ and $T$ be an iterator over
primes $\geq 11$, we look for the smallest prime $p$ such that $x = n^p$
(advancing $T$ as we go along). The $11$ is due to the fact that
\tet{is_357_power} and \kbd{issquare} are faster than the generic version for
$p < 11$.
Fail and return $0$ when the existence of $p$ would imply $2^{\kbd{cutoff}} >
x^{1/p}$, meaning that a possible $n$ is so small that it should have been
found by trial division; for maximal speed, you should start by a round of
trial division, but the cut-off may also be set to $1$ for a rigorous result
without any trial division.
Otherwise returns the smallest suitable prime power $p^i$ and set \kbd{*ptn}
to the $p^i$-th root of $x$ (which is now not a $p$-th power). We may
immediately recall the function with the same parameters after setting $x =
\kbd{*ptn}$: it will start at the next prime.
\subsec{Factorization}
\fun{GEN}{Z_factor}{GEN n} factors the \typ{INT} \kbd{n}. The ``primes''
in the factorization are actually strong pseudoprimes.
\fun{GEN}{absZ_factor}{GEN n} returns \kbd{Z\_factor(absi(n))}.
\fun{long}{Z_issmooth}{GEN n, ulong lim} returns $1$ if all the
prime factors of the \typ{INT} $n$ are less or equal to $lim$.
\fun{GEN}{Z_issmooth_fact}{GEN n, ulong lim} returns \kbd{NULL} if a prime
factor of the \typ{INT} $n$ is $> lim$, and returns the factorization
of $n$ otherwise, as a \typ{MAT} with \typ{VECSMALL} columns (word-size
primes and exponents). Neither memory-clean nor suitable for
\kbd{gerepileupto}.
\fun{GEN}{Z_factor_until}{GEN n, GEN lim} as \kbd{Z\_factor}, but stop the
factorization process as soon as the unfactored part is smaller than \kbd{lim}.
The resulting factorization matrix only contains the factors found. No other
assumptions can be made on the remaining factors.
\fun{GEN}{Z_factor_limit}{GEN n, ulong lim} trial divide $n$ by all primes $p
< \kbd{lim}$ in the precomputed list of prime numbers and the \kbd{addprimes}
prime table. Return the corresponding factorization matrix. The first column
of the factorization matrix may contain a single composite, which may
or may not be the last entry in presence of a prime table.
If $\kbd{lim} = 0$, the effect is the same as setting $\kbd{lim} =
\kbd{maxprime()} + 1$: use all precomputed primes.
\fun{GEN}{absZ_factor_limit}{GEN n, ulong all} returns
\kbd{Z\_factor\_limit(absi(n))}.
\fun{GEN}{absZ_factor_limit_strict}{GEN n, ulong all, GEN *pU}. This function
is analogous to
\tet{absZ_factor_limit}, with a better interface: trial divide $n$ by all
primes $p < \kbd{lim}$ in the precomputed list of prime numbers and the
\kbd{addprimes} prime table. Return the corresponding factorization matrix.
In this case, a composite cofactor is \emph{not} included.
If \kbd{pU} is not \kbd{NULL}, set it to the cofactor, which is either
\kbd{NULL} (no cofactor) or $[q,k]$, where $k > 0$, the prime divisors
of $q$ are greater than \kbd{all}, $q$ is not a pure power,
and $q^k$ is the largest power of $q$ dividing $n$. It may happen that $q$
is prime.
\fun{GEN}{boundfact}{GEN x, ulong lim} as \tet{Z_factor_limit}, applying to
\typ{INT} or \typ{FRAC} inputs.
\fun{GEN}{Z_smoothen}{GEN n, GEN L, GEN *pP, GEN *pE} given a \typ{VEC}
$L$ containing a list of primes and a \typ{INT} $n$, trial divide
$n$ by the elements of $L$ and return the cofactor. Return \kbd{NULL} if the
cofactor is $\pm 1$. \kbd{*P} and \kbd{*E} contain the list of prime divisors
found and their exponents, as \typ{VECSMALL}s. Neither memory-clean, nor
suitable for \tet{gerepileupto}.
\fun{GEN}{Z_lsmoothen}{GEN n, GEN L, GEN *pP, GEN *pE} as
\kbd{Z\_smoothen} where $L$ is a \typ{VECSMALL} of small primes and both
\kbd{*P} and \kbd{*E} are given as \typ{VECSMALL}.
\fun{GEN}{Z_factor_listP}{GEN N, GEN L} given a \typ{INT} $N$, a vector or
primes $L$ containing all prime divisors of $N$ (and possibly others). Return
\kbd{factor(N)}. Neither memory-clean, nor suitable for \tet{gerepileupto}.
\fun{GEN}{factor_pn_1}{GEN p, ulong n} returns the factorization of $p^n-1$,
where $p$ is prime and $n$ is a positive integer.
\fun{GEN}{factor_pn_1_limit}{GEN p, ulong n, ulong B} returns a partial
factorization of $p^n-1$, where $p$ is prime and $n$ is a positive integer.
Don't actively search for prime divisors $p > B$, but we may find still find
some due to Aurifeuillian factorizations. Any entry $> B^2$ in the output
factorization matrix is \emph{a priori} not a prime (but may well be).
\fun{GEN}{factor_Aurifeuille_prime}{GEN p, long n} an Aurifeuillian factor
of $\phi_n(p)$, assuming $p$ prime and an Aurifeuillian factor exists
($p \zeta_n$ is a square in $\Q(\zeta_n)$).
\fun{GEN}{factor_Aurifeuille}{GEN a, long n} an Aurifeuillian factor of
$\phi_n(a)$, assuming $a$ is a nonzero integer and $n > 2$. Returns $1$
if no Aurifeuillian factor exists.
\fun{GEN}{odd_prime_divisors}{GEN a} \typ{VEC} of all prime divisors of the
\typ{INT} $a$.
\fun{GEN}{factoru}{ulong n}, returns the factorization of $n$. The result
is a $2$-component vector $[P,E]$, where $P$ and $E$ are \typ{VECSMALL}
containing the prime divisors of $n$, and the $v_p(n)$.
\fun{GEN}{factoru_pow}{ulong n}, returns the factorization of $n$. The result
is a $3$-component vector $[P,E,C]$, where $P$, $E$ and $C$ are
\typ{VECSMALL} containing the prime divisors of $n$, the $v_p(n)$
and the $p^{v_p(n)}$.
\fun{GEN}{vecfactoru}{ulong a, ulong b}, returns a \typ{VEC} $v$ containing
the factorizations (\tet{factoru} format) of $a,\dots, b$; assume that $b
\geq a > 0$. Uses a sieve with primes up to $\sqrt{b}$. For all
$c$, $a \leq c \leq b$, the factorization of $c$ is given in $v[c-a+1]$.
\fun{GEN}{vecfactoroddu}{ulong a, ulong b}, returns a \typ{VEC} $v$ containing
the factorizations (\tet{factoru} format) of odd integers in $a,\dots, b$;
assume that $b \geq a > 0$ are odd. Uses a sieve with primes up to
$\sqrt{b}$. For all odd $c$, $a \leq c \leq b$, the factorization of $c$ is
given in in $v[(c-a)/2 + 1]$.
\fun{GEN}{vecfactoru_i}{ulong a, ulong b}, private version of
\kbd{vecfactoru}, not memory clean.
\fun{GEN}{vecfactoroddu_i}{ulong a, ulong b}, private version of
\kbd{vecfactoroddu}, not memory clean.
\fun{GEN}{vecfactorsquarefreeu}{ulong a, ulong b} return a \typ{VEC} $v$
containing the prime divisors of squarefree integers in $a,\dots,b$; assume
that $a \leq b$. Uses a sieve with primes up to $\sqrt{b}$.
For all squarefree $c$, $a\leq c\leq b$, the prime divisors of $c$ (as a
\typ{VECSMALL}) are given in $v[c-a+1]$, and the other entries are
\kbd{NULL}. Note that because of these \kbd{NULL} markers, $v$ is not a valid
\kbd{GEN}, it is not memory clean and cannot be used in garbage collection
routines.
\fun{GEN}{vecfactorsquarefreeu_coprime}{ulong a, ulong b, GEN P}
given a \emph{sorted} \typ{VECSMALL} of primes $P$, return a \typ{VEC} $v$
containing the prime divisors of squarefree integers in $a,\dots,b$ coprime to
the elements of $P$; assume that $a \leq b$. Uses a sieve with primes up to
$\sqrt{b}$. For all squarefree $c$, $a\leq c\leq b$, the prime divisors of $c$
(as a \typ{VECSMALL}) are given in $v[c-a+1]$, and the other entries are
\kbd{NULL}. Note that because of these \kbd{NULL} markers, $v$ is not a valid
\kbd{GEN}, it is not memory clean and cannot be used in garbage collection
routines.
\fun{GEN}{vecsquarefreeu}{ulong a, ulong b} return a \typ{VECSMALL} $v$
containing the squarefree integers in $a,\dots,b$. Assume that
$a\leq b$. Uses a sieve with primes up to $\sqrt{b}$.
\fun{ulong}{tridiv_bound}{GEN n} returns the trial division bound used by
\tet{Z_factor}$(n)$.
\fun{GEN}{tridiv_boundu}{ulong n} returns the trial division bound used
by \kbd{factoru}$n$.
\fun{GEN}{Z_pollardbrent}{GEN N, long n, long seed} try to factor
\typ{INT} $N$ using $n\geq 1$ rounds of Pollard iterations; \var{seed} is an
integer whose value (mod $8$) selects the quadratic polynomial use to
generate Pollard's (pseudo)random walk. Returns \kbd{NULL} on failure, else a
vector of 2 (possibly 3) integers whose product is $N$.
\fun{GEN}{Z_ECM}{GEN N, long n, long seed, ulong B1} try to
factor \typ{INT} $N$ using $n\geq 1$ rounds of ECM iterations (on $8$ to $64$
curves simultaneously, depending on the size of $N$); \var{seed} is an
integer whose value selects the curves to be used: increase it by $64n$ to
make sure that a subsequent call with a factor of $N$ uses a disjoint set of
curves.
Finally $B_1 > 7$ determines the computations performed on the
curves: we compute $[k]P$ for some point in $E(\Z/N\Z)$ and $k = q \prod
p^{e_p}$ where $p^{e_p} \leq B_1$ and $q \leq B_2 := 110 B_1$; a higher value
of $B_1$ means higher chances of hitting a factor and more time spent.
The computation is deterministic for a given set of parameters. Returns
\kbd{NULL} on failure, else a nontrivial factor or \kbd{N}.
\fun{GEN}{Q_factor}{GEN x} as \tet{Z_factor}, where $x$ is a \typ{INT} or
a \typ{FRAC}.
\fun{GEN}{Q_factor_limit}{GEN x, ulong lim} as \tet{Z_factor_limit}, where
$x$ is a \typ{INT} or a \typ{FRAC}.
\subsec{Coprime factorization}
Given $a$ and $b$ two nonzero integers, let \teb{ppi}$(a,b)$, \teb{ppo}$(a,b)$,
\teb{ppg}$(a,b)$, \teb{pple}$(a,b)$ (powers in $a$ of primes inside $b$,
outside $b$, greater than those in $b$, less than or equal to those in $b$) be
the integers defined by
\item $v_p(\text{ppi}) = v_p(a) [v_p(b) > 0]$,
\item $v_p(\text{ppo}) = v_p(a) [v_p(b) = 0]$,
\item $v_p(\text{ppg}) = v_p(a) [v_p(a) > v_p(b)]$,
\item $v_p(\text{pple}) = v_p(a) [v_p(a) \leq v_p(b)]$.
\fun{GEN}{Z_ppo}{GEN a, GEN b} returns $\text{ppo}(a,b)$; shallow function.
\fun{ulong}{u_ppo}{ulong a, ulong b} returns $\text{ppo}(a,b)$.
\fun{GEN}{Z_ppgle}{GEN a, GEN b} returns $[\text{ppg}(a,b), \text{pple}(a,b)]$;
shallow function.
\fun{GEN}{Z_ppio}{GEN a, GEN b} returns
$[\gcd(a,b), \text{ppi}(a,b), \text{ppo}(a,b)]$; shallow function.
\fun{GEN}{Z_cba}{GEN a, GEN b} fast natural coprime base algorithm. Returns a
vector of coprime divisors of $a$ and $b$ such that both $a$ and $b$ can
be multiplicatively generated from this set. Perfect powers are not removed,
use \tet{Z_isanypower} if needed; shallow function.
\fun{GEN}{ZV_cba_extend}{GEN P, GEN b} extend a coprime basis $P$ by the
integer $b$, the result being a coprime basis for $P\cup \{b\}$.
Perfect powers are not removed; shallow function.
\fun{GEN}{ZV_cba}{GEN v} given a vector of nonzero integers $v$, return
a coprime basis for $v$. Perfect powers are not removed; shallow function.
\subsec{Checks attached to arithmetic functions}
Arithmetic functions accept arguments of the following kind: a plain positive
integer $N$ (\typ{INT}), the factorization \var{fa} of a positive integer (a
\typ{MAT} with two columns containing respectively primes and exponents), or
a vector $[N,\var{fa}]$. A few functions accept nonzero
integers (e.g.~\tet{omega}), and some others arbitrary integers
(e.g.~\tet{factorint}, \dots).
\fun{int}{is_Z_factorpos}{GEN f} returns $1$ if $f$ looks like the
factorization of a positive integer, and $0$ otherwise. Useful for sanity
checks but not 100\% foolproof. Specifically, this routine checks that $f$ is
a two-column matrix all of whose entries are positive integers. It does
\emph{not} check that entries in the first column (``primes'') are prime,
or even pairwise coprime, nor that they are stricly increasing.
\fun{int}{is_Z_factornon0}{GEN f} returns $1$ if $f$ looks like the
factorization of a nonzero integer, and $0$ otherwise. Useful for sanity
checks but not 100\% foolproof, analogous to \tet{is_Z_factorpos}. (Entries
in the first column need only be nonzero integers.)
\fun{int}{is_Z_factor}{GEN f} returns $1$ if $f$ looks like the
factorization of an integer, and $0$ otherwise. Useful for sanity
checks but not 100\% foolproof. Specifically, this routine checks that $f$ is
a two-column matrix all of whose entries are integers. Entries in the second
column (``exponents'') are all positive. Either it encodes the
``factorization'' $0^e$, $e > 0$, or entries in the first column (``primes'')
are all nonzero.
\fun{GEN}{clean_Z_factor}{GEN f} assuming $f$ is the factorization of an
integer $n$, return the factorization of $|n|$, i.e.~remove $-1$ from the
factorization. Shallow function.
\fun{GEN}{fuse_Z_factor}{GEN f, GEN B} assuming $f$ is the
factorization of an integer $n$, return \kbd{boundfact(n, B)}, i.e.
return a factorization where all primary factors for $|p| \leq B$
are preserved, and all others are ``fused'' into a single composite
integer; if that remainder is trivial, i.e.~equal to 1, it is of course
not included. Shallow function.
In the following three routines, $f$ is the name of an arithmetic function,
and $n$ a supplied argument. They all raise exceptions if $n$ does not
correspond to an integer or an integer factorization of the expected shape.
\fun{GEN}{check_arith_pos}{GEN n, const char *f} check whether $n$
is attached to the factorization of a positive integer, and return
\kbd{NULL} (plain \typ{INT}) or a factorization extracted from $n$ otherwise.
May raise an \tet{e_DOMAIN} ($n \leq 0$) or an \tet{e_TYPE} exception (other
failures).
\fun{GEN}{check_arith_non0}{GEN n, const char *f} check whether $n$
is attached to the factorization of a nonzero integer, and return
\kbd{NULL} (plain \typ{INT}) or a factorization extracted from $n$ otherwise.
May raise an \tet{e_TYPE} exception.
\fun{GEN}{check_arith_all}{GEN n, const char *f}
is attached to the factorization of an integer, and return \kbd{NULL}
(plain \typ{INT}) or a factorization extracted from $n$ otherwise.
\subsec{Incremental integer factorization}
Routines attached to the dynamic factorization of an integer $n$, iterating
over successive prime divisors. This is useful to implement high-level
routines allowed to take shortcuts given enough partial information: e.g.
\kbd{moebius}$(n)$ can be trivially computed if we hit $p$ such that $p^2
\mid n$. For efficiency, trial division by small primes should have already
taken place. In any case, the functions below assume that no prime $< 2^{14}$
divides $n$.
\fun{GEN}{ifac_start}{GEN n, int moebius} schedules a new factorization
attempt for the integer $n$. If \kbd{moebius} is nonzero, the factorization
will be aborted as soon as a repeated factor is detected (Moebius mode).
The function assumes that $n > 1$ is a \emph{composite} \typ{INT} whose prime
divisors satisfy $p > 2^{14}$ \emph{and} that one can write to $n$ in place.
This function stores data on the stack, no \kbd{gerepile} call should
delete this data until the factorization is complete. Returns \kbd{partial},
a data structure recording the partial factorization state.
\fun{int}{ifac_next}{GEN *partial, GEN *p, long *e} deletes a primary factor
$p^e$ from \kbd{partial} and sets \kbd{p} (prime) and \kbd{e} (exponent), and
normally returns $1$. Whatever remains in the \kbd{partial} structure is now
coprime to $p$.
Returns $0$ if all primary factors have been used already, so we are done
with the factorization. In this case $p$ is set to \kbd{NULL}. If we ran in
Moebius mode and the factorization was in fact aborted, we have $e = 1$,
otherwise $e = 0$.
\fun{int}{ifac_read}{GEN part, GEN *k, long *e} peeks at the next integer
to be factored in the list $k^e$, where $k$ is not necessarily prime
and can be a perfect power as well, but will be factored by the next call to
\tet{ifac_next}. You can remove this factorization from the schedule by
calling:
\fun{void}{ifac_skip}{GEN part} removes the next scheduled factorization.
\fun{int}{ifac_isprime}{GEN n} given $n$ whose prime divisors are $> 2^{14}$,
returns the decision the factoring engine would take about the compositeness
of $n$: $0$ if $n$ is a proven composite, and $1$ if we believe it to be
prime; more precisely, $n$ is a proven prime if \tet{factor_proven} is
set, and only a BPSW-pseudoprime otherwise.
\subsec{Integer core, squarefree factorization}
\fun{long}{Z_issquarefree}{GEN n} returns $1$ if the \typ{INT} \kbd{n}
is square-free, and $0$ otherwise.
\fun{long}{Z_issquarefree_fact}{GEN fa} same, where \kbd{fa} is
\kbd{factor(n)}.
\fun{long}{Z_isfundamental}{GEN x} returns $1$ if the \typ{INT} \kbd{x}
is a fundamental discriminant, and $0$ otherwise.
\fun{GEN}{core}{GEN n} unique squarefree integer $d$ dividing $n$ such that
$n/d$ is a square. The core of $0$ is defined to be $0$.
\fun{GEN}{core2}{GEN n} return $[d,f]$ with $d$ squarefree and $n = df^2$.
\fun{GEN}{corepartial}{GEN n, long lim} as \kbd{core}, using
\kbd{boundfact(n,lim)} to partially factor \kbd{n}. The result is not
necessarily squarefree, but $p^2 \mid n$ implies $p > \kbd{lim}$.
\fun{GEN}{core2partial}{GEN n, long lim} as \kbd{core2}, using
\kbd{boundfact(n,lim)} to partially factor \kbd{n}. The resulting $d$ is not
necessarily squarefree, but $p^2 \mid n$ implies $p > \kbd{lim}$.
\subsec{Primes, primality and compositeness tests}
\subsubsec{Chebyshev's $\pi$ function, bounds}
\fun{ulong}{uprimepi}{ulong n}, returns the number of primes $p\leq n$
(Chebyshev's $\pi$ function).
\fun{double}{primepi_upper_bound}{double x} return a quick upper bound for
$\pi(x)$, using Dusart bounds.
\fun{GEN}{gprimepi_upper_bound}{GEN x} as \tet{primepi_upper_bound}, returns a
\typ{REAL}.
\fun{double}{primepi_lower_bound}{double x} return a quick lower bound for
$\pi(x)$, using Dusart bounds.
\fun{GEN}{gprimepi_lower_bound}{GEN x} as \tet{primepi_lower_bound}, returns
a \typ{REAL} or \kbd{gen\_0}.
\subsubsec{Primes, primes in intervals}
\fun{ulong}{unextprime}{ulong n}, returns the smallest prime $\geq n$. Return
$0$ if it cannot be represented as an \kbd{ulong} ($n$ bigger than $2^{64} -
59$ or $2^{32} - 5$ depending on the word size).
\fun{ulong}{uprecprime}{ulong n}, returns the largest prime $\leq n$. Return
$0$ if $n\leq 1$.
\fun{ulong}{uprime}{long n} returns the $n$-th prime, assuming it fits in an
\kbd{ulong} (overflow error otherwise).
\fun{GEN}{prime}{long n} same as \kbd{utoi(uprime(n))}.
\fun{GEN}{primes_zv}{long m} returns the first $m$ primes, in a
\typ{VECSMALL}.
\fun{GEN}{primes}{long m} return the first $m$ primes, as a \typ{VEC} of
\typ{INT}s.
\fun{GEN}{primes_interval}{GEN a, GEN b} return the primes in the interval
$[a,b]$, as a \typ{VEC} of \typ{INT}s.
\fun{GEN}{primes_interval_zv}{ulong a, ulong b} return the primes in the
interval $[a,b]$, as a \typ{VECSMALL} of \kbd{ulongs}s.
\fun{GEN}{primes_upto_zv}{ulong b} return the primes in the interval $[2,b]$,
as a \typ{VECSMALL} of \kbd{ulongs}s.
\subsubsec{Tests}
\fun{int}{uisprime}{ulong p}, returns $1$ if \kbd{p} is a prime number and
$0$ otherwise.
\fun{int}{uisprime_101}{ulong p}, assuming that $p$ has no divisor $\leq
101$, returns $1$ if \kbd{p} is a prime number and $0$ otherwise.
\fun{int}{uisprime_661}{ulong p}, assuming that $p$ has no divisor $\leq
661$, returns $1$ if \kbd{p} is a prime number and $0$ otherwise.
\fun{int}{isprime}{GEN n}, returns $1$ if the \typ{INT} \kbd{n} is a
(fully proven) prime number and $0$ otherwise.
\fun{long}{isprimeAPRCL}{GEN n}, returns $1$ if the \typ{INT} \kbd{n} is a
prime number and $0$ otherwise, using only the APRCL test --- not even trial
division or compositeness tests. The workhorse \kbd{isprime} should be
faster on average, especially if nonprimes are included!
\fun{long}{isprimeECPP}{GEN n}, returns $1$ if the \typ{INT} \kbd{n} is a
prime number and $0$ otherwise, using only the ECPP test. The workhorse
\kbd{isprime} should be faster on average.
\fun{long}{BPSW_psp}{GEN n}, returns $1$ if the \typ{INT} \kbd{n} is a
Baillie-Pomerance-Selfridge-Wagstaff pseudoprime, and $0$ otherwise (proven
composite).
\fun{int}{BPSW_isprime}{GEN x} assuming $x$ is a BPSW-pseudoprime, rigorously
prove its primality. The function \tet{isprime} is currently implemented
as
\bprog
BPSW_psp(x) && BPSW_isprime(x)
@eprog
\fun{long}{millerrabin}{GEN n, long k} performs $k$ strong Rabin-Miller
compositeness tests on the \typ{INT} $n$, using $k$ random bases. This
function also caches square roots of $-1$ that are encountered during the
successive tests and stops as soon as three distinct square roots have been
produced; we have in principle factored $n$ at this point, but
unfortunately, there is currently no way for the factoring machinery to
become aware of it. (It is highly implausible that hard to find factors
would be exhibited in this way, though.) This should be slower than
\tet{BPSW_psp} for $k\geq 4$ and we expect it to be less reliable.
\fun{GEN}{ecpp}{GEN N} returns an ECPP certificate for \typ{INT} $N$;
underlies \kbd{primecert}.
\fun{GEN}{ecpp0}{GEN N, long t} returns a (potentially)
partial ECPP certificate for \typ{INT} $N$ where strong pseudo-primes $< 2^t$
are included as primes in the certificate. Underlies \kbd{primecert} with
$t$ set to the \kbd{partial} argument.
\fun{GEN}{ecppexport}{GEN cert, long flag} export a PARI ECPP certificate to
MAGMA or Primo format; underlies \kbd{primecertexport}.
\fun{long}{ecppisvalid}{GEN cert} checks whether a PARI ECPP certificate
is valid; underlies \kbd{primecertisvalid}.
\fun{long}{check_ecppcert}{GEN cert} checks whether \kbd{cert} looks
like a PARI ECPP certificate, (valid or invalid) without doing any computation.
\subsec{Iterators over primes}
\fun{int}{forprime_init}{forprime_t *T, GEN a, GEN b} initialize an
iterator $T$ over primes in $[a,b]$; over primes $\geq a$ if $b =
\kbd{NULL}$. Return $0$ if the range is known to be empty from the start
(as if $b < a$ or $b < 0$), and return $1$ otherwise. Use \tet{forprime_next}
to iterate over the prime collection.
\fun{int}{forprimestep_init}{forprime_t *T, GEN a, GEN b, GEN q} initialize an
iterator $T$ over primes in an arithmetic progression in $[a,b]$;
over primes $\geq a$ if $b = \kbd{NULL}$. The argument $q$ is either a
\typ{INT} ($p \equiv a \pmod{q}$) or a \typ{INTMOD} \kbd{Mod(c,N)}
and we restrict to that congruence class. Return $0$ if the range is known to
be empty from the start (as if $b < a$ or $b < 0$), and return $1$ otherwise.
Use \tet{forprime_next} to iterate over the prime collection.
\fun{GEN}{forprime_next}{forprime_t *T} returns the next prime in the range,
assuming that $T$ was initialized by \tet{forprime_init}.
\fun{int}{u_forprime_init}{forprime_t *T, ulong a, ulong b}
\fun{ulong}{u_forprime_next}{forprime_t *T}
\fun{void}{u_forprime_restrict}{forprime_t *T, ulong c} let $T$ an iterator
over primes initialized via \kbd{u\_forprime\_init(\&T, a, b)}, possibly
followed by a number of calls to \tet{u_forprime_next}, and $a \leq c \leq
b$. Restrict the range of primes considered to $[a,c]$.
\fun{int}{u_forprime_arith_init}{forprime_t *T, ulong a,ulong b, ulong c,ulong q} initialize an iterator over primes in $[a,b]$, congruent to $c$
modulo $q$. Subsequent calls to \tet{u_forprime_next} will only return primes
congruent to $c$ modulo $q$. Note that unless $(c,q) = 1$ there will be at
most one such prime.
\section{Integral, rational and generic linear algebra}
\subsec{\kbd{ZC} / \kbd{ZV}, \kbd{ZM}} A \kbd{ZV} (resp.~a~\kbd{ZM},
resp.~a~\kbd{ZX}) is a \typ{VEC} or \typ{COL} (resp.~\typ{MAT},
resp.~\typ{POL}) with \typ{INT} coefficients.
\subsubsec{\kbd{ZC} / \kbd{ZV}}
\fun{void}{RgV_check_ZV}{GEN x, const char *s} Assuming \kbd{x} is a \typ{VEC}
or \typ{COL} raise an error if it is not a \kbd{ZV} ($s$ should point to the
name of the caller).
\fun{int}{RgV_is_ZV}{GEN x} Assuming \kbd{x} is a \typ{VEC}
or \typ{COL} return $1$ if it is a \kbd{ZV}, and $0$ otherwise.
\fun{int}{RgV_is_ZVpos}{GEN x} Assuming \kbd{x} is a \typ{VEC}
or \typ{COL} return $1$ if it is a \kbd{ZV} with positive entries, and $0$
otherwise.
\fun{int}{RgV_is_ZVnon0}{GEN x} Assuming \kbd{x} is a \typ{VEC}
or \typ{COL} return $1$ if it is a \kbd{ZV} with nonzero entries, and $0$
otherwise.
\fun{int}{RgV_is_QV}{GEN P} return 1 if the \kbd{RgV}~$P$ has only
\typ{INT} and \typ{FRAC} coefficients, and 0 otherwise.
\fun{int}{RgV_is_arithprog}{GEN v, GEN *a, GEN *b} assuming $x$ is a \typ{VEC}
or \typ{COL} return $1$ if its entries follow an arithmetic progression
of the form $a + b*n$, $n = 0, 1, \dots$ and set $a$ and $b$. Else return $0$.
\fun{int}{ZV_equal0}{GEN x} returns 1 if all entries of the \kbd{ZV} $x$ are
zero, and $0$ otherwise.
\fun{int}{ZV_cmp}{GEN x, GEN y} compare two \kbd{ZV}, which we assume have
the same length (lexicographic order).
\fun{int}{ZV_abscmp}{GEN x, GEN y} compare two \kbd{ZV}, which we assume have
the same length (lexicographic order, comparing absolute values).
\fun{int}{ZV_equal}{GEN x, GEN y} returns $1$ if the two \kbd{ZV} are equal
and $0$ otherwise. A \typ{COL} and a \typ{VEC} with the same entries are
declared equal.
\fun{GEN}{identity_ZV}{long n} return the \typ{VEC} $[1, 2, \dots, n]$.
\fun{GEN}{ZC_add}{GEN x, GEN y} adds \kbd{x} and \kbd{y}.
\fun{GEN}{ZC_sub}{GEN x, GEN y} subtracts \kbd{x} and \kbd{y}.
\fun{GEN}{ZC_Z_add}{GEN x, GEN y} adds \kbd{y} to \kbd{x[1]}.
\fun{GEN}{ZC_Z_sub}{GEN x, GEN y} subtracts \kbd{y} to \kbd{x[1]}.
\fun{GEN}{Z_ZC_sub}{GEN a, GEN x} returns the vector $[a - x_1,
-x_2,\dots,-x_n]$.
\fun{GEN}{ZC_copy}{GEN x} returns a (\typ{COL}) copy of \kbd{x}.
\fun{GEN}{ZC_neg}{GEN x} returns $-\kbd{x}$ as a \typ{COL}.
\fun{void}{ZV_neg_inplace}{GEN x} negates the \kbd{ZV} \kbd{x} in place, by
replacing each component by its opposite (the type of \kbd{x} remains the
same, \typ{COL} or \typ{COL}). If you want to save even more memory by
avoiding the implicit component copies, use \kbd{ZV\_togglesign}.
\fun{void}{ZV_togglesign}{GEN x} negates \kbd{x} in place, by toggling the
sign of its integer components. Universal constants \kbd{gen\_1},
\kbd{gen\_m1}, \kbd{gen\_2} and \kbd{gen\_m2} are handled specially and will
not be corrupted. (We use \tet{togglesign_safe}.)
\fun{GEN}{ZC_Z_mul}{GEN x, GEN y} multiplies the \kbd{ZC} or \kbd{ZV}~\kbd{x}
(which can be a column or row vector) by the \typ{INT}~\kbd{y}, returning a
\kbd{ZC}.
\fun{GEN}{ZC_Z_divexact}{GEN x, GEN y} returns $x/y$ assuming all divisions
are exact.
\fun{GEN}{ZC_divexactu}{GEN x, ulong y} returns $x/y$ assuming all divisions
are exact.
\fun{GEN}{ZC_Z_div}{GEN x, GEN y} returns $x/y$, where the resulting vector
has rational entries.
\fun{GEN}{ZV_ZV_mod}{GEN a, GEN b}. Assuming $a$ and $b$ are two \kbd{ZV}
of the same length, returns the vector whose $i$-th component
is \kbd{modii}$(a[i], b[i])$.
\fun{GEN}{ZV_dotproduct}{GEN x,GEN y} as \kbd{RgV\_dotproduct} assuming $x$
and $y$ have \typ{INT} entries.
\fun{GEN}{ZV_dotsquare}{GEN x} as \kbd{RgV\_dotsquare} assuming $x$
has \typ{INT} entries.
\fun{GEN}{ZC_lincomb}{GEN u, GEN v, GEN x, GEN y} returns $ux + vy$, where
$u$, $v$ are \typ{INT} and $x,y$ are \kbd{ZC} or \kbd{ZV}. Return a \kbd{ZC}
\fun{void}{ZC_lincomb1_inplace}{GEN X, GEN Y, GEN v} sets $X\leftarrow X +
vY$, where $v$ is a \typ{INT} and $X,Y$ are \kbd{ZC} or \kbd{ZV}. (The result
has the type of $X$.) Memory efficient (e.g. no-op if $v = 0$), but not
gerepile-safe.
\fun{void}{ZC_lincomb1_inplace_i}{GEN X, GEN Y, GEN v, long n}
variant of \tet{ZC_lincomb1_inplace}: only update $X[1], \dots, X[n]$,
assuming that $n < \kbd{lg}(X)$.
\fun{GEN}{ZC_ZV_mul}{GEN x, GEN y, GEN p} multiplies the \kbd{ZC}~\kbd{x}
(seen as a column vector) by the \kbd{ZV}~\kbd{y} (seen as a row vector,
assumed to have compatible dimensions).
\fun{GEN}{ZV_content}{GEN x} returns the GCD of all the components
of~\kbd{x}.
\fun{GEN}{ZV_extgcd}{GEN A} given a vector of $n$ integers $A$, returns $[d,
U]$, where $d$ is the content of $A$ and $U$ is a matrix
in $\text{GL}_n(\Z)$ such that $AU = [D,0, \dots,0]$.
\fun{GEN}{ZV_prod}{GEN x} returns the product of all the components
of~\kbd{x} ($1$ for the empty vector).
\fun{GEN}{ZV_sum}{GEN x} returns the sum of all the components
of~\kbd{x} ($0$ for the empty vector).
\fun{long}{ZV_max_lg}{GEN x} returns the effective length of the longest
entry in $x$.
\fun{int}{ZV_dvd}{GEN x, GEN y} assuming $x$, $y$ are two \kbd{ZV}s of the same
length, return $1$ if $y[i]$ divides $x[i]$ for all $i$ and $0$ otherwise.
Error if one of the $y[i]$ is $0$.
\fun{GEN}{ZV_sort}{GEN L} sort the \kbd{ZV} $L$.
Returns a vector with the same type as $L$.
\fun{GEN}{ZV_sort_shallow}{GEN L} shallow version of \kbd{ZV\_sort}.
\fun{void}{ZV_sort_inplace}{GEN L} sort the \kbd{ZV} $L$, in place.
\fun{GEN}{ZV_sort_uniq}{GEN L} sort the \kbd{ZV} $L$, removing duplicate
entries. Returns a vector with the same type as $L$.
\fun{GEN}{ZV_sort_uniq_shallow}{GEN L} shallow version of \kbd{ZV\_sort\_uniq}.
\fun{long}{ZV_search}{GEN L, GEN y} look for the \typ{INT} $y$ in the sorted
\kbd{ZV} $L$. Return an index $i$ such that $L[i] = y$, and $0$ otherwise.
\fun{GEN}{ZV_indexsort}{GEN L} returns the permutation which, applied to the
\kbd{ZV} $L$, would sort the vector. The result is a \typ{VECSMALL}.
\fun{GEN}{ZV_union_shallow}{GEN x, GEN y} given two \emph{sorted} ZV (as per
\tet{ZV_sort}, returns the union of $x$ and $y$. Shallow function. In case two
entries are equal in $x$ and $y$, include the one from $x$.
\fun{GEN}{ZC_union_shallow}{GEN x, GEN y} as \kbd{ZV\_union\_shallow} but return
a \typ{COL}.
\subsubsec{\kbd{ZM}}
\fun{void}{RgM_check_ZM}{GEN A, const char *s} Assuming \kbd{x} is a \typ{MAT}
raise an error if it is not a \kbd{ZM} ($s$ should point to the name of the
caller).
\fun{GEN}{RgM_rescale_to_int}{GEN x} given a matrix $x$ with real entries
(\typ{INT}, \typ{FRAC} or \typ{REAL}), return a \kbd{ZM} wich is very close
to $D x$ for some well-chosen integer $D$. More precisely, if the input is
exact, $D$ is the denominator of $x$; else it is a power of $2$ chosen
so that all inexact entries are correctly rounded to 1 ulp.
\fun{GEN}{ZM_copy}{GEN x} returns a copy of \kbd{x}.
\fun{int}{ZM_equal}{GEN A, GEN B} returns $1$ if the two \kbd{ZM} are equal
and $0$ otherwise.
\fun{int}{ZM_equal0}{GEN A} returns $1$ if the \kbd{ZM} $A$ is identically
equal to $0$.
\fun{GEN}{ZM_add}{GEN x, GEN y} returns $\kbd{x} + \kbd{y}$ (assumed to have
compatible dimensions).
\fun{GEN}{ZM_sub}{GEN x, GEN y} returns $\kbd{x} - \kbd{y}$ (assumed to have
compatible dimensions).
\fun{GEN}{ZM_neg}{GEN x} returns $-\kbd{x}$.
\fun{void}{ZM_togglesign}{GEN x} negates \kbd{x} in place, by toggling the
sign of its integer components. Universal constants \kbd{gen\_1},
\kbd{gen\_m1}, \kbd{gen\_2} and \kbd{gen\_m2} are handled specially and will
not be corrupted. (We use \tet{togglesign_safe}.)
\fun{GEN}{ZM_mul}{GEN x, GEN y} multiplies \kbd{x} and \kbd{y} (assumed to
have compatible dimensions).
\fun{GEN}{ZM2_mul}{GEN x, GEN y} multiplies the two-by-two \kbd{ZM} $x$ and $y$.
\fun{GEN}{ZM_sqr}{GEN x} returns $x^2$, where $x$ is a square \kbd{ZM}.
\fun{GEN}{ZM_Z_mul}{GEN x, GEN y} multiplies the \kbd{ZM}~\kbd{x}
by the \typ{INT}~\kbd{y}.
\fun{GEN}{ZM_ZC_mul}{GEN x, GEN y} multiplies the \kbd{ZM}~\kbd{x}
by the \kbd{ZC}~\kbd{y} (seen as a column vector, assumed to have compatible
dimensions).
\fun{GEN}{ZM_ZX_mul}{GEN x, GEN T} returns $x \times y$, where $y$
is \kbd{RgX\_to\_RgC}$(T, \kbd{lg}(x)-1)$.
\fun{GEN}{ZM_diag_mul}{GEN d, GEN m} given a vector $d$ with integer entries
and a \kbd{ZM} $m$ of compatible dimensions, return \kbd{diagonal(d) * m}.
\fun{GEN}{ZM_mul_diag}{GEN m, GEN d} given a vector $d$ with integer entries
and a \kbd{ZM} $m$ of compatible dimensions, return \kbd{m * diagonal(d)}.
\fun{GEN}{ZM_multosym}{GEN x, GEN y}
\fun{GEN}{ZM_transmultosym}{GEN x, GEN y}
\fun{GEN}{ZM_transmul}{GEN x, GEN y}
\fun{GEN}{ZMrow_ZC_mul}{GEN x, GEN y, long i} multiplies the $i$-th row
of \kbd{ZM}~\kbd{x} by the \kbd{ZC}~\kbd{y} (seen as a column vector, assumed
to have compatible dimensions). Assumes that $x$ is nonempty and
$0 < i < \kbd{lg(x[1])}$.
\fun{int}{ZMrow_equal0}{GEN V, long i} returns $1$ if the $i$-th row of
the \kbd{ZM}~\kbd{V} is zero, and $0$ otherwise.
\fun{GEN}{ZV_ZM_mul}{GEN x, GEN y} multiplies the \kbd{ZV}~\kbd{x}
by the \kbd{ZM}~\kbd{y}. Returns a \typ{VEC}.
\fun{GEN}{ZM_Z_divexact}{GEN x, GEN y} returns $x/y$ assuming all divisions
are exact.
\fun{GEN}{ZM_divexactu}{GEN x, ulong y} returns $x/y$ assuming all divisions
are exact.
\fun{GEN}{ZM_Z_div}{GEN x, GEN y} returns $x/y$, where the resulting matrix
has rational entries.
\fun{GEN}{ZM_ZV_mod}{GEN a, GEN b}. Assuming $a$ is a \kbd{ZM}
whose columns have the same length as the \kbd{ZV} $b$, apply
\kbd{ZV\_ZV\_mod}$(a[i],b)$ to all columns.
\fun{GEN}{ZC_Q_mul}{GEN x, GEN y} returns $x*y$, where $y$ is a rational number
and the resulting \typ{COL} has rational entries.
\fun{GEN}{ZM_Q_mul}{GEN x, GEN y} returns $x*y$, where $y$ is a rational number
and the resulting matrix has rational entries.
\fun{GEN}{ZM_pow}{GEN x, GEN n} returns $\kbd{x}^\kbd{n}$, assuming \kbd{x}
is a square \kbd{ZM} and $\kbd{n}\geq 0$.
\fun{GEN}{ZM_powu}{GEN x, ulong n} returns $\kbd{x}^\kbd{n}$, assuming \kbd{x}
is a square \kbd{ZM} and $\kbd{n}\geq 0$.
\fun{GEN}{ZM_det}{GEN M} if \kbd{M} is a \kbd{ZM}, returns the determinant of
$M$. This is the function underlying \tet{matdet} whenever $M$ is a \kbd{ZM}.
\fun{GEN}{ZM_permanent}{GEN M} if \kbd{M} is a \kbd{ZM}, returns its
permanent. This is the function underlying \tet{matpermanent} whenever $M$
is a \kbd{ZM}. It assumes that the matrix is square of dimension $<
\kbd{BITS\_IN\_LONG}$.
\fun{GEN}{ZM_detmult}{GEN M} if \kbd{M} is a \kbd{ZM}, returns a multiple of
the determinant of the lattice generated by its columns. This is the function
underlying \tet{detint}.
\fun{GEN}{ZM_supnorm}{GEN x} return the sup norm of the \kbd{ZM} $x$.
\fun{GEN}{ZM_charpoly}{GEN M} returns the characteristic polynomial (in
variable $0$) of the \kbd{ZM} $M$.
\fun{GEN}{ZM_imagecompl}{GEN x} returns \kbd{matimagecompl(x)}.
\fun{long}{ZM_rank}{GEN x} returns \kbd{matrank(x)}.
\fun{GEN}{ZM_ker}{GEN x} returns the primitive part of \kbd{matker(x)}; in
other words the $\Q$-basis vectors are made integral and primitive.
\fun{GEN}{ZM_indexrank}{GEN x} returns \kbd{matindexrank(x)}.
\fun{GEN}{ZM_indeximage}{GEN x} returns \kbd{gel(ZM\_indexrank(x), 2)}.
\fun{long}{ZM_max_lg}{GEN x} returns the effective length of the longest
entry in $x$.
\fun{GEN}{ZM_inv}{GEN M, GEN *pd} if \kbd{M} is a \kbd{ZM}, return
a primitive matrix $H$ such that $M H$ is $d$ times the identity
and set \kbd{*pd} to $d$. Uses a multimodular algorithm up to Hadamard's bound.
If you suspect that the denominator is much smaller than $\det M$, you may
use \tet{ZM_inv_ratlift}.
\fun{GEN}{ZM_inv_ratlift}{GEN M, GEN *pd} if \kbd{M} is a \kbd{ZM},
return a primitive matrix $H$ such that $M H$ is $d$ times the identity
and set \kbd{*pd} to $d$. Uses a multimodular algorithm, attempting
rational reconstruction along the way. To be used when you expect that the
denominator of $M^{-1}$ is much smaller than $\det M$ else use \kbd{ZM\_inv}.
\fun{GEN}{SL2_inv_shallow}{GEN M} return the inverse of $M \in
\text{SL}_2(\Z)$. Not gerepile-safe.
\fun{GEN}{ZM_pseudoinv}{GEN M, GEN *pv, GEN *pd} if \kbd{M} is a nonempty
\kbd{ZM}, let $v = [y,z]$ returned by \kbd{indexrank} and
let $M_1$ be the corresponding square invertible matrix.
Return a primitive left-inverse $H$ such that $H M_1$ is
$d$ times the identity and set \kbd{*pd} to $d$. If \kbd{pv} is not
\kbd{NULL}, set \kbd{*pv} to $v$. Not gerepile-safe.
\fun{GEN}{ZM_gauss}{GEN a, GEN b} as \kbd{gauss}, where $a$ and $b$
coefficients are \typ{INT}s.
\fun{GEN}{ZM_det_triangular}{GEN x} returns the product of the diagonal
entries of $x$ (its determinant if it is indeed triangular).
\fun{int}{ZM_isidentity}{GEN x} return 1 if the \kbd{ZM} $x$ is the
identity matrix, and 0 otherwise.
\fun{int}{ZM_isdiagonal}{GEN x} return 1 if the \kbd{ZM} $x$ is diagonal,
and 0 otherwise.
\fun{int}{ZM_isscalar}{GEN x, GEN s} given a \kbd{ZM} $x$ and a
\typ{INT} $s$, return 1 if $x$ is equal to $s$ times the identity, and 0
otherwise. If $s$ is \kbd{NULL}, test whether $x$ is an arbitrary scalar
matrix.
\fun{long}{ZC_is_ei}{GEN x} return $i$ if the \kbd{ZC} $x$ has $0$ entries,
but for a $1$ at position $i$.
\fun{int}{ZM_ishnf}{GEN x} return $1$ if $x$ is in HNF form, i.e. is upper
triangular with positive diagonal coefficients, and for $j>i$,
$x_{i,i}>x_{i,j} \ge 0$.
\subsec{\kbd{QM}}
\fun{GEN}{QM_charpoly_ZX}{GEN M} returns the characteristic polynomial
(in variable $0$) of the \kbd{QM} $M$, assuming that the result has integer
coefficients.
\fun{GEN}{QM_charpoly_ZX_bound}{GEN M, long b} as \tet{QM_charpoly_ZX}
assuming that the sup norm of the (integral) result is $\leq 2^b$.
\fun{GEN}{QM_gauss}{GEN a, GEN b} as \kbd{gauss}, where $a$ and $b$
coefficients are \typ{FRAC}s.
\fun{GEN}{QM_gauss_i}{GEN a, GEN b, long flag} as \kbd{QM\_gauss} if
\kbd{flag} is $0$. Else, no longer assume that $a$ is left-invertible and
return a solution of $P a x = P b$ where $P$ is a row-selection matrix
such that $A = P a Q$ is square invertible of maximal rank, for some
column-selection matrix $Q$; in particular, $x$ is a solution of
the original equation $a x = b$ if and only if a solution exists.
\fun{GEN}{QM_indexrank}{GEN x} returns \kbd{matindexrank(x)}.
\fun{GEN}{QM_inv}{GEN M} return the inverse of the \kbd{QM} $M$.
\fun{long}{QM_rank}{GEN x} returns \kbd{matrank(x)}.
\fun{GEN}{QM_image}{GEN x} returns an integral matrix with primitive columns
generating the image of $x$.
\fun{GEN}{QM_image_shallow}{GEN A} shallow version of the previous function,
not suitable for \kbd{gerepile}.
\subsec{\kbd{Qevproj}}
\fun{GEN}{Qevproj_init}{GEN M} let $M$ be a $n\times d$ \kbd{ZM} of
maximal rank $d \leq n$, representing the basis of a $\Q$-subspace
$V$ of $\Q^n$. Return a projector on $V$, to be used by \tet{Qevproj_apply}.
The interface details may change in the future, but this function currently
returns $[M, B,D,p]$, where $p$ is a \typ{VECSMALL} with $d$ entries
such that the submatrix $A = \kbd{rowpermute}(M,p)$ is invertible, $B$ is a
\kbd{ZM} and $d$ a \typ{INT} such that $A B = D \Id_d$.
\fun{GEN}{Qevproj_apply}{GEN T, GEN pro} let $T$ be an $n\times n$
\kbd{QM}, stabilizing a $\Q$-subspace $V\subset \Q^n$ of dimension $d$, and
let \kbd{pro} be a projector on that subspace initialized by
\tet{Qevproj_init}$(M)$. Return the $d\times d$ matrix representing $T_{|V}$
on the basis given by the columns of $M$.
\fun{GEN}{Qevproj_apply_vecei}{GEN T, GEN pro, long k} as
\tet{Qevproj_apply}, return only the image of the $k$-th basis vector $M[k]$
(still on the basis given by the columns of $M$).
\fun{GEN}{Qevproj_down}{GEN T, GEN pro} given a \kbd{ZC} (resp.~a \kbd{ZM})
$T$ representing an element (resp.~a vector of elements) in the subspace $V$
return a \kbd{QC} (resp.~a \kbd{QM}) $U$ such that $T = MU$.
\subsec{\kbd{zv}, \kbd{zm}}
\fun{GEN}{identity_zv}{long n} return the \typ{VECSMALL} $[1, 2, \dots, n]$.
\fun{GEN}{random_zv}{long n} returns a random \kbd{zv} with $n$ components.
\fun{GEN}{zv_abs}{GEN x} return $[|x[1]|,\ldots,|x[n]|]$ as a \kbd{zv}.
\fun{GEN}{zv_neg}{GEN x} return $-x$. No check for overflow is done, which
occurs in the fringe case where an entry is equal to $2^{\B-1}$.
\fun{GEN}{zv_neg_inplace}{GEN x} negates $x$ in place and return it. No check
for overflow is done, which occurs in the fringe case where an entry is equal
to $2^{\B-1}$.
\fun{GEN}{zm_zc_mul}{GEN x, GEN y}
\fun{GEN}{zm_mul}{GEN x, GEN y}
\fun{GEN}{zv_z_mul}{GEN x, long n} return $n\*x$. No check for overflow is
done.
\fun{long}{zv_content}{GEN x} returns the gcd of the entries of $x$.
\fun{long}{zv_dotproduct}{GEN x, GEN y}
\fun{long}{zv_prod}{GEN x} returns the product of all the components
of~\kbd{x} (assumes no overflow occurs).
\fun{GEN}{zv_prod_Z}{GEN x} returns the product of all the components
of~\kbd{x}; consider all $x[i]$ as \kbd{ulong}s.
\fun{long}{zv_sum}{GEN x} returns the sum of all the components
of~\kbd{x} (assumes no overflow occurs).
\fun{long}{zv_sumpart}{GEN v, long n} returns the sum $v[1] + \dots + v[n]$
(assumes no overflow occurs and \kbd{lg}$(v) > n$).
\fun{int}{zv_cmp0}{GEN x} returns 1 if all entries of the \kbd{zv} $x$ are $0$,
and $0$ otherwise.
\fun{int}{zv_equal}{GEN x, GEN y} returns $1$ if the two \kbd{zv} are equal
and $0$ otherwise.
\fun{int}{zv_equal0}{GEN x} returns $1$ if all entries are $0$, and return
$0$ otherwise.
\fun{long}{zv_search}{GEN L, long y} look for $y$ in the sorted
\kbd{zv} $L$. Return an index $i$ such that $L[i] = y$, and $0$ otherwise.
\fun{GEN}{zv_copy}{GEN x} as \kbd{Flv\_copy}.
\fun{GEN}{zm_transpose}{GEN x} as \kbd{Flm\_transpose}.
\fun{GEN}{zm_copy}{GEN x} as \kbd{Flm\_copy}.
\fun{GEN}{zero_zm}{long m, long n} as \kbd{zero\_Flm}.
\fun{GEN}{zero_zv}{long n} as \kbd{zero\_Flv}.
\fun{GEN}{zm_row}{GEN A, long x0} as \kbd{Flm\_row}.
\fun{GEN}{zv_diagonal}{GEN v} return the square \kbd{zm} whose diagonal
is given by the entries of $v$.
\fun{GEN}{zm_permanent}{GEN M} return the permanent of $M$.
The function assumes that the matrix is square of dimension
$< \kbd{BITS\_IN\_LONG}$.
\fun{int}{zvV_equal}{GEN x, GEN y} returns $1$ if the two \kbd{zvV} (vectors
of \kbd{zv}) are equal and $0$ otherwise.
\subsec{\kbd{ZMV} / \kbd{zmV} (vectors of \kbd{ZM}/\kbd{zm})}
\fun{int}{RgV_is_ZMV}{GEN x} Assuming \kbd{x} is a \typ{VEC}
or \typ{COL} return $1$ if its components are \kbd{ZM}, and $0$ otherwise.
\fun{GEN}{ZMV_to_zmV}{GEN z}
\fun{GEN}{zmV_to_ZMV}{GEN z}
\fun{GEN}{ZMV_to_FlmV}{GEN z, ulong m}
\subsec{\kbd{QC} / \kbd{QV}, \kbd{QM}}
\fun{GEN}{QM_mul}{GEN x, GEN y} multiplies \kbd{x} and \kbd{y} (assumed to
have compatible dimensions).
\fun{GEN}{QM_sqr}{GEN x} returns the square of \kbd{x} (assumed to be square).
\fun{GEN}{QM_QC_mul}{GEN x, GEN y} multiplies \kbd{x} and \kbd{y} (assumed to
have compatible dimensions).
\fun{GEN}{QM_det}{GEN M} returns the determinant of $M$.
\fun{GEN}{QM_ker}{GEN x} returns \kbd{matker(x)}.
\subsec{\kbd{RgC} / \kbd{RgV}, \kbd{RgM}}
\kbd{RgC} and \kbd{RgV} routines assume the inputs are \kbd{VEC} or \kbd{COL}
of the same dimension. \kbd{RgM} assume the inputs are \kbd{MAT} of
compatible dimensions.
\subsubsec{Matrix arithmetic}
\fun{void}{RgM_dimensions}{GEN x, long *m, long *n} sets $m$, resp.~$n$, to
the number of rows, resp.~columns of the \typ{MAT} $x$.
\fun{GEN}{RgC_add}{GEN x, GEN y} returns $x + y$ as a \typ{COL}.
\fun{GEN}{RgC_neg}{GEN x} returns $-x$ as a \typ{COL}.
\fun{GEN}{RgC_sub}{GEN x, GEN y} returns $x - y$ as a \typ{COL}.
\fun{GEN}{RgV_add}{GEN x, GEN y} returns $x + y$ as a \typ{VEC}.
\fun{GEN}{RgV_neg}{GEN x} returns $-x$ as a \typ{VEC}.
\fun{GEN}{RgV_sub}{GEN x, GEN y} returns $x - y$ as a \typ{VEC}.
\fun{GEN}{RgM_add}{GEN x, GEN y} return $x+y$.
\fun{GEN}{RgM_neg}{GEN x} returns $-x$.
\fun{GEN}{RgM_sub}{GEN x, GEN y} returns $x-y$.
\fun{GEN}{RgM_Rg_add}{GEN x, GEN y} assuming $x$ is a square matrix
and $y$ a scalar, returns the square matrix $x + y*\text{Id}$.
\fun{GEN}{RgM_Rg_add_shallow}{GEN x, GEN y} as \kbd{RgM\_Rg\_add} with much
fewer copies. Not suitable for \kbd{gerepileupto}.
\fun{GEN}{RgM_Rg_sub}{GEN x, GEN y} assuming $x$ is a square matrix
and $y$ a scalar, returns the square matrix $x - y*\text{Id}$.
\fun{GEN}{RgM_Rg_sub_shallow}{GEN x, GEN y} as \kbd{RgM\_Rg\_sub} with much
fewer copies. Not suitable for \kbd{gerepileupto}.
\fun{GEN}{RgC_Rg_add}{GEN x, GEN y} assuming $x$ is a nonempty column vector
and $y$ a scalar, returns the vector $[x_1 + y, x_2,\dots,x_n]$.
\fun{GEN}{RgC_Rg_sub}{GEN x, GEN y} assuming $x$ is a nonempty column vector
and $y$ a scalar, returns the vector $[x_1 - y, x_2,\dots,x_n]$.
\fun{GEN}{Rg_RgC_sub}{GEN a, GEN x} assuming $x$ is a nonempty column vector
and $a$ a scalar, returns the vector $[a - x_1, -x_2,\dots,-x_n]$.
\fun{GEN}{RgC_Rg_div}{GEN x, GEN y}
\fun{GEN}{RgM_Rg_div}{GEN x, GEN y} returns $x/y$ ($y$ treated as a scalar).
\fun{GEN}{RgC_Rg_mul}{GEN x, GEN y}
\fun{GEN}{RgV_Rg_mul}{GEN x, GEN y}
\fun{GEN}{RgM_Rg_mul}{GEN x, GEN y} returns $x\times y$ ($y$ treated as a
scalar).
\fun{GEN}{RgV_RgC_mul}{GEN x, GEN y} returns $x\times y$.
\fun{GEN}{RgV_RgM_mul}{GEN x, GEN y} returns $x\times y$.
\fun{GEN}{RgM_RgC_mul}{GEN x, GEN y} returns $x\times y$.
\fun{GEN}{RgM_RgX_mul}{GEN x, GEN T} returns $x \times y$, where $y$
is \kbd{RgX\_to\_RgC}$(T, \kbd{lg}(x)-1)$.
\fun{GEN}{RgM_mul}{GEN x, GEN y} returns $x\times y$.
\fun{GEN}{RgM_ZM_mul}{GEN x, GEN y} returns $x\times y$ assuming that $y$ is
a \kbd{ZM}.
\fun{GEN}{RgM_transmul}{GEN x, GEN y} returns $x\til \times y$.
\fun{GEN}{RgM_multosym}{GEN x, GEN y} returns $x\times y$, assuming
the result is a symmetric matrix (about twice faster than a generic matrix
multiplication).
\fun{GEN}{RgM_transmultosym}{GEN x, GEN y} returns $x\til \times y$, assuming
the result is a symmetric matrix (about twice faster than a generic matrix
multiplication).
\fun{GEN}{RgMrow_RgC_mul}{GEN x, GEN y, long i} multiplies the $i$-th row of
\kbd{RgM}~\kbd{x} by the \kbd{RgC}~\kbd{y} (seen as a column vector, assumed
to have compatible dimensions). Assumes that $x$ is nonempty and $0 < i <
\kbd{lg(x[1])}$.
\fun{GEN}{RgM_mulreal}{GEN x, GEN y} returns the real part of $x\times y$
(whose entries are \typ{INT}, \typ{FRAC}, \typ{REAL} or \typ{COMPLEX}).
\fun{GEN}{RgM_sqr}{GEN x} returns $x^2$.
\fun{GEN}{RgC_RgV_mul}{GEN x, GEN y} returns $x\times y$ (the matrix
$(x_iy_j)$).
\fun{GEN}{RgC_RgV_mulrealsym}{GEN x, GEN y} returns the real part of $x\times
y$ (whose entries are \typ{INT}, \typ{FRAC}, \typ{REAL} or \typ{COMPLEX}),
assuming the result is symmetric.
The following two functions are not well defined in general and only provided
for convenience in specific cases:
\fun{GEN}{RgC_RgM_mul}{GEN x, GEN y} returns $x\times y[1,]$ if $y$ is
a row matrix $1\times n$, error otherwise.
\fun{GEN}{RgM_RgV_mul}{GEN x, GEN y} returns $x\times y[,1]$ if $y$ is
a column matrix $n\times 1$, error otherwise.
\fun{GEN}{RgM_powers}{GEN x, long n} returns $[\kbd{x}^0,
\dots, \kbd{x}^\kbd{n}]$ as a \typ{VEC} of \kbd{RgM}s.
\smallskip
\fun{GEN}{RgV_sum}{GEN v} sum of the entries of $v$
\fun{GEN}{RgV_prod}{GEN v} product of the entries of $v$, using
a divide and conquer strategy
\fun{GEN}{RgV_sumpart}{GEN v, long n} returns the sum $v[1] + \dots + v[n]$
(assumes that \kbd{lg}$(v) > n$).
\fun{GEN}{RgV_sumpart2}{GEN v, long m, long n} returns the sum $v[m] + \dots +
v[n]$ (assumes that \kbd{lg}$(v) > n$ and $m > 0$). Returns \kbd{gen\_0}
when $m > n$.
\fun{GEN}{RgM_sumcol}{GEN v} returns a \typ{COL}, sum of the columns of the
\typ{MAT} $v$.
\fun{GEN}{RgV_dotproduct}{GEN x,GEN y} returns the scalar product of $x$ and $y$
\fun{GEN}{RgV_dotsquare}{GEN x} returns the scalar product of $x$ with itself.
\fun{GEN}{RgV_kill0}{GEN v} returns a shallow copy of $v$ where entries
matched by \kbd{gequal0} are replaced by \kbd{NULL}. The return value
is not a valid \kbd{GEN} and must be handled specially. The idea is
to pre-treat a vector of coefficients to speed up later linear combinations
or scalar products.
\fun{GEN}{gram_matrix}{GEN v} returns the \idx{Gram matrix} $(v_i\cdot v_j)$
attached to the entries of $v$ (matrix, or vector of vectors).
\fun{GEN}{RgV_polint}{GEN X, GEN Y, long v} $X$ and $Y$ being two vectors of
the same length, returns the polynomial $T$ in variable $v$ such that
$T(X[i]) = Y[i]$ for all $i$. The special case $X = \kbd{NULL}$
corresponds to $X = [1,2,\dots,n]$, where $n$ is the length of $Y$.
This is the function underlying \kbd{polint} for formal
interpolation.
\fun{GEN}{polintspec}{GEN X, GEN Y, GEN t, long n, long *pe}
return $P(t)$ where $P$ is the Lagrange interpolation polynomial
attached to the $n$ points $(X[0],Y[0]), \dots, (X[n-1],Y[n-1])$.
If \kbd{pe} is not \kbd{NULL} and $t$ is a complex numeric value, \kbd{*pe}
contains an error estimate for the returned value (Neville's algorithm, see
\kbd{polinterpolate}). In extrapolation algorithms, e.g., Romberg
integration, this function is usually called on actual \kbd{GEN} vectors
with offsets: $x + k$ and $y + k$ so as to interpolate on $x[k..k+n-1]$
without having to use \kbd{vecslice}.
This is the function underlying \kbd{polint} for numerical
interpolation.
\fun{GEN}{polint_i}{GEN X, GEN Y, GEN t, long *pe} as \kbd{polintspec},
where $X$ and $Y$ are actual \kbd{GEN} vectors.
\fun{GEN}{vandermondeinverse}{GEN r, GEN T, GEN d, GEN V} Given a vector $r$
of $n$ scalars and the \typ{POL} $T = \prod_{i=1}^n (X - r_i)$,
return $dM^{-1}$, where $M = (r_i^{j-1})_{1\leq i,j\leq n}$ is the van der
Monde matrix; $V$ is \kbd{NULL} or a vector containing the $T'(r_i)$, as
returned by \kbd{vandermodeinverseinit}. The demonimator $d$ may be set to
\kbd{NULL} (handled as $1$). If $c$ is the $k$-column of the result, it is
essentially $d$ times the $k$-th Lagrange interpolation polynomial: we have
$\sum_j c_j r_i^{j-1} = d \delta_{i=k}$. This is the function underlying
\kbd{RgV\_polint} when the base field is not $\Z/p\Z$: it uses $O(n^2)$
scalar operations and is asymptotically slower than variants using
multi-evaluation such as \kbd{FpV\_polint}; it is also accurate over inexact
fields.
\fun{GEN}{vandermondeinverseinit}{GEN r} Given a vector $r$ of $n$ scalars, let
$T$ be the \typ{POL} $T = \prod_{j=1}^n (X - r_j)$. This function returns the
$T'(r_i)$ computed stably via products of difference: the $i$-th entry is
$T'(r_i) = \prod_{j\neq i} (r_i - r_j)$. It is asymptotically slow (uses
$O(n^2)$ scalar operations, where multi-evaluation achieves quasi-linear
running time) but allows accurate computation at low accuracies when $T$ has
large complex coefficients.
\subsubsec{Special shapes}
The following routines check whether matrices or vectors have a special
shape, using \kbd{gequal1} and \kbd{gequal0} to test components. (This makes
a difference when components are inexact.)
\fun{int}{RgV_isscalar}{GEN x} return 1 if all the entries of $x$ are $0$
(as per \kbd{gequal0}), except possibly the first one. The name comes from
vectors expressing polynomials on the standard basis $1,T,\dots, T^{n-1}$, or
on \kbd{nf.zk} (whose first element is $1$).
\fun{int}{QV_isscalar}{GEN x} as \kbd{RgV\_isscalar}, assuming $x$ is a
\kbd{QV} (\typ{INT} and \typ{FRAC} entries only).
\fun{int}{ZV_isscalar}{GEN x} as \kbd{RgV\_isscalar}, assuming $x$ is a
\kbd{ZV} (\typ{INT} entries only).
\fun{int}{RgM_isscalar}{GEN x, GEN s} return 1 if $x$ is the scalar matrix
equal to $s$ times the identity, and 0 otherwise. If $s$ is \kbd{NULL}, test
whether $x$ is an arbitrary scalar matrix.
\fun{int}{RgM_isidentity}{GEN x} return 1 if the \typ{MAT} $x$ is the
identity matrix, and 0 otherwise.
\fun{int}{RgM_isdiagonal}{GEN x} return 1 if the \typ{MAT} $x$ is a
diagonal matrix, and 0 otherwise.
\fun{long}{RgC_is_ei}{GEN x} return $i$ if the \typ{COL} $x$ has $0$ entries,
but for a $1$ at position $i$.
\fun{int}{RgM_is_ZM}{GEN x} return 1 if the \typ{MAT}~$x$ has only
\typ{INT} coefficients, and 0 otherwise.
\fun{long}{qfiseven}{GEN M} return 1 if the square symmetric typ{ZM}~$x$
is an even quadratic form (all diagonal coefficients are even), and 0 otherwise.
\fun{int}{RgM_is_QM}{GEN x} return 1 if the \typ{MAT}~$x$ has only
\typ{INT} or \typ{FRAC} coefficients, and 0 otherwise.
\fun{long}{RgV_isin}{GEN v, GEN x} return the first index $i$ such that
$v[i] = x$ if it exists, and $0$ otherwise. Naive search in linear time, does
not assume that \kbd{v} is sorted.
\fun{long}{RgV_isin_i}{GEN v, GEN x, long n} return the first index $i\ leq n$
such that $v[i] = x$ if it exists, and $0$ otherwise. Naive search in linear
time, does not assume that \kbd{v} is sorted. Assume that $n < \kbd{lg(v)}$.
\fun{GEN}{RgM_diagonal}{GEN m} returns the diagonal of $m$ as a \typ{VEC}.
\fun{GEN}{RgM_diagonal_shallow}{GEN m} shallow version of \kbd{RgM\_diagonal}
\subsubsec{Conversion to floating point entries}
\fun{GEN}{RgC_gtofp}{GEN x, GEN prec} returns the \typ{COL} obtained by
applying \kbd{gtofp(gel(x,i), prec)} to all coefficients of $x$.
\fun{GEN}{RgV_gtofp}{GEN x, GEN prec} returns the \typ{VEC} obtained by
applying \kbd{gtofp(gel(x,i), prec)} to all coefficients of $x$.
\fun{GEN}{RgC_gtomp}{GEN x, long prec} returns the \typ{COL} obtained by
applying \kbd{gtomp(gel(x,i), prec)} to all coefficients of $x$.
\fun{GEN}{RgC_fpnorml2}{GEN x, long prec} returns (a stack-clean variant of)
\bprog
gnorml2( RgC_gtofp(x, prec) )
@eprog
\fun{GEN}{RgM_gtofp}{GEN x, GEN prec} returns the \typ{MAT} obtained by
applying \kbd{gtofp(gel(x,i), prec)} to all coefficients of $x$.
\fun{GEN}{RgM_gtomp}{GEN x, long prec} returns the \typ{MAT} obtained by
applying \kbd{gtomp(gel(x,i), prec)} to all coefficients of $x$.
\fun{GEN}{RgM_fpnorml2}{GEN x, long prec} returns (a stack-clean variant of)
\bprog
gnorml2( RgM_gtofp(x, prec) )
@eprog
\subsubsec{Linear algebra, linear systems}
\fun{GEN}{RgM_inv}{GEN a} returns a left inverse of $a$ (which needs not be
square), or \kbd{NULL} if this turns out to be impossible. The latter
happens when the matrix does not have maximal rank (or when rounding errors
make it appear so).
\fun{GEN}{RgM_inv_upper}{GEN a} as \kbd{RgM\_inv}, assuming that $a$ is a
nonempty invertible upper triangular matrix, hence a little faster.
\fun{GEN}{RgM_RgC_invimage}{GEN A, GEN B} returns a \typ{COL} $X$ such that
$A X = B$ if one such exists, and \kbd{NULL} otherwise.
\fun{GEN}{RgM_invimage}{GEN A, GEN B} returns a \typ{MAT} $X$ such that
$A X = B$ if one such exists, and \kbd{NULL} otherwise.
\fun{GEN}{RgM_Hadamard}{GEN a} returns a upper bound for the absolute
value of $\text{det}(a)$. The bound is a \typ{INT}.
\fun{GEN}{RgM_solve}{GEN a, GEN b} returns $a^{-1}b$ where $a$ is a square
\typ{MAT} and $b$ is a \typ{COL} or \typ{MAT}. Returns \kbd{NULL} if $a^{-1}$
cannot be computed, see \tet{RgM_inv}.
If $b = \kbd{NULL}$, the matrix $a$ need no longer be square, and we strive
to return a left inverse for $a$ (\kbd{NULL} if it does not exist).
\fun{GEN}{RgM_solve_realimag}{GEN M, GEN b} $M$ being a \typ{MAT}
with $r_1+r_2$ rows and $r_1+2r_2$ columns, $y$ a \typ{COL} or \typ{MAT}
such that the equation $Mx = y$ makes sense, returns $x$ under the following
simplifying assumptions: the first $r_1$ rows of $M$ and $y$ are real
(the $r_2$ others are complex), and $x$ is real. This is stabler and faster
than calling $\kbd{RgM\_solve}(M, b)$ over $\C$. In most applications,
$M$ approximates the complex embeddings of an integer basis in a number
field, and $x$ is actually rational.
\fun{GEN}{split_realimag}{GEN x, long r1, long r2} $x$ is a \typ{COL} or
\typ{MAT} with $r_1 + r_2$ rows, whose first $r_1$ rows have real entries
(the $r_2$ others are complex). Return an object of the same type as
$x$ and $r_1 + 2r_2$ rows, such that the first $r_1 + r_2$ rows contain
the real part of $x$, and the $r_2$ following ones contain the imaginary part
of the last $r_2$ rows of $x$. Called by \tet{RgM_solve_realimag}.
\fun{GEN}{RgM_det_triangular}{GEN x} returns the product of the diagonal
entries of $x$ (its determinant if it is indeed triangular).
\fun{GEN}{Frobeniusform}{GEN V, long n} given the vector $V$ of elementary
divisors for $M - x\text{Id}$, where $M$ is an $n\times n$ square matrix.
Returns the Frobenius form of $M$.
\fun{int}{RgM_QR_init}{GEN x, GEN *pB, GEN *pQ, GEN *pL, long prec}
QR-decomposition of a square invertible \typ{MAT} $x$ with real coefficients.
Sets \kbd{*pB} to the vector of squared lengths of the $x[i]$, \kbd{*pL} to
the Gram-Schmidt coefficients and \kbd{*pQ} to a vector of successive
Householder transforms. If $R$ denotes the transpose of $L$ and $Q$ is the
result of applying \kbd{*pQ} to the identity matrix, then $x = QR$ is the QR
decomposition of $x$. Returns $0$ is $x$ is not invertible or we hit a
precision problem, and $1$ otherwise.
\fun{int}{QR_init}{GEN x, GEN *pB, GEN *pQ, GEN *pL, long prec} as
\kbd{RgM\_QR\_init}, assuming further that $x$ has \typ{INT} or \typ{REAL}
coefficients.
\fun{GEN}{R_from_QR}{GEN x, long prec} assuming that $x$ is a square
invertible \typ{MAT} with \typ{INT} or \typ{REAL} coefficients, return
the upper triangular $R$ from the $QR$ docomposition of $x$. Not memory
clean. If the matrix is not known to have \typ{INT} or \typ{REAL}
coefficients, apply \tet{RgM_gtomp} first.
\fun{GEN}{gaussred_from_QR}{GEN x, long prec} assuming that $x$ is a square
invertible \typ{MAT} with \typ{INT} or \typ{REAL} coefficients, returns
\kbd{qfgaussred(x\til * x)}; this is essentially the upper triangular $R$
matrix from the $QR$ decomposition of $x$, renormalized to accomodate
\kbd{qfgaussred} conventions. Not memory clean.
\fun{GEN}{RgM_gram_schmidt}{GEN e, GEN *ptB} naive (unstable) Gram-Schmidt
orthogonalization of the basis $(e_i)$ given by the columns of \typ{MAT} $e$.
Return the $e_i^*$ (as columns of a \typ{MAT}) and set \kbd{*ptB} to the
vector of squared lengths $|e_i^*|^2$.
\fun{GEN}{RgM_Babai}{GEN M, GEN y} given a \typ{MAT} $M$ of maximal rank $n$
and a \typ{COL} $y$ of the same dimension, apply Babai's nearest plane
algorithm to return an \emph{integral} $x$ such that $y - Mx$ has small $L_2$
norm. This yields an approximate solution to the closest vector problem: if
$M$ is LLL-reduced, then
$$|| y - Mx ||_2 \leq 2 (2/\sqrt{3})^n || y - MX ||_2$$
for all $X \in \Z^n$.
\subsec{\kbd{ZG}}
Let $G$ be a multiplicative group with neutral element $1_G$ whose
multiplication is supported by \kbd{gmul} and where equality test is
performed using \tet{gidentical}, e.g. a matrix group. The following
routines implement basic computations in the group algebra $\Z[G]$. All of
them are shallow for efficiency reasons. A \kbd{ZG} is either
\item a \typ{INT} $n$, representing $n[1_G]$
\item or a ``factorization matrix'' with two columns $[g,e]$: the first one
contains group elements, sorted according to \tet{cmp_universal}, and the
second one contains integer ``exponents'', representing $\sum e_i [g_i]$.
Note that \tet{to_famat} and \tet{to_famat_shallow}$(g,e)$ allow to build
the \kbd{ZG} $e[g]$ from $e\in \Z$ and $g\in G$.
\fun{GEN}{ZG_normalize}{GEN x} given a \typ{INT} $x$ or a factorization
matrix \emph{without} assuming that the first column is properly sorted.
Return a valid (sorted) \kbd{ZG}. Shallow function.
\fun{GEN}{ZG_add}{GEN x, GEN y} return $x+y$; shallow function.
\fun{GEN}{ZG_neg}{GEN x} return $-x$; shallow function.
\fun{GEN}{ZG_sub}{GEN x, GEN y} return $x-y$; shallow function.
\fun{GEN}{ZG_mul}{GEN x, GEN y} return $xy$; shallow function.
\fun{GEN}{ZG_G_mul}{GEN x, GEN y} given a \kbd{ZG} $x$ and $y\in G$,
return $xy$; shallow function.
\fun{GEN}{G_ZG_mul}{GEN x, GEN y} given a \kbd{ZG} $y$ and $x\in G$,
return $xy$; shallow function.
\fun{GEN}{ZG_Z_mul}{GEN x, GEN n} given a \kbd{ZG} $x$ and $y\in \Z$,
return $xy$; shallow function.
\fun{GEN}{ZGC_G_mul}{GEN v, GEN x} given $v$ a vector of \kbd{ZG} and $x\in
G$ return the vector (with the same type as $v$ with entries $v[i]\cdot x$.
Shallow function.
\fun{void}{ZGC_G_mul_inplace}{GEN v, GEN x} as \tet{ZGC_G_mul}, modifying
$v$ in place.
\fun{GEN}{ZGC_Z_mul}{GEN v, GEN n} given $v$ a vector of \kbd{ZG} and $n\in
Z$ return the vector (with the same type as $v$ with entries $n \cdot v[i]$.
Shallow function.
\fun{GEN}{G_ZGC_mul}{GEN x, GEN v} given $v$ a vector of \kbd{ZG} and $x\in
G$ return the vector of $x \cdot v[i]$. Shallow function.
\fun{GEN}{ZGCs_add}{GEN x, GEN y} add two sparse vectors of
\kbd{ZG} elements (see Sparse linear algebra below).
\subsec{Sparse and blackbox linear algebra}
A sparse column \kbd{zCs} $v$ is a \typ{COL} with two components $C$ and $E$
which are \typ{VECSMALL} of the same length, representing $\sum_i
E[i]*e_{C[i]}$, where $(e_j)$ is the canonical basis. A sparse matrix
(\kbd{zMs}) is a \typ{VEC} of \kbd{zCs}.
\kbd{FpCs} and \kbd{FpMs} are identical to the above, but $E[i]$ is now
interpreted as a \emph{signed} C long integer representing an element of
$\F_p$. This is important since $p$ can be so large that $p+E[i]$ would not
fit in a C long.
\kbd{RgCs} and \kbd{RgMs} are similar, except that the type of the components
of $E$ is now unspecified. Functions handling those later objects
must not depend on the type of those components.
\kbd{F2Ms} are \typ{VEC} of \kbd{F2Cs}. \kbd{F2Cs} are \typ{VECSMALL} whoses
entries are the nonzero coefficients ($1$).
It is not possible to derive the space dimension (number of rows) from the
above data. Thus most functions take an argument \kbd{nbrow} which is the
number of rows of the corresponding column/matrix in dense representation.
\fun{GEN}{F2Ms_to_F2m}{GEN M, long nbrow} convert a \kbd{F2m} to a \kbd{F2Ms}.
\fun{GEN}{F2m_to_F2Ms}{GEN M} convert a \kbd{F2m} to a \kbd{F2Ms}.
\fun{GEN}{zCs_to_ZC}{GEN C, long nbrow} convert the sparse vector $C$
to a dense \kbd{ZC} of dimension \kbd{nbrow}.
\fun{GEN}{zMs_to_ZM}{GEN M, long nbrow} convert the sparse matrix $M$
to a dense \kbd{ZM} whose columns have dimension \kbd{nbrow}.
\fun{GEN}{FpMs_FpC_mul}{GEN M, GEN B, GEN p} multiply the sparse matrix $M$
(over $\F_p$) by the \kbd{FpC} $B$. The result is an \kbd{FpC}, i.e.~a
dense vector.
\fun{GEN}{zMs_ZC_mul}{GEN M, GEN B, GEN p} multiply the sparse matrix $M$
by the \kbd{ZC} $B$ (over $\Z$). The result is an \kbd{ZC}, i.e.~a
dense vector.
\fun{GEN}{FpV_FpMs_mul}{GEN B, GEN M, GEN p} multiply the \kbd{FpV} $B$
by the sparse matrix $M$ (over $\F_p$). The result is an \kbd{FpV}, i.e.~a
dense vector.
\fun{GEN}{ZV_zMs_mul}{GEN B, GEN M, GEN p} multiply the \kbd{FpV} $B$ (over
$\Z$) by the sparse matrix $M$. The result is an \kbd{ZV}, i.e.~a
dense vector.
\fun{void}{RgMs_structelim}{GEN M, long nbrow, GEN A, GEN *p_col, GEN *p_row}
$M$ being a RgMs with \kbd{nbrow} rows, $A$ being a list of row indices,
perform structured elimination on $M$ by removing some rows and columns until
the number of effectively present rows is equal to the number of columns.
The result is stored in two \typ{VECSMALL}s, \kbd{*p\_col} and \kbd{*p\_row}:
\kbd{*p\_col} is a map from the new columns indices to the old one.
\kbd{*p\_row} is a map from the old rows indices to the new one ($0$ if removed).
\fun{GEN}{F2Ms_colelim}{GEN M, long nbrow} returns some subset of the columns
of $M$ as a \typ{VECSMALL} of indices, selected such that the dimension of the
kernel of the matrix is preserved. The subset is not guaranteed to be minimal.
\fun{GEN}{F2Ms_ker}{GEN M, long nbrow} returns some kernel vectors of $M$
using block Lanczos algorithm.
\fun{GEN}{FpMs_leftkernel_elt}{GEN M, long nbrow, GEN p}
$M$ being a sparse matrix over $\F_p$, return a nonzero \kbd{FpV} $X$ such
that $X\*M$ components are almost all $0$.
\fun{GEN}{FpMs_FpCs_solve}{GEN M, GEN B, long nbrow, GEN p}
solve the equation $M\*X = B$, where $M$ is a sparse matrix and $B$ is a sparse
vector, both over $\F_p$. Return either a solution as a \typ{COL} (dense
vector), the index of a column which is linearly dependent from the
others as a \typ{VECSMALL} with a single component, or \kbd{NULL}
(can happen if $B$ is not in the image of $M$).
\fun{GEN}{FpMs_FpCs_solve_safe}{GEN M, GEN B, long nbrow, GEN p}
as above, but in the event that $p$ is not a prime and an impossible division
occurs, return \kbd{NULL}.
\fun{GEN}{ZpMs_ZpCs_solve}{GEN M, GEN B, long nbrow, GEN p, long e}
solve the equation $MX = B$, where $M$ is a sparse matrix and $B$ is a sparse
vector, both over $\Z/p^e\Z$. Return either a solution as a \typ{COL} (dense
vector), or the index of a column which is linearly dependent from the
others as a \typ{VECSMALL} with a single component.
\fun{GEN}{gen_FpM_Wiedemann}{void *E, GEN (*f)(void*, GEN), GEN B, GEN p}
solve the equation $f(X) = B$ over $\F_p$, where $B$ is a \kbd{FpV}, and $f$
is a blackbox endomorphism, where $f(E, X)$ computes the value of $f$ at the
(dense) column vector $X$. Returns either a solution \typ{COL}, or a kernel
vector as a \typ{VEC}.
\fun{GEN}{gen_ZpM_Dixon_Wiedemann}{void *E, GEN (*f)(void*, GEN), GEN B, GEN p, long e}
solve equation $f(X) = B$ over $\Z/p^e\Z$, where $B$ is a \kbd{ZV}, and $f$ is a
blackbox endomorphism, where $f(E, X)$ computes the value of $f$ at the
(dense) column vector $X$. Returns either a solution \typ{COL}, or a kernel
vector as a \typ{VEC}.
\subsec{Obsolete functions}
The functions in this section are kept for backward compatibility only
and will eventually disappear.
\fun{GEN}{image2}{GEN x} compute the image of $x$ using a very slow
algorithm. Use \tet{image} instead.
\section{Integral, rational and generic polynomial arithmetic}
\subsec{\kbd{ZX}}
\fun{void}{RgX_check_ZX}{GEN x, const char *s} Assuming \kbd{x} is a \typ{POL}
raise an error if it is not a \kbd{ZX} ($s$ should point to the name of the
caller).
\fun{GEN}{ZX_copy}{GEN x,GEN p} returns a copy of \kbd{x}.
\fun{long}{ZX_max_lg}{GEN x} returns the effective length of the longest
component in $x$.
\fun{GEN}{scalar_ZX}{GEN x, long v} returns the constant \kbd{ZX} in variable
$v$ equal to the \typ{INT} $x$.
\fun{GEN}{scalar_ZX_shallow}{GEN x, long v} returns the constant \kbd{ZX} in
variable $v$ equal to the \typ{INT} $x$. Shallow function not suitable for
\kbd{gerepile} and friends.
\fun{GEN}{ZX_renormalize}{GEN x, long l}, as \kbd{normalizepol}, where
$\kbd{l} = \kbd{lg(x)}$, in place.
\fun{int}{ZX_equal}{GEN x, GEN y} returns $1$ if the two \kbd{ZX} have
the same \kbd{degpol} and their coefficients are equal. Variable numbers are
not checked.
\fun{int}{ZX_equal1}{GEN x} returns $1$ if the \kbd{ZX} $x$ is equal to $1$
and $0$ otherwise.
\fun{int}{ZX_is_monic}{GEN x} returns $1$ if the \kbd{ZX} $x$ is monic and $0$
otherwise. The zero polynomial considered not monic.
\fun{GEN}{ZX_add}{GEN x,GEN y} adds \kbd{x} and \kbd{y}.
\fun{GEN}{ZX_sub}{GEN x,GEN y} subtracts \kbd{x} and \kbd{y}.
\fun{GEN}{ZX_neg}{GEN x} returns $-\kbd{x}$.
\fun{GEN}{ZX_Z_add}{GEN x,GEN y} adds the integer \kbd{y} to the
\kbd{ZX}~\kbd{x}.
\fun{GEN}{ZX_Z_add_shallow}{GEN x,GEN y} shallow version of \tet{ZX_Z_add}.
\fun{GEN}{ZX_Z_sub}{GEN x,GEN y} subtracts the integer \kbd{y} to the
\kbd{ZX}~\kbd{x}.
\fun{GEN}{Z_ZX_sub}{GEN x,GEN y} subtracts the \kbd{ZX} \kbd{y} to the
integer \kbd{x}.
\fun{GEN}{ZX_Z_mul}{GEN x,GEN y} multiplies the \kbd{ZX} \kbd{x} by the
integer \kbd{y}.
\fun{GEN}{ZX_mulu}{GEN x, ulong y} multiplies \kbd{x} by the integer \kbd{y}.
\fun{GEN}{ZX_shifti}{GEN x, long n} shifts all coefficients of \kbd{x} by $n$
bits, which can be negative.
\fun{GEN}{ZX_Z_divexact}{GEN x, GEN y} returns $x/y$ assuming all divisions
are exact.
\fun{GEN}{ZX_divuexact}{GEN x, ulong y} returns $x/y$ assuming all divisions
are exact.
\fun{GEN}{ZX_remi2n}{GEN x, long n} reduces all coefficients of \kbd{x} to
$n$ bits, using \tet{remi2n}.
\fun{GEN}{ZX_mul}{GEN x,GEN y} multiplies \kbd{x} and \kbd{y}.
\fun{GEN}{ZX_sqr}{GEN x,GEN p} returns $\kbd{x}^2$.
\fun{GEN}{ZX_mulspec}{GEN a, GEN b, long na, long nb}. Internal routine:
\kbd{a} and \kbd{b} are arrays of coefficients representing polynomials
$\sum_{i = 0}^{\kbd{na-1}} \kbd{a}[i] X^i$ and
$\sum_{i = 0}^{\kbd{nb-1}} \kbd{b}[i] X^i$. Returns their product (as a true
\kbd{GEN}) in variable $0$.
\fun{GEN}{ZX_sqrspec}{GEN a, long na}. Internal routine:
\kbd{a} is an array of coefficients representing polynomial
$\sum_{i = 0}^{\kbd{na-1}} \kbd{a}[i] X^i$. Return its square (as a true
\kbd{GEN}) in variable $0$.
\fun{GEN}{ZX_rem}{GEN x, GEN y} returns the remainder of the Euclidean
division of $x$ mod $y$. Assume that $x$, $y$ are two \kbd{ZX} and that
$y$ is monic.
\fun{GEN}{ZX_mod_Xnm1}{GEN T, ulong n} return $T$ modulo $X^n - 1)$. Shallow
function.
\fun{GEN}{ZX_div_by_X_1}{GEN T, GEN *r} return the quotient of $T$ by $X-1$.
If $r$ is not \kbd{NULL} set it to $T(1)$.
\fun{GEN}{ZX_digits}{GEN x, GEN B} returns a vector of \kbd{ZX}
$[c_0,\ldots,c_n]$ of degree less than the degree of $B$ and such that
$x=\sum_{i=0}^{n}{c_i\*B^i}$. Assume that $B$ is monic.
\fun{GEN}{ZXV_ZX_fromdigits}{GEN v, GEN B} where $v=[c_0,\ldots,c_n]$
is a vector of \kbd{ZX}, returns $\sum_{i=0}^{n}{c_i\*B^i}$.
\fun{GEN}{ZX_gcd}{GEN x,GEN y} returns a gcd of the \kbd{ZX} $x$ and $y$.
Not memory-clean, but suitable for \kbd{gerepileupto}.
\fun{GEN}{ZX_gcd_all}{GEN x, GEN y, GEN *pX} returns a gcd $d$ of $x$ and
$y$. If \kbd{pX} is not \kbd{NULL}, set $\kbd{*pX}$ to a (nonzero) integer
multiple of $x/d$. If $x$ and $y$ are both monic, then $d$ is monic and
\kbd{*pX} is exactly $x/d$. Not memory clean.
\fun{GEN}{ZX_radical}{GEN x} returns the largest squarefree divisor
of the \kbd{ZX} $x$. Not memory clean.
\fun{GEN}{ZX_content}{GEN x} returns the content of the \kbd{ZX} $x$.
\fun{long}{ZX_val}{GEN P} as \kbd{RgX\_val}, but assumes \kbd{P} has \typ{INT}
coefficients.
\fun{long}{ZX_valrem}{GEN P, GEN *z} as \kbd{RgX\_valrem}, but assumes
\kbd{P} has \typ{INT} coefficients.
\fun{GEN}{ZX_to_monic}{GEN q GEN *L} given $q$ a nonzero \kbd{ZX},
returns a monic integral polynomial $Q$ such that $Q(x) = C q(x/L)$, for some
rational $C$ and positive integer $L > 0$. If $\kbd{L}$ is not \kbd{NULL},
set \kbd{*L} to $L$; if $L = 1$, \kbd{*L} is set to \kbd{gen\_1}. Shallow
function.
\fun{GEN}{ZX_primitive_to_monic}{GEN q, GEN *L} as \tet{ZX_to_monic} except
$q$ is assumed to have trivial content, which avoids recomputing it.
The result is suboptimal if $q$ is not primitive ($L$ larger than
necessary), but remains correct. Shallow function.
\fun{GEN}{ZX_Z_normalize}{GEN q, GEN *L} a restricted version of
\kbd{ZX\_primitive\_to\_monic}, where $q$ is a \emph{monic} \kbd{ZX}
of degree $> 0$. Finds the largest integer $L > 0$ such that
$Q(X) := L^{-\deg q} q(Lx)$ is integral and return $Q$; this is not
well-defined if $q$ is a monomial, in that case, set $L=1$ and $Q = q$. If
\kbd{L} is not \kbd{NULL}, set \kbd{*L} to $L$. Shallow function.
\fun{GEN}{ZX_Q_normalize}{GEN q, GEN *L} a variant of \tet{ZX_Z_normalize}
where $L > 0$ is allowed to be rational, the monic $Q\in \Z[X]$ has possibly
smaller coefficients. Shallow function.
\fun{GEN}{ZX_Q_mul}{GEN x, GEN y} returns $x*y$, where $y$ is a rational number
and the resulting \typ{POL} has rational entries.
\fun{long}{ZX_deflate_order}{GEN P} given a nonconstant \kbd{ZX}
$P$, returns the largest exponent $d$ such that $P$ is of the form $P(x^d)$.
\fun{long}{ZX_deflate_max}{GEN P, long *d}. Given a nonconstant
polynomial with integer coefficients $P$, sets \kbd{d} to
\kbd{ZX\_deflate\_order(P)} and returns \kbd{RgX\_deflate(P,d)}. Shallow
function.
\fun{GEN}{ZX_rescale}{GEN P, GEN h} returns $h^{\deg(P)} P(x/h)$.
\kbd{P} is a \kbd{ZX} and \kbd{h} is a nonzero integer. Neither memory-clean
nor suitable for \kbd{gerepileupto}.
\fun{GEN}{ZX_rescale2n}{GEN P, long n} returns $2^{n\deg(P)} P(x>>n)$ where
\kbd{P} is a \kbd{ZX}.
\fun{GEN}{ZX_rescale_lt}{GEN P} returns the monic integral polynomial
$h^{\deg(P)-1} P(x/h)$, where \kbd{P} is a nonzero \kbd{ZX} and \kbd{h} is
its leading coefficient. Neither memory-clean nor suitable for
\kbd{gerepileupto}.
\fun{GEN}{ZX_translate}{GEN P, GEN c} assume $P$ is a \kbd{ZX} and $c$ an
integer. Returns $P(X + c)$ (optimized for $c = \pm 1$).
\fun{GEN}{ZX_affine}{GEN P, GEN a, GEN b} $P$ is a \kbd{ZX}, $a$ and $b$
are \typ{INT}. Return $P(aX + b)$ (optimized for $b = \pm 1$). Not memory
clean.
\fun{GEN}{ZX_Z_eval}{GEN P,GEN x} evaluate the \kbd{ZX} $P$ at the integer $x$.
\fun{GEN}{ZX_unscale}{GEN P, GEN h} given a \kbd{ZX} $P$ and a \typ{INT} $h$,
returns $P(hx)$. Not memory clean.
\fun{GEN}{ZX_z_unscale}{GEN P, long h} given a \kbd{ZX} $P$,
returns $P(hx)$. Not memory clean.
\fun{GEN}{ZX_unscale2n}{GEN P, long n} given a \kbd{ZX} $P$, returns
$P(x<