Function: idealred
Section: number_fields
C-Name: idealred0
Prototype: GGDG
Help: idealred(nf,I,{v=0}): LLL reduction of the ideal I in the number
field nf along direction v, in HNF.
Doc: \idx{LLL} reduction of
the ideal $I$ in the number field $K$ attached to \var{nf}, along the
direction $v$. The $v$ parameter is best left omitted, but if it is present,
it must be an $\kbd{nf.r1} + \kbd{nf.r2}$-component vector of
\emph{non-negative} integers. (What counts is the relative magnitude of the
entries: if all entries are equal, the effect is the same as if the vector
had been omitted.)
This function finds an $a\in K^*$ such that $J = (a)I$ is
``small'' and integral (see the end for technical details).
The result is the Hermite normal form of
the ``reduced'' ideal $J$.
\bprog
? K = nfinit(y^2+1);
? P = idealprimedec(K,5)[1];
? idealred(K, P)
%3 =
[1 0]
[0 1]
@eprog\noindent More often than not, a \idx{principal ideal} yields the unit
ideal as above. This is a quick and dirty way to check if ideals are principal,
but it is not a necessary condition: a non-trivial result does not prove that
the ideal is non-principal. For guaranteed results, see \kbd{bnfisprincipal},
which requires the computation of a full \kbd{bnf} structure.
If the input is an extended ideal $[I,s]$, the output is $[J, sa]$; in
this way, one keeps track of the principal ideal part:
\bprog
? idealred(K, [P, 1])
%5 = [[1, 0; 0, 1], [2, -1]~]
@eprog\noindent
meaning that $P$ is generated by $[2, -1]~$. The number field element in the
extended part is an algebraic number in any form \emph{or} a factorization
matrix (in terms of number field elements, not ideals!). In the latter case,
elements stay in factored form, which is a convenient way to avoid
coefficient explosion; see also \tet{idealpow}.
\misctitle{Technical note} The routine computes an LLL-reduced
basis for the lattice $I^{-1}$ equipped with the quadratic
form
$$|| 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. The element
$a$ is simply the first vector in the LLL basis. The only reason you may want
to try to change some directions and set some $v_i\neq 0$ is to randomize
the elements found for a fixed ideal, which is heuristically useful in index
calculus algorithms like \tet{bnfinit} and \tet{bnfisprincipal}.
\misctitle{Even more technical note} In fact, the above is a white lie.
We do not use $||\cdot||_v$ exactly but a rescaled rounded variant which
gets us faster and simpler LLLs. There's no harm since we are not using any
theoretical property of $a$ after all, except that it belongs to $I^{-1}$
and that $a I$ is ``expected to be small''.