# On the calculation of roots of unity in a number field

Pascal Molin

► To cite this version:

Pascal Molin. On the calculation of roots of unity in a number field. IMJ-PRG. 2010. hal-05025975

HAL Id: hal-05025975

https://hal.science/hal-05025975v1

Submitted on 8 Apr 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# On the calculation of roots of unity in a number field

Pascal Molin

IMJ

Université Paris 7

75013 Paris

## Abstract

We review some algorithms for the calculation of roots of unity in a number field, and provide evidence that hard cases exist for each of them. We suggest a hybrid approach with guaranteed polynomial complexity which proves to be efficient in practice.

*Key words:* roots of unity, Kannan's algorithm, LLL algorithm, polynomial factorization, linear programming, effective Čebotarev's theorem.

## 1. Introduction

Let $K$ be a number field. The computation of its torsion units $\mu(K)$ is a basic task in algorithmic number theory, necessary in particular for the computation of the class group. The problem is not considered to be hard, and Cohen (1993) recommends to use a lattice enumeration technique due to Kannan. This has become a standard for computer algebra systems.

This enumeration algorithm is efficient for most cases, however its estimated complexity is exponential. In the context of extensive computations linked to class group heuristics, many examples of moderate size have been found recently for which the automatic computation of torsion units bottlenecked the whole process, if not definitely stopping it.

In addition, the computational context has evolved during the last 20 years, and great improvements have been made in the directions of short vectors enumeration (Hanrot and Stehlé, 2007), as well as polynomial factorization over number fields (Belabas, 2004).

<footnote>* This research was carried out during my Ph.D. thesis at university Bordeaux 1.
Email address: pascal.molin@math.univ-paris-diderot.fr (Pascal Molin).
URL: http://www.math.jussieu.fr/~molinp (Pascal Molin).</footnote>
This paper reconsiders several strategies for the computation of roots of unity: we first recall Kannan's small vectors point of vue; then we separate the two problems of computing the order $m = \#\mu(\mathbb{K})$, for which we propose heuristics, and the actual algebraic computation of a primitive unit $\zeta_m \in \mathcal{O}_{\mathbb{K}}$, for which we give two algorithms: an optimization of Belabas's polynomial factorization algorithm to the cyclotomic setting, and a LLL approach obtained via the complex embeddings.

We exhibit or construct critical examples for each technique. Along the way we present a linear programming approach to build number fields with prescribed ramification.

A hybrid approach having polynomial complexity is proposed. It has been successfully implemented as default algorithm in the PARI/gp software (function nfrootsof1).

## Notations

For the following:

* $\mathbb{K}$ is a number field of degree $n$, $\mathcal{O}_{\mathbb{K}}$ its ring of integers and disc($\mathbb{K}$) its discriminant. The algebraic norm of an element $x \in \mathbb{K}$ is denoted $\text{Norm}(x)$.

* For $m \ge 2$, $\mu_m$ is the set of $m$-th roots of unity. A $m$-th primitive root is denoted $\zeta_m$. We write $\mu(\mathbb{K})$ for the roots of unity present in $\mathbb{K}$.

* $p$ is a prime number, $\mathfrak{p}$ a prime integral ideal dividing it in $\mathcal{O}_{\mathbb{K}}$. Let $\mathfrak{k}(\mathfrak{p})$ be its residual field and $\text{Frob}_{\mathfrak{p}}$ the Frobenius automorphism induced in $\mathbb{K}$, if the extension is Galois.

* for $\sigma$ an embedding $\mathbb{K} \hookrightarrow \mathbb{C}$, we denote by $x^{\sigma}$ its action on $x$.

## 2. Torsion units as short vectors: Kannan's algorithm

$\mathbb{K}$ being a separable extension, it has $n = [\mathbb{K} : \mathbb{Q}]$ complex embeddings

$$ \sigma : \mathbb{K} \hookrightarrow \mathbb{C}. $$

This makes it possible to define a product

$$ \langle x, y \rangle = \sum_{\sigma} \overline{x^{\sigma} y^{\sigma}}, x, y \in \mathbb{K} \qquad (1) $$

endowing $\mathbb{K} \otimes \mathbb{R}$ with a Euclidean norm

$$ \|x\|_{\mathbb{C}} = \sqrt{\sum_{\sigma} |x^{\sigma}|^2}. \qquad (2) $$

This norm is related to the usual algebraic norm $\text{Norm}(x) = \prod_{\sigma} x^{\sigma}$ by the arithmetic-geometric means inequality

$$ \|x\|_{\mathbb{C}}^{2} \ge n |\text{Norm}(x)|^{\frac{2}{n}}. \qquad (3) $$

This allows to characterize the roots of unity in $\mathbb{K}$ as the shortest non-zero vectors of the lattice $\mathcal{O}_{\mathbb{K}}$. More precisely, we have (Cohen, 1993):

**Proposition 1** (Kronecker). For all $x \in \mathcal{O}_{\mathbb{K}} \setminus \{0\}$, one has $\|x\|_{\mathbb{C}}^{2} \ge [\mathbb{K} : \mathbb{Q}]$, with equality if and only if $x$ is a root of unity.

Thus the computation of roots of unity in $\mathbb{K}$ amounts to enumerating vectors in the ellipsoid $\|x\|_{\mathbb{C}}^{2} \le n$.
Contrary to other approaches, one advantage of this technique is that it combines the problem of computing the order $m = \#\mu(\mathbb{K})$, and that of finding an actual primitive root $\zeta_m \in \mathcal{O}_{\mathbb{K}}$.

Two closely related algorithms perform this task: the first is due to Fincke and Pohst (1985), the other to Kannan (1985). These are deterministic algorithms which rely on an initial reduction of the lattice and a exhaustive enumeration of its short vectors. The binary complexity of this task is in any case exponential, respectively $2^{O(n^2)}$ and $O(n^{\frac{n}{2}})$ binary operations (Hanrot and Stehlé, 2007).

## 2.1. Results

Despite its huge theoretic complexity, this exhaustive search performs well in practice in the following settings: low dimension (say $n \le 50$); when there are no non-trivial roots of unity; or when $\mathbb{K}$ is cyclotomic.

However, one can easily construct number fields for which the enumeration step is time consuming. In particular, random composita of fields of small degree provide many hard cases.

As an example, the polynomial

$$ 
\begin{aligned}
P = & x^{66} - x^{65} + x^{64} - x^{62} + 2x^{61} - 2x^{60} + x^{59} + x^{58} - 3x^{57} + 4x^{56} - 3x^{55} \\
& + 4x^{53} - 7x^{52} + 7x^{51} - 3x^{50} - 4x^{49} + 11x^{48} - 14x^{47} + 10x^{46} + x^{45} - 15x^{44} \\
& - 20x^{43} + 21x^{42} - 36x^{41} + 16x^{40} + 5x^{39} - 41x^{38} + 57x^{37} - 52x^{36} + 11x^{35} \\
& + 46x^{34} - 98x^{33} + 109x^{32} - 63x^{31} - 35x^{30} + 144x^{29} - 207x^{28} + 172x^{27} \\
& - 28x^{26} - 179x^{25} + 351x^{24} - 379x^{23} + 200x^{22} + 151x^{21} + 114x^{20} + 86x^{19} \\
& + 65x^{18} + 49x^{17} + 37x^{16} + 28x^{15} + 21x^{14} + 16x^{13} + 12x^{12} + 9x^{11} + 7x^{10} \\
& + 5x^{9} + 4x^{8} + 3x^{7} + 2x^{6} + 2x^{5} + x^{4} + x^{3} + x^{2} + 1
\end{aligned} 
\quad (4) 
$$

defines a field containing the forty-sixth roots of unity. The search for roots of unity using Fincke-Pohst algorithm (with the PARI/gp implementation) has been interrupted after four weeks on a dedicated machine.

## 3. Find the order

Computing the order $m = \#\mu(\mathbb{K})$, or at least finding a close upper bound is much simpler than computing a generator $\zeta_m$. This is also a prerequisite for the algorithms we will present next.

First of all, if there exist one real embedding $\sigma: \mathbb{K} \hookrightarrow \mathbb{R}$, then $\mu(\mathbb{K}) = \mu(\mathbb{R}) = \{\pm 1\}$. In particular this is the case for all fields of odd degree $n$.

### 3.1. Ramification of primes

Greater restrictions can be obtained by the ramification of primes induced by the inclusion $\mathcal{Q}(\zeta_m) \subset \mathbb{K}$.

**Proposition 2.** Let $p$ be a prime. If $\mu_{p^k} \subset \mathbb{K}$, one has

* $(p-1) | n$ and $k \le 1 + v_p(n)$;

* $k \le \lfloor \frac{v_p(\text{disc}(\mathbb{K}))}{n} + \frac{1}{p-1} \rfloor$.
where $n = [K : \mathbb{Q}]$ and $v_p$ denotes the p-adic valuation.

**Proof.** The first point derives from the multiplicativity of degrees

$$[\mathbb{Q}(\zeta_{p^k}) : \mathbb{Q}] = (p-1)p^{k-1} \mid n = [K : \mathbb{Q}].$$

The second is obtained from the discriminants relation: if $K \subset \mathbb{K}$ then $\mathrm{disc}(K)^{[K:K]} | \mathrm{disc}(\mathbb{K})$.

The cyclotomic field $\mathbb{Q}(\zeta_{p^k})$ having degree $(p-1)p^{k-1}$ and discriminant (Lang, 1964)

$$\mathrm{disc}(\mathbb{Q}(\zeta_{p^k})) = \pm p^{p^{k-1}(pk-k-1)},$$

the second inequality follows. □

## 3.2. Decomposition of primes

The local global principle works for roots of unity.

**Proposition 3.** The following statements are equivalent:

(i) $\mu_m \subset \mathbb{K}$;

(ii) $\mu_m \subset \mathbb{K}_p$ for each prime ideal $\mathfrak{p}$;

(iii) for every prime $p$ not dividing $m \times \mathrm{disc}\mathbb{K}$ and all prime ideals $\mathfrak{p}$ dividing $p$, $\mathrm{Norm}(\mathfrak{p}) \equiv 1 \mod m$.

**Proof.** We consider the Galois extension $\mathbb{K}(\zeta_m)/\mathbb{K}$. Let us suppose that for each non ramified prime $\mathfrak{p} \subset \mathcal{O}_{\mathbb{K}}$ one has $\mathrm{Norm}(\mathfrak{p}) \equiv 1 \mod m$, then the action of $\mathrm{Frob}_{\mathfrak{p}}$ on $\zeta_m$ is given by $\zeta_m \mapsto \zeta_m^{\mathrm{Norm}(\mathfrak{p})} = \zeta_m$, so that this Frobenius acts as identity. Čebotarev's density theorem concludes that the Galois group contains only the trivial class of conjugacy, which means that the extension has degree 1. □

**Remark 4.** Čebotarev's theorem allows to replace every prime $p$ by almost all primes, that is a set of primes of density 1.

This proposition makes it possible to guess the number of roots of unity in $\mathbb{K}$ with the following procedure: "compute the gcd of a number of values $\mathrm{Norm}(\mathfrak{p}) - 1$ until it stabilizes".

Computationally speaking, this is easy to implement, and one does not even need to compute $\mathcal{O}_{\mathbb{K}}$ nor perform any arithmetic in $\mathbb{K}$. If $p$ is unramified in $\mathbb{K} = \mathbb{Q}[x]/R(x)$, write

$$R(x) = \prod_{i=1}^{r} R_i(x) \mod p \qquad (5)$$

the factorization of $R(x)$ in $\mathbb{F}_p$, which corresponds to the prime ideal decomposition

$$p\mathcal{O}_{\mathbb{K}} = \prod_{i=1}^{r} \mathfrak{p}_i \qquad (6)$$

with $f_i = \mathrm{deg}(R_i)$ the inertia degree of the prime ideal $\mathfrak{p}_i$. Then the gcd of $\mathrm{Norm}(\mathfrak{p}_i) - 1$ is simply $p^f - 1$ where $f = \mathrm{gcd}\{f_i\}$.
Combining this idea with proposition 2, we obtain the following algorithm, in which the parameter N will be discussed later.

**Input:** K a number field, N integer

**Output:** a multiple m of the number of roots of unity in K;

Set m = 0 and p = 2;

repeat

1 | set p next unramified prime;
   | compute the decomposition of p in O_K;
   | compute the gcd f of the inertia degrees;
   | set m = gcd(m, p^f - 1);

until m stable since the last N loops;

for each divisor $p_i^{k_i}$ of m do

if $p_i - 1 \nmid [K : \mathbb{Q}]$ then
| $k_i = 0$

else

$k_i = \min(k_i, 1 + v_{p_i}([K : \mathbb{Q}]);$

$k_i = \min(k_i, \lfloor \frac{v_{p_i}(\text{disc}(K))}{[K:\mathbb{Q}]} + \frac{1}{p_i-1} \rfloor);$

end

done

return the product of $p_i^{k_i}$

**Algorithm 1:** Heuristic on the number of roots

This heuristic is quite precise in practice: the output number is in any case a multiple of the number of roots of unity in $K$, and in most cases it matches the true value.

However, one can build “bad” number fields $K$, which means that any sensible implementation of Algorithm 1 (i.e. any reasonable value of $N$) will output a strict multiple of $m$.

As an example, the number field

$$K = \mathbb{Q}(\sqrt{-51}, \sqrt{-230}, \sqrt{263}, \sqrt{307}) \qquad (7)$$

has degree $n = 8$, and no real embedding. Running Algorithm 1,

* the ramification criterion gives $\mu(K) \subset \mu_{24}$;

* the decomposition criterion of primes ($p$) gives $\mu(K) \subset \mu_{24}$ for $p \le 317$, then $\mu(K) \subset \mu_4$ for all primes $p \le 2999$.

However, these conclusions are still inaccurate. In fact, $K$ contains only the trivial roots $\mu_2$.

### 3.3. Randomized version

The example above seems to show that Algorithm 1 is ineffective. In fact, algorithm 1 can be made rigorous for explicit values of the parameter $N$. However such values must be large, this will be discussed in the next section.

On the other hand, it is quite easy to randomize the algorithm so that it outputs the correct value $m$ with probability

$$P(m = \#\mu(K)) > 1 - 2^{-N}. \qquad (8)$$

One needs to replace the line 1 “set $p$ next unramified prime” by “set $p \neq 1 \mod m$ a random unramified prime”.
In fact, if $d = [K(\zeta_m) : K]$, only a density $\frac{1}{d}$ of unramified primes satisfy $\text{Norm}(\mathfrak{p}) = 1 \mod m$, hence the result.

### 3.4. Effective Čebotarev's theorems

In order to make proposition 3 effective, we introduce two quantities:

* the upper bound for $m$ computed by considering all primes up to $x$

$$m_K(x) = \text{gcd}\{\text{Norm}(\mathfrak{p}) - 1, \mathfrak{p} \mid \mathfrak{p} \in \mathcal{O}_K, p \le x \text{ unramified}\}. \quad (9)$$

* the number of primes one needs to consider to get the correct value $m = \#\mu(K) = \lim_{x \to \infty} m_K(x)$

$$S(K) = \inf\{x \ge 2, m_K(x) = m \text{ where } \mu(K) = \mu_m\}. \quad (10)$$

Algorithm 1 can be made rigorous if one is able to bound $S(K)$. This question is solved with effective versions of Čebotarev's density theorems.

Under the generalized Riemann's hypothesis (GRH), Lagarias and Odlyzko (1977, cor1.2) give the following statement, (where the constant is due to Serre (1981)):

**Theorem 5.** Let $\mathbb{L}/K$ be a Galois extension, and assume that the Dedekind zeta function of $\mathbb{L}$ does not have any zero of real part greater than $\frac{1}{2}$. Then for every conjugacy class $C$ of $\text{Gal}(\mathbb{L}/K)$, there exists an unramified prime $\mathfrak{p}$ of $K$ with $\text{Frob}_{\mathfrak{p}} \in C$ and

$$\text{Norm}(\mathfrak{p}) \le c(\log \text{disc}(\mathbb{L}))^2$$

where $c$ is an absolute constant, which one can take equal to 70.

One applies this theorem to any non trivial class of automorphisms of $K(\mu_m)/K$, which gives

**Proposition 6.** Under GRH, if $\mu_m \notin K$ then $m \nmid m_K(x)$ for

$$x = 70(\log \text{disc}(K(\mu_m)))^2.$$

On the other hand, one can use the bounds of (Serre, 1981, prop.4') to give a criterion which does not depend on $\text{disc}(K(\mu_m))$:

**Proposition 7.** Under GRH, for all $p, k$ such that $\mu_{p^k} \notin K$, then $p^k \nmid m_K(x)$ for

$$x \ge 70\varphi(p^k)^2[\log \text{disc}(K) + n \log(p\varphi(p^k))]^2$$

where $n = [K : \mathbb{Q}]$.

**Corollary 8.** Under GRH, and with the notation of proposition 7, Algorithm 1 outputs the correct value $m = \#\mu(K)$ for the choice of parameter

$$N = 70(n^2\text{disc}(K) + 2n^3 \log(n))^2. \quad (11)$$

**Proof.** Let $p^k$ be an integer such that $\mu_{p^k} \subset K$. From the ramification criterion, we know that $\phi(p^k) \mid n$, in particular $\phi(p^k) \le n$. The corresponding primes are then filtered by the decomposition criterion under the bound of proposition 7. $\square$
<table><caption>**Table 1.** S(K) for quadratic fields, comparison with $\Delta_6 = \log \text{discK}(\zeta_6)$</caption><thead><tr><th>{D<sub>i</sub>}</th><th>S(K)</th><th>S(K)/Δ<sub>6</sub><sup>2</sup></th><th>S(K)/Δ<sub>6</sub></th></tr></thead><tbody><tr><td>{-1}</td><td>5</td><td>0.33</td><td>1.29</td></tr><tr><td>{-7}</td><td>11</td><td>0.44</td><td>2.20</td></tr><tr><td>{-23}</td><td>23</td><td>0.42</td><td>3.12</td></tr><tr><td>{-177}</td><td>59</td><td>0.29</td><td>4.15</td></tr><tr><td>{-2033}</td><td>101</td><td>0.28</td><td>5.29</td></tr><tr><td>{-172417}</td><td>149</td><td>0.19</td><td>5.32</td></tr><tr><td>{-58, 73}</td><td>227</td><td>0.14</td><td>5.67</td></tr><tr><td>{-311, 58}</td><td>317</td><td>0.15</td><td>6.91</td></tr><tr><td>{-1167, 389}</td><td>389</td><td>0.14</td><td>7.31</td></tr><tr><td>{-467, 1401}</td><td>467</td><td>0.16</td><td>8.54</td></tr><tr><td>{-1671, 557}</td><td>557</td><td>0.18</td><td>9.93</td></tr><tr><td>{-1707, 569}</td><td>569</td><td>0.18</td><td>10.12</td></tr><tr><td>{-2, -7, -1}</td><td>113</td><td>0.06</td><td>2.55</td></tr><tr><td>{-19, 5, 2}</td><td>191</td><td>0.07</td><td>3.53</td></tr><tr><td>{-47, -2, -7}</td><td>347</td><td>0.08</td><td>5.41</td></tr><tr><td>{-7, 5, 41}</td><td>359</td><td>0.10</td><td>6.06</td></tr><tr><td>{-87, -10, 19}</td><td>653</td><td>0.06</td><td>6.47</td></tr><tr><td>{-86, 17, 105}</td><td>977</td><td>0.08</td><td>9.07</td></tr></tbody></table>

This bound is by far too big to be used in practice: on the example (4), Proposition 7 states we need to check all primes less than $p = 12159134333$ to prove (under GRH) that $\mu(K) = \mu_{46}$. In practice, $S(K) = 5$ already proves $m | 46$, and the next step is to find $\zeta_{46}$.

In the next section, we investigate the sharpness of this bound on $S(K)$.

### 3.4.1. Finding bad examples

We are looking for large values of $S(K)$: our strategy is to choose a value $m > 2$, and find numerically fields $K$ such that $m | m_K(x)$ for large values of $x$, but $\mu_m \not\subset K$.

As a first example, we consider quadratic fields $K = \mathbb{Q}(\sqrt{D})$ for $m = 4$ or $m = 6$ (i.e. $\varphi(m) = 2$).

m = 4: We want $\text{Norm}(\mathfrak{p}) \equiv 1 \mod 4$, which means that primes congruent to 3 mod 4 are inert, that is $(\mathfrak{D}/p) = -1$.

m = 6: This time, we demand that $\text{Norm}(\mathfrak{p}) \equiv 1 \mod 3$, so that the primes $p \equiv 2 \mod 3$ (except 2) should be inert $(\mathfrak{D}/p) = -1$.
With a compositum of two fields $K = \mathbb{Q}(\sqrt{D_1}, \sqrt{D_2})$, we can also mimic the eighth roots of unity when all primes congruent to 3, 5, 7 mod 8 have a non trivial inertia in at least one quadratic subfield.

As an example $K = \mathbb{Q}(\sqrt{7}, \sqrt{-723})$, for which $S(K) = 131$. The heuristic detects wrongly $\mu_{24}$ (or $\mu_{12}$ with the ramification criterion).

Focusing on 8-th roots, one obtains for example $K = \mathbb{Q}(\sqrt{11}, \sqrt{-23})$ which passes all tests up to $S(K) = 127$.

Another nice example is $K = \mathbb{Q}(\sqrt{-7}, \sqrt{5}, \sqrt{41})$, which seems to contain $\mu_{24}$ until $S(K) = 359$.

Table 1 shows a list of fields $K = \mathbb{Q}(\sqrt{D_1}, \dots)$ such that $\mu(K) = \mu_2$ but (at least) $3 | m_K(x)$ for $x < S(K)$.

In particular, we tried to obtain good lower bounds of the $c$ constant appearing in theorem 5, that is of the ratio $S(K)/\Delta_m^2$, where $\Delta_m = \log \text{disc}K(\zeta_m)$.

The values obtained are small compared to the proven value 70, and they are decreasing when we aim at larger $S(K)$.

On the other hand, it is asked in Serre (1981) if the exponent 2 in proposition 5 can be replaced by $1 + \varepsilon$. In this context, the last column of table 1 shows increasing values of $S(K)/\delta_m$.

### 3.4.2. Generalization with linear programming

Larger values of $S(K)$ can be reached with the same idea of composing small fields, in order to distribute inertia degrees among them.

Linear programming can be used to find good combinations with a degree as small as possible. Let $K = K_1 \dots K_n$ be the compositum of the $K_j = \mathbb{Q}[X]/(Q_j)$.

As before, one demands that for each prime $p$ up to a certain fixed bound, the inertia degree $f_{p/p}$ of $\mathfrak{p}$ | $pO_K$ is a multiple of the order of $p$ in $(\mathbb{Z}/m\mathbb{Z})^*$.

Let us write

$$(\mathbb{Z}/m\mathbb{Z})^\times = \prod_q \prod_i \mathbb{Z}/q^{e_{q,i}}\mathbb{Z},$$

the $p$-primary decomposition of $(\mathbb{Z}/m\mathbb{Z})^\times$ and

$$o(p) = \prod_q q^{\alpha_{p,q}}$$

the decomposition into prime factors of the order of $p$ modulo $m$.

Then define the coefficients

$$\delta(K_j, p, q^\alpha) = \begin{cases} 1 & \text{if } \forall \mathfrak{p} \mid pO_{K_j}, \text{Norm}(\mathfrak{p}) \equiv 1 \mod [q^\alpha] \\ 0 & \text{otherwise.} \end{cases}$$

The fact that $m | m_K(x)$ is then coded by the following linear program, where the columns are indexed by a family of polynomials $Q_j$, and the lines describe the inertia degree with respect to every prime $p$ less than $x$:

$$\forall p \le x, \forall q \mid o(p), \sum_j x_j \delta(K_j, p, q^{\alpha_{p,q}}) \ge 1 \quad (12)$$

We add the following objective function:

$$\text{Minimize} \quad \sum_j x_j \deg(Q_j) - \text{disc}(Q_j)^{-1}$$
<table><caption>**Table 2.** Fields found with linear programming (using GLPK<sup>2</sup> library)</caption><thead><tr><th>m</th><th>deg(K)</th><th>Δ<sub>m</sub> = log disc(K(μ<sub>m</sub>))</th><th>S(K)</th><th>S(K)/Δ<sub>m</sub><sup>2</sup></th><th>S(K)/Δ<sub>m</sub></th></tr></thead><tbody><tr><td>6</td><td>8</td><td>29.1</td><td>131</td><td>1.55e-1</td><td>4.50</td></tr><tr><td>6</td><td>8</td><td>29.9</td><td>149</td><td>1.67e-1</td><td>4.98</td></tr><tr><td>4</td><td>16</td><td>137.3</td><td>991</td><td>5.26e-2</td><td>7.21</td></tr><tr><td>4</td><td>32</td><td>249.4</td><td>2003</td><td>3.22e-2</td><td>8.03</td></tr><tr><td>4</td><td>32</td><td>364.0</td><td>2999</td><td>2.26e-2</td><td>8.24</td></tr><tr><td>6</td><td>32</td><td>344.0</td><td>2999</td><td>2.53e-2</td><td>8.72</td></tr><tr><td>6</td><td>32</td><td>397.1</td><td>3089</td><td>1.96e-2</td><td>7.78</td></tr><tr><td>12</td><td>64</td><td>1354.2</td><td>8009</td><td>4.37e-3</td><td>5.91</td></tr></tbody></table>

in order to minimize the degree of the compositum $K$, and to a minor extent its discriminant.

As is, this program would output the $m$-th cyclotomic extension as a compositum of some of its subfields. Thus we add some low inertia constraints on a prime $p > p_n$ to avoid this situation.

Running this integer linear program<sup>1</sup>, even without reaching the true optimum, yields extensions with interesting extremal ramification properties in the context of the effective Čebotarev theorem.

The table 2 shows some of the constructions obtained this way. The remarks made about table 1 are still valid here, in particular one can increase the ratio $S(K)/\Delta_m$. The method described here could help further investigations on this topic.

# 4. Roots via Hensel lifting

This section is an restriction to the roots of unity setting of the general algorithm of polynomial factorisation in number fields, for which we refer to (Belabas, 2004).

## 4.1. Principle

Once a multiple $m$ of the order of $\mu(K)$ is known, the true order can be found by factoring the cyclotomic polynomial $\Phi_m$ over $K$. The modular algorithm of Belabas consists in the following steps:

(1) compute a local root $\bar{\zeta}$ modulo a prime ideal $\mathfrak{p}$;

(2) lift $\bar{\zeta}$ modulo $\mathfrak{p}^k$ with Hensel's lemma;

(3) take a representative $\zeta \in \mathcal{O}_K$ as soon as the fundamental domain of the lattice $\mathfrak{p}^k$ is sufficiently large so that it contains the ellipsoid $\|x\|_C^2 \le n$, hence $\mu(K)$.

<footnote n="1">¹ available at http://www.math.jussieu.fr/~molinp.</footnote>

<footnote n="2">² Gnu Linear Programming Kit, see references.</footnote>
<figure><img src="image_2.png" /></figure>

The first two steps are straightforward. As for the third, one must make sure that the lift will be a root of unity, if it exists. If such a lift does not exists, it then proves that the heuristic on $m$ has to be refined and we proceed with its divisors.

In the next paragraphs, we give some details for each step of Algorithm 2.

**Input:** $K$ a number field with a basis of $O_K$, a multiple $m$ of the order of $\mu_K$

**Output:** the expression of a primitive root in $\mu_K$

**begin**

choose a prime ideal $\mathfrak{p}$;

evaluate the lift exponent $k$;

**repeat** for $k$ increasing

compute $\mathfrak{p}^k$ and determine a LLL-reduced basis;

compute the maximal radius in its fundamental domain $D$;

**until** $B(n) \subset D$;

**for each** $q = \mathfrak{p}^l$ dividing $m$ **do**

compute $\bar{\zeta}_q \in O_K/\mathfrak{p}$ a primitive $q$-th root of unity;

lift it modulo $\mathfrak{p}^k$ by Hensel;

**repeat** for $l$ decreasing

take central lift $\zeta_q \in O_K$;

**until** $\zeta_q \in B(n)$, otherwise set $\bar{\zeta}_q \leftarrow \bar{\zeta}_q^p$;

**done**

**return** product of $\zeta_q$

**end**

<caption>**Algorithm 2:** Modular calculation of roots of unity</caption>

### 4.1.1. Choice of $\mathfrak{p}$ and computation in $\mathbb{K}(\mathfrak{p})$

In theory, every non ramified prime allows to perform the following steps. In practice, one must balance two aspects: a large value of $p$ or a greater inertia degree result in a lattice $\mathfrak{p}$ of larger volume, thus reducing the exponent $k$. The drawback is however the cost of calculations in $\mathbb{K}(\mathfrak{p})$.

In practice, it is interesting to choose a small prime of big inertia degree.

We then use the standard Cantor-Zassenhaus algorithm to find a root of the cyclotomic polynomial $\Phi_q$ in the finite field $\mathbb{K}(\mathfrak{p}) = \mathbb{F}_p[X]/\bar{P}$.

If there is no root, $m$ was overestimated and we proceed to the next value of $q$; otherwise we obtain one $\bar{\zeta}$.

A prime ideal $\mathfrak{p}$ is represented by two generators $\mathfrak{p} = \langle p, \beta \rangle$, its powers are given by

$$ \mathfrak{p}^k = \langle p^k, \beta^k \rangle $$

before one applies LLL to obtain a nicer fundamental domain.
### 4.1.2. Lifting in $O_K$

The lattice $\mathfrak{p}^k \subset O_K$ is represented with a Z-basis $(v_1, \dots, v_n)$, and the canonical lift $O_K/\mathfrak{p}^k \to O_K$ is the lift belonging to the centered fundamental domain

$$D = \left\{ \sum x_i v_i, x_i \in ] -\frac{1}{2}; \frac{1}{2}] \right\}.$$

We use the geometric setting of section 2, in particular the Euclidean space inherited from the complex embeddings. For $r \ge 0$, we introduce the ball

$$B(r) = \{ x \in O_K, \|x\|_C^2 \le r \}. \qquad (13)$$

We note

$$G = (\langle v_i, v_j \rangle) \qquad (14)$$

the Gram matrix of $(v_1, \dots, v_n)$, so that $\langle x, y \rangle = {}^t x G y$ for $x = \sum_i x_i v_i$ and $y = \sum_i y_i v_i \in \mathfrak{p}^k$.

Proposition 1 asserts that $\mu(K) \subset B(n)$, so that one can make sure that the lift $\bar{\zeta} \in O_K/\mathfrak{p}^k \to \zeta \in D$ will give a root of unity if $B(n) \subset D$. The following criterion answers this question.

**Lemma 9.**

$$B(r) \subset D \Leftrightarrow r \le R_{\max} = \frac{1}{2 \max_j \sqrt{(G^{-1})_{j,j}}} \qquad (15)$$

where $(G^{-1})_{j,j}$ denote the diagonal terms of the inverse matrix $G^{-1}$.

**Proof.** This radius is the shortest distance of the centre of $D$ to its facets. These distances are given by

$$d\left(\sum \frac{v_i}{2}, H_j\right) = \frac{1}{2} d(v_j, H_j)$$

where $H_j = \text{Vect}(v_1, \dots, \tilde{v}_j, \dots, v_n)$ is the hyperplane spanned by the $v_i$ for $i \ne j$.

Let us write $\tilde{v}_j$ the vector orthogonal to $H_j$ defined by

$$\forall i, \langle \tilde{v}_j, v_i \rangle = \delta_{i,j},$$

so that $\tilde{v}_j$ is precisely the $j$-th column of $G^{-1}$.

We then obtain $d(v_j, H_j) = \frac{|\langle \tilde{v}_j, v_j \rangle|}{\|\tilde{v}_j\|_C}$, hence $d(v_j, H_j) = \|(G^{-1})_j\|_C^{-1}$.

It remains to compute the norm

$$\|(G^{-1})_j\|_C^2 = {}^t (G^{-1})_j G (G^{-1})_j = (G^{-1})_{j,j},$$

which concludes the proof. $\square$

For calculations, it is preferable to express $\tilde{v}_i$ on the orthonormal basis $(v_i^*)$, that is to replace the Gram matrix $G$ by the Gram-Schmidt orthogonalization matrix

$$K = (\langle v_i^*, v_j \rangle)_{i,j}.$$

The inversion step is simpler since this matrix is triangular. The computations have to be adapted only when taking the norm, where the orthogonality gives

$$\|K_j^{-1}\|_C^2 = \sum_i \frac{K_{i,j}^2}{\|v_i^*\|_C^2}.$$
As a consequence we have the alternative expression

$$R_{\max} = \frac{1}{2} \min_j \sqrt{\sum_i \frac{K_{i,j}^2}{\|v_i^*\|_C^2}}. \qquad (16)$$

### 4.1.3. Estimates for the exponent k

The radius (16) will be bigger if the basis $(v_1, \dots, v_n)$ is almost orthogonal and made of short vectors. This explains why we first take $(v_1, \dots, v_n)$ to be LLL-reduced.

This LLL-reduction of $\mathfrak{p}^k$ is the most time-consuming part of the algorithm, since the matrix has dimension $n$ and entries of size $p^k$, using the best $\tilde{L}^1$ algorithm of Novocin et al. (2011), the complexity $O_{\varepsilon}(n^{5+\varepsilon}k \log p + n^{3.5+\varepsilon}(k \log p)^{1+\varepsilon})$ can be quasi-linear in terms of $k$.

If one adopts a LLL-reduction with a quality factor $\gamma$, a study of the formula (16) gives the following upper bound for $k$ (Belabas, 2004)

$$R_{\max} \geq \frac{\|v_1\|_C}{2\left(\frac{3\sqrt{\gamma}}{2}\right)^{n-1}}.$$

Moreover, the norm of $v_1 \in \mathfrak{p}^k$ is a multiple of $\text{Norm}(\mathfrak{p})^k$ and the arithmetic-geometric means inequality (3) gives

$$\|v_1\|_C \geq n \text{Norm}(\mathfrak{p})^{\frac{2k}{n}}.$$

Thus we have the following upper bound:

$$k \leq \frac{n \log(2n^{\frac{3}{2}}(\frac{3\sqrt{\gamma}}{2})^{n-1})}{2f \log(p)} = O\left(\frac{n^2}{f \log(p)}\right). \qquad (17)$$

All in all, using latest LLL algorithms, Algorithm ?? has polynomial running time $O_{\varepsilon}(n^{7+\varepsilon})$.

## 5. Integral linear system

Assume we know that $\mu(\mathbb{K}) = \mu_m$. A primitive root $\zeta_m \in \mathcal{O}_{\mathbb{K}}$ is obtained as a solution of the integer linear system

$$\sum_{i=1}^{n} \alpha_i \omega_i^{\sigma} = e^{\frac{2i\pi}{m}}, \quad (a_i) \in \mathbb{Z}^n, \qquad (18)$$

where $\mathcal{O}_{\mathbb{K}} = \bigoplus \mathbb{Z}\omega_i$ and $\sigma: \mathbb{K} \to \mathbb{C}$ is a fixed embedding.

This system has complex coefficients and is hard to solve. However there is a standard way to find integral relations with small coefficients between complex numbers, based on the LLL algorithm.

We consider the lattice $\Lambda = \mathbb{Z}^{n+1}A$, where $A$ is the $(n+1) \times (n+2)$ matrix

$$A = \begin{bmatrix} 1 & \cdots & 0 & [M\text{Re}(\omega_1^\sigma)] & [M\text{Im}(\omega_1^\sigma)] \\ \vdots & \ddots & \vdots & \vdots & \vdots \\ 0 & \cdots & 1 & [M\text{Re}(\omega_n^\sigma)] & [M\text{Im}(\omega_n^\sigma)] \\ 0 & \cdots & 0 & [M\text{Re}(e^{\frac{2i\pi}{m}})] & [M\text{Im}(e^{\frac{2i\pi}{m}})] \end{bmatrix} \qquad (19)$$
and depends on a big constant $M$ chosen on purpose, so that the shortest non-zero vector of the lattice

$$Z = (\alpha_1, \dots, \alpha_n, k)A$$

corresponds to an equality

$$\sum_{i=1}^{n} \alpha_i \omega_i^{\sigma} = ke^{\frac{2i\pi}{m}}, k = \pm 1,$$

and has its two last components almost equal to zero, while other vectors should be of norm in the greater range given by $M$.

Rigorously setting up this knapsack strategy demands two estimates: an upper bound for the expected vector norm, and a lower bound for other unwanted vectors. We give such bounds in the proposition 14 below.

Then, the properties of LLL-reduced basis (proposition 15) allow to choose the constant $M$ to select exactly the desired of unity:

**Theorem 10.** For the explicit values $C_O$ and $C_\sigma$ defined in equations (24) and (25) below, if one chooses

$$M > 2^{n(n+1)/2} C_{\sigma} (\sqrt{n+2}(nC_{O} + 1))^{n}. \quad (20)$$

then the first vector $Z_1$ of a LLL reduced basis of $\Lambda$ satisfies:

* either its $n$ first components give the expression of a $m$-th primitive root of unity $\zeta_m$;

* or $O$ does not contain the group of $m$-th roots of unity.

We prove this theorem in the following paragraphs.

In practice, the size of $M$ would lead to huge computations. However we can decide to run the LLL reduction with a much smaller value $M$, and test whether the first vector $Z_1$ corresponds to a root of unity or not, in which case one has to switch to a more rigorous approach to refine the result.

**Input:** a number field $K$ with a basis of $O_K$ and the order $m$ of $\mu_m$

**Output:** an expression of a $m$-th primitive root $\zeta$ or failure

begin

choose $M$ to be, say, the $n$-th root of (20);

build the matrix $A$ of (19);

perform its LLL reduction;

compute the vector $x \in O_K$ defined by its first components;

if $x$ is of order $m$ then

| **return** $(m, x)$;

else

| **return** failure;

end

end

**Algorithm 3:** Linear dependency

## 5.1. Norm inequalities

Every vector $Z$ of $\Lambda$ is the data of an algebraic integer $x$ given by its coordinates on the basis of $O$, and the decimal approximation of a complex number $Mz$ formed of the two last components.
More precisely, to any couple $(x, k) \in \mathcal{O}_{\mathbb{K}} \times \mathbb{Z}$, with $x = \sum \alpha_i \omega_i$, we define

• the vector $X = (\alpha_1, \dots, \alpha_n, k) \in \mathbb{Z}^{n+1}$;

• its image $Z = (\alpha_1, \dots, \alpha_n, a, b) \in \Lambda$;

• the complex $z = \sum \alpha_i \omega_i^\sigma + k e^{2i\pi/m} \in \mathbb{C}$.

Each space above is endowed with its Euclidean norm $\|\cdot\|_2$, for which we have

$$ \|Z\|_2^2 = \sum \alpha_i^2 + a^2 + b^2 = \|x\|_2^2 + a^2 + b^2. \qquad (21) $$

We also consider the 1-norm $\|x\|_1 = \sum |\alpha_i|$.

**Lemma 11.** With the notations above, we have

$$ \|X\|_2^2 + (M|z| - \sqrt{2}\|X\|_1)^2 \le \|Z\|_2^2 \le \|X\|_2^2 + (M|z| + \sqrt{2}\|X\|_1)^2. $$

**Proof.** In fact, the definition of integer part implies

$$ M\mathrm{Re}(z) - \sum |\alpha_i| \le a \le M\mathrm{Re}(z) + \sum |\alpha_i| $$

and the same inequality on imaginary parts, so that when taking the square

$$ \begin{aligned} a^2 + b^2 &\ge M^2 |z|^2 - 2M \|X\|_1 (|\mathrm{Re}(z)| + |\mathrm{Im}(z)|) + 2 \|X\|_1^2 \\ &\ge (M|z| - \sqrt{2}\|X\|_1)^2. \end{aligned} $$

□

The conversion from and to the norm $\|\cdot\|_C$ introduced in section 2 is straightforward: introducing the matrix of conjugates

$$ V = (\omega_j^\sigma)_{\sigma:K \hookrightarrow \mathbb{C}, 1 \le j \le n} \qquad (22) $$

we have

$$ \|x\|_C = \|Vx\|_2. \qquad (23) $$

We define the constants

$$ C_O = \|V^{-1}\|_2 \qquad (24) $$

and

$$ C_{\sigma} = \prod_{\tau \neq \sigma} \max(1, \|V_{\tau}\|_2) \qquad (25) $$

where $\tau$ runs over the complex embeddings, and $V_\tau$ is the line $(\omega_1^\tau, \dots, \omega_n^\tau)$ of $V$.

From proposition 1 we deduce

**Lemma 12.** For all $\zeta \in \mu(\mathbb{K})$,

$$ \|\zeta\|_2^2 \le nC_O. \qquad (26) $$

On the other hand, we have the lower bound

**Lemma 13.** Suppose $\zeta_m \in \mathcal{O}$, then keeping current notations, if $z \neq 0$ we have

$$ |z| \ge \frac{1}{C_{\sigma} \|X\|_1^{n-1}}. \qquad (27) $$
**Proof.** Since we supposed $\zeta_m \in \mathcal{O}$, there exist some $y = x+k\zeta_m \in \mathcal{O}_K$, with $x = \sum \alpha_i \omega_i$ such that $z = y^\sigma$. For each embedding $\tau: K \hookrightarrow \mathbb{C}$ we have

$$|y^\tau| \le |x^\tau| + |ke^{2i\pi k/m}| \le \|V_\tau\|_2 \|(\alpha_1, \dots, \alpha_n)\|_2 + |k| \le \max(\|V_\tau\|_2, 1) \|X\|_1$$

and since $y \in \mathcal{O}_K$, we obtain the result from (25) and $1 \le |\text{Norm}(y)| = |y^\sigma| \prod_{\tau \ne \sigma} |y^\tau|$. $\square$

From these inequalities we deduce

**Proposition 14.** Suppose $\mu_m \subset \mathcal{O}$, and set $\zeta_m = \sum \alpha_i \omega_i$ the root of unity whose image by $\sigma$ is $e^{\frac{2i\pi}{m}}$. Then

* the vector $Z \in \Lambda$ obtained as image of the vector $X$ of components $(\alpha_1, \dots, \alpha_n, -1)$ satisfies

$$\|Z\|_2^2 \le 2nC_O + 2; \qquad (28)$$

* for all vector $Z$ in $\Lambda$ whose associated complex number $z$ is non zero, we have

$$\|Z\|_2 \ge \frac{1}{\sqrt{n+1}} \left( \frac{M}{\sqrt{2}C_{\sigma}} \right)^{\frac{1}{n}}. \qquad (29)$$

**Proof.** The vector $Z$ corresponds to the complex $z = 0$, so lemma 11 implies $\|Z\|_2^2 \le \|X\|_2^2 + \|X\|_1^2 = \|\zeta\|_2^2 + \|\zeta\|_1 + 2$. With the trivial upper bound $\|\zeta\|_1 \le \|\zeta\|_2^2$, the lemma 12 proves the assertion.

The second part is deduced from the other inequality in lemma 11 combined with the lower bound of lemma 13: let $U = \|X\|_1 \ge 1$, $|z|$ is a solution of the system

$$\begin{cases} \sqrt{n+2} \|Z\|_2 \ge U + |M| |z| - \sqrt{2U}| \\ |z| \ge \frac{1}{C_{\sigma} U^{n-1}}. \end{cases}$$

If $M|z| \le \sqrt{2U}$, then

$$U \ge \left( \frac{M}{\sqrt{2}C_{\sigma}} \right)^{\frac{1}{n}} = U_M \qquad (30)$$

so that

$$\sqrt{n+2} \|Z\|_2 \ge U_M.$$

On the other hand, if $M|z| \ge \sqrt{2U}$, then

$$\sqrt{n+2} \|Z\|_2 \ge \frac{M}{C_{\sigma} U^{n-1}} - (\sqrt{2}-1)U$$

with a right-hand member which is decreasing in $U$, hence always greater than its value for $U_M$, which is $U_M$. Thus, if $|z| \ne 0$ we obtain the inequality (29). $\square$

We finish the proof of theorem 10. The theory of LLL reduction gives a quality bound on the short vector output:

**Proposition 15.** Let $\Lambda$ be a lattice of dimension $n$, and $Z_1$ the first vector of a LLL reduced basis. Then for all non-zero vector $Z$ of $\Lambda$ we have

$$\|Z_1\|_2 \le 2^n \|Z\|_2.$$
**Proof.** See (von zur Gathen and Gerhard, 2003). Note that the lattice here has dimension $n + 1$. □

To make sure that, under the hypotheses of proposition 14, the short vector output by the LLL reduction is $\zeta_m$, we only need to make the inequality

$$ \frac{1}{\sqrt{n+1}} \left( \frac{M}{\sqrt{2C_{\sigma}}} \right)^{\frac{1}{n}} \le 2^n (2nC_O + 2) $$

impossible. Therefore we set

$$ M > 2^{n(n+1)+1/2} C_{\sigma} (\sqrt{n+2}(nC_O+1))^n, $$

which concludes the proof of theorem 10.

## 6. Suggested Algorithm

Collecting the results of the previous sections, we suggest the following steps, each one making the algorithm stop if it manages to give a definitive answer.

**Input:** a number field $K$ with a basis of $O_K$

**Output:** the order of $\mu(K)$ and the expression of a primitive root $\zeta$

begin

guess $m = \#\mu_K$ with heuristic algorithm 1;

if $m = 2$ then

return ($m = 2, \zeta = -1$);

else

try algorithm 3;

if we obtain $\zeta$ of order $m$ then

return ($m, \zeta$);

else

run the modular algorithm 2;

return its result ($m', \zeta$);

end

end

end

**Algorithm 4:** Complete strategy

## 7. Timings

The table 3 below gives the results obtained by the different algorithms studied on a panel of polynomials. The factorisation algorithm means algorithm 2 run after heuristic 1; and lindep refers to algorithm 3, also after the guess of heuristic 1. A star (⋆) indicates that the test had to be interrupted after long calculations.

These results illustrate the strength of the factorisation algorithm: it always give the result in a reasonable time, even in the case we fooled the heuristic step with fields built on purpose (last lines), compelling it to factor more polynomials. The hybrid approach we suggest amounts to taking the lindep column, and eventually add the factorisation column when there is a failure. It manages to solve quickly all simple cases for which Kannan's algorithm performs well, and remains polynomial in hard cases.
<table><caption>**Table 3.** comparison of all approaches</caption><thead><tr><th>degree</th><th>roots m</th><th>factorisation</th><th>Kannan</th><th>lindep</th></tr></thead><tbody><tr><td colspan="5"><em>small fields</em></td></tr><tr><td>12</td><td>36</td><td>20.0ms</td><td>0.0ms</td><td>20.0ms</td></tr><tr><td>32</td><td>96</td><td>310.0ms</td><td>30.0ms</td><td>440.0ms</td></tr><tr><td colspan="5"><em>large cyclotomics</em></td></tr><tr><td>96</td><td>194</td><td>2mn</td><td>690.0ms</td><td>5.2s</td></tr><tr><td>180</td><td>362</td><td>1.6h</td><td>5.4s</td><td>17.4s</td></tr><tr><td colspan="5"><em>compositum of small fields</em></td></tr><tr><td>54</td><td>18</td><td>7.7s</td><td>★ > 3 days</td><td>2.3s</td></tr><tr><td>66</td><td>46</td><td>17.4s</td><td>★ > 4 weeks</td><td>1.1s</td></tr><tr><td>72</td><td>24</td><td>15.3s</td><td>5h27</td><td>fail</td></tr><tr><td colspan="5"><em>fields constructed with linear programming</em></td></tr><tr><td>24</td><td>72</td><td>0.2s</td><td>0.1s</td><td>0.2s</td></tr><tr><td>48</td><td>24</td><td>11s</td><td>0.2s</td><td>1.7s</td></tr><tr><td>54</td><td>6</td><td>12s</td><td>0.2s</td><td>2.1s</td></tr><tr><td>64</td><td>4</td><td>18.6s</td><td>0.4s</td><td>3.3s</td></tr><tr><td>64</td><td>6</td><td>36.4s</td><td>0.4s</td><td>3.7s</td></tr></tbody></table>

## Acknowledgements

The author would like to thank Karim Belabas who has suggested this work, and Régis de la Bretèche for pointing an error in a previous version.

## References

* Belabas, K., 2004. A relative van Hoeij algorithm over number fields. J. Symbolic Comput. 37 (5), 641–668.

* Cohen, H., 1993. A course in computational algebraic number theory. Vol. 138 of Graduate Texts in Mathematics. Springer-Verlag, Berlin.

* Fincke, U., Pohst, M., 1985. Improved methods for calculating vectors of short length in a lattice, including a complexity analysis. Math. Comp. 44 (170), 463–471.

* Hanrot, G., Stehlé, D., 2007. Improved analysis of Kannan's shortest lattice vector algorithm (extended abstract). In: Advances in cryptology—CRYPTO 2007. Vol. 4622 of Lecture Notes in Comput. Sci. Springer, Berlin, pp. 170–186.

* Kannan, R., 1985. Lattices, basis reduction and the shortest vector problem. In: Theory of algorithms (Pécs, 1984). Vol. 44 of Colloq. Math. Soc. János Bolyai. North-Holland, Amsterdam, pp. 283–311.
Lagarias, J. C., Odlyzko, A. M., 1977. Effective versions of the Chebotarev density theorem. In: Algebraic number fields: L-functions and Galois properties (Proc. Sympos., Univ. Durham, Durham, 1975). Academic Press, London, pp. 409–464.

Lang, S., 1964. Algebraic numbers. Addison-Wesley Publishing Co., Inc., Reading, Mass.-Palo Alto-London.

Novocin, A., Stehlé, D., Villard, G., 2011. An LLL-reduction algorithm with quasi-linear time complexity. In: Proceedings of the 43rd annual ACM symposium on Theory of computing. ACM New York, NY, USA, San Jose, United States, pp. 403–412.

Serre, J.-P., 1981. Quelques applications du théorème de densité de Chebotarev. Inst. Hautes Études Sci. Publ. Math. (54), 323–401.

von zur Gathen, J., Gerhard, J., 2003. Modern computer algebra, 2nd Edition. Cambridge University Press, Cambridge.