/usr/share/pari/doc/usersch6.tex

% 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{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{GEN}{checkbnf_i}{GEN bnf} same as \kbd{checkbnf} but return \kbd{NULL}
instead of raising an exception.

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

\fun{GEN}{checknf_i}{GEN nf} same as \kbd{checknf} but return \kbd{NULL}
instead of raising an exception.

\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{int}{checkrnf_i}{GEN rnf} same as \kbd{checkrnf} but return $0$
on failure and $1$ on success.

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

\fun{GEN}{checkbid_i}{GEN bid} same as \kbd{checkbid} but return \kbd{NULL}
instead of raising an exception and return \kbd{bid} on success.

\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{int}{checkprid_i}{GEN pr} same as \kbd{checkprid} but return $0$
instead of raising an exception and return $1$ on success.

\fun{int}{is_nf_factor}{GEN F} return $1$ if $F$ is an ideal factorization
and $0$ otherwise.

\fun{int}{is_nf_extfactor}{GEN F} return $1$ if $F$ is an extended ideal
factorization (allowing $0$ or negative exponents) and $0$ otherwise.

\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
\kbd{modpr} structure (from \kbd{nfmodprinit}).

\fun{GEN}{get_modpr}{GEN x} return $x$ if it is a \kbd{modpr} structure
and \kbd{NULL} otherwise.

\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 attached
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 attached 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} attached
to the \var{bnr} modulus.

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

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

These functions expect a true \var{rnf} argument, attached 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$ attached 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$ attached 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 attached 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, attached to a modulus $I
= I_0 I_\infty$ in a number field $K$.

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

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

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

\fun{GEN}{bid_get_arch}{GEN bid} return the Archimedean part $I_\infty$
of the \var{bid} modulus as a vector of real places in vec01 format,
see~\secref{se:signatures}.

\fun{GEN}{bid_get_archp}{GEN bid} return the Archimedean part $I_\infty$
of the \var{bid} modulus, as a vector of real places in indices format
see~\secref{se:signatures}.

\fun{GEN}{bid_get_fact}{GEN bid} returns the ideal factorization
$I_0 = \prod_i \goth{p}_i^{e_i}$.

\tet{bid_get_ideal}$(\var{bid})$, via \kbd{idealfactor}.

\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!

\fun{GEN}{bid_get_sprk}{GEN bid} return a list of structures attached to the
$(\Z_K/\goth{p}^e)^*$ where $\goth{p}^e$ divides $I_0$ exactly.

\fun{GEN}{bid_get_sarch}{GEN bid} return the structure attached
to $(\Z_K/I_\infty)^*$, by \kbd{nfarchstar}.

\fun{GEN}{bid_get_U}{GEN bid} return the matrix with integral coefficients
relating the local generators (from chinese remainders) to the global
SNF generators (\kbd{\var{bid}.gen}).

\fun{GEN}{bid_get_ind}{GEN bid} return a \typ{VECSMALL} $v$ of indices used
while converting from local generators to the global generators: $v[i]$
is the number of generators used to describe $(\Z_K / \prod_{j < i}
\goth{p}_j^{e_j})^*$.

\subsec{Inserting info in a number field structure}

If the required data is not part of the structure, it is computed then
inserted, and the new value is returned.

These functions expect a \kbd{bnf} argument:

\fun{GEN}{bnf_build_cycgen}{GEN bnf} the \var{bnf}
contains generators $[g_1,\ldots,g_k]$ of the class group, each with order
$d_i$. Then $g_i^{d_i} = (x_i)$ is a principal ideal. This function returns
the $x_i$ as a factorization matrix (\kbd{famat}) giving the element in
factored form as a product of $S$-units.

\fun{GEN}{bnf_build_matalpha}{GEN bnf} the class group was
computed using a factorbase $S$ of prime ideals $\goth{p}_i$, $i \leq r$.
They satisfy relations of the form $\prod_j \goth{p}_i^{e_{i,j}} = (\alpha_j)$,
where the $e_{i,j}$ are given by the matrices $\var{bnf}[1]$ ($W$, singling
out a minimal set of generators in $S$) and $\var{bnf}[2]$ ($B$, expressing the
rest of $S$ in terms of the singled out generators). This function returns the
$\alpha_j$ in factored form as a product of $S$-units.

\fun{GEN}{bnf_build_units}{GEN bnf} returns a minimal set of generators
for the unit group. The first element is a torsion unit, the others have
infinite order.

These functions expect a \kbd{rnf} argument:

\fun{GEN}{rnf_build_nfabs}{GEN rnf, long prec} given a \var{rnf} structure
attched to $L/K$, (compute and) return an \var{nf} structure attached to $L$
at precision \kbd{prec}.

\fun{void}{rnfcomplete}{GEN rnf} as \tet{rnf_build_nfabs} using the precision
of $K$ for \kbd{prec}.

\fun{GEN}{rnf_zkabs}{GEN rnf} returns a $\Z$-basis in HNF for $\Z_L$ as a
pair $[T, v]$, where $T$ is \tet{rnf_get_polabs}$(\var{rnf})$ and $v$
a vector of elements lifted from $\Q[X]/(T)$. Note that \tet{rnf_build_nfabs}
essentially applies \kbd{nfinit} to the output of this function.

\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}{nfsub}{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}$ attached to the \var{prid} \kbd{pr}.
Returns \kbd{LONG\_MAX} if $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 = nfsub(nf, a, nfmul(nf,q,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 = nfsub(nf, a, nfmul(nf,q,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}{nfC_multable_mul}{GEN v, GEN mx} same as \tet{nfC_nf_mul},
where the argument $x$ is replaced by its multiplication table \kbd{mx}.

\fun{GEN}{zkC_multable_mul}{GEN v, GEN x} same as \tet{nfC_nf_mul},
where $v$ is a vector of algebraic integers, $x$ is an algebraic
integer, and $x$ is replaced by \kbd{zk\_multable}$(x)$.

\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_inv}{GEN nf, GEN x} given a \kbd{ZC} $x$ (implicitly
representing an algebraic integer), returns the \kbd{QC} giving the
inverse $x^{-1}$. Return \kbd{NULL} if $x$ is $0$.
Not memory clean but safe for \kbd{gerepileupto}.

\fun{GEN}{zkmultable_inv}{GEN mx} as \tet{zk_inv}, where
the argument given is \kbd{zk\_multable}$(x)$.

\fun{GEN}{zkmultable_capZ}{GEN mx} given a non-zero \var{zkmultable}
\var{mx} attached to $x \in \Z_K$, return the positive generator of
$(x)\cap \Z$.

\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]$.

The following routines implement naive linear algebra using the \emph{black box
field} mechanism:

\fun{GEN}{nfM_det}{GEN nf, GEN M}

\fun{GEN}{nfM_inv}{GEN nf, GEN M}

\fun{GEN}{nfM_mul}{GEN nf, GEN A, GEN B}

\fun{GEN}{nfM_nfC_mul}{GEN nf, GEN A, GEN B}

\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} shallow version of \tet{famat_mul}.

\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_pow_shallow}{GEN f, GEN n} shallow version of \tet{famat_pow}.

\fun{GEN}{famat_mulpow_shallow}{GEN f, GEN g, GEN e} \kbd{famat}
corresponding to $f \cdot g^e$. Shallow function.

\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 or a rational number, and
\kbd{pr} a \var{prid} attached 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 or a rational number, and
\kbd{pr} a \var{prid} attached to $\goth{p}$. Not suitable for
\tet{gerepileupto} since it retunrs $x$ when $n = 0$.

\fun{GEN}{idealprodprime}{GEN nf, GEN v} given a list $v$ of prime ideals
in \var{prid} form, return their product. Assume that \var{nf} is a true
\var{nf} structure.

\fun{GEN}{idealprod}{GEN nf, GEN v} given a list $v$ of ideals,
return their product. Assume that \var{nf} is a true \var{nf} structure.

\fun{GEN}{idealHNF_mul}{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$).

\fun{GEN}{idealHNF_inv}{GEN nf, GEN I} returns $I^{-1}$, assuming that
\kbd{nf} is a true \var{nf} and $x$ is a fractional ideal in HNF.

\fun{GEN}{idealHNF_inv_Z}{GEN nf, GEN I} returns $(I\cap \Z) \cdot I^{-1}$,
assuming that \kbd{nf} is a true \var{nf} and $x$ is an integral fractional
ideal in HNF. The result is an integral ideal in HNF.

\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}{zkchineseinit}{GEN nf, GEN A, GEN B, GEN AB} given two coprime
integral ideals $A$ and $B$ (in any form, preferably HNF) and
their product \kbd{AB} (in HNF form), initialize a solution to the Chinese
remainder problem modulo $AB$.

\fun{GEN}{zkchinese}{GEN zkc, GEN x, GEN y} given \kbd{zkc} from
\kbd{zkchineseinit}, and $x$, $y$ two integral elements given as \typ{INT}
or \kbd{ZC}, return a $z$ modulo $AB$ such that
$z = x \mod A$ and $z = y \mod B$.

\fun{GEN}{zkchinese1}{GEN zkc, GEN x} as \kbd{zkchinese} for $y = 1$; useful
to lift elements in a nice way from $(\Z_K/A_i)^*$ to $(\Z_K/\prod_i A_i)^*$.

\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}{idealapprfact}{GEN nf, GEN fx} as \tet{idealappr}, except that
$x$ \emph{must} be given in factored form. (This is unchecked.)

\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}

\fun{GEN}{idealchineseinit}{GEN nf, GEN x}

\subsec{Maximal ideals}

The PARI structure attached 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} attached 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).

\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{ulong}{upr_norm}{GEN pr} returns the norm $p^f$ of the maximal ideal, as
an \kbd{ulong}. Assume that the result does not overflow.

\fun{GEN}{pr_inv}{GEN pr} return the fractional ideal $\goth{p}^{-1}$, in HNF.

\fun{GEN}{pr_inv_p}{GEN pr} return the integral ideal $p \goth{p}^{-1}$, in HNF.

\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}.

\fun{GEN}{idealprimedec_kummer}{GEN nf, GEN Ti, long ei, GEN p} let \var{nf}
(true \var{nf}) correspond to $K = \Q[X]/(T)$ ($T$ monic \kbd{ZX}).
Let $T \equiv \prod_i T_i^{e_i} \pmod{p}$ be the factorization of $T$ and let
$(f,g,h)$ be as in Dedekind criterion for prime $p$: $f \equiv \prod T_i$,
$g \equiv \prod T_i^{e_i-1}$, $h = (T - fg) / p$, and let $D$ be the gcd
of $(f,g,h)$ in $\F_p[X]$. Let \kbd{Ti} (\kbd{FpX}) be one irreducible factor
$T_i$ not dividing $D$, with \kbd{ei} $= e_i$. This function returns the
prime ideal attached to $T_i$ by Kummer / Dedekind criterion, namely
$p \Z_K + T_i(\bar{X}) \Z_K$, which has ramification index $e_i$ over $p$.
Shallow function.

\fun{GEN}{idealHNF_Z_factor}{GEN x, GEN *pvN, GEN *pvZ} given an integral
(non-$0$) ideal $x$ in HNF, compute both the factorization of $Nx$ and
of $x\cap\Z$. This returns the vector of prime divisors of both
and sets \kbd{*pvN} and \kbd{*pvZ} to the corresponding \typ{VECSMALL} vector
of exponents for the factorization for the Norm and intersection with $\Z$
respetively.

\fun{GEN}{nf_pV_to_prV}{GEN}{nf, GEN P} given a vector of rational primes
$P$, return the vector of all prime ideals above the $P[i]$.

\fun{GEN}{nf_deg1_prime}{GEN nf} let \kbd{nf} be a true \var{nf}. This
function returns a degree $1$ (unramified) prime ideal not dividing
\kbd{nf.index}. In fact it returns an ideal above the smallest prime
$p \geq [K:\Q]$ satisfying those conditions.

\fun{GEN}{prV_lcm_capZ}{GEN L} given a vector $L$ of \var{prid}
(maximal ideals) return the squarefree positive integer generating their
lcm intersected with $\Z$. Not \kbd{gerepile}-safe.

\fun{GEN}{pr_uniformizer}{GEN pr, GEN F} given a \var{prid} attached to
$\goth{p} / p$ and $F$ in $\Z$ divisible exactly by $p$, return an
$F$-uniformizer for \kbd{pr}, i.e. a $t$ in $\Z_K$ such that $v_{\goth{p}}(t)
= 1$ and $(t, F/\goth{p}) = 1$. Not \kbd{gerepile}-safe.

\subsec{Decomposition group}

\fun{GEN}{idealramfrobenius}{GEN nf, GEN gal, GEN pr, GEN ram}
Let $K$ be the number field defined by $nf$ and assume $K/\Q$ be a
Galois extension with Galois group given \kbd{gal=galoisinit(nf)},
and that $pr$ is the prime ideal $\goth{P}$ in prid format, and that
$\goth{P}$ is ramified, and \kbd{ram} is its list of ramification groups as
output by \kbd{idealramgroups}.
This function returns a permutation of \kbd{gal.group} which defines an
automorphism $\sigma$ in the decomposition group of $\goth{P}$
such that if $p$ is the unique prime number
in $\goth{P}$, then $\sigma(x)\equiv x^p\mod\P$ for all $x\in\Z_K$.

\fun{GEN}{idealfrobenius_aut}{GEN nf, GEN gal, GEN aut, GEN pr}
faster version of \tet{idealfrobenius(nf, gal, pr} where
\kbd{aut} must be equal to \kbd{nfgaloispermtobasis(nf, gal)}.

\subsec{Reducing modulo maximal ideals}

\fun{GEN}{nfmodprinit}{GEN nf, GEN pr} returns an abstract \kbd{modpr}
structure, attached 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 attached 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}.

The following function is technical and may avoid computing a true
\kbd{nfmodpr}:

\fun{GEN}{pr_basis_perm}{GEN nf, GEN pr} given a true \var{nf} structure
and a prime ideal \kbd{pr} above $p$, return as a \typ{VECSMALL} the
$f(\goth{p}/p)$ indices $i$ such that the \kbd{nf.zk}$[i]$ mod \goth{p}
form an $\F_p$-basis of the residue field.

\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}\label{se: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
return as a \typ{VECSMALL} the list of indices $i$ such that $v[i] \neq 0$.
(Typically used with $0,1$-vectors but not necessarily so.) 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$ (attached 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{int}{nfchecksigns}{GEN nf, GEN x, GEN pl} \var{pl} is a
\typ{VECSMALL} with $r_1$ components, all of which are in $\{-1,0,1\}$.
Return $1$ if $\sigma_i(x) \var{pl}[i] \geq 0$ for all $i$, and $0$ otherwise.

\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 sarch}
let $f = f_0f_\infty$ be a divisor, let \kbd{sarch} be the output of
\kbd{nfarchstar(nf, f0, finf)}, and let $x,y$ be two number field elements.
Returns $yt$ with $t$ integral, $t = 1 \text{mod}^* f_0$ such that $x$ and
$ty$ have the same signs at $f_\infty$; if $x = \kbd{NULL}$, make $ty$
totally positive at $f_\infty$.

\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, \var{finf}]$, 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, conversion to \kbd{nf} structure}

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$ (monic \kbd{ZX}), 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, both of them
deprecated:

\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}]$ format 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.

\fun{void}{nfinit_basic}{nfmaxord_t *S, GEN T0} a wrapper around
\kbd{nfmaxord} (without the deprecated \kbd{flag}) that also accepts number
field structures (\var{nf}, \var{bnf}, \dots) for \kbd{T0}.

\fun{GEN}{nfmaxord_to_nf}{nfmaxord_t *S, GEN ro, long prec} convert an
\tet{nfmaxord_t} to an \var{nf} structure at precision \kbd{prec},
where \kbd{ro} is \kbd{NULL}. The argument \kbd{ro} may also be set to a
vector with $r_1 + r_2$ components containing the roots of \kbd{S->T}
suitably ordered, i.e. first $r_1$ \typ{REAL} roots, then $r_2$ \typ{COMPLEX}
representing the conguate pairs, but this is \emph{strongly discouraged}: the
format is error-prone, and it is hard to compute the roots to the right
accuracy in order to achieve \kbd{prec} accuracy for the \kbd{nf}. This
function uses the integer basis \kbd{S->basis} as is, \emph{without}
performing LLL-reduction. Unless the basis is already known to be reduced,
use rather the following higher-level function:

\fun{GEN}{nfinit_complete}{nfmaxord_t *S, long flag, long prec} convert
an \tet{nfmaxord_t} to an \var{nf} structure at precision \kbd{prec}.
The \kbd{flag} has the same meaning as in \kbd{nfinitall}. If
\kbd{S->basis} is known to be reduced, it will be faster to
use \tet{nfmaxord_to_nf}.

\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.

\fun{void}{bnftestprimes}{GEN bnf, GEN B} is an ingredient to certify
unconditionnally a \kbd{bnf} computed assuming GRH, cf. \kbd{bnfcertify}.
Running this function successfully proves that the classes of all prime
ideals of norm $\leq B$ belong to the subgroup of the class group generated
by the factorbase used to compute the \kbd{bnf} (equal to the class group
under GRH). If the condition is not true, then (GRH is false and) the
function will run forever.

If it is known that primes of norm less than $B$ generate the class group
(through variants of Minkowski's convex body or Zimmert's twin classes
theorems), then the true class group is proven to be a quotient of
\kbd{bnf.clgp}.

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

We assume the \var{nf} is a true \kbd{nf} structure, attached 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}, attached 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. For
convenience, also allow $v = $\kbd{NULL} (\tet{nf_get_roundG}) and $v$
a \typ{MAT} as output from the function itself: in both these cases,
shallow function.

\fun{GEN}{nf_get_Gtwist1}{GEN nf, long i}. Simple special case. Returns the
twisted $G$ matrix attached 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}{idealpseudored}{GEN x, GEN G}. As \tet{idealpseudomin} but we
return the full reduced $\Z$-basis of $x$ as a \typ{MAT} instead of a single
vector.

\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 an $a\in K^*$ such that
$(a) x$ is integral of small norm and returns it, 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_\Z) x^(-1),G)$
divided by $x_\Z$, where $x_\Z = (x\cap \Z)$ and 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).

\fun{GEN}{idealmoddivisor}{GEN bnr, GEN x} A proof-of-concept implementation,
useless in practice. If \kbd{bnr} is attached 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} attached to a number field $K$, a \var{bid} structure
attached 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$).

\fun{GEN}{nf_to_Fp_coprime}{GEN nf, GEN x, GEN modpr} a low-level simple
variant of \tet{famat_to_nf_modideal_coprime}: \var{nf} is a true \var{nf}
structure, \kbd{modpr} is from \kbd{zkmodprinit} attached to a prime of
degree $1$ above the prime number $p$, and $x$ is either a number field
element or a \kbd{famat} factorization matrix. We finally assume that
no component of $x$ has a denominator $p$.


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
attached 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}).

\fun{GEN}{Idealstarprk}{GEN nf, GEN pr, long k, long flag} same as
\kbd{Idealstar} for $I = \kbd{pr}^k$

\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{GEN}{bnrconductor_i}{GEN bnr, GEN H, long flag} shallow
variant of \kbd{bnrconductor}. Useful when $\fl=2$ and the conductor
is the \kbd{bnr} modulus: avoids copying the \kbd{bnr} (wasteful).

\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}{bnrchar_primitive}{GEN bnr, GEN chi, GEN bnrc}
Given a normalized character $\kbd{chi} = [d,c]$ on \kbd{bnr.clgp} (see
\tet{char_normalize}) of conductor \kbd{bnrc.mod},  compute the primitive
character \kbd{chic} on \kbd{bnrc.clgp} equivalent to \kbd{chi}, given as a
normalized character $[D,C]$ : \kbd{chic(bnrc.gen[i])} is $\zeta_D^{C[i]}$,
where $D$ is minimal. It is easier to use \kbd{bnrconductor\_i(bnr,chi,2)},
but the latter recomputes \kbd{bnrc} for each new character.

\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 attached \var{bnr}, and set $H$ to the attached 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 attached 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 in \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.

\fun{GEN}{nfroots_if_split}{GEN *pt, GEN T} let \kbd{*pt} point
either to a number field structure or an irreducible \kbd{ZX}, defining
a number field $K$. Given $T$ a monic squarefree polynomial with
coefficients in $\Z_K$, return the list of roots of \kbd{pol} in $K$
if the polynomial splits completely, and \kbd{NULL} otherwise.
In other words, this checks whether $K[X]/(T)$ is normal over $K$ (hence
Galois since $T$ is separable by assumption).

In the case where \kbd{*pT} is a \kbd{ZX}, the function has to compute
internally a conditional \kbd{nf} attached to $K$ , whose \kbd{nf.zk} may not
define the maximal order $\Z_K$ (see \kbd{nfroots}); \kbd{*pT} is then
replaced by the conditional \kbd{nf} to avoid losing that information.

\subsec{Cyclotomics units}

\fun{GEN}{nfrootsof1}{GEN nf} returns a two-component vector $[w,z]$ where $w$
is the number of roots of unity in the number field \var{nf}, and $z$ is a
primitive $w$-th root of unity.

\fun{GEN}{nfcyclotomicunits}{GEN nf, GEN zu} where \kbd{zu} is as output by
\kbd{nfrootsof1(nf)}, return the vector of the cyclotomic units in \kbd{nf}
expressed over the integral basis.

\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{bnrdisclist0}:

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

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

\noindent Superseded by \tet{idealappr} (\fl is ignored)

\fun{GEN}{idealappr0}{GEN nf, GEN x, long flag}

\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}{nfgaloispermtobasis}{GEN nf, GEN gal}
return the images of the field generator by the automorphisms
\kbd{gal.orders} expressed on the integral basis \kbd{nf.zk}.

\fun{GEN}{nfgaloismatrix}{GEN nf, GEN s} returns the \kbd{ZM} attached 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$.

\fun{int}{qfb_equal1}{GEN q} returns 1 if the \typ{QFI} or \typ{QFR}
$q$ is the unit form.

\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{Order, discrete log}

\fun{GEN}{qfi_order}{GEN q, GEN o}
assuming that the \typ{QFI} $q$ has order dividing $o$, compute its
order in the class group. The order can be given in all formats allowed by
generic discrete log functions, the preferred format being \kbd{[ord, fa]}
(\typ{INT} and its factorization).

\fun{GEN}{qfi_log}{GEN a, GEN g, GEN o} given a \typ{QFI} $a$ and assuming
that the \typ{QFI} $g$ has order $o$, compute an integer $k$ such that $a^k =
g$. Return \kbd{cgetg(1, t\_VEC)} if there are no solutions. Uses a generic
Pollig-Hellman algorithm, then either Shanks (small $o$) or Pollard rho
(large $o$) method. The order can be given in all formats allowed by generic
discrete log functions, the preferred format being \kbd{[ord, fa]}
(\typ{INT} and its factorization).

\fun{GEN}{qfi_Shanks}{GEN a, GEN g, long n} given a \typ{QFI} $a$ and
assuming that the \typ{QFI} $g$ has (small) order $n$, compute an integer $k$
such that $a^k = g$. Return \kbd{cgetg(1, t\_VEC)} if there are no solutions.
Directly uses Shanks algorithm, which is inefficient when $n$ is composite.

\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_hnfmodall_i}{GEN x, GEN d, long flag} as \tet{ZM_hnfmodall}
without final garbage collection. Not \kbd{gerepile}-safe.

\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_hnfall_i}{GEN x, GEN *U, long remove} as \tet{ZM_hnfall} without
final garbage collection. Not \kbd{gerepile}-safe.

\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 attached 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_hnf_knapsack}{GEN x} given a \kbd{ZM} $x$, compute its
HNF $h$. Return $h$ if it has the knapsack property: every column contains
only zeroes and ones and each row contains a single $1$;
return \kbd{NULL} otherwise. Not suitable for gerepile.

\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_invscale}{GEN A, GEN t} $A$ an upper triangular \kbd{ZM},
$t$ an integer such that $C := tA^{-1}$ is integral. Return $C$. Special case
of \tet{hnf_divscale} when $B$ is the identity matrix.

\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\_snf(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}{ZV_snfall}{GEN d, GEN *U, GEN *V} here $d$ is a \kbd{ZV}; same as
\tet{ZM_snfall} applied to \kbd{diagonal(d)}, but faster.

\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{void}{ZV_snf_trunc}{GEN D} given a vector $D$ of elementary divisors
(i.e. a \kbd{ZV} such that $d_i \mid d_{i+1}$), truncate it \emph{in place}
to leave out the trivial divisors (equal to $1$).

\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.

\fun{GEN}{ZV_snf_group}{GEN d, GEN *newU, GEN *newUi}, here $d$ is a
\kbd{ZV}; same as \tet{ZM_snf_group} applied to \kbd{diagonal(d)}, but faster.


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\_snf}. Normally useless in library mode.

\fun{GEN}{smithall}{GEN x} checks whether $x$ is a \kbd{ZM}, then calls
\kbd{ZM\_snfall(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 attached 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^*)$ attached 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}.

\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.

\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.

\section{Finite abelian groups and characters}

\subsec{Abstract groups}

A finite abelian group $G$ in GP format is given by its Smith
Normal Form as a pair $[h,d]$ or triple $[h,d,g]$.
Here $h$ is the cardinality of $G$, $(d_i)$ is the vector of elementary
divisors, and $(g_i)$ is a vector of generators. In short,
$G = \oplus_{i\leq n} (\Z/d_i\Z) g_i$, with $d_n \mid \dots \mid d_2 \mid d_1$
and $\prod d_i = h$.

Let $e(x) := \exp(2i\pi x)$. For ease of exposition, we restrict to
complex-valued characters, but everything applies to more general fields $K$
where $e$ denotes a morphism $(\Q,+) \to (K^*,\times)$ such that $e(a/b)$
denotes a $b$-th root of unity.

A \tev{character} on the abelian group $\oplus (\Z/d_j\Z) g_j$
is given by a row vector $\chi = [a_1,\ldots,a_n]$ such that
$\chi(\prod g_j^{n_j}) = e(\sum a_j n_j / d_j)$.

\fun{GEN}{cyc_normalize}{GEN d} shallow function. Given a vector
$(d_i)_{i \leq n}$
of elementary divisors for a finite group (no $d_i$ vanish), returns the vector
$D = [1]$ if $n = 0$ (trivial group) and
 $[d_1, d_1/d_2, \dots, d_1/d_n]$ otherwise. This will allow to define
characters as $\chi(\prod g_j^{x_j}) = e(\sum_j x_j a_j D_j / D_1)$,
see \tet{char_normalize}.

\fun{GEN}{char_normalize}{GEN chi, GEN ncyc} shallow function. Given a
character \kbd{chi} $ = (a_j)$ and \var{ncyc} from \kbd{cyc\_normalize}
above, returns the normalized representation $[d, (n_j)]$, such that
$\chi(\prod g_j^{x_j}) = \zeta_d^{\sum_j n_j x_j}$, where $\zeta_d =
e(1/d)$ and $d$ is \emph{minimal}. In particular, $d$ is the order
of \kbd{chi}. Shallow function.

\fun{GEN}{char_simplify}{GEN D, GEN N} given a quasi-normalized character
$[D, (N_j)]$ such that $\chi(\prod g_j^{x_j}) = \zeta_D^{\sum_j N_j x_j}$,
but where we only  assume that $D$ is a multiple of the character
order, return a normalized character $[d, (n_j)]$ with $d$ \emph{minimal}.
Shallow function.

\fun{GEN}{char_denormalize}{GEN cyc, GEN d, GEN n} given a normalized
representation $[d, n]$ (where $d$ need not be minimal) of a character on the
abelian group with abelian divisors \kbd{cyc}, return the attached character
(where the image of each generator $g_i$ is given in terms of roots
of unity of different orders $\kbd{cyc}[i]$).

\fun{GEN}{charconj}{GEN cyc, GEN chi} return the complex conjugate of
\kbd{chi}.

\fun{GEN}{charmul}{GEN cyc, GEN a, GEN b} return the product character $a\times
b$.

\fun{GEN}{chardiv}{GEN cyc, GEN a, GEN b} returns the character
$a / b = a \times \overline{b}$.

\fun{int}{char_check}{GEN cyc, GEN chi} return $1$ if \kbd{chi} is a character
compatible with cyclic factors \kbd{cyc}, and $0$ otherwise.

\fun{GEN}{cyc2elts}{GEN d} given a \typ{VEC} $d = (d_1,\dots,d_n)$
of non-negative integers, return the vector of all \typ{VECSMALL}s of length
$n$ whose $i$-th entry lies in $[0,d_i]$. Assumes that the product
of the $d_i$ fits in a \kbd{long}.

\subsec{Dirichlet characters}

The functions in this section are  specific to characters on $(\Z/N\Z)^*$.
The argument $G$ is a special \kbd{bid} structure as returned by
\kbd{znstar0(N, nf\_INIT)}. In this case, there are additional ways
to input character via Conrey's representation. The character \kbd{chi} is
either a \typ{INT} (Conrey label), a \typ{COL} (a Conrey logarithm) or a
\typ{VEC} (generic character on \kbd{bid.gen} as explained in the previous
subsection). The following low-level functions are called by GP's generic
character functions.

\fun{int}{zncharcheck}{GEN G, GEN chi} return $1$ if \kbd{chi} is
a valid character and $0$ otherwise.

\fun{GEN}{zncharconj}{GEN G, GEN chi} as \kbd{charconj}.

\fun{GEN}{znchardiv}{GEN G, GEN a, GEN b} as \kbd{chardiv}.

\fun{GEN}{zncharker}{GEN G, GEN chi} as \kbd{charker}.

\fun{GEN}{znchareval}{GEN G, GEN chi, GEN n, GEN z} as \kbd{chareval}.

\fun{GEN}{zncharmul}{GEN G, GEN a, GEN b} as \kbd{charmul}.

\fun{GEN}{zncharorder}{GEN G,  GEN chi} as \kbd{charorder}.

The following functions handle characters in Conrey notation (attached to
Conrey generators, not \kbd{G.gen}):

\fun{int}{znconrey_check}{GEN cyc, GEN chi} return $1$ if \kbd{chi} is
a valid Conrey logarithm and $0$ otherwise.

\fun{GEN}{znconrey_normalized}{GEN G, GEN chi} return normalized character
attached to \kbd{chi}, as in \kbd{char\_normalize} but on Conrey generators.

\fun{GEN}{znconreyfromchar}{GEN G, GEN chi} return Conrey logarithm
attached to the generic (\typ{VEC}, on \kbd{G.gen})

\fun{GEN}{znconreyfromchar_normalized}{GEN G, GEN chi} return normalized
Conrey character attached to the generic (\typ{VEC}, on \kbd{G.gen})
character \kbd{chi}.

\fun{GEN}{znconreylog_normalize}{GEN G, GEN m} given a Conrey logarithm $m$
(\typ{COL}), return the attached normalized Conrey character, as in
\kbd{char\_normalize} but on Conrey generators.

\fun{GEN}{Zideallog}{GEN G, GEN x} return the \kbd{znconreylog} of $x$
expressed on \kbd{G.gen}, i.e. the ordinary discrete logarithm
from \kbd{ideallog}.

\section{Central simple algebras}

\subsec{Initialization}

Low-level routines underlying \kbd{alginit}.

\fun{GEN}{alg_csa_table}{GEN nf, GEN mt, long v, long flag}
algebra defined by a multiplication table.

\fun{GEN}{alg_cyclic}{GEN rnf, GEN aut, GEN b, long flag}
cyclic algebra.

\fun{GEN}{alg_hasse}{GEN nf, long d, GEN hi, GEN hf, long v, long flag}
algebra defined by local Hasse invariants.

\fun{GEN}{alg_hilbert}{GEN nf, GEN a, GEN b, long v, long flag}
quaternion algebra.

\fun{GEN}{alg_matrix}{GEN nf, long n, long v, GEN L, long flag}
matrix algebra.

\subsec{Type checks}

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

\fun{long}{alg_type}{GEN al} internal function called by \tet{algtype}: assume
\kbd{al} was created by \tet{alginit} (thereby saving a call to \kbd{checkalg}).
Return values are symbolic rather than numeric:

\item \kbd{al\_NULL}: not a valid algebra.

\item \kbd{al\_TABLE}: table algebra output by \kbd{algtableinit}.

\item \kbd{al\_CSA}: central simple algebra output by \kbd{alginit} and
represented by a multiplication table over its center.

\item \kbd{al\_CYCLIC}: central  simple  algebra  output  by \kbd{alginit} and
represented by a cyclic algebra.

\fun{long}{alg_model}{GEN al, GEN x} given an element $x$ in algebra \var{al},
check for inconsistencies (raise a type error) and return the representation
model used for $x$:

\item \kbd{al\_ALGEBRAIC}: \kbd{basistoalg} form, algebraic representation.

\item \kbd{al\_BASIS}: \kbd{algtobasis} form, column vector on the integral
basis.

\item \kbd{al\_MATRIX}: left multiplication table.

\item \kbd{al\_TRIVIAL}: trivial algebra of degree $1$; can be understood
as both basis or algebraic form (since $e_1 = 1$).

\subsec{Shallow accessors}

All these routines assume their argument was initialized by \tet{alginit}
and provide minor speedups compared to the GP equivalent. The routines
returning a \kbd{GEN} are shallow.

\fun{long}{alg_get_absdim}{GEN al} low-level version of \kbd{algabsdim}.

\fun{long}{alg_get_dim}{GEN al} low-level version of \kbd{algdim}.

\fun{long}{alg_get_degree}{GEN al} low-level version of \kbd{algdegree}.

\fun{GEN}{alg_get_aut}{GEN al} low-level version of \kbd{algaut}.

\fun{GEN}{alg_get_auts}{GEN al}, given a cyclic algebra $\var{al} =
(L/K,\sigma,b)$ of degree $n$, returns the vector of $\sigma^i$,
$1 \leq i < n$.

\fun{GEN}{alg_get_b}{GEN al} low-level version of \kbd{algb}.

\fun{GEN}{alg_get_basis}{GEN al} low-level version of \kbd{albasis}.

\fun{GEN}{alg_get_center}{GEN al} low-level version of \kbd{algcenter}.

\fun{GEN}{alg_get_char}{GEN al} low-level version of \kbd{algchar}.

\fun{GEN}{alg_get_hasse_f}{GEN al} low-level version of \kbd{alghassef}.

\fun{GEN}{alg_get_hasse_i}{GEN al} low-level version of \kbd{alghassei}.

\fun{GEN}{alg_get_invbasis}{GEN al} low-level version of \kbd{alginvbasis}.

\fun{GEN}{alg_get_multable}{GEN al} low-level version of \kbd{algmultable}.

\fun{GEN}{alg_get_relmultable}{GEN al} low-level version of
\kbd{algrelmultable}.

\fun{GEN}{alg_get_splittingfield}{GEN al}
low-level version of \kbd{algsplittingfield}.

\fun{GEN}{alg_get_abssplitting}{GEN al} returns the absolute \var{nf}
structure attached to the \var{rnf} returned by \kbd{algsplittingfield}.

\fun{GEN}{alg_get_splitpol}{GEN al}  returns the relative polynomial
defining the \var{rnf} returned by \kbd{algsplittingfield}.

\fun{GEN}{alg_get_splittingdata}{GEN al}
low-level version of \kbd{algsplittingdata}.

\fun{GEN}{alg_get_splittingbasis}{GEN al}
the matrix \var{Lbas} from \kbd{algsplittingdata}

\fun{GEN}{alg_get_splittingbasisinv}{GEN al}
the matrix \var{Lbasinv} from \kbd{algsplittingdata}.

\fun{GEN}{alg_get_tracebasis}{GEN al} returns the traces of the
basis elements; used by \kbd{algtrace}.

% TODO

\fun{GEN}{alg_change_overorder_shallow}{GEN al, GEN ord}

\fun{GEN}{alg_complete}{GEN rnf, GEN aut, GEN hi, GEN hf, int maxord}

\fun{GEN}{alg_ordermodp}{GEN al, GEN p}

\fun{GEN}{algbasischarpoly}{GEN al, GEN x, long v}

\fun{GEN}{algbasismul}{GEN al, GEN x, GEN y}

\fun{GEN}{algbasismultable}{GEN al, GEN x}

\fun{GEN}{algbasismultable_Flm}{GEN mt, GEN x, ulong m}

\fun{GEN}{algleftordermodp}{GEN al, GEN Ip, GEN p}

\fun{GEN}{bnfgwgeneric}{GEN bnf, GEN Lpr, GEN Ld, GEN pl, long var}

\fun{GEN}{bnrgwsearch}{GEN bnr, GEN Lpr, GEN Ld, GEN pl}

\fun{void}{checkhasse}{GEN nf, GEN hi, GEN hf, long n}

\fun{long}{cyclicrelfrob}{GEN rnf, GEN auts, GEN pr}

\fun{GEN}{hassecoprime}{GEN hi, GEN hf, long n}

\fun{GEN}{hassedown}{GEN nf, long n, GEN hi, GEN hf}

\fun{GEN}{hassewedderburn}{GEN hi, GEN hf, long n}

\fun{long}{localhasse}{GEN rnf, GEN cnd, GEN pl, GEN auts, GEN b, long k}

\fun{GEN}{nfgwkummer}{GEN nf, GEN Lpr, GEN Ld, GEN pl, long var}

\newpage
pari-doc 2.9.1-1 / usr / share / pari / doc / usersch6.tex
