\section{Defining the number field}
\label{sec:polredabs}
Every number field has the form $K={\mathbb Q}(\alpha)$ where $\alpha$ is an
algebraic integer.  The minimal polynomial of~$\alpha$ is an
irreducible monic polynomial in~${\mathbb Z}[X]$, called the \emph{defining
  polynomial} of~$K$.  While every field has infinitely many such
defining polynomials, for our purposes, we need to make a choice once
and for all of one defining polynomial for each field, since the way
in which we order field elements and ideals will depend on this
choice.

The \emph{reduced defining polynomial} of the number field~$K$ is
defined to be the unique monic integral polynomial determined by the
following process. Recall that the $T_2$-norm of a polynomial is the
sum of the squares of the modulus of the roots, and for a
polynomial~$P = x^n + a_1x + \dots + a_n$, let~$S(P) =
(|a_1|,a_1,\dots,|a_n|,a_n)$; there are only finitely many monic integral
polynomials of a given degree and bounded~$T_2$ norm.
\begin{enumerate}
  \item Let~$L_0$ be the finite list of monic integral defining polynomials
    of~$K$ which are minimal with respect to the~$T_2$ norm.
  \item Let~$L_1$ be the sublist of~$L_0$ of polynomials whose
    discriminant has minimal absolute value.
  \item Order the polynomials in~$L_1$ by lexicographic order of the
    vectors~$S(P)$.

    Then the reduced defining polynomial of~$K$ is the smallest
    polynomial in~$L_1$ with respect to this order.
\end{enumerate}

\begin{comment}
\begin{enumerate}
  \item Let~$L_0$ be the list of characteristic polynomials in ${\mathbb Z}[x]$
    of integral primitive elements of~$K$, minimal with respect to
    the~$T_2$ norm (the sum of the squares of the modulus of the
    roots).
  \item Let~$L_1$ be the sublist of~$L_0$ of polynomials whose discriminant has
    minimal absolute value.
  \item Let~$L_2$ be the sublist of~$L_1$ defined as follows. In each
    pair~$\{P(x), (-1)^{\deg P}P(-x)\}$ of monic polynomials, choose the unique
    polynomial~$Q$ such that when written~$Q(x) = Q_1(x^2)+xQ_2(x^2)$, at most
    one of~$Q_1,Q_2$ has positive leading coefficient.
  \item Order the integers by absolute value first, breaking ties by
    putting~$-|x|$ before~$|x|$. Order the polynomials in~$L_2$ by the
    lexicographic order of the coefficient vectors (from the leading coefficient
    to the constant coefficient) where integers are ordered as above. Then the
    {\tt polredabs} polynomial of~$K$ is the smallest polynomial in~$L_2$ for
    that order.
\end{enumerate}
\end{comment}

Note that in the second step, we restrict to the list~$L_0$ of
polynomials defined in the first step; hence the defining polynomial
for the field with smallest discriminant may not belong to the list.

The third step distinguishes, for example, between $x^2-x+1$ and
$x^2+x+1$ as defining polynomials for ${\mathbb Q}(\sqrt{-3})$, choosing the
first, and hence the generator $(1+\sqrt{-3})/2$ (a 6th root of unity)
rather than $(-1+\sqrt{-3})/2$ (a 3rd root of unity).

This definition is due to Karim Belabas, and is implemented in the
{\tt Pari}\ function {\tt polredabs()}, which is guaranteed to always
return the same polynomial, given any defining polynomial for a number
field: see \cite{polredabs}.  Note that computing this polynomial can
be very time-consuming when the degree or discriminant of the field is
large: in particular it requires computation of the ring of integers
of~$K$, and hence the factorization of the discriminant of an initial
(monic integral irreducible) defining polynomial for~$K$; in addition the number
of potential defining polynomials to consider could be exponential in the
degree.

We do not assume that ${\mathbb Z}[\alpha]$ is the full ring of integers
${\mathcal O}_K$.  Indeed, for most number fields $K$ this condition is
not satisfied by any choice of $\alpha$ (in general the ring ${\mathcal O}_K$
will not be monogenic over ${\mathbb Z}$).

We emphasise that both the defining polynomial $g(X)$ and the
generator $\alpha$ of~$K$ are fixed from now on.  In other words we
are fixing the structure of $K={\mathbb Q}[X]/(g(X))$ not just as a field, but
as a ${\mathbb Q}[X]$-algebra, where the structure map ${\mathbb Q}[X]\to K$ has kernel
$(g(X))$ and $\alpha$ is the image of $X$ in $K$.  In what follows,
the order we define on field elements and ideals depends on the choice
of defining polynomial, so is canonical when the reduced defining
polynomial is used.


\section{Sorting prime ideals}\label{sec:primes}
Fix a number field $K={\mathbb Q}(\alpha)={\mathbb Q}[X]/(g(X))$ with defining
polynomial $g\in{\mathbb Z}[X]$ and generator $\alpha$ as above, and let
${\mathcal O}_K$ denote its ring of integers.  We do not assume that $K/{\mathbb Q}$ is
Galois or that ${\mathcal O}_K={\mathbb Z}[\alpha]$.  By a \emph{prime} of $K$ (or of
${\mathcal O}_K$) we mean a nonzero prime ideal in the ring ${\mathcal O}_K$; for primes
of ${\mathbb Q}$ we may also use $p$ to denote the prime ideal $(p)$.

We wish to define a total order on the set of prime ideals~${\mathfrak p}$
of ${\mathcal O}_K$.  Let $(p)={\mathfrak p}\cap {\mathbb Z}$ be the prime of ${\mathbb Z}$ lying below ${\mathfrak p}$,
let $e=e({\mathfrak p}/p)$ be the ramification index (the multiplicity of ${\mathfrak p}$ in the prime factorization of $(p)$ in the Dedekind domain ${\mathcal O}_K$), and let $f=f({\mathfrak p}/p)$ the residue field degree $[{\mathcal O}_K/{\mathfrak p}:{\mathbb F}_p]$.
The (absolute) norm of ${\mathfrak p}$ is then $N({\mathfrak p})=p^f$.


We order the primes ${\mathfrak p}$ first by norm and then by the ramification
index.  It remains only to order the primes~${\mathfrak p}$ of $K$ that lie above
the same rational prime $p$ and have the same norm (hence the same
residue degree) and ramification index.  Such primes will necessarily
have the same value of $p^{ef}$; the converse need not hold (primes
with the same value of $p^{ef}$ need not have the same norm $p^{f}$),
but this will not concern us since we order by norm first.

\subsection{The case of unramified primes}

Our general method is simplest when $p$ is unramified, not just in $K$
but in the order ${\mathbb Z}[\alpha]$; this holds precisely when $p\nmid
[{\mathcal O}_K:{\mathbb Z}[\alpha]]\disc(K)$, or equivalently, $p\nmid\disc(g)$, which
applies to all but finitely many $p$.  In this case $g(X)$ factors
modulo~$p$ into distinct irreducible elements of ${\mathbb F}_p[X]$, and we may
write
\[
    g(X) \equiv \prod_i h_i(X) \pmod{p},
\]
with the factors $h_i(X)\in{\mathbb Z}[X]$ monic and such that their reductions
modulo~$p$ are distinct and irreducible.  We may assume that the
coefficients of each $h_i(X)$ are reduced modulo~$p$ to integers in the interval $[0,p-1]$, and we order these factors first by degree and then lexicographically by their coefficient vectors in $[0,p-1]^{f+1}$.

The Dedekind-Kummer theorem allows us to associate to each factor
$h_i(X)$ the prime ideal ${\mathfrak p}_i=(p,h_i(\alpha))$ above $p$, with
residue degree $f({\mathfrak p}_i/p)=\deg h_i$ and norm $N({\mathfrak p}_i)=p^{\deg h_i}$.
We then have $p{\mathcal O}_K=\prod_i {\mathfrak p}_i$ and our ordering of the $h_i$
induces an ordering of the primes~${\mathfrak p}_i$ above $p$.  If we have any
representation of ${\mathfrak p}_i$ in the form ${\mathfrak p}_i=(p,\beta)$ where
$\beta=b(\alpha)$ for some $b(X)\in{\mathbb Z}[X]$, then we can recover
$h_i(X)$ since $h_i(X)=\gcd(g(X),b(X))$ (with the $\gcd$ computed in
${\mathbb F}_p[X]$).  This follows from the observation that
$\ord_{{\mathfrak p}_i}(\beta)>0$ while $\ord_{{\mathfrak p}_j}(\beta)=0$ for all primes
${\mathfrak p}_j$ above~$p$ other than~${\mathfrak p}_i$.  This makes implementation of the
sorting function on the primes above~$p$ very simple in this case.

\subsection{The general case, including ramified primes}

There is a bijection between the distinct primes ${\mathfrak p}$ above $p$ and
the irreducible factors $h(X)$ of $g(X)$ in ${\mathbb Q}_p[X]$ in which $\deg h
= e({\mathfrak p}/p)f({\mathfrak p}/p)$ (see \cite[Theorem 3.8 (d)]{Janusz}).  Write
\[
  g(X) = h_1(X)h_2(X)\dots h_r(X)
\]
with the $h_i(X)$ monic and irreducible in ${\mathbb Z}_p[X]$. Since we sort
prime ideals by norm and ramification index, it is enough to describe
an order on polynomials of the same degree; in fact, we only need to
order the set of polynomials $h_i(X)$ that have the same degree~$ef$,
and also correspond to primes ${\mathfrak p}_i$ with both the same ramification
index~$e$ and the same residue degree~$f$, which may be a smaller set.

We sort polynomials in~${\mathbb Z}_p[X]$ of degree~$d$ as follows. Such a polynomial~$P$
can be written uniquely in the form
\[
  (a_{0,0}+a_{0,1}p+a_{0,2}p^2+\dots) + (a_{1,0}+a_{1,1}p+\dots)X
  + \dots + (a_{d,0}+a_{d,1}p+\dots)X^d,
\]
with all~$a_{i,j}\in{\mathbb Z}\cap[0,p-1]$. We can then attach to~$P$ the infinite
vector
\[
(a_{0,0},a_{1,0},\dots,a_{d,0},a_{0,1},a_{1,1},\dots,a_{d,1},a_{0,2},\dots)\in [0,p-1]^\infty,
\]
and we sort polynomials according to the lexicographic ordering of such vectors.
Comparisons can be made using finite precision, provided that the polynomials are known to be
distinct, which is the case for the~$h_i$.


We now explain how to compute the bijection between the~$h_i$ and the primes
above~$p$. Let~$h\in{\mathbb Z}_p[X]$ be one of the~$h_i$, and let~${\mathfrak p}$ be a prime
above~$p$. The valuation~$v_{{\mathfrak p}}$ on the number field~$K$ (a finite \'etale ${\mathbb Q}$-algebra) extends to the \'etale ${\mathbb Q}_p$-algebra ~$K\otimes_{{\mathbb Q}}{\mathbb Q}_p = \prod_i
{\mathbb Q}_p[X]/(h_i(X))$ obtained via base-change in the following way.
Let~$j$ be such that~$h_{j}$ corresponds
to~${\mathfrak p}$, and let~$v_j$ be the valuation of the $p$-adic field~${\mathbb Q}_p[X]/(h_j(X))$.
Define the extension of~$v_{\mathfrak p}$ to $K\otimes_{\mathbb Q}\Q_p$ to be the composition of the maps
\[
  K\otimes_{{\mathbb Q}}{\mathbb Q}_p \longrightarrow {\mathbb Q}_p[X]/(h_j(X)) \stackrel{v_j}{\longrightarrow} {\mathbb Z}\cup\{\infty\}.
\]
We then have~$v_{{\mathfrak p}}(h(\alpha)) = \infty$ if and only
if~${\mathfrak p}$ corresponds to~$h$.
While this valuation cannot be computed using finite
approximations to~$h$, for all integers~$k\ge 1$ we have~$v_{\mathfrak p}((p^k,h(\alpha)))
= \min(e({\mathfrak p}/p)k, v_{\mathfrak p}(h(\alpha)))$, and this value equals~$e({\mathfrak p}/p)k$
if~$h$ corresponds to~${\mathfrak p}$ and is bounded above otherwise (independently of~$k$). The
valuation~$v_{\mathfrak p}((p^k,h(\alpha)))$ can be computed using finite approximations
to~$h$, and if $k$ is such that the set $\{v_{\mathfrak p}((p^k,h_i(\alpha)))\}$ has a unique maximum, this maximum occurs for the polynomial $h_i(X)$ corresponding to ${\mathfrak p}$.
Thus we can compute the bijection by making $k$ sufficiently large (and any $k$ that yields a unique maximum works).

We remark that ``Round 4" of the $p$-adic polynomial factorization
algorithm implemented in {\tt Pari}\ \cite{Roblot} computes the prime
ideals corresponding to the various $p$-adic factors, but this part of
the output is not available via the standard interface.  The same is
true in {\tt Sage}, which uses the {\tt Pari}\ library for $p$-adic
factorization.  Nevertheless, the discussion above allows us to
recover the bijection without requiring direct access to this
implementation, which may not be the same in other computer algebra
systems in any case.


\subsection{Examples}
We use number fields in the LMFDB database (see~\cite{lmfdb}) to
illustrate the sorting of prime ideals.

Let $K={\mathbb Q}(\alpha)$ be the non-Galois cubic field with LMFDB
label~\href{www.lmfdb.org/NumberField/3.1.503.1}{\texttt{3.1.503.1}}
of discriminant $-503$ with reduced defining polynomial
$g(x)=X^3-X^2+2X+8$.  The prime $2$ is unramified, but it divides
$\disc(g(X))=-2^2\cdot 503$ and is an essential divisor of
$[{\mathcal O}_K:{\mathbb Z}[\alpha]]$ in the sense that $2\mid[{\mathcal O}_K:{\mathbb Z}[\alpha']]$ for
every algebraic integer $\alpha'$ in $K$ (this example, due to
Dedekind, is the standard example of a non-monogenic field).

Let $p=2$ and $k=2$; the $2$-adic factors of $g(X)$ are: $h_1=X+O(2^2)$,
$h_2=X+2+O(2^2)$, $h_3=X+1+O(2^2)$.  So there are $3$
primes above $2$, each with residue degree $1$.
Calling these ${\mathfrak p}_a = (2,\frac 12\alpha^2+\frac 12\alpha+3)$, ${\mathfrak p}_b =
(2,\alpha+3)$, ${\mathfrak p}_c = (2,\frac 12\alpha^2-\frac 12\alpha)$ in random order we find that
\begin{itemize}
  \item the ${\mathfrak p}_a$-valuations of the $(2^2,h_i(\alpha))$ are $(1,2,0)$,
  \item the ${\mathfrak p}_b$-valuations of the $(2^2,h_i(\alpha))$ are $(0,0,2)$,
  \item the ${\mathfrak p}_c$-valuations of the $(2^2,h_i(\alpha))$ are $(2,1,0)$,
\end{itemize}
thus ${\mathfrak p}_1={\mathfrak p}_c$, ${\mathfrak p}_2={\mathfrak p}_a$ and ${\mathfrak p}_3={\mathfrak p}_b$.

Let $p=503$.  There are two primes above~$p$, both of norm~$p$, only
one of which is ramified (with $e=2$). Our ordering puts the
unramified prime first and the ramified prime second, so we do not even need to
look at the $p$-adic factorization of $g(X)$ in this case.  In fact,
with $k=2$ we find factors $X+191929+O(503^2)$ and $X^2+61079X+87617+O(503^2)$.

For a larger example, let $K={\mathbb Q}(\alpha)={\mathbb Q}[X]/(g(X))$, where
\[
g(X)= X^{10} - 3X^9 - 35X^8 + 120X^7 + 242X^6 - 1080X^5 + 44X^4 + 2343X^3 -
1631X^2 + 111X + 79.
\]
This field has LMFDB
label~\href{http://beta.lmfdb.org/NumberField/10.10.24952891341003125.1}{\texttt{10.10.24952891341003125.1}} and discriminant~$5^5 41^8$, but we have
\[
\disc(g)=3^{12}\cdot 5^5\cdot 41^8\cdot 2141^2\cdot 26641^2.
\]
Let us consider the primes above $3$.
Over~${\mathbb Q}_3$, the polynomial $g(X)$ splits as
a product of~$5$ polynomials of degree~$2$, that is, $g = h_1h_2h_3h_4h_5$ with
$h_i\in{\mathbb Z}_3[x]$. Modulo~$3$, we have
\begin{itemize}
  \item $h_1 = X^2 + 1 +O(3)$,
  \item $h_2 = X^2 + 2X + 2 + O(3)$,
  \item $h_3 = X^2 + X + 2 + O(3)$,
  \item $h_4 = X^2 + 2X + 2 + O(3)$,
  \item $h_5 = X^2 + X + 2 + O(3)$.
\end{itemize}
The prime $3$ is unramified, so we can already see that it splits into 5 primes of norm $9$.  These approximations are not sufficient to distinguish all the $h_i$,
but we get the following initial segments of the associated vectors (omitting
the maximal degree term since they are all monic):
\begin{itemize}
  \item $(1,0,\dots)$,
  \item $(2,2,\dots)$,
  \item $(2,1,\dots)$,
  \item $(2,2,\dots)$,
  \item $(2,1,\dots)$,
\end{itemize}
so we have~$h_1 < \{h_3,h_5\} < \{h_2,h_4\}$. Modulo~$9$, we get
\begin{itemize}
  \item $h_1 = X^2 + 3X + 1 + O(3^2)$,
  \item $h_2 = X^2 + 5X + 5 + O(3^2)$,
  \item $h_3 = X^2 + 7X + 2 + O(3^2)$,
  \item $h_4 = X^2 + 5X + 5 + O(3^2)$,
  \item $h_5 = X^2 + 4X + 5 + O(3^2)$.
\end{itemize}
This is still not enough to distinguish them, but
we get the refined initial segments
\begin{itemize}
  \item $(1,0,0,1,\dots)$,
  \item $(2,2,1,1,\dots)$,
  \item $(2,1,0,2,\dots)$,
  \item $(2,2,1,1,\dots)$,
  \item $(2,1,1,1,\dots)$,
\end{itemize}
so we have~$h_1<h_3<h_5<\{h_2,h_4\}$. Finally, modulo~$27$ we have
\begin{itemize}
  \item $h_1 = X^2 + 3X + 1 + O(3^3)$,
  \item $h_2 = X^2 + 5X + 5 + O(3^3)$,
  \item $h_3 = X^2 + 7X + 11 + O(3^3)$,
  \item $h_4 = X^2 + 23X + 23 + O(3^3)$,
  \item $h_5 = X^2 + 13X + 14 + O(3^3)$.
\end{itemize}
This is now enough to distinguish all the~$h_i$, and we obtain the initial segments
\begin{itemize}
  \item $(1,0,0,1,0,0\dots)$,
  \item $(2,2,1,1,0,0,\dots)$,
  \item $(2,1,0,2,1,0,\dots)$,
  \item $(2,2,1,1,2,2,\dots)$,
  \item $(2,1,1,1,1,1,\dots)$,
\end{itemize}
yielding the order~$h_1 < h_3 < h_5 < h_2 < h_4$.
As noted above, the prime~$3$ decomposes as a product of~$5$ prime ideals of norm~$9$,
which we denote~${\mathfrak p}_a, \dots, {\mathfrak p}_e$ in arbitrary order. We know that we need
precision at least~$O(3^3)$ to distinguish the polynomials~$h_i$, so we compute
the valuations~$v_{\mathfrak p}((3^3,h_i(\alpha)))$. We obtain:
\begin{itemize}
  \item The~${\mathfrak p}_a$-valuations of~$(3^3,h_i(\alpha))$ are~$(0,0,0,0,3)$,
  \item The~${\mathfrak p}_b$-valuations of~$(3^3,h_i(\alpha))$ are~$(0,3,0,2,0)$,
  \item The~${\mathfrak p}_c$-valuations of~$(3^3,h_i(\alpha))$ are~$(3,0,1,0,0)$,
  \item The~${\mathfrak p}_d$-valuations of~$(3^3,h_i(\alpha))$ are~$(0,2,0,3,0)$,
  \item The~${\mathfrak p}_e$-valuations of~$(3^3,h_i(\alpha))$ are~$(1,0,3,0,0)$,
\end{itemize}
thus we have the bijection~${\mathfrak p}_a\leftrightarrow h_5$, ${\mathfrak p}_b\leftrightarrow h_2$,
${\mathfrak p}_c\leftrightarrow h_1$, ${\mathfrak p}_d\leftrightarrow h_4$, ${\mathfrak p}_e\leftrightarrow h_3$.
Since these ideals all have norm~$9$ and ramification index~$1$, our ordering of
the primes above~$3$ is~${\mathfrak p}_c < {\mathfrak p}_e < {\mathfrak p}_a < {\mathfrak p}_b < {\mathfrak p}_d$.

\section{Sorting all nonzero integral ideals}
\label{sec:ideals}
Fix a number field $K={\mathbb Q}(\alpha)$ with defining polynomial
$g(X)\in{\mathbb Z}[X]$ and generator $\alpha$ as above.  We now define a total
order on the set of all nonzero integral ideals of~$K$.  We first
order ideals by norm, and then sort ideals of the same norm according
to the criterion which we specify in this section. This defines for
each ideal~${\mathfrak a}$ a unique label~$N.i$, where~$N$ is the norm of~${\mathfrak a}$
and~$i\ge 1$ is the index of~${\mathfrak a}$ in the ordered list of ideals of
norm~$N$.  This order has the following properties:
\begin{itemize}
  \item prime ideals are smaller than every non-prime ideal of the same norm,
    and are ordered in the same way as before;
  \item if~${\mathfrak a},{\mathfrak b},{\mathfrak c}$ are integral ideals such that~${\mathfrak a}<{\mathfrak b}$,
    then~${\mathfrak a}{\mathfrak c}<{\mathfrak b}{\mathfrak c}$; so our ordering makes the set of nonzero
    integral ideals into a totally ordered monoid;
  \item if the factorisation of a positive integer~$N$ is known, then the
    bijection between ideals of norm~$N$ and their labels is computable in
    polynomial time (even though the number of such ideals might not be
    polynomial in~$\log N$).
\end{itemize}

\subsection{Ideals of prime power norm}\label{sec:primepowernorm}

We first define an order on the set of ideals of prime power
norm. Let~${\mathfrak a}$ be an ideal of norm~$p^n$, and let~${\mathfrak p}_1,\dots,{\mathfrak p}_r$ be
the prime ideals of~$K$ above~$p$, ordered as in
Section~\ref{sec:primes}. We have~${\mathfrak a} = {\mathfrak p}_1^{v_1}\dots {\mathfrak p}_r^{v_r}$
for some integers~$v_i\ge 0$. We define the weight of this
factorization to be~$v_1+\dots+v_r$. We order ideals of norm a power
of $p$ by increasing norm first, then increasing weight, and finally
by reverse lexicographic order of the vector of
exponents~$(v_1,\dots,v_r)$. For this order, the prime ideals come
first (having weight~$1$), and are ordered in the same way as
previously.

Example: let~$K$ be a number field and~$p$ a prime number that
decomposes in~$K$ as the product~${\mathfrak p}_1{\mathfrak p}_2{\mathfrak p}_3{\mathfrak p}_4$ where~${\mathfrak p}_1$,
${\mathfrak p}_2$ and~${\mathfrak p}_3$ have residue degree~$1$ and~${\mathfrak p}_4$ has residue
degree~$2$. We assume that the order defined in
Section~\ref{sec:primes} gives~${\mathfrak p}_1 < {\mathfrak p}_2 < {\mathfrak p}_3$. We first consider
ideals of norm~$p$. The only such ideals are~${\mathfrak p}_1$, ${\mathfrak p}_2$
and~${\mathfrak p}_3$, and they have weight~$1$ and exponent vectors~$(1,0,0,0)$,
$(0,1,0,0)$ and~$(0,0,1,0)$. Since lexicographically we
have~$(0,0,1,0)<(0,1,0,0)<(1,0,0,0)$, the reverse lexicographic order
gives~${\mathfrak p}_1<{\mathfrak p}_2<{\mathfrak p}_3$. Now consider the ideals of norm~$p^2$, which
are ${\mathfrak p}_4$, ${\mathfrak p}_1^2$, ${\mathfrak p}_2^2$, ${\mathfrak p}_3^2$, ${\mathfrak p}_1{\mathfrak p}_2$, ${\mathfrak p}_1{\mathfrak p}_3$
and~${\mathfrak p}_2{\mathfrak p}_3$. The corresponding exponent vectors are~$(0,0,0,1)$,
$(2,0,0,0)$, $(0,2,0,0)$, $(0,0,2,0)$, $(1,1,0,0)$, $(1,0,1,0)$
and~$(0,1,1,0)$, with weights~$1,2,2,2,2,2,2$. The order we defined is
therefore~${\mathfrak p}_4 < {\mathfrak p}_1^2 < {\mathfrak p}_1{\mathfrak p}_2 < {\mathfrak p}_1{\mathfrak p}_3 < {\mathfrak p}_2^2 < {\mathfrak p}_2{\mathfrak p}_3 <
{\mathfrak p}_3^2$. The reader can check that the ideals of norm~$p^3$
are~${\mathfrak p}_4{\mathfrak p}_1 < {\mathfrak p}_4{\mathfrak p}_2 < {\mathfrak p}_4{\mathfrak p}_3 < {\mathfrak p}_1^3 < {\mathfrak p}_1^2{\mathfrak p}_2 < {\mathfrak p}_1^2{\mathfrak p}_3
< {\mathfrak p}_1{\mathfrak p}_2^2 < {\mathfrak p}_1{\mathfrak p}_2{\mathfrak p}_3 < {\mathfrak p}_1{\mathfrak p}_3^2 < {\mathfrak p}_2^3 < {\mathfrak p}_2^2{\mathfrak p}_3 <
{\mathfrak p}_2{\mathfrak p}_3^2 < {\mathfrak p}_3^3$.

\subsection{Arbitrary integral ideals}

We finally define an order on the set of all nonzero integral
ideals. Again, we first order them by norm, so we only have to define
an order on nonzero ideals of the same norm. Let~${\mathfrak a}$ be an ideal of
norm~$N = p_1^{a_1}\dots p_k^{a_k}$ with~$p_1 < \dots <
p_k$. Then~${\mathfrak a}$ has a unique factorization as~${\mathfrak a} = {\mathfrak a}_1\dots{\mathfrak a}_k$
where~${\mathfrak a}_i$ has norm~$p_i^{a_i}$. We order ideals of norm~$N$
according to the lexicographic order of the
$k$-uple~$({\mathfrak a}_1,\dots,{\mathfrak a}_k)$.

Example: let~$K$ be a number field, and assume that~$2$ decomposes
as~${\mathfrak p}_1{\mathfrak p}_2{\mathfrak p}_3$ where~${\mathfrak p}_1<{\mathfrak p}_2$ have residue degree~$1$ and~${\mathfrak p}_3$ has
residue degree~$2$, and that~$3$ decomposes as~${\mathfrak q}_1{\mathfrak q}_2$ where~${\mathfrak q}_1$ has
degree~$1$ and~${\mathfrak q}_2$ has degree~$3$. Let us order ideals of norm~$18$. Such an
ideal is uniquely a product of an ideal of norm~$2$ and an ideal of norm~$9$. The ideals
of norm~$2$ are~${\mathfrak p}_1 < {\mathfrak p}_2$, and the only ideal of norm~$9$ is~${\mathfrak q}_1^2$. The
ideals of norm~$18$ are therefore~${\mathfrak p}_1{\mathfrak q}_1^2 < {\mathfrak p}_2{\mathfrak q}_1^2$. Let us now order ideals
of norm~$108 = 2^2\cdot 3^3$. The ideals of norm~$4$ are~${\mathfrak p}_3 < {\mathfrak p}_1^2 < {\mathfrak p}_1{\mathfrak p}_2 <
{\mathfrak p}_2^2$, and the ideals of norm~$27$ are~${\mathfrak q}_2 < {\mathfrak q}_1^3$. The ideals of
norm~$108$ are therefore~${\mathfrak p}_3{\mathfrak q}_2 < {\mathfrak p}_3{\mathfrak q}_1^3 < {\mathfrak p}_1^2{\mathfrak q}_2 < {\mathfrak p}_1^2{\mathfrak q}_1^3 <
{\mathfrak p}_1{\mathfrak p}_2{\mathfrak q}_2 < {\mathfrak p}_1{\mathfrak p}_2{\mathfrak q}_1^3 < {\mathfrak p}_2^2{\mathfrak q}_2 < {\mathfrak p}_2^2{\mathfrak q}_1^3$.

\begin{comment}
\section{Standard generators for nonzero integral ideals}

The goal of this section is to define, for every nonzero integral ideal~${\mathfrak a}$ of
a number field~$K$ with fixed primitive element~$\alpha$ as above, a pair of
standard generators~${\mathfrak a} = (N,g)$ with~$N\in{\mathbb Z}$ and~$g\in{\mathcal O}_K$.


\subsection{Standard basis of a lattice in~$K$}
Let~$L\subset K$ be a finitely generated subgroup. Let~$f$ be the minimal
positive integer such that~$f L \subset {\mathbb Z}[\alpha]$. This can be computed as
follows: let~$a_1,\dots,a_k$ be an arbitrary~${\mathbb Z}$-basis of~$L$; then~$f$ is the
LCM of the denominators of the coefficients of the~$a_i$ when written
as~${\mathbb Q}$-linear combinations of the power basis~$1,\alpha,\dots,\alpha^{d-1}$.

We define the \emph{standard basis} of~$L$ to be the
basis~$b_1=\frac{1}{f}c_1,\dots,b_k=\frac{1}{f}c_k$, where~$c_1,\dots,c_k$ is
the~${\mathbb Z}$-basis of~$fL$ whose column-vector matrix with respect to the power
basis~$1,\alpha,\dots,\alpha^{d-1}$ of~${\mathbb Z}[\alpha]$ is in upper triangular,
right multiplication Hermite Normal Form.

\textbf{Note for us:} it would be nice if we could do without this notion of standard
basis. It is mostly used in the notion of standard lift below. It is also used in the
definition of standard uniformisers of ramified primes (but this second use
could be replaced by another definition).

\subsection{Standard lifts modulo integers}
Let~$b_1,\dots,b_n$ be the standard basis of~${\mathcal O}_K$.
Let~$N>0$ be an integer and let~$\bar{g}\in{\mathcal O}_K/N{\mathcal O}_K$. We define the \emph{standard
lift} of~$\bar{g}$ to be the element~$g = \sum_{i=1}^d \lambda_i b_i$ that is
congruent to~$\bar{g}$ modulo~$N$, where~$\lambda_i\in {\mathbb Z}\cap [0,N-1]$.

\subsection{Standard uniformisers}
Let~${\mathfrak p}$ be a prime of~$K$. We define the \emph{standard uniformiser} of~${\mathfrak p}$,
i.e. a standard element~$\pi$ of~${\mathcal O}_K$ such that~$v_{\mathfrak p}(\pi)=1$, as follows:
\begin{itemize}
  \item if~${\mathfrak p}$ is unramified, $\pi=p$;
  \item if~${\mathfrak p}$ is ramified, then~$\pi$ is, among the vectors~$b_1,\dots,b_d$ of
    the standard basis of~${\mathfrak p}$, the first one such that~$b_i\notin{\mathfrak p}^2$.
\end{itemize}
In the unramified case, it is clear that~$v_{\mathfrak p}(\pi)=1$. In the ramified case, we
know that not all~$b_i$ are contained in~${\mathfrak p}^2$ since~${\mathfrak p}\neq{\mathfrak p}^2$, so the
definition makes sense; moreover~$\pi \in{\mathfrak p}\setminus{\mathfrak p}^2$ and
therefore~$v_{\mathfrak p}(\pi)=1$.

\subsection{Standard generators}
Let~${\mathfrak a}\subset{\mathcal O}_K$ be a nonzero integral ideal. Let~$N$ be the positive
integer such that~${\mathfrak a}\cap{\mathbb Z} = N{\mathbb Z}$. Let~${\mathfrak p}_1,\dots,{\mathfrak p}_k$ be the primes
dividing~$N{\mathcal O}_K$ (note that these may be more than the primes dividing~${\mathfrak a}$),
and let~$\pi_1,\dots,\pi_k$ be the corresponding standard uniformisers.
Write~$N{\mathcal O}_K = \prod_{i=1}^k{\mathfrak p}_i^{n_i}$ and~${\mathfrak a} = \prod_{i=1}^k{\mathfrak p}_i^{a_i}$
with~$n_i,a_i\in{\mathbb Z}_{\ge 0}$ (some~$a_i$ can be~$0$). Let~$\bar{g}$ be the unique
element of~${\mathcal O}_K/N{\mathcal O}_K$ that is congruent to~$\pi_i^{a_i} \bmod{{\mathfrak p}_i^{n_i}}$,
and let~$g\in{\mathcal O}_K$ be the standard lift of~$\bar{g}$.

We claim that~${\mathfrak a} = (N,g)$. Indeed, the only primes that divide either~${\mathfrak a}$
or~$(N,g)$ are the~${\mathfrak p}_i$; moreover for every~${\mathfrak p}_i$ by construction we have~$v_{{\mathfrak p}_i}(g)=
a_i$ if~$a_i<n_i$ and~$v_{{\mathfrak p}_i}(g)\ge n_i$ if~$a_i=n_i$, and
therefore~$v_{{\mathfrak p}_i}((N,g)) = \min(n_i,v_{{\mathfrak p}_i}(g)) = a_i = v_{{\mathfrak p}_i}({\mathfrak a})$. This proves the
claim.

We define the \emph{standard generators} of~${\mathfrak a}$ to be~$(N,g)$.

\end{comment}

\bibliographystyle{abbrv}
