% Copyright (c) 2000  The PARI Group
%
% This file is part of the PARI/GP documentation
%
% Permission is granted to copy, distribute and/or modify this document
% under the terms of the GNU General Public License
\newpage
\chapter{Technical Reference Guide for Algebraic Number Theory}

\section{General Number Fields}

\subsec{Number field types}

None of the following routines thoroughly check their input: they
distinguish between \emph{bona fide} structures as output by PARI routines,
but designing perverse data will easily fool them. To give an example, a
square matrix will be interpreted as an ideal even though the $\Z$-module
generated by its columns may not be an $\Z_K$-module (i.e. the expensive
\kbd{nfisideal} routine will \emph{not} be called).

\fun{long}{nftyp}{GEN x}. Returns the type of number field structure stored in
\kbd{x}, \tet{typ_NF}, \tet{typ_BNF}, or \tet{typ_BNR}. Other answers
are possible, meaning \kbd{x} is not a number field structure.

\fun{GEN}{get_nf}{GEN x, long *t}. Extract an \var{nf} structure from
\kbd{x} if possible and return it, otherwise return \kbd{NULL}. Sets
\kbd{t} to the \kbd{nftyp} of \kbd{x} in any case.

\fun{GEN}{get_bnf}{GEN x, long *t}. Extract a \kbd{bnf} structure from
\kbd{x} if possible and return it, otherwise return \kbd{NULL}. Sets
\kbd{t} to the \kbd{nftyp} of \kbd{x} in any case.

\fun{GEN}{get_nfpol}{GEN x, GEN *nf} try to extract an \var{nf} structure
from \kbd{x}, and sets \kbd{*nf} to \kbd{NULL} (failure) or to the \var{nf}.
Returns the (monic, integral) polynomial defining the field.

\fun{GEN}{get_bnfpol}{GEN x, GEN *bnf, GEN *nf} try to extract a \var{bnf}
and an \var{nf} structure from \kbd{x}, and sets \kbd{*bnf}
and \kbd{*nf} to \kbd{NULL} (failure) or to the corresponding structure.
Returns the (monic, integral) polynomial defining the field.

\fun{GEN}{checknf}{GEN x} if an \var{nf} structure can be extracted from
\kbd{x}, return it; otherwise raise an exception. The more general
\kbd{get\_nf} is often more flexible.

\fun{GEN}{checkbnf}{GEN x} if an \var{bnf} structure can be extracted from
\kbd{x}, return it; otherwise raise an exception. The more general
\kbd{get\_bnf} is often more flexible.

\fun{void}{checkbnr}{GEN bnr} Raise an exception if the argument
is not a \var{bnr} structure.

\fun{void}{checkbnrgen}{GEN bnr} Raise an exception if the argument is not a
\var{bnr} structure, complete with explicit generators for the ray class group.
This is normally useless and \tet{checkbnr} should be instead, unless
you are absolutely certain that the generators will be needed at a later
point, and you are about to embark in a costly intermediate computation.
PARI functions do check that generators are present in \var{bnr} before
accessing them: they will raise an error themselves; many functions
that may require them, e.g. \kbd{bnrconductor}, often
do not actually need them.

\fun{void}{checkrnf}{GEN rnf} Raise an exception if the argument is not an
\var{rnf} structure.

\fun{void}{checkbid}{GEN bid} Raise an exception if the argument is not a
\var{bid} structure.

\fun{GEN}{checkgal}{GEN x} if a \var{galoisinit} structure can be extracted
from \kbd{x}, return it; otherwise raise an exception.

\fun{void}{checksqmat}{GEN x, long N} check whether \kbd{x} is a square matrix
of dimension \kbd{N}. May be used to check for ideals if \kbd{N} is the field
degree.

\fun{void}{checkprid}{GEN pr} Raise an exception if the argument is not a
prime ideal structure.

\fun{GEN}{get_prid}{GEN ideal} return the underlying prime ideal structure
if one can be extracted from \kbd{ideal} (ideal or extended ideal), and
return \kbd{NULL} otherwise.

\fun{void}{checkabgrp}{GEN v} Raise an exception if the argument
is not an abelian group structure, i.e. a \typ{VEC} with either $2$ or $3$
entries: $[N,\var{cyc}]$ or $[N,\var{cyc}, \var{gen}]$.

\fun{GEN}{abgrp_get_no}{GEN x}
 extract the cardinality $N$ from an abelian group structure.

\fun{GEN}{abgrp_get_cyc}{GEN x}
 extract the elementary divisors \var{cyc} from an abelian group structure.

\fun{GEN}{abgrp_get_gen}{GEN x}
 extract the generators \var{gen} from an abelian group structure.

\fun{void}{checkmodpr}{GEN modpr} Raise an exception if the argument is not a
 prime ideal structure.

\fun{GEN}{checknfelt_mod}{GEN nf, GEN x, const char *s} given an \var{nf}
structure \kbd{nf} and a \typ{POLMOD} \kbd{x}, return the associated
polynomial representative (shallow) if \kbd{x} and \kbd{nf} are compatible.
Raise an exception otherwise. Set $s$ to the name of the caller for a
meaningful error message.

\fun{void}{check_ZKmodule}{GEN x, const char *s} check whether $x$ looks like
$\Z_K$-module (a pair $[A,I]$, where $A$ is a matrix and $I$ is a list of
ideals; $A$ has as many columns as $I$ has elements. Otherwise
raises an exception. Set $s$ to the name of the caller for a
meaningful error message.

\fun{long}{idealtyp}{GEN *ideal, GEN *fa} The input is \kbd{ideal}, a pointer
to an ideal (or extended ideal), which is usually modified, \kbd{fa} being
set as a side-effect. Returns the type of the underlying ideal among
\tet{id_PRINCIPAL} (a number field element), \tet{id_PRIME} (a prime ideal)
\tet{id_MAT} (an ideal in matrix form).

If \kbd{ideal} pointed to an ideal, set \kbd{fa} to \kbd{NULL}, and
possibly simplify \kbd{ideal} (for instance the zero ideal is replaced by
\kbd{gen\_0}). If it pointed to an extended ideal, replace
\kbd{ideal} by the underlying ideal and set \kbd{fa} to the factorization
matrix component.

\subsec{Extracting info from a \kbd{nf} structure}

These functions expect a true \var{nf} argument associated to a number field
$K = \Q[x]/(T)$, e.g.~a \var{bnf} will not work. Let $n = [K:\Q]$ be the
field degree.

\fun{GEN}{nf_get_pol}{GEN nf} returns the polynomial $T$ (monic, in $\Z[x]$).

\fun{long}{nf_get_varn}{GEN nf} returns the variable number of the number
field defining polynomial.

\fun{long}{nf_get_r1}{GEN nf} returns the number of real places $r_1$.

\fun{long}{nf_get_r2}{GEN nf} returns the number of complex places $r_2$.

\fun{void}{nf_get_sign}{GEN nf, long *r1, long *r2} sets $r_1$ and $r_2$
to the number of real and complex places respectively. Note that
$r_1+2r_2$ is the field degree.

\fun{long}{nf_get_degree}{GEN nf} returns the number field degree, $n = r_1 +
2r_2$.

\fun{GEN}{nf_get_disc}{GEN nf} returns the field discriminant.

\fun{GEN}{nf_get_index}{GEN nf} returns the index of $T$, i.e. the index of
the order generated by the power basis $(1,x,\ldots,x^{n-1})$ in the
maximal order of $K$.

\fun{GEN}{nf_get_zk}{GEN nf} returns a basis $(w_1,w_2,\ldots,w_n)$ for the
maximal order of $K$. Those are polynomials in $\Q[x]$ of degree $<n$; it is
guaranteed that $w_1 = 1$.

\fun{GEN}{nf_get_invzk}{GEN nf} returns the matrix $(m_{i,j})\in M_n(\Z)$
giving the power basis $(x^i)$ in terms of the $(w_j)$, i.e such that
$x^{j-1} = \sum_{i = 1}^n m_{i,j} w_i$ for all $1\leq j \leq n$; since $w_1 =
1 = x^0$, we have $m_{i,1} = \delta_{i,1}$ for all $i$. The conversion
functions in the \kbd{algtobasis} family essentially amount to a left
multiplication by this matrix.

\fun{GEN}{nf_get_roots}{GEN nf} returns the $r_1$ real roots of the polynomial
defining the number fields: first the $r_1$ real roots (as \typ{REAL}s), then
the $r_2$ representatives of the pairs of complex conjugates.

\fun{GEN}{nf_get_allroots}{GEN nf} returns all the complex roots of $T$:
first the $r_1$ real roots (as \typ{REAL}s), then the $r_2$ pairs of complex
conjugates.

\fun{GEN}{nf_get_M}{GEN nf} returns the $(r_1+r_2)\times n$ matrix $M$
giving the embeddings of $K$: $M[i,j]$ contains $w_j(\alpha_i)$, where
$\alpha_i$ is the $i$-th element of \kbd{nf\_get\_roots(nf)}. In particular,
if $v$ is an $n$-th dimensional \typ{COL} representing the element
$\sum_{i=1}^n v[i] w_i$ of $K$, then \kbd{RgM\_RgC\_mul(M,v)} represents the
embeddings of $v$.

\fun{GEN}{nf_get_G}{GEN nf} returns a $n\times n$ real matrix $G$ such that
$Gv \cdot Gv = T_2(v)$, where $v$ is an $n$-th dimensional \typ{COL}
representing the element $\sum_{i=1}^n v[i] w_i$ of $K$ and $T_2$ is the
standard Euclidean form on $K\otimes \R$, i.e.~$T_2(v)
= \sum_{\sigma} |\sigma(v)|^2$, where $\sigma$ runs through all $n$ complex
embeddings of $K$.

\fun{GEN}{nf_get_roundG}{GEN nf} returns a rescaled version of $G$, rounded
to nearest integers, specifically \tet{RM_round_maxrank}$(G)$.

\fun{GEN}{nf_get_ramified_primes}{GEN nf} returns the vector of ramified
primes.

\fun{GEN}{nf_get_Tr}{GEN nf} returns the matrix of the Trace quadratic form
on the basis $(w_1,\ldots,w_n)$: its $(i,j)$ entry is $\text{Tr} w_i w_j$.

\fun{GEN}{nf_get_diff}{GEN nf} returns the primitive part of the inverse of
the above Trace matrix.

\fun{long}{nf_get_prec}{GEN nf} returns the precision (in words) to which the
\var{nf} was computed.

\subsec{Extracting info from a \kbd{bnf} structure}

These functions expect a true \var{bnf} argument, e.g.~a \var{bnr} will not
work.

\fun{GEN}{bnf_get_nf}{GEN bnf} returns the underlying \var{nf}.

\fun{GEN}{bnf_get_clgp}{GEN bnf} returns the class group in \var{bnf},
which is a $3$-component vector $[h, \var{cyc}, \var{gen}]$.

\fun{GEN}{bnf_get_cyc}{GEN bnf} returns the elementary divisors
of the class group (cyclic components) $[d_1,\ldots, d_k]$, where
$d_k \mid \ldots \mid d_1$.

\fun{GEN}{bnf_get_gen}{GEN bnf} returns the generators $[g_1,\ldots,g_k]$
of the class group. Each $g_i$ has order $d_i$, and the full module of relations
between the $g_i$ is generated by the $d_ig_i = 0$.

\fun{GEN}{bnf_get_no}{GEN bnf} returns the class number.

\fun{GEN}{bnf_get_reg}{GEN bnf} returns the regulator.

\fun{GEN}{bnf_get_logfu}{GEN bnf} returns (complex floating point
approximations to) the logarithms of the complex embeddings of our system of
fundamental units.

\fun{GEN}{bnf_get_fu}{GEN bnf} returns the fundamental units. Raise
an error if the \var{bnf} does not contain units in algebraic form.

\fun{GEN}{bnf_get_fu_nocheck}{GEN bnf} as \tet{bnf_get_fu} without
checking whether units are present. Do not use this unless
you initialize the \var{bnf} yourself!

\fun{GEN}{bnf_get_tuU}{GEN bnf} returns a generator of the torsion part
of $\Z_K^*$.

\fun{long}{bnf_get_tuN}{GEN bnf} returns the order of the torsion part of
$\Z_K^*$, i.e.~the number of roots of unity in $K$.

\subsec{Extracting info from a \kbd{bnr} structure}

These functions expect a true \var{bnr} argument.

\fun{GEN}{bnr_get_bnf}{GEN bnr} returns the underlying \var{bnf}.

\fun{GEN}{bnr_get_nf}{GEN bnr} returns the underlying \var{nf}.

\fun{GEN}{bnr_get_clgp}{GEN bnr} returns the ray class group.

\fun{GEN}{bnr_get_no}{GEN bnr} returns the ray class number.

\fun{GEN}{bnr_get_cyc}{GEN bnr} returns the elementary divisors
of the ray class group (cyclic components) $[d_1,\ldots, d_k]$, where
$d_k \mid \ldots \mid d_1$.

\fun{GEN}{bnr_get_gen}{GEN bnr} returns the generators $[g_1,\ldots,g_k]$ of
the ray class group. Each $g_i$ has order $d_i$, and the full module of
relations between the $g_i$ is generated by the $d_ig_i = 0$. Raise
a generic error if the \var{bnr} does not contain the ray class group
generators.

\fun{GEN}{bnr_get_gen_nocheck}{GEN bnr} as \tet{bnr_get_gen} without
checking whether generators are present. Do not use this unless
you initialize the \var{bnr} yourself!

\fun{GEN}{bnr_get_bid}{GEN bnr} returns the \var{bid} associated
to the \var{bnr} modulus.

\fun{GEN}{bnr_get_mod}{GEN bnr} returns the modulus associated
to the \var{bnr}.

\subsec{Extracting info from an \kbd{rnf} structure}

These functions expect a true \var{rnf} argument, associated to an extension
$L/K$, $K = \Q[y]/(T)$, $L = K[x]/(P)$.

\fun{long}{rnf_get_degree}{GEN rnf} returns the \emph{relative} degree
$[L:K]$.

\fun{long}{rnf_get_absdegree}{GEN rnf} returns the absolute degree
$[L:\Q]$.

\fun{long}{rnf_get_nfdegree}{GEN rnf} returns the degree of the base
field $[K:\Q]$.

\fun{GEN}{rnf_get_nf}{GEN rnf} returns the base field $K$, an \var{nf}
structure.

\fun{GEN}{rnf_get_nfpol}{GEN rnf} returns the polynomial $T$ defining the
base field $K$.

\fun{long}{rnf_get_nfvarn}{GEN rnf} returns the variable $y$ associated to the
base field $K$.

\fun{void}{rnf_get_nfzk}{GEN rnf, GEN *b, GEN *cb} returns the integer basis
of the base field $K$.

\fun{GEN}{rnf_get_pol}{GEN rnf} returns the relative polynomial defining
$L/K$.

\fun{long}{rnf_get_varn}{GEN rnf} returns the variable $x$ associated to $L$.

\fun{GEN}{rnf_get_zk}{GEN nf} returns the relative integer basis generating
$\Z_L$ as a $\Z_K$-module, as a pseudo-matrix $(A,I)$ in HNF.

\fun{GEN}{rnf_get_disc}{GEN rnf} is the output $[\goth{d}, s]$
 of \kbd{rnfdisc}.

\fun{GEN}{rnf_get_idealdisc}{GEN rnf} is the ideal discriminant $\goth{d}$
from \kbd{rnfdisc}.

\fun{GEN}{rnf_get_index}{GEN rnf} is the index ideal $\goth{f}$

\fun{GEN}{rnf_get_polabs}{GEN rnf} returns an absolute polynomial defining
$L/\Q$.

\fun{GEN}{rnf_get_alpha}{GEN rnf} a root $\alpha$ of the polynomial
defining the base field, modulo \kbd{polabs} (cf.~\kbd{rnfequation})

\fun{GEN}{rnf_get_k}{GEN rnf}
a small integer $k$ such that $\theta = \beta + k\alpha$ is a root of
\kbd{polabs}, where $\beta$ is a root of \kbd{pol}
and $\alpha$ a root of the polynomial defining the base field,
as in \tet{rnf_get_alpha} (cf.~also \kbd{rnfequation}).

\fun{GEN}{rnf_get_invzk}{GEN rnf} contains $A^{-1}$, where $(A,I)$
is the chosen pseudo-basis for $\Z_L$ over $\Z_K$.

\fun{GEN}{rnf_get_map}{GEN rnf} returns technical data associated to the map
$K\to L$. Currently, this contains data from \kbd{rnfequation},
as well as the polynomials $T$ and $P$.

\subsec{Extracting info from a \kbd{bid} structure}

These functions expect a true \var{bid} argument, associated to a modulus $I$
in a number field $K$.

\fun{GEN}{bid_get_mod}{GEN bid} returns the modulus associated to the \var{bid}.

\fun{GEN}{bid_get_grp}{GEN bid} returns the Abelian group associated
to $(\Z_K/I)^*$modulus associated to the \var{bid}.

\fun{GEN}{bid_get_ideal}{GEN bid} return the finite part of the \var{bid}
modulus (an integer ideal).

\fun{GEN}{bid_get_arch}{GEN bid} return the Archimedean part of the \var{bid}
modulus (a vector of real places).

\fun{GEN}{bid_get_no}{GEN bid} returns the cardinality of the
group $(\Z_K/I)^*$.

\fun{GEN}{bid_get_cyc}{GEN bid} returns the elementary divisors
of the group $(\Z_K/I)^*$ (cyclic components) $[d_1,\ldots, d_k]$, where $d_k
\mid \ldots \mid d_1$.

\fun{GEN}{bid_get_gen}{GEN bid} returns the generators of $(\Z_K/I)^*$
contained in \var{bid}. Raise a generic error if \var{bid} does not contain
generators.

\fun{GEN}{bid_get_gen_nocheck}{GEN bid} as \tet{bid_get_gen} without
checking whether generators are present. Do not use this unless
you initialize the \var{bid} yourself!

\subsec{Increasing accuracy}

\fun{GEN}{nfnewprec}{GEN x, long prec}. Raise an exception if \kbd{x}
is not a number field structure (\var{nf}, \var{bnf} or \var{bnr}).
Otherwise, sets its accuracy to \kbd{prec} and return the new structure.
This is mostly useful with \kbd{prec} larger than the accuracy to
which \kbd{x} was computed, but it is also possible to decrease the accuracy
of \kbd{x} (truncating relevant components, which may speed up later
computations). This routine may modify the original \kbd{x} (see below).

This routine is straightforward for \var{nf} structures, but for the
other ones, it requires all principal ideals corresponding to the \var{bnf}
relations in algebraic form (they are originally only available via floating
point approximations). This in turn requires many calls to
\tet{bnfisprincipal0}, which is often slow, and may fail if the initial
accuracy was too low. In this case, the routine will not actually fail but
recomputes a \var{bnf} from scratch!

Since this process may be very expensive, the corresponding data is cached
(as a \emph{clone}) in the \emph{original} \kbd{x} so that later precision
increases become very fast. In particular, the copy returned by
\kbd{nfnewprec} also contains this additional data.

\fun{GEN}{bnfnewprec}{GEN x, long prec}. As \kbd{nfnewprec}, but extracts
a \var{bnf} structure form \kbd{x} before increasing its accuracy, and
returns only the latter.

\fun{GEN}{bnrnewprec}{GEN x, long prec}. As \kbd{nfnewprec}, but extracts a
\var{bnr} structure form \kbd{x} before increasing its accuracy, and
returns only the latter.

\fun{GEN}{nfnewprec_shallow}{GEN nf, long prec}

\fun{GEN}{bnfnewprec_shallow}{GEN bnf, long prec}

\fun{GEN}{bnrnewprec_shallow}{GEN bnr, long prec} Shallow functions
underlying the above, except that the first argument must now have the
corresponding number field type. I.e. one cannot call
\kbd{nfnewprec\_shallow(nf, prec)} if \kbd{nf} is actually a \var{bnf}.

\subsec{Number field arithmetic}
The number field $K = \Q[X]/(T)$ is represented by an \kbd{nf} (or \kbd{bnf}
or \kbd{bnr} structure). An algebraic number belonging to $K$ is given as

\item a \typ{INT}, \typ{FRAC} or \typ{POL} (implicitly modulo $T$), or

\item a \typ{POLMOD} (modulo $T$), or

\item a \typ{COL}~\kbd{v} of dimension $N = [K:\Q]$, representing
the element in terms of the computed integral basis $(e_i)$, as
\bprog
  sum(i = 1, N, v[i] * nf.zk[i])
@eprog
The preferred forms are \typ{INT} and \typ{COL} of \typ{INT}. Routines can
handle denominators but it is much more efficient to remove  denominators
first (\tet{Q_remove_denom}) and take them into account at the end.

\misctitle{Safe routines} The following routines do not assume that their
\kbd{nf} argument is a true \var{nf} (it can be any number field type, e.g.~a
\var{bnf}), and accept number field elements in all the above forms. They
return their result in \typ{COL} form.

\fun{GEN}{nfadd}{GEN nf, GEN x, GEN y} returns $x+y$.

\fun{GEN}{nfdiv}{GEN nf, GEN x, GEN y} returns $x / y$.

\fun{GEN}{nfinv}{GEN nf, GEN x} returns $x^{-1}$.

\fun{GEN}{nfmul}{GEN nf,GEN x,GEN y} returns $xy$.

\fun{GEN}{nfpow}{GEN nf,GEN x,GEN k} returns $x^k$, $k$ is in $\Z$.

\fun{GEN}{nfpow_u}{GEN nf,GEN x, ulong k} returns $x^k$, $k\geq 0$.

\fun{GEN}{nfsqr}{GEN nf,GEN x} returns $x^2$.

\fun{long}{nfval}{GEN nf, GEN x, GEN pr} returns the valuation of $x$ at the
maximal ideal $\goth{p}$ associated to the \var{prid} \kbd{pr}.
Returns \kbd{LONG\_MAX} is $x$ is $0$.

\fun{GEN}{nfnorm}{GEN nf,GEN x} absolute norm of $x$.

\fun{GEN}{nftrace}{GEN nf,GEN x} absolute trace of $x$.

\fun{GEN}{nfpoleval}{GEN nf, GEN pol, GEN a} evaluate the \typ{POL} \kbd{pol}
(with coefficients in \kbd{nf}) on the algebraic number $a$ (also in $nf$).

\fun{GEN}{FpX_FpC_nfpoleval}{GEN nf, GEN pol, GEN a, GEN p} evaluate the
\kbd{FpX} \kbd{pol} on the algebraic number $a$ (also in $nf$).

The following three functions implement trivial functionality akin to
Euclidean division for which we currently have no real use. Of course, even if
the number field is actually Euclidean, these do not in general implement a
true Euclidean division.

\fun{GEN}{nfdiveuc}{GEN nf, GEN a, GEN b} returns the algebraic integer
closest to $x / y$. Functionally identical to \kbd{ground( nfdiv(nf,x,y) )}.

\fun{GEN}{nfdivrem}{GEN nf, GEN a, GEN b} returns the vector $[q,r]$, where
\bprog
  q = nfdiveuc(nf, a,b);
  r = nfadd(nf, a,nfmul(nf,q,gneg(b)));    \\ or r = nfmod(nf,a,b);
@eprog

\fun{GEN}{nfmod}{GEN nf, GEN a, GEN b} returns $r$ such that
\bprog
  q = nfdiveuc(nf, a,b);
  r = nfadd(nf, a, nfmul(nf,q, gneg(b)));
@eprog

\fun{GEN}{nf_to_scalar_or_basis}{GEN nf, GEN x} let $x$ be a number field
element. If it is a rational scalar, i.e.~can be represented by a \typ{INT}
or \typ{FRAC}, return the latter. Otherwise returns its basis representation
(\tet{nfalgtobasis}). Shallow function.

\fun{GEN}{nf_to_scalar_or_alg}{GEN nf, GEN x} let $x$ be a number field
element. If it is a rational scalar, i.e.~can be represented by a \typ{INT}
or \typ{FRAC}, return the latter. Otherwise returns its lifted \typ{POLMOD}
representation (lifted \tet{nfbasistoalg}). Shallow function.

\fun{GEN}{RgX_to_nfX}{GEN nf, GEN x} let $x$ be a \typ{POL} whose coefficients
are number field elements; apply \kbd{nf\_to\_scalar\_or\_basis} to each
coefficient and return the resulting new polynomial. Shallow function.

\fun{GEN}{RgM_to_nfM}{GEN nf, GEN x} let $x$ be a \typ{MAT} whose coefficients
are number field elements; apply \kbd{nf\_to\_scalar\_or\_basis} to each
coefficient and return the resulting new matrix. Shallow function.

\fun{GEN}{RgC_to_nfC}{GEN nf, GEN x} let $x$ be a \typ{COL} or
\typ{VEC} whose coefficients
are number field elements; apply \kbd{nf\_to\_scalar\_or\_basis} to each
coefficient and return the resulting new \typ{COL}. Shallow function.

\misctitle{Unsafe routines} The following routines assume that their \kbd{nf}
argument is a true \var{nf} (e.g.~a \var{bnf} is not allowed) and their
argument are restricted in various ways, see the precise description below.

\fun{GEN}{nfinvmodideal}{GEN nf, GEN x, GEN A} given an algebraic integer
$x$ and a non-zero integral ideal $A$ in HNF, returns a $y$ such that
$xy \equiv 1$ modulo $A$.

\fun{GEN}{nfpowmodideal}{GEN nf, GEN x, GEN n, GEN ideal} given an algebraic
integer $x$, an integer $n$, and a non-zero integral ideal $A$ in HNF,
returns an algebraic integer congruent to $x^n$ modulo $A$.

\fun{GEN}{nfmuli}{GEN nf, GEN x, GEN y} returns $x\times y$ assuming
that both $x$ and $y$ are either \typ{INT}s or \kbd{ZV}s of the correct
dimension.

\fun{GEN}{nfsqri}{GEN nf, GEN x} returns $x^2$ assuming that $x$ is a \typ{INT}
or a \kbd{ZV} of the correct dimension.

\fun{GEN}{nfC_nf_mul}{GEN nf, GEN v, GEN x} given a \typ{VEC} or \typ{COL}
$v$ of elements of $K$ in \typ{INT}, \typ{FRAC} or \typ{COL} form, multiply
it by the element $x$ (arbitrary form). This is faster than multiplying
coordinatewise since pre-computations related to $x$ (computing the
multiplication table) are done only once. The components of the result
are in most cases \typ{COL}s but are allowed to be \typ{INT}s or \typ{FRAC}s.
Shallow function.

\fun{GEN}{zk_multable}{GEN nf, GEN x} given a \kbd{ZC} $x$ (implicitly
representing an algebraic integer), returns the \kbd{ZM} giving the
multiplication table by $x$. Shallow function (the first column of the result
points to the same data as $x$).

\fun{GEN}{zk_scalar_or_multable}{GEN nf, GEN x} given a \typ{INT} or \kbd{ZC}
$x$, returns a \typ{INT} equal to $x$ if the latter is a scalar
(\typ{INT} or \kbd{ZV\_isscalar}$(x)$ is 1) and
\kbd{zk\_multable}$(\var{nf},x)$ otherwise. Shallow function.


The following routines implement multiplication in a commutative $R$-algebra,
generated by $(e_1 = 1,\dots, e_n)$, and given by a multiplication table $M$:
elements in the algebra are $n$-dimensional \typ{COL}s, and the matrix
$M$ is such that for all $1\leq i,j\leq n$, its column with index $(i-1)n +
j$, say $(c_k)$, gives $e_i\cdot e_j = \sum c_k e_k$. It is assumed that
$e_1$ is the neutral element for the multiplication (a convenient
optimization, true in practice for all multiplications we needed to implement).
If $x$ has any other type than \typ{COL} where an algebra element is
expected, it is understood as $x e_1$.

\fun{GEN}{multable}{GEN M, GEN x} given a column vector $x$, representing
the quantity $\sum_{i=1}^N x_i e_i$, returns the multiplication table by $x$.
Shallow function.

\fun{GEN}{ei_multable}{GEN M, long i} returns the multiplication table
by the $i$-th basis element $e_i$. Shallow function.

\fun{GEN}{tablemul}{GEN M, GEN x, GEN y} returns $x\cdot y$.

\fun{GEN}{tablesqr}{GEN M, GEN x} returns $x^2$.

\fun{GEN}{tablemul_ei}{GEN M, GEN x, long i} returns $x\cdot e_i$.

\fun{GEN}{tablemul_ei_ej}{GEN M, long i, long j} returns $e_i\cdot e_j$.

\fun{GEN}{tablemulvec}{GEN M, GEN x, GEN v} given a vector $v$ of elements
in the algebra, returns the $x\cdot v[i]$.

\subsec{Elements in factored form}

Computational algebraic theory performs extensively linear
algebra on $\Z$-modules with a natural multiplicative structure ($K^*$,
fractional ideals in $K$, $\Z_K^*$, ideal class group), thereby raising
elements to horrendously large powers. A seemingly innocuous elementary linear
algebra operation like $C_i\leftarrow C_i - 10000 C_1$ involves raising
entries in $C_1$ to the $10000$-th power. Understandably, it is often more
efficient to keep elements in factored form rather than expand every such
expression. A \emph{factorization matrix} (or \tev{famat}) is a two column
matrix, the first column containing \emph{elements} (arbitrary objects which
may be repeated in the column), and the second one contains \emph{exponents}
(\typ{INT}s, allowed to be 0). By abuse of notation, the empty matrix
\kbd{cgetg(1, t\_MAT)} is recognized as the trivial factorization (no
element, no exponent).

Even though we think of a \var{famat} with columns $g$ and $e$
as one meaningful object when fully expanded as $\prod g[i]^{e[i]}$,
\var{famat}s are basically about concatenating information to keep track of
linear algebra: the objects stored in a \var{famat} need not be
operation-compatible, they will not even be compared to each other (with one
exception: \tet{famat_reduce}). Multiplying two \var{famat}s just
concatenates their elements and exponents columns. In a context where a
\var{famat} is expected, an object $x$ which is not of type \typ{MAT} will be
treated as the factorization $x^1$. The following functions all return
\var{famat}s:

\fun{GEN}{famat_mul}{GEN f, GEN g} $f$, $g$ are \var{famat},
or objects whose type is \emph{not} \typ{MAT} (understood as $f^1$ or $g^1$).
Returns $fg$. The empty factorization is the neutral element for \var{famat}
multiplication.

\fun{GEN}{famat_mul_shallow}{GEN f, GEN g} $f$, $g$ are \var{famat}, returns
$fg$. Shallow function.

\fun{GEN}{famat_pow}{GEN f, GEN n} $n$ is a \typ{INT}. If $f$ is a \typ{MAT},
assume it is a \var{famat} and return $f^n$ (multiplies the exponent column
by $n$). Otherwise, understand it as an element and returns the $1$-line
\var{famat} $f^n$.

\fun{GEN}{famat_sqr}{GEN f} returns $f^2$.

\fun{GEN}{famat_inv}{GEN f} returns $f^{-1}$.

\fun{GEN}{famat_inv_shallow}{GEN f} shallow version of \tet{famat_inv}.

\fun{GEN}{famat_Z_gcd}{GEN M, GEN n} restrict the \var{famat} $M$ to
the prime power dividing $n$.

\fun{GEN}{to_famat}{GEN x, GEN k} given an element $x$ and an exponent
$k$, returns the \var{famat} $x^k$.

\fun{GEN}{to_famat_shallow}{GEN x, GEN k} same, as a shallow function.

Note that it is trivial to break up a \var{famat} into its two constituent
columns: \kbd{gel(f,1)} and \kbd{gel(f,2)} are the elements and exponents
respectively. Conversely, \kbd{mkmat2} builds a (shallow) \var{famat} from
two \typ{COL}s of the same length.

The last two functions makes an assumption about the elements: they must be
regular algebraic numbers (not \var{famat}s) over a given number field:

\fun{GEN}{famat_reduce}{GEN f} given a \var{famat} $f$, returns a \var{famat}
$g$ without repeated elements or 0 exponents, such that the expanded forms
of $f$ and $g$ would be equal. Shallow function.

\fun{GEN}{ZM_famat_limit}{GEN f, GEN limit} given a \var{famat} $f$ with
\typ{INT} entries, returns a \var{famat} $g$ with all factors larger than
\kbd{limit} multiplied out as the last entry (with exponent $1$).

\fun{GEN}{famat_to_nf}{GEN nf, GEN f} You normally never want to do this!
This is a simplified form of \tet{nffactorback}, where we do not check the
user input for consistency.

The description of \tet{famat_to_nf} says that you do not want to use this
function. Then how do we recover genuine number field elements? Well, in
most cases, we do not need to: most of the functions useful in this
context accept \var{famat}s as inputs, for instance \tet{nfsign},
\tet{nfsign_arch}, \tet{ideallog} and \tet{bnfisunit}. Otherwise, we can
generally make good use of a quotient operation (modulo a fixed conductor,
modulo $\ell$-th powers); see the end of \secref{se:Ideal_reduction}.

\misctitle{Caveat} Receiving a \var{famat} input, \kbd{bnfisunit} assumes that
it is an algebraic integer, since this is expensive to check, and normally
easy to ensure from the user's side; do not feed it ridiculous inputs.

\fun{GEN}{famatsmall_reduce}{GEN f} as \kbd{famat\_reduce}, but for exponents
given by a \typ{VECSMALL}.

\subsec{Ideal arithmetic}

\misctitle{Conversion to HNF}

\fun{GEN}{idealhnf}{GEN nf, GEN x} returns the HNF of the ideal defined by $x$:
$x$ may be an algebraic  number (defining a principal ideal),  a maximal ideal
(as given by \tet{idealprimedec} or  \tet{idealfactor}), or a matrix whose
columns give generators for the  ideal. This  last format is complicated,  but
useful to reduce general modules to the canonical form once in a while:

\item if strictly less than $N = [K:Q]$ generators are given,  $x$ is the
$\Z_K$-module they generate,

\item if $N$ or more are given,  it is assumed that they form a $\Z$-basis
(that the matrix has maximal rank $N$).  This acts as \tet{mathnf} since the
$\Z_K$-module structure is (taken for granted hence) not taken into account
in this case.

Extended ideals are also accepted, their principal part being discarded.

\fun{GEN}{idealhnf0}{GEN nf, GEN x, GEN y} returns the HNF of the ideal
generated by the two algebraic numbers $x$ and $y$.

The following low-level functions underlie the above two: they all assume
that \kbd{nf} is a true \var{nf} and perform no type checks:

\fun{GEN}{idealhnf_principal}{GEN nf, GEN x}
returns the ideal generated by the algebraic number $x$.

\fun{GEN}{idealhnf_shallow}{GEN nf, GEN x} is \tet{idealhnf} except that the
result may not be suitable for \kbd{gerepile}: if $x$ is already in HNF, we
return $x$, not a copy!

\fun{GEN}{idealhnf_two}{GEN nf, GEN v} assuming $a = v[1]$ is a non-zero
\typ{INT} and $b = v[2]$ is an algebraic integer, possibly given in regular
representation by a \typ{MAT} (the multiplication table by $b$, see
\tet{zk_multable}), returns the HNF of $a\Z_K+b\Z_K$.

\misctitle{Operations}

The basic ideal routines accept all \kbd{nf}s (\var{nf}, \var{bnf},
\var{bnr}) and ideals in any form, including extended ideals, and return
ideals in HNF, or an extended ideal when that makes sense:

\fun{GEN}{idealadd}{GEN nf, GEN x, GEN y} returns $x+y$.

\fun{GEN}{idealdiv}{GEN nf, GEN x, GEN y} returns $x/y$. Returns an extended
ideal if $x$ or $y$ is an extended ideal.

\fun{GEN}{idealmul}{GEN nf, GEN x, GEN y} returns $xy$.
Returns an extended ideal if $x$ or $y$ is an extended ideal.

\fun{GEN}{idealsqr}{GEN nf, GEN x} returns $x^2$.
Returns an extended ideal if $x$ is an extended ideal.

\fun{GEN}{idealinv}{GEN nf, GEN x} returns $x^{-1}$.
Returns an extended ideal if $x$ is an extended ideal.

\fun{GEN}{idealpow}{GEN nf, GEN x, GEN n} returns $x^n$.
Returns an extended ideal if $x$ is an extended ideal.

\fun{GEN}{idealpows}{GEN nf, GEN ideal, long n} returns $x^n$.
Returns an extended ideal if $x$ is an extended ideal.

\fun{GEN}{idealmulred}{GEN nf, GEN x, GEN y} returns an extended ideal equal
to $xy$.

\fun{GEN}{idealpowred}{GEN nf, GEN x, GEN n} returns an extended ideal equal
to $x^n$.

More specialized routines suffer from various restrictions:

\fun{GEN}{idealdivexact}{GEN nf, GEN x, GEN y} returns $x/y$, assuming that
the quotient is an integral ideal. Much faster than \tet{idealdiv} when the
norm of the quotient is small compared to $Nx$. Strips the principal parts
if either $x$ or $y$ is an extended ideal.

\fun{GEN}{idealdivpowprime}{GEN nf, GEN x, GEN pr, GEN n} returns $x
\goth{p}^{-n}$, assuming $x$ is an ideal in HNF, and \kbd{pr}
a \var{prid} associated to $\goth{p}$. Not suitable for \tet{gerepileupto}
since it returns $x$ when $n = 0$.

\fun{GEN}{idealmulpowprime}{GEN nf, GEN x, GEN pr, GEN n} returns $x
\goth{p}^{n}$, assuming $x$ is an ideal in HNF, and \kbd{pr} a \var{prid}
associated to $\goth{p}$. Not suitable for \tet{gerepileupto} since it
retunrs $x$ when $n = 0$.

\fun{GEN}{idealprodprime}{GEN nf, GEN P} given a list $P$ of prime ideals
in \var{prid} form, return their product.

\fun{GEN}{idealmul_HNF}{GEN nf, GEN x, GEN y} returns $xy$, assuming
than \kbd{nf} is a true \var{nf}, $x$ is an integral ideal in HNF and $y$
is an integral ideal in HNF or precompiled form (see below).
For maximal speed, the second ideal $y$ may be given in precompiled form $y =
[a,b]$, where $a$ is a non-zero \typ{INT} and $b$ is an algebraic integer in
regular representation (a \typ{MAT} giving the multiplication table by the
fixed element): very useful when many ideals $x$ are going to be multiplied by
the same ideal $y$. This essentially reduces each ideal multiplication to
an $N\times N$ matrix multiplication followed by a $N\times 2N$ modular
HNF reduction (modulo $xy\cap \Z$).

\misctitle{Approximation}

\fun{GEN}{idealaddtoone}{GEN nf, GEN A, GEN B} given to coprime integer ideals
$A$, $B$, returns $[a,b]$ with $a\in A$, $b\in B$, such that $a + b = 1$
The result is reduced mod $AB$, so $a$, $b$ will be small.

\fun{GEN}{idealaddtoone_i}{GEN nf, GEN A, GEN B} as \tet{idealaddtoone} except
that \kbd{nf} must be a true \var{nf}, and only $a$ is returned.

\fun{GEN}{hnfmerge_get_1}{GEN A, GEN B} given two square upper HNF integral
matrices $A$, $B$ of the same dimension $n > 0$, return $a$ in the image of
$A$ such that $1-a$ is in the image of $B$. (By abuse of notation we denote
$1$ the column vector $[1,0,\dots,0]$.) If such an $a$ does not exist, return
\kbd{NULL}. This is the function underlying \tet{idealaddtoone}.

\fun{GEN}{idealaddmultoone}{GEN nf, GEN v} given a list of $n$ (globally)
coprime integer ideals $(v[i])$ returns an $n$-dimensional vector $a$ such that
$a[i]\in v[i]$ and $\sum a[i] = 1$. If $[K:\Q] = N$, this routine computes
the HNF reduction (with $Gl_{nN}(\Z)$ base change) of an $N\times nN$ matrix;
so it is well worth pruning "useless" ideals from the list (as long as the
ideals remain globally coprime).

\fun{GEN}{idealappr}{GEN nf, GEN x} given a fractional ideal $x$, returns
an algebraic number $\alpha$ such that $v(x) = v(\alpha)$ for all valuations
such that $v(x) > 0$, and $v(\alpha) \geq 0$ at all others.

\fun{GEN}{idealapprfact}{GEN nf, GEN fx} same as \tet{idealappr}, $x$ being
given in factored form, as after \kbd{fx = idealfactor(nf,x)}, except that we
allow $0$ exponents in the factorization. Returns an algebraic number
$\alpha$ such that $v(x) = v(\alpha)$ for all valuations associated to the
prime ideal decomposition of $x$, and $v(\alpha) \geq 0$ at all others.

\fun{GEN}{idealcoprime}{GEN nf, GEN x, GEN y}. Given 2 integral ideals $x$ and
$y$, returns an algebraic number $\alpha$ such that
$\alpha x$ is an integral ideal coprime to $y$.

\fun{GEN}{idealcoprimefact}{GEN nf, GEN x, GEN fy} same as
\tet{idealcoprime}, except that $y$ is given in factored form, as from
\tet{idealfactor}.

\fun{GEN}{idealchinese}{GEN nf, GEN x, GEN y} $x$ being a prime ideal
factorization (i.e.~a 2 by 2 matrix whose first column contain prime ideals,
and the second column integral exponents), $y$ a vector of elements in
$\var{nf}$ indexed by the ideals in $x$, computes an element $b$ such that
$v_\wp(b - y_\wp) \geq v_\wp(x)$ for all prime ideals in $x$ and $v_\wp(b)\geq
0$ for all other $\wp$.

\subsec{Maximal ideals}

The PARI structure associated to maximal ideals is a \tev{prid} (for
\emph{pr}ime \emph{id}eal), usually produced by \tet{idealprimedec}
and \tet{idealfactor}. In this section, we describe the format; other sections
will deal with their daily use.

A \var{prid} associated to a maximal ideal $\goth{p}$ stores the following
data: the underlying rational prime $p$, the ramification degree $e\geq 1$,
the residue field degree $f\geq 1$, a $p$-uniformizer $\pi$ with valuation
$1$ at $\goth{p}$ and valuation $0$ at all other primes dividing $p$ and
a rescaled ``anti-uniformizer'' $\tau$ used to compute valuations. This
$\tau$ is an algebraic integer such that $\tau/p$ has valuation $-1$ at
$\goth{p}$ and valuation $0$ at all other primes dividing $p$; in particular,
the valuation of $x\in\Z_K$ is positive if and only if the algebraic integer
$x\tau$ is divisible by $p$ (easy to check for elements in \typ{COL} form).

The following functions are shallow and return directly components of the
\var{prid} \kbd{pr}:

\fun{GEN}{pr_get_p}{GEN pr} returns $p$. Shallow function.

\fun{GEN}{pr_get_gen}{GEN pr} returns $\pi$. Shallow function.

\fun{long}{pr_get_e}{GEN pr} returns $e$.

\fun{long}{pr_get_f}{GEN pr} returns $f$.

\fun{GEN}{pr_get_tau}{GEN pr} returns
$\tet{zk_scalar_or_multable}(\var{nf}, \tau)$, which is the \typ{INT}~$1$
iff $p$ is inert, and a \kbd{ZM} otherwise. Shallow function.

\fun{int}{pr_is_inert}{GEN pr} returns $1$ if $p$ is inert, $0$ otherwise.

\fun{GEN}{pr_norm}{GEN pr} returns the norm $p^f$ of the maximal ideal.

\fun{GEN}{idealprimedec}{GEN nf, GEN p} list of maximal ideals dividing the
prime $p$.

\fun{GEN}{idealprimedec_limit_f}{GEN nf, GEN p, long f} as \tet{idealprimedec},
limiting the list to primes of residual degree $\leq f$ if $f$ is non-zero.

\fun{GEN}{idealprimedec_limit_norm}{GEN nf, GEN p, GEN B} as
\tet{idealprimedec}, limiting the list to primes of norm $\leq B$, which
must be a positive \typ{INT}.

\subsec{Reducing modulo maximal ideals}

\fun{GEN}{nfmodprinit}{GEN nf, GEN pr} returns an abstract \kbd{modpr}
structure, associated to reduction modulo the maximal ideal \kbd{pr}, in
\kbd{idealprimedec} format. From this data we can quickly project any
\kbd{pr}-integral number field element to the residue field.

\fun{GEN}{modpr_get_pr}{GEN x} return the \kbd{pr} component from a \kbd{modpr}
structure.

\fun{GEN}{modpr_get_p}{GEN x} return the $p$ component from a \kbd{modpr}
structure (underlying rational prime).

\fun{GEN}{modpr_get_T}{GEN x} return the \kbd{T} component from a \kbd{modpr}
structure: either \kbd{NULL} (prime of degree $1$) or an irreducible
\kbd{FpX} defining the residue field over $\F_p$.

In library mode, it is often easier to use directly

\fun{GEN}{nf_to_Fq_init}{GEN nf, GEN *ppr, GEN *pT, GEN *pp} concrete
version of \kbd{nfmodprinit}: \kbd{nf} and \kbd{*ppr} are the inputs, the
return value is a \kbd{modpr} and \kbd{*ppr}, \kbd{*pT} and \kbd{*pp} are set
as side effects.

The input \kbd{*ppr} is either a maximal ideal or already a \kbd{modpr} (in
which case it is replaced by the underlying maximal ideal). The residue field
is realized as $\F_p[X]/(T)$ for some monic $T\in\F_p[X]$, and we set
\kbd{*pT} to $T$ and \kbd{*pp} to $p$. Set $T = \kbd{NULL}$ if the prime has
degree $1$ and the residue field is $\F_p$.

In short, this receives (or initializes) a \kbd{modpr} structure, and
extracts from it $T$, $p$ and $\goth{p}$.

\fun{GEN}{nf_to_Fq}{GEN nf, GEN x, GEN modpr} returns an \kbd{Fq} congruent
to $x$ modulo the maximal ideal associated to \kbd{modpr}. The output is
canonical: all elements in a given residue class are represented by the same
\kbd{Fq}.

\fun{GEN}{Fq_to_nf}{GEN x, GEN modpr} returns an \kbd{nf} element lifting
the residue field element $x$, either a \typ{INT} or an algebraic integer
in \kbd{algtobasis} format.

\fun{GEN}{modpr_genFq}{GEN modpr} Returns an \kbd{nf} element whose image by
\tet{nf_to_Fq} is $X \pmod T$, if $\deg T>1$, else $1$.

\fun{GEN}{zkmodprinit}{GEN nf, GEN pr} as \tet{nfmodprinit}, but we assume we
will only reduce algebraic integers, hence do not initialize data allowing to
remove denominators. More precisely, we can in fact still handle an $x$ whose
rational denominator is not $0$ in the residue field (i.e. if the valuation
of $x$ is non-negative at all primes dividing $p$).

\fun{GEN}{zk_to_Fq_init}{GEN nf, GEN *pr, GEN *T, GEN *p} as
\kbd{nf\_to\_Fq\_init}, able to reduce only $p$-integral elements.

\fun{GEN}{zk_to_Fq}{GEN x, GEN modpr} as \kbd{nf\_to\_Fq}, for
a $p$-integral $x$.

\fun{GEN}{nfM_to_FqM}{GEN M, GEN nf,GEN modpr} reduces a matrix
of \kbd{nf} elements to the residue field; returns an \kbd{FqM}.

\fun{GEN}{FqM_to_nfM}{GEN M, GEN modpr} lifts an \kbd{FqM} to a matrix of
\kbd{nf} elements.

\fun{GEN}{nfV_to_FqV}{GEN A, GEN nf,GEN modpr} reduces a vector
of \kbd{nf} elements to the residue field; returns an \kbd{FqV}
with the same type as \kbd{A} (\typ{VEC} or \typ{COL}).

\fun{GEN}{FqV_to_nfV}{GEN A, GEN modpr} lifts an \kbd{FqV} to a vector of
\kbd{nf} elements (same type as \kbd{A}).

\fun{GEN}{nfX_to_FqX}{GEN Q, GEN nf,GEN modpr} reduces a polynomial
with \kbd{nf} coefficients to the residue field; returns an \kbd{FqX}.

\fun{GEN}{FqX_to_nfX}{GEN Q, GEN modpr} lifts an \kbd{FqX} to a polynomial
with coefficients in \kbd{nf}.

\subsec{Valuations}

\fun{long}{nfval}{GEN nf, GEN x, GEN P} return $v_P(x)$

\misctitle{Unsafe functions} assume \var{nf} is a genuine \kbd{nf}
structure, that $P$, $Q$ are \kbd{prid}.

\fun{long}{ZC_nfval}{GEN nf, GEN x, GEN P} returns $v_P(x)$,
assuming $x$ is a \kbd{ZC}, representing a non-zero algebraic integer.

\fun{long}{ZC_nfvalrem}{GEN nf, GEN x, GEN pr, GEN *newx} returns $v = v_P(x)$,
assuming $x$ is a \kbd{ZC}, representing a non-zero algebraic integer, and sets
\kbd{*newx} to $x\tau^v$ which is an algebraic integer coprime to $p$.

\fun{int}{ZC_prdvd}{GEN nf, GEN x, GEN P} returns $1$ is $P$ divides $x$ and
$0$ otherwise. Assumes that $x$ is a \kbd{ZC}, representing an algebraic
integer. Faster than computing $v_P(x)$.

\fun{int}{pr_equal}{GEN nf, GEN P, GEN Q} returns 1 is $P$ and $Q$ represent
the same maximal ideal: they must lie above the same $p$ and share the same
$e,f$ invariants, but the $p$-uniformizer and $\tau$ element may differ.
Returns $0$ otherwise.

\subsec{Signatures}

``Signs'' of the real embeddings of number field element are represented in
additive notation, using the standard identification $(\Z/2\Z, +) \to
(\{-1,1\},\times)$, $s\mapsto (-1)^s$.

With respect to a fixed \kbd{nf} structure, a selection of real places (a
divisor at infinity) is normally given as a \typ{VECSMALL} of indices of the
roots \kbd{nf.roots} of the defining polynomial for the number field. For
compatibility reasons, in particular under GP, the (obsolete) \kbd{vec01}
form is also accepted: a \typ{VEC} with \kbd{gen\_0} or \kbd{gen\_1} entries.

The following internal functions go back and forth between the two
representations for the Archimedean part of divisors (GP: $0/1$ vectors,
library: list of indices):

\fun{GEN}{vec01_to_indices}{GEN v} given a \typ{VEC} $v$ with \typ{INT} entries
equal to $0$ or $1$, return as a \typ{VECSMALL} the list of indices $i$
such that $v[i] = 1$. If $v$ is already a \typ{VECSMALL}, return it
(not suitable for \kbd{gerepile} in this case).

\fun{GEN}{vecsmall01_to_indices}{GEN v} as
\bprog
  vec01_to_indices(zv_to_ZV(v));
@eprog

\fun{GEN}{indices_to_vec01}{GEN p, long n} return the $0/1$ vector of length
$n$ with ones exactly at the positions $p[1], p[2], \ldots$

\fun{GEN}{nfembed}{GEN nf, GEN x, long k} returns a floating point
approximation of the $k$-th embedding of $x$ (associated to the $k$-th
complex root in \kbd{nf.roots}).

\fun{GEN}{nfsign}{GEN nf,GEN x} $x$ being a number field element and \kbd{nf}
any form of number field, return the $0-1$-vector giving the signs of the
$r_1$ real embeddings of $x$, as a \typ{VECSMALL}. Linear algebra functions
like \tet{Flv_add_inplace} then allow keeping track of signs in series of
multiplications.

If $x$ is a \typ{VEC} of number field elements, return the matrix whose
columns are the signs of the $x[i]$.

\fun{GEN}{nfsign_arch}{GEN nf,GEN x,GEN arch} \kbd{arch} being a list of
distinct real places, either in \kbd{vec01} (\typ{VEC} with \kbd{gen\_0} or
\kbd{gen\_1} entries) or \kbd{indices} (\typ{VECSMALL}) form (see
\tet{vec01_to_indices}), returns the signs of $x$ at the corresponding
places. This is the low-level function underlying \kbd{nfsign}.

\fun{GEN}{nfsign_units}{GEN bnf, GEN archp, int add_tu}
\kbd{archp} being a divisor at infinity in \kbd{indices} form
(or \kbd{NULL} for the divisor including all real places), return the signs
at \kbd{archp} of a system of fundamental units for the field, in the same
order as \kbd{bnf.tufu} if \kbd{add\_tu} is set; and in the same order as
\kbd{bnf.fu} otherwise.

\fun{GEN}{nfsign_from_logarch}{GEN L, GEN invpi, GEN archp} given $L$
the vector of the $\log \sigma(x)$, where $\sigma$ runs through the (real
or complex) embeddings of some number field, \kbd{invpi} being
a floating point approximation to $1/\pi$, and \kbd{archp} being a divisor
at infinity in \kbd{indices} form, return the signs of $x$
at the corresponding places. This is the low-level function underlying
\kbd{nfsign\_units}; the latter is actually a trivial wrapper
\kbd{bnf} structures include the $\log \sigma(x)$ for a system of fundamental
units of the field.

\fun{GEN}{set_sign_mod_divisor}{GEN nf, GEN x, GEN y, GEN module, GEN sarch}
let $f = f_0f_\infty$ be the divisor represented by \kbd{module}, $x$, $y$ two
number field elements. Returns $yt$ with $t = 1 \text{mod}^* f$ such that $x$
and $ty$ have the same signs at $f_\infty$; if $x =
\kbd{NULL}$, make $ty$ totally positive at $f_\infty$. \kbd{sarch} is the
output of \kbd{nfarchstar(nf, f0, finf)}.

\fun{GEN}{nfarchstar}{GEN nf, GEN f0, GEN finf} for a divisor $f =
f_0f_\infty$ represented by the integral ideal \kbd{f0} in HNF and
the \kbd{finf} in \kbd{indices} form, returns $(\Z_K/f_\infty)^*$ in a form
suitable for computations mod $f$. More precisely, returns
$[c, g, M]$, where $c = [2,\ldots, 2]$ gives the cyclic structure of that
group ($\#f_\infty$ copies of $\Z/2\Z$), $g$ a minimal system of independent
generators, which are furthermore congruent to $1$ mod $f_0$ (no condition if
$f_0 = \Z_K$), and $M$ is the matrix of signs of the $g[i]$ at $f_\infty$,
which is square and invertible over $\F_2$.

\fun{GEN}{idealprincipalunits}{GEN nf, GEN pr, long e} returns the
multiplicative group $(1 + \var{pr}) / (1 + \var{pr}^e)$ as an abelian group.
Faster than \tet{idealstar} when the norm of \var{pr} is large, since it
avoids (useless) work in the multiplicative group of the residue field.

\subsec{Maximal order and discriminant}

A number field $K = \Q[X]/(T)$ is defined by a monic $T\in\Z[X]$. The
low-level function computing a maximal order is

\fun{void}{nfmaxord}{nfmaxord_t *S, GEN T0, long flag}, where
the polynomial $T_0$ is squarefree with integer coefficients. Let $K$ be the
\'etale algebra $\Q[X]/(T_0)$ and let $T = \kbd{ZX\_Q\_normalize}(T_0)$,
i.e. $T = C T_0(X/L)$ is monic and integral for some $C,Q\in \Q$.

The structure \tet{nfmaxord_t} is initialized by the call; it has the
following fields:
\bprog
  GEN T0, T, dT, dK; /* T0, T, discriminants of T and K */
  GEN unscale; /* the integer L */
  GEN index; /* index of power basis in maximal order */
  GEN dTP, dTE; /* factorization of |dT|, primes / exponents */
  GEN dKP, dKE; /* factorization of |dK|, primes / exponents */
  GEN basis; /* Z-basis for maximal order of Q[X]/(T) */
@eprog\noindent The exponent vectors are \typ{VECSMALL}. The primes
in \kbd{dTP} and \kbd{dKP} are pseudoprimes, not proven primes. We recommend
restricting to $T = T_0$, i.e. either to pass the input polynomial through
\tet{ZX_Q_normalize} \emph{before} the call, or to forget about $T_0$
and go on with the polynomial $T$; otherwise $\kbd{unscale}\neq 1$, all data
is expressed in terms of $T\neq T_0$, and needs to be converted to $T_0$. For
instance to convert the basis to $\Q[X]/(T_0)$:
\bprog
  RgXV_unscale(S.basis, S.unscale)
@eprog

Instead of passing $T$, one can use the format $[T,\var{listP}]$ as in
\kbd{nfbasis} or \kbd{nfinit}, which computes an order which is maximal
at a set of primes, but need not be the maximal order.

The \kbd{flag} is an or-ed combination of the binary flags:

\tet{nf_PARTIALFACT}: do not try to fully factor \kbd{dT} and only look for
primes less than \kbd{primelimit}. In that case, the elements in \kbd{dTP}
and \kbd{dKP} need not all be primes. But the resulting \kbd{dK},
\kbd{index} and \kbd{basis} are correct provided there exists no prime $p >
\kbd{primelimit}$ such that $p^2$ divides the field discriminant \kbd{dK}.
This flag is \emph{deprecated}: the $[T,\var{listP}]$ is safer and more
flexible.

\tet{nf_ROUND2}: use the ROUND2 algorithm instead of the default ROUND4.
This flag is \emph{deprecated}: this algorithm is consistently slower.

$T$ is the input polynomial (monic \kbd{ZX}). The format $[T, \kbd{listP}]$
is also recognized, where \kbd{listP} is as in \tet{nfbasis} and is used to
compute a local integral basis with respect to a specific set of primes.

\fun{GEN}{indexpartial}{GEN T, GEN dT} $T$ a monic separable \kbd{ZX},
\kbd{dT} is either \kbd{NULL} (no information) or a multiple of the
discriminant of $T$. Let $K = \Q[X]/(T)$ and $\Z_K$ its maximal order.
Returns a multiple of the exponent of the quotient group $\Z_K/(\Z[X]/(T))$.
In other word, a \emph{denominator} $d$ such that $d x\in\Z[X]/(T)$ for all
$x\in\Z_K$.

\subsec{Computing in the class group}

We compute with arbitrary ideal representatives (in any of the various
formats seen above), and call

\fun{GEN}{bnfisprincipal0}{GEN bnf, GEN x, long flag}. The \kbd{bnf}
structure already contains information about the class group in the form
$\oplus_{i=1}^n (\Z/d_i\Z) g_i$ for canonical integers $d_i$
(with $d_n\mid\dots\mid d_1$ all $> 1$) and essentially random generators
$g_i$, which are ideals in HNF. We normally do not need the value of the
$g_i$, only that they are fixed once and for all and that any (non-zero)
fractional ideal $x$ can be expressed uniquely as $x = (t)\prod_{i=1}^n
g_i^{e_i}$, where $0 \leq e_i < d_i$, and $(t)$ is some principal ideal.
Computing $e$ is straightforward, but $t$ may be very expensive to obtain
explicitly. The routine returns (possibly partial) information about the pair
$[e,t]$, depending on \kbd{flag}, which is an or-ed combination of the
following symbolic flags:

\item \tet{nf_GEN} tries to compute $t$.
Returns $[e,t]$, with $t$ an empty vector if the computation failed. This
flag is normally useless in non-trivial situations since the next two serve
analogous purposes in more efficient ways.

\item \tet{nf_GENMAT} tries to compute $t$ in factored form, which is
much more efficient than \kbd{nf\_GEN} if the class group is moderately
large; imagine a small ideal $x = (t)g^{10000}$: the norm of $t$ has $10000$
as many digits as the norm of $g$; do we want to see it as a vector
of huge meaningless integers? The idea is to compute $e$ first, which is
easy, then compute $(t)$ as $x \prod g_i^{-e_i}$ using successive
\tet{idealmulred}, where the ideal reduction extracts small principal ideals
along the way, eventually raised to large powers because of the binary
exponentiation technique; the point is to keep this principal part in
factored \emph{unexpanded} form. Returns $[e,t]$, with $t$ an empty vector if
the computation failed; this should be exceedingly rare, unless the initial
accuracy to which \kbd{bnf} was computed was ridiculously low (and then
\kbd{bnfinit} should not have succeeded either). Setting/unsetting
\kbd{nf\_GEN} has no effect when this flag is set.

\item \tet{nf_GEN_IF_PRINCIPAL} tries to compute $t$ \emph{only} if the
ideal is principal ($e = 0$). Returns \kbd{gen\_0} if the ideal is not
principal. Setting/unsetting \kbd{nf\_GEN} has no effect when this flag is
set, but setting/unsetting \kbd{nf\_GENMAT} is possible.

\item \tet{nf_FORCE} in the above, insist on computing $t$, even if it
requires recomputing a \kbd{bnf} from scratch. This is a last resort, and
normally the accuracy of a \kbd{bnf} can be increased without trouble, but it
may be that some algebraic information simply cannot be recovered from what
we have: see \tet{bnfnewprec}. It should be very rare, though.

In simple cases where you do not care about $t$, you may use

\fun{GEN}{isprincipal}{GEN bnf, GEN x}, which is a shortcut for
\kbd{bnfisprincipal0(bnf, x, 0)}.

The following low-level functions are often more useful:

\fun{GEN}{isprincipalfact}{GEN bnf, GEN C, GEN L, GEN f, long flag} is
about the same as \kbd{bnfisprincipal0} applied to $C \prod L[i]^{f[i]}$,
where the $L[i]$ are ideals, the $f[i]$ integers and $C$ is either an ideal
or \kbd{NULL} (omitted). Make sure to include \tet{nf_GENMAT} in \kbd{flag}!

\fun{GEN}{isprincipalfact_or_fail}{GEN bnf, GEN C, GEN L, GEN f} is
for delicate cases, where we must be more clever than \kbd{nf\_FORCE}
(it is used when trying to increase the accuracy of a \var{bnf}, for
instance). If performs
\bprog
  isprincipalfact(bnf,C, L, f, nf_GENMAT);
@eprog\noindent
but if it fails to compute $t$, it just returns a \typ{INT}, which is the
estimated precision (in words, as usual) that would have been sufficient to
complete the computation. The point is that \kbd{nf\_FORCE} does exactly this
internally, but goes on increasing the accuracy of the \kbd{bnf}, then
discarding it, which is a major inefficiency if you intend to compute lots of
discrete logs and have selected a precision which is just too low.
(It is sometimes not so bad since most of the really expensive data is cached
in \kbd{bnf} anyway, if all goes well.)  With this function, the \emph{caller}
may decide to increase the accuracy using \tet{bnfnewprec} (and keep the
resulting \kbd{bnf}!), or avoid the computation altogether. In any case the
decision can be taken at the place where it is most likely to be correct.

\subsec{Floating point embeddings, the $T_2$ quadratic form}

We assume the \var{nf} is a true \kbd{nf} structure, associated to a number
field $K$ of degree $n$ and signature $(r_1,r_2)$. We saw that

\fun{GEN}{nf_get_M}{GEN nf} returns the $(r_1+r_2)\times n$ matrix $M$
giving the embeddings of $K$, so that if $v$ is an $n$-th dimensional
\typ{COL} representing the element $\sum_{i=1}^n v[i] w_i$ of $K$, then
\kbd{RgM\_RgC\_mul(M,v)} represents the embeddings of $v$. Its first $r_1$
components are real numbers (\typ{INT}, \typ{FRAC} or \typ{REAL}, usually the
latter), and the last $r_2$ are complex numbers (usually of \typ{COMPLEX},
but not necessarily for embeddings of rational numbers).

\fun{GEN}{embed_T2}{GEN x, long r1} assuming $x$ is the vector of floating point
embeddings of some algebraic number $v$, i.e.
\bprog
  x = RgM_RgC_mul(nf_get_M(nf), algtobasis(nf,v));
@eprog\noindent returns $T_2(v)$. If the floating point embeddings themselves
are not needed, but only the values of $T_2$, it is more efficient to
restrict to real arithmetic and use
\bprog
  gnorml2( RgM_RgC_mul(nf_get_G(nf), algtobasis(nf,v)));
@eprog

\fun{GEN}{embednorm_T2}{GEN x, long r1} analogous to \tet{embed_T2},
applied to the \kbd{gnorm} of the floating point embeddings. Assuming that
\bprog
  x = gnorm( RgM_RgC_mul(nf_get_M(nf), algtobasis(nf,v)) );
@eprog\noindent returns $T_2(v)$.

\fun{GEN}{embed_roots}{GEN z, long r1} given a vector $z$ of $r_1+r_2$
complex embeddings of the algebraic number $v$, return the $r_1+2r_2$ roots
of its characteristic polynomial. Shallow function.

\fun{GEN}{embed_disc}{GEN z, long r1, long prec} given a vector $z$ of
$r_1+r_2$ complex embeddings of the algebraic number $v$, return a floating
point approximation of the discriminant of its characteristic polynomial as a
\typ{REAL} of precision \kbd{prec}.

\fun{GEN}{embed_norm}{GEN x, long r1} given a vector $z$ of $r_1+r_2$ complex
embeddings of the algebraic number $v$, return (a floating point
approximation of) the norm of $v$.

\subsec{Ideal reduction, low level}

In the following routines \var{nf} is a true \kbd{nf}, associated to a number
field $K$ of degree $n$:

\fun{GEN}{nf_get_Gtwist}{GEN nf, GEN v} assuming $v$ is a \typ{VECSMALL}
with $r_1+r_2$ entries, let
$$|| x ||_v^2 = \sum_{i=1}^{r_1+r_2} 2^{v_i}\varepsilon_i|\sigma_i(x)|^2,$$
where as usual the $\sigma_i$ are the (real and) complex embeddings and
$\varepsilon_i = 1$, resp.~$2$, for a real, resp.~complex place.
This is a twisted variant of the $T_2$ quadratic form, the standard Euclidean
form on $K\otimes \R$. In applications, only the relative size of the $v_i$
will matter.

Let $G_v\in M_n(\R)$ be a square matrix such that if $x\in K$ is represented by
the column vector $X$ in terms of the fixed $\Z$-basis of $\Z_K$ in \var{nf},
then
$$||x||_v^2 = {}^t (G_v X) \cdot G_v X.$$
(This is a kind of Cholesky decomposition.) This function
returns a rescaled copy of $G_v$, rounded to nearest integers, specifically
\tet{RM_round_maxrank}$(G_v)$.
Suitable for \kbd{gerepileupto}, but does not collect garbage.

\fun{GEN}{nf_get_Gtwist1}{GEN nf, long i}. Simple special case. Returns the
twisted $G$ matrix associated to the vector $v$ whose entries are all $0$
except the $i$-th one, which is equal to $10$.

\fun{GEN}{idealpseudomin}{GEN x, GEN G}. Let $x$, $G$ be two \kbd{ZM}s,
such that the product $Gx$ is well-defined. This returns a ``small'' integral
linear combinations of the columns of $x$, given by the LLL-algorithm applied
to the lattice $G x$. Suitable for \kbd{gerepileupto}, but does not collect
garbage.

In applications, $x$ is an integral ideal, $G$ approximates a Cholesky form for
the $T_2$ quadratic form as returned by \tet{nf_get_Gtwist}, and we return
a small element $a$ in the lattice $(x,T_2)$. This is used to implement
\tet{idealred}.

\fun{GEN}{idealpseudomin_nonscalar}{GEN x, GEN G}. As \tet{idealpseudomin},
but we insist of returning a non-scalar $a$ (\kbd{ZV\_isscalar} is false), if
the dimension of $x$ is $> 1$.

In the interpretation where $x$ defines an integral ideal on a fixed $\Z_K$
basis whose first element is $1$, this means that $a$ is not rational.

\fun{GEN}{idealred_elt}{GEN nf, GEN x} shortcut for
\bprog
  idealpseudomin(x, nf_get_roundG(nf))
@eprog

\subsec{Ideal reduction, high level} \label{se:Ideal_reduction}

Given an ideal $x$ this means finding a ``simpler'' ideal in the same ideal
class. The public GP function is of course available

\fun{GEN}{idealred0}{GEN nf, GEN x, GEN v} finds a small $a\in x$ and returns
the primitive part of $x/(a)$, as an ideal in HNF. What ``small'' means
depends on the parameter $v$, see the GP description. More precisely,
$a$ is returned by \kbd{idealpseudomin}$(x,G)$, where $G$
is \tet{nf_get_Gtwist}$(\var{nf}, v)$ for $v\neq \kbd{NULL}$
and \tet{nf_get_roundG}$(\var{nf})$ otherwise.

\noindent Usually one sets $v = \kbd{NULL}$ to obtain an element of small $T_2$
norm in $x$:

\fun{GEN}{idealred}{GEN nf, GEN x} is a shortcut for \kbd{idealred0(nf,x,NULL)}.

The function \kbd{idealred} remains complicated to use: in order not to lose
information $x$ must be an extended ideal, otherwise the value of $a$ is lost.
There is a subtlety here: the principal ideal $(a)$ is easy to recover, but $a$
itself is an instance of the principal ideal problem which is very difficult
given only an \var{nf} (once a \var{bnf} structure is available,
\tet{bnfisprincipal0} will recover it). It is in general simpler to use
directly \tet{idealred_elt}.

\fun{GEN}{idealmoddivisor}{GEN bnr, GEN x} A proof-of-concept implementation,
useless in practice. If \kbd{bnr} is associated to some modulus $f$, returns a
``small'' ideal in the same class as $x$ in the ray class group modulo $f$.
The reason why this is useless is that using extended ideals with principal
part in a computation, there is a simple way to reduce them: simply reduce
the generator of the principal part in $(\Z_K/f)^*$.

\fun{GEN}{famat_to_nf_moddivisor}{GEN nf, GEN g, GEN e, GEN bid}
given a true \var{nf} associated to a number field $K$, a \var{bid} structure
associated to a modulus $f$, and an algebraic number in factored form $\prod
g[i]^{e[i]}$, such that $(g[i],f) = 1$ for all $i$, returns a small element in
$\Z_K$ congruent to it mod $f$. Note that if $f$ contains places at infinity,
this includes sign conditions at the specified places.

A simpler case when the conductor has no place at infinity:

\fun{GEN}{famat_to_nf_modideal_coprime}{GEN nf, GEN g, GEN e, GEN f, GEN expo}
as above except that the ideal $f$ is now integral in HNF (no need for a full
\var{bid}), and we pass the exponent of the group $(\Z_K/f)^*$ as \kbd{expo};
any multiple will also do, at the expense of efficiency. Of course if a
\var{bid} for $f$ is available, if is easy to extract $f$ and the exact value
of \kbd{expo} from it (the latter is the first elementary divisor in the
group structure). A useful trick: if you set \kbd{expo} to \emph{any}
positive integer, the result is correct up to \kbd{expo}-th powers, hence
exact if \kbd{expo} is a multiple of the exponent; this is useful when trying
to decide whether an element is a square in a residue field for instance!
(take \kbd{expo}$ = 2$).

What to do when the $g[i]$ are not coprime to $f$, but only $\prod
g[i]^{e[i]}$ is? Then the situation is more complicated, and we advise to
solve it one prime divisor of $f$ at a time. Let $v$ the valuation
associated to a maximal ideal \kbd{pr} and assume $v(f) = k > 0$:

\fun{GEN}{famat_makecoprime}{GEN nf, GEN g, GEN e, GEN pr, GEN prk, GEN expo}
returns an element in $(\Z_K/\kbd{pr}^k)^*$ congruent to the product
$\prod g[i]^{e[i]}$, assumed to be globally coprime to $f$. As above,
\kbd{expo} is any positive multiple of the exponent of $(\Z_K/\kbd{pr}^k)^*$,
for instance $(Nv-1)p^{k-1}$, if $p$ is the underlying rational prime. You
may use other values of \kbd{expo} (see the useful trick in
\tet{famat_to_nf_modideal_coprime}).

\subsec{Class field theory}

Under GP, a class-field theoretic description of a number field is given by a
triple $A$, $B$, $C$, where the defining set $[A,B,C]$ can have any of the
following forms: $[\var{bnr}]$, $[\var{bnr},\var{subgroup}]$,
$[\var{bnf},\var{modulus}]$, $[\var{bnf},\var{modulus},\var{subgroup}]$.
You can still use directly all of (\kbd{libpari}'s routines implementing) GP's
functions as described in Chapter~3, but they are often awkward in the context
of \kbd{libpari} programming. In particular, it does not make much sense to
always input a triple $A,B,C$ because of the fringe
$[\var{bnf},\var{modulus},\var{subgroup}]$. The first routine to call, is
thus

\fun{GEN}{Buchray}{GEN bnf, GEN mod, long flag} initializes a \var{bnr}
structure from \kbd{bnf} and modulus \kbd{mod}. \kbd{flag} is an or-ed
combination of \kbd{nf\_GEN} (include generators) and \kbd{nf\_INIT} (if
omitted, do not return a \var{bnr}, only the ray class group as an abelian
group). In fact, a single value of \kbd{flag} actually makes sense:
\kbd{nf\_GEN | nf\_INIT} to initialize a proper \var{bnr}: removing
\kbd{nf\_GEN} saves very little time, but the corresponding crippled
\var{bnr} structure will raise errors in most class field theoretic
functions. Possibly also 0 to quickly compute the ray class group structure;
\tet{bnrclassno} is faster if we only need the \emph{order} of the ray class
group.

Now we have a proper \var{bnr} encoding a \kbd{bnf} and a modulus, we no longer
need the $[\var{bnf},\var{modulus}]$ and
$[\var{bnf},\var{modulus},\var{subgroup}]$ forms, which would internally call
\tet{Buchray} anyway. Recall that a subgroup $H$ is given by a matrix in HNF,
whose column express generators of $H$ on the fixed generators of the ray class
group that stored in our \var{bnr}. You may also code the trivial subgroup by
\kbd{NULL}.

\fun{GEN}{bnrconductor}{GEN bnr, GEN H, long flag} see the documentation of
the GP function.

\fun{long}{bnrisconductor}{GEN bnr, GEN H} returns 1 is the class field
defined by the subgroup $H$ (of the ray class group mod $f$ coded in \kbd{bnr})
has conductor $f$. Returns 0 otherwise.

\fun{GEN}{bnrdisc}{GEN bnr, GEN H, long flag} returns the discriminant and
signature of the class field defined by \kbd{bnr} and $H$. See the description
of the GP function for details. \fl\ is an or-ed combination of the flags
\tet{rnf_REL} (output relative data) and \tet{rnf_COND} (return 0 unless the
modulus is the conductor).

\fun{GEN}{bnrsurjection}{GEN BNR, GEN bnr} \kbd{BNR} and \kbd{bnr}
defined over the same field $K$, for moduli $F$ and $f$ with
$F\mid f$, returns the matrix of the canonical surjection
$\text{Cl}_K(F)\to \text{Cl}_K(f)$ (giving the image of the fixed ray class
group generators of \kbd{BNR} in terms of the ones in \kbd{bnr}).
\kbd{BNR} must include the ray class group generators.

\fun{GEN}{ABC_to_bnr}{GEN A, GEN B, GEN C, GEN *H, int addgen} This is a
quick conversion function designed to go from the too general (inefficient)
$A$, $B$, $C$ form to the preferred \var{bnr}, $H$ form for class fields.
Given $A$, $B$, $C$ as explained above (omitted entries coded by \kbd{NULL}),
return the associated \var{bnr}, and set $H$ to the associated subgroup. If
\kbd{addgen} is $1$, make sure that if the \var{bnr} needed to be computed,
then it contains generators.

\subsec{Relative equations, Galois conjugates}

\fun{GEN}{nfissquarefree}{GEN nf, GEN P} given $P$ a polynomial with
coefficients in \var{nf}, return $1$ is $P$ is squarefree, and $0$
otherwise. If is allowed (though less efficient) to replace \var{nf}
by a monic \kbd{ZX} defining the field.

\fun{GEN}{rnfequationall}{GEN A, GEN B, long *pk, GEN *pLPRS} $A$ is either an
\var{nf} type (corresponding to a number field $K$) or an irreducible \kbd{ZX}
defining a number field $K$. $B$ is an irreducible polynomial in $K[X]$.
Returns an absolute equation $C$ (over $\Q$) for the number field $K[X]/(B)$.
$C$ is the characteristic polynomial of $b + k a$ for some roots $a$ of $A$
and $b$ of $B$, and $k$ is a small rational integer. Set \kbd{*pk} to $k$.

If \kbd{pLPRS} is not \kbd{NULL} set it to $[h_0, h_1]$, $h_i\in \Q[X]$,
where $h_0+h_1 Y$ is the last non-constant polynomial in the pseudo-Euclidean
remainder sequence associated to $A(Y)$ and $B(X-kY)$, leading to $C =
\text{Res}_Y(A(Y), B(Y-kX))$. In particular $a := -h_0/h_1$ is a root of $A$
in $\Q[X]/(C)$, and $X - ka$ is a root of $B$.

\fun{GEN}{nf_rnfeq}{GEN A, GEN B} wrapper around \tet{rnfequationall} to allow
mapping $K\to L$ (\kbd{eltup}) and converting elements of $L$
between absolute and relative form (\kbd{reltoabs}, \kbd{abstorel}),
\emph{without} computing a full \var{rnf} structure, which is useful if the
relative integral basis is not required. In fact, since $A$ may be a \typ{POL}
or an \var{nf}, the integral basis of the base field is not needed either. The
return value is the same as \tet{rnf_get_map}. Shallow function.

\fun{GEN}{nf_rnfeqsimple}{GEN nf, GEN relpol} as \tet{nf_rnfeq} except some
fields are omitted, so that only the \tet{abstorel} operation is supported.
Shallow function.

\fun{GEN}{eltabstorel}{GEN rnfeq, GEN x} \kbd{rnfeq} is as
given by \tet{rnf_get_map} (but in this case \tet{rnfeltabstorel} is more
robust), \tet{nf_rnfeq} or \tet{nf_rnfeqsimple}, return $x$ as an element
of $L/K$, i.e. as a \typ{POLMOD} with \typ{POLMOD} coefficients. Shallow
function.

\fun{GEN}{eltabstorel_lift}{GEN rnfeq, GEN x} same as \tet{eltabstorel},
except that $x$ is returned in partially lifted form, i.e.~ as a
\typ{POL} with \typ{POLMOD} coefficients.

\fun{GEN}{eltreltoabs}{GEN rnfeq, GEN x} \kbd{rnfeq} is as given by
\tet{rnf_get_map} (but in this case \tet{rnfeltreltoabs} is more robust)
or \tet{nf_rnfeq}, return $x$ in absolute form.

\fun{void}{nf_nfzk}{GEN nf, GEN rnfeq, GEN *zknf, GEN *czknf} \kbd{rnfeq} as
given by \tet{nf_rnfeq}, \kbd{nf} a true \var{nf} structure, set \kbd{*zknf}
and \kbd{*czknf} to a suitable representation of \kbd{nf.zk} allowing quick
computation of the map $K\to L$ by the function \tet{nfeltup}, \emph{without}
computing a full \var{rnf} structure, which is useful if the relative
integral basis is not required. The computed values are the same as in
\tet{rnf_get_nfzk}. Shallow function.

\fun{GEN}{nfeltup}{GEN nf, GEN x, GEN zknf, GEN czknf} \kbd{zknf} and
\kbd{czknf} are initialized by \tet{nf_nfzk} or \tet{rnf_get_nfzk} (but in
this case \tet{rnfeltup} is more robust); \kbd{nf} is a true \var{nf}
structure for $K$, returns $x \in K$ as a (lifted) element of $L$, in
absolute form.

\fun{GEN}{Rg_nffix}{const char *f, GEN T, GEN c, int lift} given
a \kbd{ZX} $T$ and a ``coefficient'' $c$ supposedly belonging to $\Q[y]/(T)$,
check whether this is a the case and return a cleaned up version of $c$.
The string $f$ is the calling function name, used to report errors.

This means that $c$ must be one of \typ{INT}, \typ{FRAC}, \typ{POL} in the
variable $y$ with rational coefficients, or \typ{POLMOD} modulo $T$ which lift
to a rational \typ{POL} as above. The cleanup consists in the following
improvements:

\item \typ{POL} coefficients are reduced modulo $T$.

\item \typ{POL} and \typ{POLMOD} belonging to $\Q$ are converted to rationals,
\typ{INT} or \typ{FRAC}.

\item if \kbd{lift} is non-zero, convert \typ{POLMOD} to \typ{POL},
and otherwise convert \typ{POL} to \typ{POLMOD}s modulo $T$.

\fun{GEN}{RgX_nffix}{const char *f, GEN T, GEN P, int lift} check whether
$P$ is a polynomials with coefficients in the number field defined by the
absolute equation $T(y) = 0$, where $T$ is a \kbd{ZX} and returns a cleaned
up version of $P$. This checks whether $P$ is indeed a \typ{POL}
with variable compatible with coefficients in $\Q[y]/(T)$, i.e.
\bprog
  varncmp(varn(P), varn(T)) < 0
@eprog\noindent and applies \tet{Rg_nffix} to each coefficient.

\fun{GEN}{RgV_nffix}{const char *f, GEN T, GEN P, int lift} as \tet{RgX_nffix}
for a vector of coefficients.

\fun{GEN}{polmod_nffix}{const char *f, GEN rnf, GEN x, int lift} given
a \typ{POLMOD} $x$ supposedly defining an element of \var{rnf}, check this
and perform \tet{Rg_nffix} cleanups.

\fun{GEN}{polmod_nffix2}{const char *f, GEN T, GEN P, GEN x, int lift} as
\tet{polmod_nffix}, where the relative extension is explicitly defined
as $L = (\Q[y]/(T))[x]/(P)$, instead of by an \kbd{rnf} structure.

\fun{long}{numberofconjugates}{GEN T, long pinit} returns a quick
multiple for the number of  $\Q$-automorphism of the (integral, monic)
\typ{POL} $T$, from modular factorizations, starting from prime \kbd{pinit}
(you can set it to $2$). This upper bounds often coincides with the
actual number of conjugates. Of course, you should use \tet{nfgaloisconj}
to be sure.

\subsec{Obsolete routines}

Still provided for backward compatibility, but should not be used in new
programs. They will eventually disappear.

\fun{GEN}{zidealstar}{GEN nf, GEN x} short for \kbd{Idealstar(nf,x,nf\_GEN)}

\fun{GEN}{zidealstarinit}{GEN nf, GEN x}
short for \kbd{Idealstar(nf,x,nf\_INIT)}

\fun{GEN}{zidealstarinitgen}{GEN nf, GEN x}
short for \kbd{Idealstar(nf,x,nf\_GEN|nf\_INIT)}

\fun{GEN}{buchimag}{GEN D, GEN c1, GEN c2, GEN gCO} short for
\bprog
  Buchquad(D,gtodouble(c1),gtodouble(c2), /*ignored*/0)
@eprog

\fun{GEN}{buchreal}{GEN D, GEN gsens, GEN c1, GEN c2, GEN RELSUP, long prec}
short for
\bprog
Buchquad(D,gtodouble(c1),gtodouble(c2), prec)
@eprog

The following use a naming scheme which is error-prone and not easily
extensible; besides, they compute generators as per \kbd{nf\_GEN} and
not \kbd{nf\_GENMAT}. Don't use them:

\fun{GEN}{isprincipalforce}{GEN bnf,GEN x}

\fun{GEN}{isprincipalgen}{GEN bnf, GEN x}

\fun{GEN}{isprincipalgenforce}{GEN bnf, GEN x}

\fun{GEN}{isprincipalraygen}{GEN bnr, GEN x}, use \tet{bnrisprincipal}.

\noindent Variants on \kbd{polred}: use \kbd{polredbest}.

\fun{GEN}{factoredpolred}{GEN x, GEN fa}

\fun{GEN}{factoredpolred2}{GEN x, GEN fa}

\fun{GEN}{smallpolred}{GEN x}

\fun{GEN}{smallpolred2}{GEN x}, use \tet{Polred}.

\fun{GEN}{polred0}{GEN x, long flag, GEN p}

\fun{GEN}{polredabs}{GEN x}

\fun{GEN}{polredabs2}{GEN x}

\fun{GEN}{polredabsall}{GEN x, long flun}

\noindent Superseded by \tet{bnrdisc}:

\fun{GEN}{discrayabs}{GEN bnr,GEN subgroup}

\fun{GEN}{discrayabscond}{GEN bnr,GEN subgroup}

\fun{GEN}{discrayrel}{GEN bnr,GEN subgroup}

\fun{GEN}{discrayrelcond}{GEN bnr,GEN subgroup}

\noindent Superseded by \tet{bnrdisclist0}:

\fun{GEN}{discrayabslist}{GEN bnf,GEN listes}

\fun{GEN}{discrayabslistarch}{GEN bnf, GEN arch, long bound}

\fun{GEN}{discrayabslistlong}{GEN bnf, long bound}

\section{Galois extensions of $\Q$}

This section describes the data structure output by the function
\tet{galoisinit}. This will be called a \kbd{gal} structure in
the following.

\subsec{Extracting info from a \kbd{gal} structure}

The functions below expect a \kbd{gal} structure and are shallow. See the
documentation of \tet{galoisinit} for the meaning of the member functions.

\fun{GEN}{gal_get_pol}{GEN gal} returns \kbd{gal.pol}

\fun{GEN}{gal_get_p}{GEN gal} returns \kbd{gal.p}

\fun{GEN}{gal_get_e}{GEN gal} returns the integer $e$ such that
\kbd{gal.mod==gal.p\pow e}.

\fun{GEN}{gal_get_mod}{GEN gal} returns \kbd{gal.mod}.

\fun{GEN}{gal_get_roots}{GEN gal} returns \kbd{gal.roots}.

\fun{GEN}{gal_get_invvdm}{GEN gal} \kbd{gal[4]}.

\fun{GEN}{gal_get_den}{GEN gal} return \kbd{gal[5]}.

\fun{GEN}{gal_get_group}{GEN gal} returns \kbd{gal.group}.

\fun{GEN}{gal_get_gen}{GEN gal} returns \kbd{gal.gen}.

\fun{GEN}{gal_get_orders}{GEN gal} returns \kbd{gal.orders}.

\subsec{Miscellaneous functions}

\fun{GEN}{nfgaloismatrix}{GEN nf, GEN s} returns the \kbd{ZM} associated to
the automorphism $s$, seen as a linear operator expressend on the number
field integer basis. This allows to use
\bprog
  M = nfgaloismatrix(nf, s);
  sx = ZM_ZC_mul(M, x);   /* or RgM_RgC_mul(M, x) if x is not integral */
@eprog\noindent
instead of
\bprog
  sx = nfgaloisapply(nf, s, x);
@eprog\noindent
for an algebraic integer $x$.

\section{Quadratic number fields and quadratic forms}

\subsec{Checks}

\fun{void}{check_quaddisc}{GEN x, long *s, long *mod4, const char *f}
checks whether the \kbd{GEN} $x$ is a quadratic discriminant (\typ{INT},
not a square, congruent to $0,1$ modulo $4$), and raise an exception
otherwise. Set \kbd{*s} to the sign of $x$ and \kbd{*mod4} to $x$ modulo
$4$ (0 or 1).

\fun{void}{check_quaddisc_real}{GEN x, long *mod4, const char *f} as
\tet{check_quaddisc}; check that \kbd{signe(x)} is positive.

\fun{void}{check_quaddisc_imag}{GEN x, long *mod4, const char *f} as
\tet{check_quaddisc}; check that \kbd{signe(x)} is negative.

\subsec{\typ{QFI}, \typ{QFR}}

\fun{GEN}{qfi}{GEN x, GEN y, GEN z} creates the \typ{QFI} $(x,y,z)$.

\fun{GEN}{qfr}{GEN x, GEN y, GEN z, GEN d} creates the \typ{QFR} $(x,y,z)$
with distance component $d$.

\fun{GEN}{qfr_1}{GEN q} given a \typ{QFR} $q$, return the unit form $q^0$.

\fun{GEN}{qfi_1}{GEN q} given a \typ{QFI} $q$, return the unit form $q^0$.

\subsubsec{Composition}

\fun{GEN}{qficomp}{GEN x, GEN y} compose the two \typ{QFI} $x$ and $y$,
then reduce the result. This is the same as \kbd{gmul(x,y)}.

\fun{GEN}{qfrcomp}{GEN x, GEN y} compose the two \typ{QFR} $x$ and $y$,
then reduce the result. This is the same as \kbd{gmul(x,y)}.

\fun{GEN}{qfisqr}{GEN x} as \kbd{qficomp(x,y)}.

\fun{GEN}{qfrsqr}{GEN x} as \kbd{qfrcomp(x,y)}.

\noindent Same as above, \emph{without} reducing the result:

\fun{GEN}{qficompraw}{GEN x, GEN y}

\fun{GEN}{qfrcompraw}{GEN x, GEN y}

\fun{GEN}{qfisqrraw}{GEN x}

\fun{GEN}{qfrsqrraw}{GEN x}

\fun{GEN}{qfbcompraw}{GEN x, GEN y} compose two \typ{QFI}s or two \typ{QFR}s,
without reduce the result.

\subsubsec{Powering}

\fun{GEN}{powgi}{GEN x, GEN n} computes $x^n$ (will work for many more types
than \typ{QFI} and \typ{QFR}, of course). Reduce the result.

\fun{GEN}{qfrpow}{GEN x, GEN n} computes $x^n$ for a \typ{QFR} $x$, reducing
along the way. If the distance component is initially $0$, leave it alone;
otherwise update it.

\fun{GEN}{qfbpowraw}{GEN x, long n} compute $x^n$ (pure composition, no
reduction), for a \typ{QFI} or \typ{QFR} $x$.

\fun{GEN}{qfipowraw}{GEN x, long n} as \tet{qfbpowraw}, for a \typ{QFI} $x$.

\fun{GEN}{qfrpowraw}{GEN x, long n} as \tet{qfbpowraw}, for a \typ{QFR} $x$.

\subsubsec{Solve, Cornacchia}

The following functions underly \tet{qfbsolve}; $p$ denotes a prime number.

\fun{GEN}{qfisolvep}{GEN Q, GEN p} solves $Q(x,y) = p$ over the integers, for
a \typ{QFI} $Q$. Return \kbd{gen\_0} if there are no solutions.

\fun{GEN}{qfrsolvep}{GEN Q, GEN p} solves $Q(x,y) = p$ over the integers, for
a \typ{QFR} $Q$. Return \kbd{gen\_0} if there are no solutions.

\fun{long}{cornacchia}{GEN d, GEN p, GEN *px, GEN *py} solves
$x^2+ dy^2 = p$ over the integers, where $d > 0$. Return $1$ if there is a
solution (and store it in \kbd{*x} and \kbd{*y}), $0$ otherwise.

\fun{long}{cornacchia2}{GEN d, GEN p, GEN *px, GEN *py} as \kbd{cornacchia},
for the equation $x^2 + dy^2 = 4p$.

\subsubsec{Prime forms}

\fun{GEN}{primeform_u}{GEN x, ulong p} \typ{QFI} whose first coefficient
is the prime $p$.

\fun{GEN}{primeform}{GEN x, GEN p, long prec}

\subsec{Efficient real quadratic forms} Unfortunately, \typ{QFR}s
are very inefficient, and are only provided for backward compatibility.

\item they do not contain needed quantities, which are thus constantly
recomputed (the discriminant $D$, $\sqrt{D}$ and its integer part),

\item the distance component is stored in logarithmic form, which involves
computing one extra logarithm per operation. It is much more efficient
to store its exponential, computed from ordinary multiplications and
divisions (taking exponent overflow into account), and compute its logarithm
at the very end.

Internally, we have two representations for real quadratic forms:

\item \tet{qfr3}, a container $[a,b,c]$ with at least 3 entries: the three
coefficients; the idea is to ignore the distance component.

\item \tet{qfr5}, a container with at least 5 entries $[a,b,c,e,d]$: the
three coefficients a \typ{REAL} $d$ and a \typ{INT} $e$ coding the distance
component $2^{Ne} d$, in exponential form, for some large fixed $N$.

It is a feature that \kbd{qfr3} and \kbd{qfr5} have no specified length or
type. It implies that a \kbd{qfr5} or \typ{QFR} will do whenever a \kbd{qfr3}
is expected. Routines using these objects all require a global context,
provided by a \kbd{struct qfr\_data *}:
\bprog
  struct qfr_data {
    GEN D;        /* discriminant, t_INT   */
    GEN sqrtD;    /* sqrt(D), t_REAL       */
    GEN isqrtD;   /* floor(sqrt(D)), t_INT */
  };
@eprog
\fun{void}{qfr_data_init}{GEN D, long prec, struct qfr_data *S}
given a discriminant $D > 0$, initialize $S$ for computations at precision
\kbd{prec} ($\sqrt{D}$ is computed to that initial accuracy).

\noindent All functions below are shallow, and not stack clean.

\fun{GEN}{qfr3_comp}{GEN x, GEN y, struct qfr_data *S} compose two
\kbd{qfr3}, reducing the result.

\fun{GEN}{qfr3_pow}{GEN x, GEN n, struct qfr_data *S} compute $x^n$, reducing
along the way.

\fun{GEN}{qfr3_red}{GEN x, struct qfr_data *S} reduce $x$.

\fun{GEN}{qfr3_rho}{GEN x, struct qfr_data *S} perform one reduction step;
\kbd{qfr3\_red} just performs reduction steps until we hit a reduced form.

\fun{GEN}{qfr3_to_qfr}{GEN x, GEN d} recover an ordinary \typ{QFR} from the
\kbd{qfr3} $x$, adding distance component $d$.

Before we explain \kbd{qfr5}, recall that it corresponds to an ideal, that
reduction corresponds to multiplying by a principal ideal, and that the
distance component is a clever way to keep track of these principal ideals.
More precisely, reduction consists in a number of reduction steps,
going from the form $(a,b,c)$ to $\rho(a,b,c) = (c, -b \mod 2c, *)$;
the distance component is multiplied by (a floating point approximation to)
$(b + \sqrt{D}) / (b - \sqrt{D})$.

\fun{GEN}{qfr5_comp}{GEN x, GEN y, struct qfr_data *S} compose two
\kbd{qfr5}, reducing the result, and updating the distance component.

\fun{GEN}{qfr5_pow}{GEN x, GEN n, struct qfr_data *S} compute $x^n$, reducing
along the way.

\fun{GEN}{qfr5_red}{GEN x, struct qfr_data *S} reduce $x$.

\fun{GEN}{qfr5_rho}{GEN x, struct qfr_data *S} perform one reduction step.

\fun{GEN}{qfr5_dist}{GEN e, GEN d, long prec} decode the distance component
from exponential (\kbd{qfr5}-specific) to logarithmic form (as in a
\typ{QFR}).

\fun{GEN}{qfr_to_qfr5}{GEN x, long prec} convert a \typ{QFR} to a
\kbd{qfr5} with initial trivial distance component ($= 1$).

\fun{GEN}{qfr5_to_qfr}{GEN x, GEN d}, assume $x$ is a \kbd{qfr5} and
$d$ was the original distance component of some \typ{QFR} that we converted
using \tet{qfr_to_qfr5} to perform efficiently a number of operations.
Convert $x$ to a \typ{QFR} with the correct (logarithmic) distance component.

\section{Linear algebra over $\Z$}
\subsec{Hermite and Smith Normal Forms}

\fun{GEN}{ZM_hnf}{GEN x} returns the upper triangular Hermite Normal Form of the
\kbd{ZM} $x$ (removing $0$ columns), using the \tet{ZM_hnfall} algorithm. If you
want the true HNF, use \kbd{ZM\_hnfall(x, NULL, 0)}.

\fun{GEN}{ZM_hnfmod}{GEN x, GEN d} returns the HNF of the \kbd{ZM} $x$
(removing $0$ columns), assuming the \typ{INT} $d$ is a multiple of the
determinant of $x$. This is usually faster than \tet{ZM_hnf} (and uses less
memory) if the dimension is large, $> 50$ say.

\fun{GEN}{ZM_hnfmodid}{GEN x, GEN d} returns the HNF of the matrix $(x \mid d
\text{Id})$ (removing $0$ columns), for a \kbd{ZM} $x$ and a \typ{INT} $d$.

\fun{GEN}{ZM_hnfmodall}{GEN x, GEN d, long flag} low-level function
underlying the \kbd{ZM\_hnfmod} variants. If \kbd{flag} is $0$, calls
\kbd{ZM\_hnfmod(x,d)}; \kbd{flag} is an or-ed combination of:

\item \tet{hnf_MODID} call \kbd{ZM\_hnfmodid} instead of \kbd{ZM\_hnfmod},

\item \tet{hnf_PART} return as soon as we obtain an upper triangular matrix,
saving time. The pivots are non-negative and give the diagonal of the true HNF,
but the entries to the right of the pivots need not be reduced, i.e.~they may be
large or negative.

\item \tet{hnf_CENTER} returns the centered HNF, where the entries to the
right of a pivot $p$ are centered residues in $[-p/2, p/2[$, hence smallest
possible in absolute value, but possibly negative.

\fun{GEN}{ZM_hnfall}{GEN x, GEN *U, long remove} returns the upper triangular
HNF $H$ of the \kbd{ZM} $x$; if $U$ is not \kbd{NULL}, set if to the matrix
$U$ such that $x U = H$. If $\kbd{remove} = 0$, $H$ is the true HNF,
including $0$ columns; if $\kbd{remove} = 1$, delete the $0$ columns from $H$
but do not update $U$ accordingly (so that the integer kernel may still be
recovered): we no longer have $x U = H$; if $\kbd{remove} = 2$, remove $0$
columns from $H$ and update $U$ so that $x U = H$. The matrix $U$ is square
and invertible unless $\kbd{remove} = 2$.

This routine uses a naive algorithm which is potentially exponential in the
dimension (due to coefficient explosion) but is fast in practice, although it
may require lots of memory. The base change matrix $U$ may be very large,
when the kernel is large.

\fun{GEN}{ZM_hnfperm}{GEN A, GEN *ptU, GEN *ptperm} returns the hnf
$H = P A U$ of the matrix $P A$, where $P$ is a suitable permutation matrix,
and $U\in \text{Gl}_n(\Z)$. $P$ is chosen so as to (heuristically) minimize the
size of $U$; in this respect it is less efficient than \kbd{ZM\_hnflll}
but usually faster. Set \kbd{*ptU} to $U$ and \kbd{*pterm} to a \typ{VECSMALL}
representing the row permutation associated to $P = (\delta_{i,\kbd{perm}[i]}$.
If \kbd{ptU} is set to \kbd{NULL}, $U$ is not computed, saving some time;
although useless, setting \kbd{ptperm} to \kbd{NULL} is also allowed.

\fun{GEN}{ZM_hnflll}{GEN x, GEN *U, int remove} returns the HNF $H$ of the
\kbd{ZM} $x$; if $U$ is not \kbd{NULL}, set if to the matrix $U$ such that $x
U = H$. The meaning of \kbd{remove} is the same as in \tet{ZM_hnfall}.

This routine uses the \idx{LLL} variant of Havas, Majewski and Mathews, which is
polynomial time, but rather slow in practice because it uses an exact LLL
over the integers instead of a floating point variant; it uses polynomial
space but lots of memory is needed for large dimensions, say larger than 300.
On the other hand, the base change matrix $U$ is essentially optimally small
with respect to the $L_2$ norm.

\fun{GEN}{ZM_hnfcenter}{GEN M}. Given a \kbd{ZM} in HNF $M$, update it in
place so that non-diagonal entries belong to a system of \emph{centered}
residues. Not suitable for gerepile.

Some direct applications: the following routines apply to upper triangular
integral matrices; in practice, these come from HNF algorithms.

\fun{GEN}{hnf_divscale}{GEN A, GEN B,GEN t} $A$ an upper triangular \kbd{ZM},
$B$ a \kbd{ZM}, $t$ an integer, such that $C := tA^{-1}B$ is integral.
Return $C$.

\fun{GEN}{hnf_solve}{GEN A, GEN B} $A$ a \kbd{ZM} in upper HNF (not
necessarily square), $B$ a \kbd{ZM} or \kbd{ZC}. Return $A^{-1}B$ if it is
integral, and \kbd{NULL} if it is not.

\fun{GEN}{hnf_invimage}{GEN A, GEN b} $A$ a \kbd{ZM} in upper HNF
(not necessarily square), $b$ a \kbd{ZC}.  Return $A^{-1}B$ if it is
integral, and \kbd{NULL} if it is not.

\fun{int}{hnfdivide}{GEN A, GEN B} $A$ and $B$ are two upper triangular
\kbd{ZM}. Return $1$ if $A^{-1} B$ is integral, and $0$ otherwise.

\misctitle{Smith Normal Form}

\fun{GEN}{ZM_snf}{GEN x} returns the Smith Normal Form (vector of
elementary divisors) of the \kbd{ZM} $x$.

\fun{GEN}{ZM_snfall}{GEN x, GEN *U, GEN *V} returns
\kbd{ZM\_smith(x)} and sets $U$ and $V$ to unimodular matrices such that $U\,
x\, V = D$ (diagonal matrix of elementary divisors). Either (or both) $U$ or
$V$ may be \kbd{NULL} in which case the corresponding matrix is not computed.

\fun{GEN}{ZM_snfall_i}{GEN x, GEN *U, GEN *V, int returnvec} same as
\kbd{ZM\_snfall}, except that, depending on the value of \kbd{returnvec}, we
either return a diagonal matrix (as in \kbd{ZM\_snfall}, \kbd{returnvec} is 0)
or a vector of elementary divisors (as in \kbd{ZM\_snf}, \kbd{returnvec} is 1) .

\fun{void}{ZM_snfclean}{GEN d, GEN U, GEN V} assuming $d$, $U$, $V$ come
from \kbd{d = ZM\_snfall(x, \&U, \&V)}, where $U$ or $V$ may be \kbd{NULL},
cleans up the output in place. This means that elementary divisors equal to 1
are deleted and $U$, $V$ are updated. The output is not suitable for
\kbd{gerepileupto}.

\fun{GEN}{ZM_snf_group}{GEN H, GEN *U, GEN *Uinv} this function computes data
to go back and forth between an abelian group (of finite type) given by
generators and relations, and its canonical SNF form. Given an abstract
abelian group with generators $g = (g_1,\dots,g_n)$ and a vector
$X=(x_i)\in\Z^n$, we write $g X$ for the group element $\sum_i x_i g_i$;
analogously if $M$ is an $n\times r$ integer matrix $g M$ is a vector
containing $r$ group elements. The group neutral element is $0$; by abuse of
notation, we still write $0$ for a vector of group elements all equal to the
neutral element. The input is a full relation matrix $H$ among the
generators, i.e. a \kbd{ZM} (not necessarily square) such that $gX = 0$ for
some $X\in\Z^n$ if and only if $X$ is in the integer image of $H$, so that
the abelian group is isomorphic to $\Z^n/\text{Im} H$. \emph{The routine
assumes that $H$ is in HNF;} replace it by its HNF if it is not the case. (Of
course this defines the same group.)

Let $G$ a minimal system of generators in SNF for our abstract group:
if the $d_i$ are the elementary divisors ($\dots \mid d_2\mid d_1$), each
$G_i$ has either infinite order ($d_i = 0$) or order $d_i > 1$. Let $D$
the matrix with diagonal $(d_i)$, then
$$G D = 0,\quad G = g U_{\text{inv}},\quad g = G U,$$
for some integer matrices $U$ and $U_{\text{inv}}$. Note that these are not
even square in general; even if square, there is no guarantee that these are
unimodular: they are chosen to have minimal entries given the known relations
in the group and only satisfy $D \mid (U U_{\text{inv}} - \text{Id})$ and $H
\mid (U_{\text{inv}}U - \text{Id})$.

The function returns the vector of elementary divisors $(d_i)$; if \kbd{U} is
not \kbd{NULL}, it is set to $U$; if \kbd{Uinv} is not \kbd{NULL} it is
set to $U_{\text{inv}}$. The function is not memory clean.


The following 3 routines underly the various \tet{matrixqz} variants.
In all case the $m\times n$ \typ{MAT} $x$ is assumed to have rational
(\typ{INT} and \typ{FRAC}) coefficients

\fun{GEN}{QM_ImQ_hnf}{GEN x} returns an HNF basis for
$\text{Im}_\Q x \cap \Z^n$.

\fun{GEN}{QM_ImZ_hnf}{GEN x} returns an HNF basis for
$\text{Im}_\Z x \cap \Z^n$.

\fun{GEN}{QM_minors_coprime}{GEN x, GEN D}, assumes $m\geq n$, and returns
a matrix in $M_{m,n}(\Z)$ with the same $\Q$-image as $x$, such that
the GCD of all $n\times n$ minors is coprime to $D$; if $D$ is \kbd{NULL},
we want the GCD to be $1$.
\smallskip

The following routines are simple wrappers around the above ones and are
normally useless in library mode:

\fun{GEN}{hnf}{GEN x} checks whether $x$ is a \kbd{ZM}, then calls \tet{ZM_hnf}.
Normally useless in library mode.

\fun{GEN}{hnfmod}{GEN x, GEN d} checks whether $x$ is a \kbd{ZM}, then calls
\tet{ZM_hnfmod}. Normally useless in library mode.

\fun{GEN}{hnfmodid}{GEN x,GEN d} checks whether $x$ is a \kbd{ZM}, then calls
\tet{ZM_hnfmodid}. Normally useless in library mode.

\fun{GEN}{hnfall}{GEN x} calls
\kbd{ZM\_hnfall(x, \&U, 1)} and returns $[H, U]$. Normally useless in library
mode.

\fun{GEN}{hnflll}{GEN x} calls \kbd{ZM\_hnflll(x, \&U, 1)} and returns $[H,
U]$. Normally useless in library mode.

\fun{GEN}{hnfperm}{GEN x} calls \kbd{ZM\_hnfperm(x, \&U, \&P)} and returns
$[H, U, P]$. Normally useless in library mode.

\fun{GEN}{smith}{GEN x} checks whether $x$ is a \kbd{ZM}, then calls
\kbd{ZM\_smith}. Normally useless in library mode.

\fun{GEN}{smithall}{GEN x} checks whether $x$ is a \kbd{ZM}, then calls
\kbd{ZM\_smithall(x, \&U, \&V)} and returns $[U,V,D]$. Normally useless in
library mode.

\noindent Some related functions over $K[X]$, $K$ a field:

\fun{GEN}{gsmith}{GEN A} the input matrix must be square, returns the
elementary divisors.

\fun{GEN}{gsmithall}{GEN A} the input matrix must be square, returns the
$[U,V,D]$, $D$ diagonal, such that $UAV = D$.

\fun{GEN}{RgM_hnfall}{GEN A, GEN *pB, long remove} analogous to \tet{ZM_hnfall}.

\fun{GEN}{smithclean}{GEN z} cleanup the output of \kbd{smithall} or
\kbd{gsmithall} (delete elementary divisors equal to $1$, updating base
change matrices).

\subsec{The LLL algorithm}\sidx{LLL}

The basic GP functions and their immediate variants are normally not very
useful in library mode. We briefly list them here for completeness, see the
documentation of \kbd{qflll} and \kbd{qflllgram} for details:

\item \fun{GEN}{qflll0}{GEN x, long flag}

\fun{GEN}{lll}{GEN x} \fl = 0

\fun{GEN}{lllint}{GEN x} \fl = 1

\fun{GEN}{lllkerim}{GEN x} \fl = 4

\fun{GEN}{lllkerimgen}{GEN x} \fl = 5

\fun{GEN}{lllgen}{GEN x} \fl = 8

\item \fun{GEN}{qflllgram0}{GEN x, long flag}

\fun{GEN}{lllgram}{GEN x} \fl = 0

\fun{GEN}{lllgramint}{GEN x} \fl = 1

\fun{GEN}{lllgramkerim}{GEN x} \fl = 4

\fun{GEN}{lllgramkerimgen}{GEN x} \fl = 5

\fun{GEN}{lllgramgen}{GEN x} \fl = 8

\smallskip

The basic workhorse underlying all integral and floating point LLLs is

\fun{GEN}{ZM_lll}{GEN x, double D, long flag}, where $x$ is a \kbd{ZM};
$D \in ]1/4,1[$ is the Lov\'{a}sz constant determining the frequency of
swaps during the algorithm: a larger values means better guarantees for
the basis (in principle smaller basis vectors) but longer running times
(suggested value: $D = 0.99$).

\misctitle{Important} This function does not collect garbage and its output
is not suitable for either \kbd{gerepile} or \kbd{gerepileupto}. We expect
the caller to do something simple with the output (e.g. matrix
multiplication), then collect garbage immediately.

\noindent\kbd{flag} is an or-ed combination of the following flags:

\item  \tet{LLL_GRAM}. If set, the input matrix $x$ is the Gram matrix ${}^t
v v$ of some lattice vectors $v$.

\item  \tet{LLL_INPLACE}. If unset, we return the base change matrix $U$,
otherwise the transformed matrix $x U$ or ${}^t U x U$ (\kbd{LLL\_GRAM}).
Implies \tet{LLL_IM} (see below).

\item  \tet{LLL_KEEP_FIRST}. The first vector in the output basis is the same
one as was originally input. Provided this is a shortest non-zero vector of
the lattice, the output basis is still LLL-reduced. This is used to reduce
maximal orders of number fields with respect to the $T_2$ quadratic form, to
ensure that the first vector in the output basis corresponds to $1$ (which is
a shortest vector).

\item  \tet{LLL_COMPATIBLE}. This is a no-op on 64-bit kernels; on 32-bit
kernels, restrict to 64-bit-compatible accuracies in the course of LLL
algorithms. This is very likely to produce identical results on all
kernels, but this is not guaranteed.

The last three flags are mutually exclusive, either 0 or a single one must be
set:

\item  \tet{LLL_KER} If set, only return a kernel basis $K$ (not LLL-reduced).

\item  \tet{LLL_IM} If set, only return an LLL-reduced lattice basis $T$.
(This is implied by \tet{LLL_INPLACE}).

\item  \tet{LLL_ALL} If set, returns a 2-component vector $[K, T]$
corresponding to both kernel and image.


\fun{GEN}{lllfp}{GEN x, double D, long flag} is a variant for matrices
with inexact entries: $x$ is a matrix with real coefficients (types
\typ{INT}, \typ{FRAC} and \typ{REAL}), $D$ and $\fl$ are as in \tet{ZM_lll}.
The matrix is rescaled, rounded to nearest integers, then fed to
\kbd{ZM\_lll}. The flag \kbd{LLL\_INPLACE} is still accepted but less useful
(it returns an LLL-reduced basis associated to rounded input, instead of an
exact base change matrix).

\fun{GEN}{ZM_lll_norms}{GEN x, double D, long flag, GEN *ptB} slightly more
general version of \kbd{ZM\_lll}, setting \kbd{*ptB} to a vector containing
the squared norms of the Gram-Schmidt vectors $(b_i^*)$ associated to the
output basis $(b_i)$, $b_i^* = b_i + \sum_{j < i} \mu_{i,j} b_j^*$.


\fun{GEN}{lllintpartial_inplace}{GEN x} given a \kbd{ZM} $x$ of maximal rank,
returns a partially reduced basis $(b_i)$ for the space spanned by the
columns of $x$: $|b_i \pm b_j| \geq |b_i|$ for any two distinct basis vectors
$b_i$, $b_j$. This is faster than the LLL algorithm, but produces much larger
bases.

\fun{GEN}{lllintpartial}{GEN x} as \kbd{lllintpartial\_inplace}, but returns
the base change matrix $U$ from the canonical basis to the $b_i$, i.e. $x U$
is the output of \kbd{lllintpartial\_inplace}.

\subsec{Reduction modulo matrices}

\fun{GEN}{ZC_hnfremdiv}{GEN x, GEN y, GEN *Q} assuming $y$ is an
invertible \kbd{ZM} in HNF and $x$ is a \kbd{ZC}, returns the \kbd{ZC} $R$
equal to $x$ mod $y$ (whose $i$-th entry belongs to $[-y_{i,i}/2, y_{i,i}/2[$).
Stack clean \emph{unless} $x$ is already reduced (in which case, returns $x$
itself, not a copy). If $Q$ is not \kbd{NULL}, set it to the \kbd{ZC} such that
$x = yQ + R$.

\fun{GEN}{ZM_hnfdivrem}{GEN x, GEN y, GEN *Q} reduce
each column of the \kbd{ZM} $x$ using \kbd{ZC\_hnfremdiv}. If $Q$ is not
\kbd{NULL}, set it to the \kbd{ZM} such that $x = yQ + R$.

\fun{GEN}{ZC_hnfrem}{GEN x, GEN y} alias for \kbd{ZC\_hnfremdiv(x,y,NULL)}.

\fun{GEN}{ZM_hnfrem}{GEN x, GEN y} alias for \kbd{ZM\_hnfremdiv(x,y,NULL)}.

\fun{GEN}{ZC_reducemodmatrix}{GEN v, GEN y} Let $y$ be a ZM, not necessarily
square, which is assumed to be LLL-reduced (otherwise, very poor reduction is
expected). Size-reduces the ZC $v$ modulo the $\Z$-module $Y$ spanned by $y$
: if the columns of $y$ are denoted by $(y_1,\dots, y_{n-1})$, we return $y_n
\equiv v$ modulo $Y$, such that the Gram-Schmidt coefficients $\mu_{n,j}$ are
less than $1/2$ in absolute value for all $j < n$. In short, $y_n$ is almost
orthogonal to $Y$.

\fun{GEN}{ZM_reducemodmatrix}{GEN v, GEN y} Let $y$ be as in
\tet{ZC_reducemodmatrix}, and $v$ be a ZM. This returns a matrix $v$ which is
congruent to $v$ modulo the $\Z$-module spanned by $y$, whose columns are
size-reduced. This is faster than repeatedly calling \tet{ZC_reducemodmatrix}
on the columns since most of the Gram-Schmidt coefficients can be reused.

\fun{GEN}{ZC_reducemodlll}{GEN v, GEN y} Let $y$ be an arbitrary ZM,
LLL-reduce it then call \tet{ZC_reducemodmatrix}.

\fun{GEN}{ZM_reducemodlll}{GEN v, GEN y} Let $y$ be an arbitrary ZM,
LLL-reduce it then call \tet{ZM_reducemodmatrix}.

Besides the above functions, which were specific to integral input, we also
have:

\fun{GEN}{reducemodinvertible}{GEN x, GEN y} $y$ is an invertible matrix
and $x$ a \typ{COL} or \typ{MAT} of compatible dimension.
Returns $x - y\lfloor y^{-1}x \rceil$, which has small entries and differs
from $x$ by an integral linear combination of the columns of $y$. Suitable
for \kbd{gerepileupto}, but does not collect garbage.

\fun{GEN}{closemodinvertible}{GEN x, GEN y} returns $x -
\kbd{reducemodinvertible}(x,y)$, i.e. an integral linear combination of
the columns of $y$, which is close to $x$.

\fun{GEN}{reducemodlll}{GEN x,GEN y} LLL-reduce the non-singular \kbd{ZM} $y$
and call \kbd{reducemodinvertible} to find a small representative of $x$ mod $y
\Z^n$. Suitable for \kbd{gerepileupto}, but does not collect garbage.

\subsec{Miscellaneous}

\fun{GEN}{RM_round_maxrank}{GEN G} given a matrix $G$ with real floating
point entries and independent columns, let $G_e$ be the
rescaled matrix $2^e G$ rounded to nearest integers, for $e \geq 0$.
Finds a small $e$ such that the rank of $G_e$ is equal to the rank of $G$
(its number of columns) and return $G_e$. This is useful as a preconditioning
step to speed up LLL reductions, see \tet{nf_get_Gtwist}.
Suitable for \kbd{gerepileupto}, but does not collect garbage.

\section{Central simple algebras}

\fun{void}{checkal}{GEN a} raise an exception if $a$ was not initialized
by \tet{alinit}.

\fun{long}{al_type}{GEN al} internal function called by \tet{altype}: assume
\kbd{al} was created by \tet{alinit} (thereby saving a call to \kbd{checkal}).

\newpage
