Algorithm 4 to generate the entire log-$\mathbb{S}$-unit lattice satisfies, for any $\alpha > 0$,

$$ \Pr[S > 3 \cdot (2 + \alpha)(t + n_1)] \le e^{-\alpha(t+n_1)/2}, \quad (131) $$

where $n_1 = |\mathbb{S}| + r = \dim(\mathrm{Log}_{\mathbb{S}}(\mathcal{O}_{K,\mathbb{S}}^{\times})) = n_0 - 1$ and$^{22}$

$$ \begin{aligned} t &= n_1 \cdot \log_2(R_0) - \log_2(\mathrm{Vol}(\mathrm{Log}_{\mathbb{S}}(\mathcal{O}_{K,\mathbb{S}}^{\times}))) \\ &\le n_1 \cdot \log_2(R_0) + 2 \\ &\le n_1[\log(n_0\varsigma) + \mathcal{O}(\log \log |\Delta_K|)]. \end{aligned} $$

Taking $\alpha = 2k/(t + n_1)$, we have $\alpha(t + n_1)/2 = k$, and

$$ 3 \cdot (2 + \alpha)(t + n_1) = 6(t + n_1) + 3\alpha(t + n_1) = 6(t + n_1) + 6k. $$

Hence, replacing the above formula into Equation (131), we obtain

$$ \Pr[S > 6(t + n_1) + 6k] \le e^{-k}. $$

Therefore, the probability that $6(t + n_1) + 6k$ samples from the output distribution of Algorithm 4 generate the entire logarithmic $\mathbb{S}$-unit lattice $\mathrm{Log}_{\mathbb{S}}(\mathcal{O}_{K,\mathbb{S}}^{\times})$ is at least $1 - e^{-k}$. Replacing $t + n_1$ by the larger $n_1[\log(n_1\varsigma) + C(\log \log |\Delta_K|)]$ (for some absolute constant, and hiding $n_1$ under this constant by increasing the constant slightly if needed), yields the final claim. $\square$

This theorem roughly states that the number of samples drawn from $\bar{D}$ (the output distribution of Algorithm 4) for the sampled vectors to generate the log-$\mathbb{S}$-unit lattice $\mathrm{Log}_{\mathbb{S}}(\mathcal{O}_{K,\mathbb{S}}^{\times})$ (with high probability) only needs to exceed a small multiple of the dimension of $\mathrm{Log}_{\mathbb{S}}(\mathcal{O}_{K,\mathbb{S}}^{\times})$. In other words, if one assembles sufficiently many of such samples (quasi-linearly in the dimension), they generate the log-$\mathbb{S}$-unit lattice except for an exponentially small probability.

In almost all applications involving $\mathbb{S}$-units, a generating set with high probability is not sufficient. Instead, often a basis of the logarithmic $\mathbb{S}$-units is demanded (or, equivalently, a fundamental set of $\mathbb{S}$-units, see Section 19.1); and, additionally, no probabilistic error is allowed (i.e., one wants to be sure that the basis at hand truly is a basis of the full log-$\mathbb{S}$-unit lattice).

To resolve these issues, one needs to post-process the set of generators by lattice reduction techniques. This is the subject of Section 19.

## 19. POST-PROCESSING PHASE

19.1. **Introduction.** Up to now, the algorithm of this paper allows to provably sample $\mathbb{S}$-units in $\mathcal{O}_{K,\mathbb{S}}^{\times}$ with a certain probability. Furthermore, a sufficient number of these $\mathbb{S}$-units samples will generate the entire $\mathcal{O}_{K,\mathbb{S}}^{\times}$ with overwhelming probability. To complete the entire algorithm, two tasks remain to be done.

(I) An algorithm to verify that the sampled elements truly generate all of $\mathcal{O}_{K,\mathbb{S}}^{\times}$ and not a subgroup thereof$^{23}$.

<footnote>$^{22}$We use here that $\mathrm{Vol}(\mathrm{Log}_{\mathbb{S}}(\mathcal{O}_{K,\mathbb{S}}^{\times})) = h_K \cdot R_K \cdot \sqrt{n_{\mathbb{R}} + n_{\mathbb{C}}} \ge R_K \ge 0.206$, since $R_K \ge 0.206$ uniformly for all number fields [31, Theorem B].</footnote>

<footnote>$^{23}$One could say that this algorithm changes the probabilistic algorithm of this paper from a Monte Carlo algorithm (a randomized algorithm whose output may be incorrect with a small probability, but with bounded running time) to a Las Vegas algorithm (a randomized algorithm that always gives correct results, but whose running time is a random variable)</footnote>
(II) An algorithm to compute a fundamental system of $\mathbb{S}$-units of $\mathcal{O}_{K,\mathbb{S}}^\times$ out of these generators, i.e., a sequence of elements $(\eta_j)_j \in \mathcal{O}_{K,\mathbb{S}}^\times$ with $j \in \{1, \dots, \text{rank}(\mathcal{O}_{K,\mathbb{S}}^\times)\}$ such that every element $\eta \in \mathcal{O}_{K,\mathbb{S}}^\times$ is a power product of these elements (and a possible root of unity): $\eta = \tau_K \prod_{j=1}^{\text{rank}(\mathcal{O}_{K,\mathbb{S}}^\times)} \eta_j^{m_j}$ for some $m_j \in \mathbb{Z}$; where $\tau_K \in \mathcal{O}_K$ is some root of unity$^{24}$.

**19.2. Solving both (I) and (II) by computing bases.** Let $G \subseteq \mathcal{O}_{K,\mathbb{S}}^\times$ be a finite set of $\mathbb{S}$-units. Then its associated lattice

$$ \mathcal{L}_G := \sum_{\eta \in G} \mathrm{Log}_{\mathbb{S}}(\eta) \cdot \mathbb{Z} = \{\mathrm{Log}_{\mathbb{S}}(\eta') \mid \eta' \in \langle G \rangle\} $$

satisfies $\mathcal{L}_G \subseteq \mathrm{Log}_{\mathbb{S}}(\mathcal{O}_{K,\mathbb{S}}^\times)$, i.e., it is a sublattice of $\mathrm{Log}_{\mathbb{S}}(\mathcal{O}_{K,\mathbb{S}}^\times)$.

An immediate observation is now that both the tasks (I) and (II) can be solved$^{25}$ if one is able to compute a basis of the lattice $\mathcal{L}_G$. Indeed, such a basis allows to retrieve the rank and the determinant of $\mathcal{L}_G$. If $\text{rank}(\mathcal{L}_G) = \text{rank}(\mathrm{Log}_{\mathbb{S}}(\mathcal{O}_{K,\mathbb{S}}^\times)) = n_{\mathbb{C}} + n_{\mathbb{R}} + |\mathbb{S}| - 1$ and $\mathrm{Vol}(\mathcal{L}_G) = \mathrm{Vol}(\mathrm{Log}_{\mathbb{S}}(\mathcal{O}_{K,\mathbb{S}}^\times)) = R_K \cdot h_K \cdot \sqrt{n_{\mathbb{R}} + n_{\mathbb{C}}} \ (\text{see Equation (9)}),$ we deduce that $\mathcal{L}_G = \mathrm{Log}_{\mathbb{S}}(\mathcal{O}_{K,\mathbb{S}}^\times)$ (solving (I)) and that the basis of $\mathcal{L}_G$ is a basis for $\mathrm{Log}_{\mathbb{S}}(\mathcal{O}_{K,\mathbb{S}}^\times)$ (solving (II)).

So, the naive approach would be to create the matrix $\mathbf{G}$ whose rows consist of $\mathrm{Log}_{\mathbb{S}}(\eta)$ with $\eta \in G$; the rows of this matrix then generate $\mathrm{Log}_{\mathbb{S}}(\mathcal{L}_G)$. Apply LLL-reduction to $\mathbf{G}$ to obtain a basis of $\mathrm{Log}_{\mathbb{S}}(\mathcal{L}_G)$ and compute its rank and determinant. Unfortunately, this approach is not directly applicable.

**19.3. The challenge of approximate matrices.** The challenge lies in the fact that the infinite places of $\mathrm{Log}_{\mathbb{S}}(\eta)$ for $\eta \in \mathcal{O}_{K,\mathbb{S}}^\times$ can only be approximated. Indeed, these infinite places consists of logarithms of algebraic numbers, whose can only be computed with a certain precision.

This has as a consequence that the row-oriented matrix $\mathbf{G}$ consisting of the (exact) elements $\mathrm{Log}_{\mathbb{S}}(\eta)$ for $\eta \in G$ is computationally out of reach. Instead one is forced to work with $\tilde{\mathbf{G}}$, an approximation of $\mathbf{G}$. This rational matrix $\tilde{\mathbf{G}}$ consists of elements $\mathrm{Log}_{\mathbb{S}}(\eta) + \epsilon_\eta$ for $\eta \in G$ and $\|\epsilon_\eta\|_1 < \epsilon$. Given the set $G$, we can compute $\tilde{\mathbf{G}}$ in time $|G| \cdot \mathrm{poly}(\log(\epsilon))$. Of course, we have

$$ \|\mathbf{G} - \tilde{\mathbf{G}}\|_{\infty} \leq \epsilon. $$

where $\| \cdot \|_{\infty}$ is the induced $\infty$-norm on matrices$^{26}$.

**19.4. The Buchmann-Kessler-Pohst algorithm.** For sufficiently (but still feasibly) small $\epsilon \in (0, 1)$, an algorithm by Buchmann, Pohst and Kessler [17, 18] allows to compute an integer matrix $\mathbf{M}$ such that $\tilde{\mathbf{B}} = \mathbf{M}\tilde{\mathbf{G}}$ is an approximate basis that satisfies

$$ \|\tilde{\mathbf{B}} - \mathbf{B}\|_{\infty} \leq C \cdot \epsilon \quad \text{and} \quad \|\mathbf{M}\|_{\infty} \leq C $$

for some very large, but sufficiently bounded $C$ (depending on $\|\mathbf{G}\|_{\infty}$ and invariants of the lattice $\mathrm{Log}_{\mathbb{S}}(\mathcal{O}_{K,\mathbb{S}}^\times)$) and where $\mathbf{B} = \mathbf{M}\mathbf{G}$ is a well-conditioned basis for the lattice $\mathcal{L}_G$ generated by $\mathbf{G}$.

<footnote>$^{24}$As roots of unity vanish under the Logarithmic embedding into $H$ and are easily computed, we omit them often in discussions.</footnote>

<footnote>$^{25}$Note that we assume that the primes in $\mathbb{S}$ generate the ideal class group.</footnote>

<footnote>$^{26}$We have $\|\mathbf{A}\|_{\infty} = \max_j \|\mathbf{a}_j\|_1$ where $\mathbf{a}_j$ are the rows of $\mathbf{A}$.</footnote>
Though this algorithm is analyzed well [17], its analysis can only be applied whenever the rank of the lattice $\mathcal{L}_G$ is known. A slight variation of this analysis, in which the rank of $\mathcal{L}_G$ is not required to be known beforehand, is described in Section 23. Note that this analysis proves that the Buchmann-Kessler-Pohst algorithm actually computes the rank of $\mathcal{L}_G$.

**19.5. Computing the determinant.** So, the Buchmann-Kessler-Pohst algorithm allows to compute a $\tilde{\mathbf{B}} = \mathbf{B} + \epsilon' X$ close to a well-conditioned basis $\mathbf{B}$; say, $\|X\|_{\infty} \le 1$ and $\epsilon' < 1$ is small.

Then, by a bound of Ipsen and Rehman [42, Corollary 2.14], for sufficiently (but feasibly) small $\epsilon' < 1$, one has

$$ \det(\tilde{\mathbf{B}}^{\top}\tilde{\mathbf{B}}) \in [\frac{7}{8}, \frac{9}{8}] \cdot \det(\mathbf{B}^{\top}\mathbf{B}). $$

The determinant $\mathrm{Vol}(\mathrm{Log}_{\mathbb{S}}(\mathcal{O}_{K,\mathbb{S}}^{\times}))$ of the full log-$\mathbb{S}$-unit lattice can be (multiplicatively) approximated by means of Euler products (e.g., [5] or Proposition 2.9). In other words, we can efficiently compute a $D \in \mathbb{R}_{>0}$ such that

$$ D \in [\frac{3}{4}, \frac{5}{4}] \cdot \mathrm{Vol}(\mathrm{Log}_{\mathbb{S}}(\mathcal{O}_{K,\mathbb{S}}^{\times})). $$

The index $[\mathrm{Log}_{\mathbb{S}}(\mathcal{O}_{K,\mathbb{S}}^{\times}) : \mathcal{L}_G]$ can then be approximated by computing $\sqrt{\det(\tilde{\mathbf{B}}^{\top}\tilde{\mathbf{B}})}/D$, and satisfies$^{27}$

$$ \sqrt{\det(\tilde{\mathbf{B}}^{\top}\tilde{\mathbf{B}})}/D \in (0.74, 1.42) \cdot [\mathrm{Log}_{\mathbb{S}}(\mathcal{O}_{K,\mathbb{S}}^{\times}) : \mathcal{L}_G]. $$

One deduces that if $[\mathrm{Log}_{\mathbb{S}}(\mathcal{O}_{K,\mathbb{S}}^{\times}) : \mathcal{L}_G] \ge 2$, then $\sqrt{\det(\tilde{\mathbf{B}}^{\top}\tilde{\mathbf{B}})}/D > 1.48$. Contrarily, if $[\mathrm{Log}_{\mathbb{S}}(\mathcal{O}_{K,\mathbb{S}}^{\times}) : \mathcal{L}_G] = 1$, then $\sqrt{\det(\tilde{\mathbf{B}}^{\top}\tilde{\mathbf{B}})}/D < 1.42$, which allows us to distinguish the two cases. Additionally, in the second case $\tilde{\mathbf{B}}$ is an approximate basis of $\mathrm{Log}_{\mathbb{S}}(\mathcal{O}_{K,\mathbb{S}}^{\times})$.

**19.6. Assembling a fundamental set of $\mathbb{S}$-units.** Recall that $G = \{\eta_1, \dots, \eta_k\} \subseteq \mathcal{O}_{K,\mathbb{S}}^{\times}$ is a set of $\mathbb{S}$-units and $\mathbf{G} = (\mathrm{Log}_{\mathbb{S}}(\eta_j))_{j \in \{1, \dots, k\}}$ its associated matrix of logarithmic images. Assume that (by means of the algorithm in the text above) one has deduced that $G$ indeed generates $\mathcal{O}_{K,\mathbb{S}}^{\times}$, i.e., $\langle G \rangle = \mathcal{O}_{K,\mathbb{S}}^{\times}$.

By the algorithm of Buchmann-Kessler-Pohst in Section 19.4, we can find an $\mathbf{M} = (m_{ij})_{ij}$ for which $\mathbf{B} = \mathbf{M}\mathbf{G}$ is a basis of $\mathrm{Log}_{\mathbb{S}}(\mathcal{O}_{K,\mathbb{S}}^{\times})$. In other words, for $j = 1, \dots, \mathrm{rank}(\mathcal{O}_{K,\mathbb{S}}^{\times})$,

$$ \mathbf{b}_j = \sum_{i=1}^{k} m_{ji} \mathrm{Log}_{\mathbb{S}}(\eta_i) = \mathrm{Log}_{\mathbb{S}}(\beta_j) \quad \text{form a basis of } \mathrm{Log}_{\mathbb{S}}(\mathcal{O}_{K,\mathbb{S}}^{\times}). $$

As a consequence, by taking exponentials, for $j = 1, \dots, \mathrm{rank}(\mathcal{O}_{K,\mathbb{S}}^{\times})$,

$$ \beta_j = \prod_{i=1}^{k} \eta_i^{m_{ji}} \quad \text{form a system of fundamental units of } \mathcal{O}_{K,\mathbb{S}}^{\times}. \qquad (132) $$

<footnote>$^{27}$We have $\sqrt{\det(\tilde{\mathbf{B}}^{\top}\tilde{\mathbf{B}})} \cdot c_1 = \sqrt{\det(\tilde{\mathbf{B}}^{\top}\tilde{\mathbf{B}})}$ for $c_1 \in [\sqrt{\frac{7}{8}}, \sqrt{\frac{9}{8}}]$ and $D = c_2 \cdot \mathrm{Vol}(\mathrm{Log}_{\mathbb{S}}(\mathcal{O}_{K,\mathbb{S}}^{\times}))$ with $c_2 \in [\frac{3}{4}, \frac{5}{4}]$. Therefore, $\sqrt{\det(\tilde{\mathbf{B}}^{\top}\tilde{\mathbf{B}})}/D = (c_1/c_2) \cdot \sqrt{\det(\tilde{\mathbf{B}}^{\top}\tilde{\mathbf{B}})}/\mathrm{Vol}(\mathrm{Log}_{\mathbb{S}}(\mathcal{O}_{K,\mathbb{S}}^{\times}))$, with $(c_1/c_2) \in [\sqrt{\frac{7}{8}} \cdot \frac{4}{5}, \sqrt{\frac{9}{8}} \cdot \frac{4}{3}] \subseteq (0.74, 1.42)$.</footnote>
Note that the expression in Equation (132) is in exact arithmetic (i.e., no precision issues). Namely, the elements $\eta_i \in G$ are written in the basis of the number ring and the exponents $m_{ji}$ are integers from the integer matrix $M$.

**19.7. A fundamental set of $\mathbb{S}$-units by means of compact representation.**
Note that actually representing $\beta_j$ in terms of basis elements of $O_K$ or $K$ is generally computationally out of reach. Indeed, since the coefficients $m_{ij}$ are rather large, the computation of $\beta_j$ (i.e., expanding the product in Equation (132)) suffers from coefficient explosion.

This is the reason why the computation of a system of fundamental ($\mathbb{S}$)-units is generally given in 'compact representation' (e.g., [10], [25, §5.8.3]). That just means that, instead of giving the $\beta_j$ in Equation (132) by expanding its product and writing $\beta_j$ in the basis of the number ring, one represents $\beta_j$ by the formal product consisting of $m_{ji}$-th powers of $\eta_i$.

In other words, a compact representation of $(\beta_j)_{j=1,...,rank(O_{K,\mathbb{S}}^\times)}$ is just given by the pair $(\mathbf{M}, G)$ with $\mathbf{M} = (m_{ij})_{ij} \in \mathbb{Z}^{k \times (rank(O_{K,\mathbb{S}}^\times))}$ and $G = \{\eta_1, ..., \eta_k\}$, by which we represent, for $j \in \{1, ..., rank(O_{K,\mathbb{S}}^\times)\}$,

$$ \beta_j = \prod_{i=1}^{k} \eta_i^{m_{ij}}. $$

The final output of the log-$\mathbb{S}$-unit algorithm of this paper is thus the pair $(\mathbf{M}, G)$.

**19.8. Final post-processing theorem.** A rigorous treatment of the post-processing phase can be found in Sections 23 to 25, as well as the proof of the following theorem. The techniques used in that treatment generally involve well-known lattice reductions and computations, though for their rigorousness there is a heavy emphasis on numerical stability. For now, to stay close to the current subject manner, those numerical stability computations are thus deferred to Part 3.

**Theorem 19.1.** Let $K$ be a number field with degree $n$, and let $G = \{\eta_1, ..., \eta_k\} \subseteq O_{K,\mathbb{S}}^\times$ a finite set of $\mathbb{S}$-units. There exists an algorithm that takes as input the set $G^{28}$ and computes a system of fundamental $\mathbb{S}$-units for the subgroup $\langle G \rangle \subseteq O_{K,\mathbb{S}}^\times$ generated by $G$ in compact representation, i.e., a pair $(\mathbf{N}, G)$ with $\mathbf{N} \in \mathbb{Z}^{r \times k}$ such that $v_j = \prod_{i=1}^{k} \eta_i^{N_{ji}}$ for $j \in \{1, ..., r\}$ form a system of fundamental $\mathbb{S}$-units for $\langle G \rangle$.

Additionally, this algorithm decides whether $\langle G \rangle = O_{K,\mathbb{S}}^\times$ or not, and runs in time polynomial in $k$, $\log|\Delta_K|$, $|\mathbb{S}|$, $\log(\max_j \|\mathrm{Log}_{\mathbb{S}}(\eta_j)\|)$ and $\max_j(\mathrm{size}(\eta_j))$.

**20. GENERATING THE EXCEPTIONAL $\mathbb{S}$-UNITS**

**20.1. Introduction.** In Theorem 18.14, the main result of Section 18, the set of primes $\mathbb{S}$ is assumed to contain no primes dividing the modulus $\mathfrak{m}_0$. This modulus $\mathfrak{m}_0$ is defined in lines 2 - 8 of Algorithm 3, and only depends on the Dedekind residue $\rho_K$, the degree $n = [K : \mathbb{Q}]$ and the absolute discriminant $|\Delta_K|$.

In our end result, we would like to be able to compute $\mathbb{S}'$-units for any set of primes $\mathbb{S}'$, without any restrictions. Indeed, we do want to allow $\mathbb{S}'$ to contain primes dividing $\mathfrak{m}_0$. Hence, in this section we aim, for any $\mathfrak{p} \mid \mathfrak{m}_0$, for computing

<footnote n="28">²⁸The elements $\eta_i \in K$ are represented as vectors of rational coordinates in a fixed $O_K$-basis, as explained in Section 2.6.</footnote>
an $(\mathbb{S} \cup \{\mathfrak{p}\})$-unit $\eta_{\mathfrak{p}} \in \mathcal{O}_{K, \mathbb{S}, \cup \{\mathfrak{p}\}}^{\times}$ that additionally satisfies $\mathrm{ord}_{\mathfrak{p}}(\eta_{\mathfrak{p}}) = 1$. Such an $(\mathbb{S} \cup \{\mathfrak{p}\})$-unit we will then call an *exceptional S-unit*.

By adding these exceptional S-units $\eta_{\mathfrak{p}}$ (for $\mathfrak{p} \mid \mathfrak{m}_0$) to a fundamental system of S-units, one gets a fundamental system of $(\mathbb{S} \cup \{\mathfrak{p} \mid \mathfrak{p} \text{ divides } \mathfrak{m}_0\})$-units. Hence computing these $\eta_{\mathfrak{p}}$ allows for computing a S' unit group without any restrictions on the prime ideals. Note that, if $\mathfrak{m}_0 = (1)$ is trivial, no exceptional S-units exist, and the algorithm of this section can be omitted. Hence, throughout this section we will assume that $\mathfrak{m}_0 \neq (1)$.

**20.2. Algorithm for generating exceptional S-units.** In Algorithm 5, we describe how to compute an exceptional S-unit in the case of $\mathfrak{m}_0 \neq (1)$. The following lemma shows that the running time of this algorithm is the same as the running time of sampling a single S-unit as in Theorem 17.7.

<caption>**Algorithm 5 Computing an exceptional S-unit**</caption>

**Require:**
(i) An LLL-reduced basis of $\mathcal{O}_K$,
(ii) a prime ideal $\mathfrak{q} \mid \mathfrak{m}_0$, (we assume $\mathfrak{m}_0 \neq (1)$)
(iii) a set of prime ideals $\mathbb{S}$ of $K$, that does not contain the primes dividing $\mathfrak{m}_0$.
**Ensure:** $\alpha \in \mathfrak{q}$ and $(v_{\mathfrak{p}})_{\mathfrak{p} \in \mathbb{S}} \in \mathbb{Z}_{\ge 0}^{|\mathbb{S}|}$ such that $\alpha \mathcal{O}_K = \mathfrak{q} \cdot \prod_{\mathfrak{p} \in \mathbb{S}} \mathfrak{p}^{v_{\mathfrak{p}}}$
1: define $\mathfrak{b}, \omega$ as in Algorithm 3.
2: **repeat**
3: &nbsp;&nbsp;&nbsp;&nbsp;$\alpha \leftarrow \text{Sample}(\mathfrak{q}, y = 1, \mathfrak{m}_0 \cdot \mathfrak{q}^{-1}, \mathfrak{b}, \omega)$ (see Theorem 13.2)
4: &nbsp;&nbsp;&nbsp;&nbsp;**until** $\alpha \mathcal{O}_K \cdot \mathfrak{q}^{-1}$ is S-smooth
5: &nbsp;&nbsp;&nbsp;&nbsp;compute $(v_{\mathfrak{p}})_{\mathfrak{p} \in \mathbb{S}} \in \mathbb{Z}_{\ge 0}^{\mathbb{S}}$ such that $\alpha \mathcal{O}_K \cdot \mathfrak{q}^{-1} = \prod_{\mathfrak{p} \in \mathbb{S}} \mathfrak{p}^{v_{\mathfrak{p}}}$
6: &nbsp;&nbsp;&nbsp;&nbsp;**return** $(\alpha, (v_{\mathfrak{p}})_{\mathfrak{p} \in \mathbb{S}})$.

**Proposition 20.1.** *There exists some $B_{\max} = \text{poly}(L_{|\Delta_K|}(1/2), L_{n^n}(2/3), \rho_K^{\text{cut}})$, where*

$$ \rho_K^{\text{cut}} = \min \left( \rho_K, \max \left( e^{\log \frac{2}{3} |\Delta_K| \cdot \log \frac{2}{3} (\log |\Delta_K|)}, e^{n \frac{2}{3} \log \frac{4}{3} (n)} \right) \right), $$

such that the following holds. Assume that $\mathbb{S}$ contains all prime ideals coprime to $\mathfrak{m}_0$ of norm $\le B_{\max}$ (where $\mathfrak{m}_0$ is defined as in lines 2 - 8 of Algorithm 3).

Then, on input $\mathfrak{q} \mid \mathfrak{m}_0$ and the set $\mathbb{S}$, Algorithm 5 outputs $(\alpha, (v_{\mathfrak{p}})_{\mathfrak{p} \in \mathbb{S}}) \in \mathfrak{q} \times \mathbb{Z}_{\ge 0}^{|\mathbb{S}|}$ such that

$$ \alpha \mathcal{O}_K = \mathfrak{q} \prod_{\mathfrak{p} \in \mathbb{S}} \mathfrak{p}^{v_{\mathfrak{p}}}. $$

Furthermore, Algorithm 3 runs in expected time

$$ \text{poly}(L_{|\Delta_K|}(\frac{1}{2}), L_{n^n}(\frac{2}{3}), \text{size}(\mathbb{S}), \rho_K^{\text{cut}}, \log |\Delta_K|). $$

*Proof.* The proof can be copied from that of Theorem 17.7. The sole differences are the instantiation $\mathfrak{m}_0 \cdot \mathfrak{q}^{-1}$ instead of $\mathfrak{m}_0$, and the instantiations $\mathfrak{a} = \mathfrak{q}$ and $y = 1$. The latter instantiations do not impact the proof, and since $\text{size}(\mathfrak{q}) \le \text{poly}(\log |\Delta_K|) \cdot x \le \text{poly}(\log |\Delta_K|)$ by the definition of $x$ in line 3 of Algorithm 3, the size of $\mathfrak{q}$ can be omitted in the running time.
Note that in Theorem 17.7, the input ideal $\mathfrak{a}$ is required to be coprime to $\mathfrak{m}_0$. In the context of the current theorem, $\mathfrak{q}$ is coprime to $\mathfrak{m}_0 \cdot \mathfrak{q}^{-1}$ by construction, and hence the same reasoning as in Theorem 17.7 applies.

The instantiation $\mathfrak{m}_0 \cdot \mathfrak{q}^{-1}$ instead of $\mathfrak{m}_0$ does impact the value of $N(\mathfrak{m}_0)/\phi(\mathfrak{m}_0)$, but only by a factor $\frac{N(\mathfrak{q})}{N(\mathfrak{q})-1} \in [1, 2]$, which only impacts the success probability by a factor in $[1, 2]$ and hence does not impact the final running time. Therefore, the running time of Proposition 20.1 equals that of Theorem 17.7, with size($\mathfrak{a}$) and size($\mathfrak{y}$) deleted. $\square$

## 21. FULL ALGORITHM, FINAL THEOREM AND DISCUSSION

**Algorithm 6 Computing a fundamental system of $\mathbb{S}$-units**

**Require:** A number field $K$, an LLL-reduced basis of $O_K$, and a set $\mathbb{S}$ of prime ideals of $K$.

**Ensure:** A pair $(\mathbf{M}, G)$ with $\mathbf{M} = (m_{ij})_{ij} \in \mathbb{Z}^{k \times \mathrm{rank}(O_{K,\mathbb{S}}^{\times})}$ and $G = \{\eta_1, \dots, \eta_k\} \subseteq O_{K,\mathbb{S}}^{\times}$ such that $\{\beta_1, \dots, \beta_{\mathrm{rank}(O_{K,\mathbb{S}}^{\times})}\}$ is a fundamental set of $\mathbb{S}$-units, where

$$ \beta_j = \prod_{i=1}^{k} \eta_i^{m_{ji}}. $$

1. Put $G = \emptyset$

2. Define $\mathfrak{m}_0$ as in lines 2 - 8 of Algorithm 3.

3. Define $\mathbb{T} = \mathbb{S} \setminus \{\mathfrak{p} | \mathfrak{p} | \mathfrak{m}_0\}$.

4. **repeat**

5. Apply Algorithm 4 with input $\mathbb{T}$, yielding $(\alpha, (a_{\mathfrak{p}})_{\mathfrak{p} \in \mathbb{T}})$.

6. Add the output $\alpha$ (and its factorization) to $G'$.

7. **until** the Buchmann-Kessler-Pohst algorithm as in Section 19 finds that $G'$ generates $O_{K,\mathbb{T}}^{\times}$.

8. Let $(\mathbf{M}', G')$ be the output of the Buchmann-Kessler-Pohst algorithm, as in Theorem 19.1. Write $G' = \{\eta_1, \dots, \eta_{k'}\}$ and $\mathbf{M}' = (m'_{ij})_{ij} \in \mathbb{Z}^{k' \times \mathrm{rank}(O_{K,\mathbb{S}}^{\times})}$.

9. Compute for any $\mathfrak{q} | \mathfrak{m}_0$, an exceptional $\mathbb{T}$-unit $\eta_{\mathfrak{q}} \in O_{K,\mathbb{T} \cup \{\mathfrak{q}\}}^{\times}$, using Algorithm 5.

10. Order $\{\eta_{\mathfrak{q}} | \mathfrak{q} | \mathfrak{m}_0\} = \{\eta_{k'+1}, \dots, \eta_k\}$ and extend the set $G'$ to $G = \{\eta_1, \dots, \eta_{k'}, \eta_{k'+1}, \dots, \eta_k\}$. Put $m_{ji} = m'_{ji}$ for $i \in \{1, \dots, k'\}$ and $j \in \{1, \dots, \mathrm{rank}(O_{K,\mathbb{T}}^{\times})\}$, put $m_{ji} = \delta_{ji}$ (Kronecker delta) for $i \in \{k' + 1, \dots, k\}$. Set $\mathbf{M} = (m_{ij})_{ij} \in \mathbb{Z}^{k \times \mathrm{rank}(O_{K,\mathbb{S}}^{\times})}$

11. **return** $(\mathbf{M}, G)$.

**Proposition 21.1 (ERH).** There is a randomized algorithm $\mathcal{A}$ (Algorithm 6) for which the following holds. Let $K$ be a number field and let

$$ \rho_K^{\mathrm{cut}} = \min(\rho_K, \max(e^{\log \frac{3}{3} |\Delta_K| \cdot \log \frac{3}{3} (\log |\Delta_K|)}, e^{n \frac{3}{3} \cdot \log \frac{4}{3} (n)}). $$

Note that $\rho_K^{\mathrm{cut}} \le L_{|\Delta_K|}(2/3 + o(1))$.

Then there exists a bound

$$ B = \mathrm{poly}(L_{|\Delta_K|}(1/2), L_n^n(2/3), \rho_K^{\mathrm{cut}}). $$
such that if the algorithm $\mathcal{A}$ is given a set of primes $\mathcal{S}$ of $K$ containing all primes with norm bounded by $B$ and generating the ray class group $Cl_K^{\mathfrak{m}_0}$ of $K$, the algorithm $\mathcal{A}$ computes a fundamental system of $\mathcal{S}$-units of $O_{K,\mathcal{S}}^{\times}$ in compact representation, in expected time

$$ \mathrm{poly}(L_{|\Delta_K|}(1/2), L_{n^n}(2/3), \rho_K^{\mathrm{cut}}, \mathrm{size}(\mathcal{S})). $$

*Proof.* The correctness of the algorithm follows from the following two arguments. By the ‘until’ criterion in step 7, that requires $G'$ to generate the $\mathcal{T}$-unit group, where $\mathcal{T} = \mathcal{S} \setminus \{\mathfrak{p} \mid \mathfrak{p} \mid \mathfrak{m}_0\}$. Since the exceptional $\mathcal{T}$-units $\eta_q$ satisfy $\mathrm{ord}_q(\eta_q) = 1$ and $\eta_q \in O_{K,\mathcal{S}}^{\times}$, adding these indeed result in a fundamental set of $\mathcal{S}$-units.

The running time of the algorithm is dominated by the repeat loop and the computation of the exceptional units. We will use that $\mathrm{size}(\mathcal{T}) \le \mathrm{size}(\mathcal{S})$.

In the repeat loop, Algorithm 4 and the ‘post-processing’ Buchmann-Kessler-Pohst algorithm take expected time $\mathrm{poly}(L_{|\Delta_K|}(1/2), L_{n^n}(2/3), \rho_K^{\mathrm{cut}}, \mathrm{size}(\mathcal{S}))$ (see Lemma 18.9, Theorem 17.7, Theorem 19.1, and the bound

$$ \zeta \le 3 \max(\sqrt{\log(n_{\mathcal{R}} + n_{\mathcal{C}} + |\mathcal{S}|)}, \tilde{\eta}) \le \mathrm{poly}(\log |\Delta_K|, \mathrm{size}(\mathcal{S})) $$

from Proposition 16.10). The number of repetitions is expected to be within $\tilde{O}(|\mathcal{S}| \log \log |\Delta_K|) = \mathrm{poly}(\mathrm{size}(\mathcal{S}))$ (see Theorem 18.14).

The run time of computing all exceptional units is, by Proposition 20.1, at most $\mathrm{poly}(L_{|\Delta_K|}(\frac{1}{2}), L_{n^n}(\frac{2}{3}), \mathrm{size}(\mathcal{S}), \rho_K^{\mathrm{cut}}, \log |\Delta_K|)$, where we use that the number of prime ideals dividing $\mathfrak{m}_0$ can be at most $O(\log(\mathcal{N}(\mathfrak{m}_0))) = \mathrm{poly}(\log |\Delta_K|)$ (see Equation (113)).

Therefore, the expected running time of the overall computation is $\mathrm{poly}(L_{|\Delta_K|}(1/2), L_{n^n}(2/3), \rho_K^{\mathrm{cut}}, \mathrm{size}(\mathcal{S}))$ as well. $\square$

The following theorem is the same as Proposition 21.1 except that the set of primes $\mathcal{S}$ can now be arbitrary.

**Theorem 21.2 (ERH).** There is a probabilistic algorithm which, on input a number field $K$ and a set of primes $\mathcal{S}$ of $K$, computes a fundamental system of $\mathcal{S}$-units of $O_{K,\mathcal{S}}^{\times}$ in compact representation, in expected time

$$ \mathrm{poly}(L_{|\Delta_K|}(1/2), L_{n^n}(2/3), \rho_K^{\mathrm{cut}}, \mathrm{size}(\mathcal{S})). $$

where $\rho_K^{\mathrm{cut}} = \min(\rho_K, \max(e^{\log \frac{2}{3} |\Delta_K| \cdot \log \frac{2}{3} (\log |\Delta_K|)}, e^{\frac{2}{3} \cdot \log \frac{4}{3} (n)}))$. Note that $\rho_K^{\mathrm{cut}} \le L_{|\Delta_K|}(2/3 + o(1))$.

*Proof.* Extend $\mathcal{S}$ to a set $\mathcal{S}' \supset \mathcal{S}$ of primes, containing all primes with norm below $B = \mathrm{poly}(\max(L_{|\Delta_K|}(1/2, 1), L_{n^n}(2/3, 1), \rho_K^{\mathrm{cut}}))$ and generating the ray class group $Cl_K^{\mathfrak{m}_0}$ of $K$, as in Proposition 21.1. Note that, since $\log(\mathcal{N}(\mathfrak{m}_0)) = O(\log^2 |\Delta_K|)$ (see Equation (113)) and by Bach’s bound $O(\log(|\Delta_K|^2 N(\mathfrak{m}_0)))$ for ray class groups [4] this is asymptotically clearly satisfied.

Then, apply Algorithm 6 to get the pair $(\mathcal{M}, G)$ representing a fundamental system of $\mathcal{S}'$-units. This costs expected time $\mathrm{poly}(L_{|\Delta_K|}(1/2), L_{n^n}(2/3), \rho_K^{\mathrm{cut}}, \mathrm{size}(\mathcal{S}))$, since $\mathrm{size}(\mathcal{S}') = \mathrm{poly}(B, \mathrm{size}(\mathcal{S}))$.

As a preparation for the Hermite normal form algorithm, we put the infinite primes and the primes of $\mathcal{S}$ to the very left in the representation of $\mathrm{Log}_{\mathcal{S}'}(\gamma)$, i.e.,

$$ \mathrm{Log}_{\mathcal{S}'}(\gamma) := \left( \underbrace{\mathrm{Log}(\gamma)}_{\text{infinite places}}, \underbrace{(-\mathrm{ord}_{\mathfrak{p}}(\gamma))_{\mathfrak{p} \in \mathcal{S}'}, (-\mathrm{ord}_{\mathfrak{p}}(\gamma))_{\mathfrak{p} \in \mathcal{S}' \setminus \mathcal{S}}}_{\text{places in } \mathcal{S}} \right) $$
Put $\tilde{\mathbf{G}}$ for the row-matrix consisting of the approximations of $\mathrm{Log}_{\mathbb{S}'}(\gamma_j)$ for $j = 1, \dots, |G|$, where $G = \{\gamma_1, \dots, \gamma_{|G|}\}$. We then can write $\tilde{\mathbf{B}} = \mathbf{M}\tilde{\mathbf{G}}$ for an approximate basis for the log-$\mathbb{S}'$-unit lattice (with the infinite places and the places of $\mathbb{S}$ at the very left).

We now apply a Hermite normal form algorithm to $\tilde{\mathbf{B}}$, leading to $\tilde{\mathbf{H}} = \mathbf{U}\tilde{\mathbf{B}}$ that is in a lower-triangular shape. Hence, the first $|\mathbb{S}| + n_{\mathbb{R}} + n_{\mathbb{C}} - 1$ rows must then represent the Log-$\mathbb{S}$-units, as it is the dimension of $\mathbb{S}$ plus the dimension of the logarithmic unit lattice $\mathrm{Log}(\mathcal{O}_K^\times)$. Hence, the $\mathbb{S}$-units can be given in compact representation $(\mathbf{N}, G)$ with $\mathbf{N}$ being the first $|\mathbb{S}| + n_{\mathbb{R}} + n_{\mathbb{C}} - 1$ rows of $\mathbf{U}\mathbf{M}$. I.e., a fundamental set of $\mathbb{S}$-units is

$$ \eta_k = \prod_{j=1}^{|G|} \gamma_j^{\mathbf{N}_{kj}} \quad \text{for } k \in \{1, \dots, |\mathbb{S}| + n_{\mathbb{R}} + n_{\mathbb{C}} - 1\}. $$

Since the running time of the Hermite normal form is polynomial in the dimensions of the input matrix and the maximum size($c_{ij}$) of the coefficients$^{29}$ [71], we simply deduce that computing this Hermite normal form also takes time $\mathrm{poly}(L_{|\Delta_K|}(1/2), L_{n^n}(2/3), \rho_K^{\mathrm{cut}}, \mathrm{size}(\mathbb{S}))$. This concludes the proof. $\square$

**21.1. On the complexity of the $\mathbb{S}$-unit computation algorithm.** Now that we have proved the main result of this part of the article, we turn to its meta-analysis, comparing it with former heuristic claims. Both the provable and the heuristic running time of the $\mathbb{S}$-unit computation algorithm depend heavily and quite intricately on both the parameters $\log(|\Delta_K|)$ and the degree $n$ of the number field $K$ at hand (see Figure 2). We will explain here the origin of the various changes in the running times, starting with that of the heuristic algorithm in Section 21.3 and ending with the running time of the provable algorithm of this paper in Section 21.4.

In this explanation of the running times, we will only discuss the running time in terms of their ‘dominant part’, which are of the shape $\exp(\tilde{O}(\log^\delta |\Delta_K|))$ or $\exp(\tilde{O}(n^\delta))$ for some $\delta \in [0, 1]$. Also, in Figure 2 only this ‘dominant part’ is shown. It is useful to think of, for example, $\exp(\tilde{O}(\log^\delta |\Delta_K|))$ of being of ‘approximately the same magnitude’ as $L_{|\Delta_K|}(\delta, 1)$, while keeping in mind that $L_{|\Delta_K|}(\delta, 1)$ is a much more precise way of estimating complexities. For the more intricate analysis, we refer to the proof of Theorem 17.7.

**21.2. A general formula for the complexity of the $\mathbb{S}$-unit computation algorithm.** At the very core, most $\mathbb{S}$-unit computation algorithms consist of the following two steps (in which $\mathbb{S} = \{\mathfrak{p} \text{ prime ideal } | \mathcal{N}(\mathfrak{p}) \le B\}$):

(I) Assemble $R$ ‘relations’ in the shape of $B$-smooth elements of norm $\le M$. Those are just elements of $\mathcal{O}_{K, \mathbb{S}}^\times$.

(II) Post-process these $R$ ‘relations’ to get a system of fundamental $\mathbb{S}$-units using lattice reduction techniques. Such a system of fundamental $\mathbb{S}$-units can be seen as a (multiplicative) ‘basis’ of $\mathcal{O}_{K, \mathbb{S}}^\times$.

<footnote>$^{29}$We might have to scale up the coefficients of the infinite places to integers (column-wise), but that does not impact significantly the size of the coefficients.</footnote>
<figure><img src="image_7.png" /><figcaption>FIGURE 2. A depiction of the (dominant part of the) provable running time compared to the (dominant part of the) heuristic running time for number fields K, depending on $log(\rho_K)$ and the value of $log(|\Delta_K|)$ compared to the degree n.</figcaption></figure>

The blue line corresponds to the heuristic running time claimed in [10].

The provable running time of the $\mathbb{S}$-unit algorithm of the present work varies between the blue and red lines, depending on $log(\rho_K)$. The running time can be found in this graph by first searching the point $log|\Delta_K|$ (in terms of powers of the degree $n$) on the x-axis, and then read off, depending on the size of $log(\rho_K)$, where between the blue and red line the (logarithm of the) run time must be. For number fields with $log(\rho_K) \le n^{2/3}$, the running time is dictated by the blue line, and when $log(\rho_K) \ge n$, the complexity is dictated by the red line.

21.2.1. Part (I). The B-smooth elements are sampled in a probabilistic way, by 'picking an element of norm $\le M$ at random and hoping it will be smooth'. One such attempt costs 1 sampling of a norm $\le M$ element (denoted $S_M$) and 1 check for being B-smooth (denoted $C_B$). Let us denote $p_{M,B}$ for the probability of success, namely that such sampling indeed yields a B-smooth element. Then, the running time for sampling a single B-smooth element (a 'relation') with constant success probability takes time $(S_M + C_B) \cdot p_{M,B}^{-1}$. To obtain $R$ such relations, one obtains for part (I) an expected complexity of

$$ \text{poly}(R(S_M + C_B) \cdot p_{M,B}^{-1}). $$

21.2.2. Part (II). The post-processing step consists of lattice reduction on a sort-of 'valuation matrix' of the gathered relations (elements in $O_{K,\mathbb{S}}^*$). Namely, each of
these $R$ elements $\eta \in \mathcal{O}_{K,\mathcal{S}}^{\times}$ are decomposed as

$$[\mathrm{Log}(\eta), (v_p(\eta))_{p \in \mathcal{S}}] \in \mathbb{R}^{n_{\mathbb{R}}+n_{\mathcal{C}}-1} \times \mathbb{Z}^{\mathcal{S}},$$

where each vector entry is bounded by$^{30}$ poly($\log(M)$), where $M$ is the maximum norm of the elements. Reducing an $R \times (\mathcal{S} + n_{\mathbb{R}} + n_{\mathcal{C}} - 1)$-matrix like this costs, roughly said, time at most poly($R \cdot B \cdot \log(M)$) (where we use $B \approx |\mathcal{S}|$). Here we assume that the decomposition of the elements into prime ideals has already be done in the ‘check for being smooth’ step in Part (I).

21.2.3. *The general formula for the complexity.* Adding the complexities, using that $R \ge B$ and assuming that $\log(M)$ is negligible compared to $B$, we obtain a general formula for the complexity, by effectively ignoring the costs of Part (II):

$$\mathrm{poly}(R \cdot (S_M + C_B) \cdot p_{M,B}^{-1}), \qquad (133)$$

where $S_M$ is the cost of sampling a random element in $\mathcal{O}_K$ of norm $\le M$, where $C_B$ is the costs of checking whether an element is $B$-smooth, where $p_{M,B}$ is the probability that a randomly sampled norm $\le M$ element in $\mathcal{O}_K$ is $B$-smooth, and where $R$ is the (average) number of relations (elements in $\mathcal{O}_{K,\mathcal{S}}^{\times}$) needed to generate $\mathcal{O}_{K,\mathcal{S}}^{\times}$.

21.3. **Heuristic running time of Biasse & Fieker [10].** For the heuristic running time [10], there are essentially two ‘regimes’ of number fields. Namely, ‘regime A’, the fields for which $n \le \log|\Delta_K| \le n^{4/3}$ and ‘regime B’ the fields for which $n^{4/3} \le \log|\Delta_K| < \infty$ (see the blue ‘Heuristic’ line in Figure 2). We will explain, with the general formula of Equation (133) and the heuristic assumptions of [10], why these regimes pop up.

Heuristic 1 (and 2) of [10] roughly state that they assume that the probability $p_{M,B}$ of a random element of norm $\le M$ being $B$-smooth equals

$$p_{M,B} = \exp\left(-\tilde{O}\left(\frac{\log(M)}{\log(B)}\right)\right) \quad \text{(heuristic)}$$

Additionally, Heuristic 3 of [10], roughly states that the number of elements (‘relations’) $R$ required to generate the full $\mathcal{S}$-unit group $\mathcal{O}_{K,\mathcal{S}}^{\times}$, is only slightly larger than $B$, i.e.,

$$R = \tilde{O}(B) \quad \text{(heuristic)}$$

Using trivial trial division for $B$-smooth checking yields $C_B = O(B)$. One of the main improvements of [10] is the use of stronger lattice reduction techniques (BKZ-b) to sample small norm elements. More precisely, in their paper, they roughly take $M = e^{n^2/b} \cdot |\Delta_K|$ and $S_M = \tilde{O}(b^b)$; where $b$ is the block size parameter of BKZ.

Filling in these parameters into the formula of Equation (133) and simplifying adequately, we obtain

$$\mathrm{poly}(b^b \cdot B \cdot p_{M,B}) = \exp\left(\tilde{O}\left(b + \log(B) + \frac{n^2/b + \log|\Delta_K|}{\log(B)}\right)\right)$$

<footnote>$^{30}$This is not the case per se, a fixed norm element can have arbitrarily large entries of the logarithmic embedding. Though, here, in this quick explanation, we assume that this is the case.</footnote>
Optimizing the parameters B and b, we quickly arrive at a complexity<fnref n="31" /> of $\exp(\tilde{O}(\log^{1/2} |\Delta_K|))$ whenever $n^{4/3} \le \log |\Delta_K|$ and $\exp(\tilde{O}(n^{2/3}))$ whenever $n^{4/3} \ge \log |\Delta_K|$. This explains the differences in complexity in the two regimes.

**Remark 21.3.** Intuitively, these two regimes can be explained by the hardness of sampling small-norm elements in $O_K$. Recall that for a sample of an element of maximum norm $M = e^{n^{2/\mathbf{b}}} |\Delta_K|$ one has to pay $\mathbf{b}^\mathbf{b}$.

For $|\Delta_K|$ large compared to the degree (regime B), the extra factor $e^{n^{2/\mathbf{b}}}$ in $M$ does not impact the asymptotic size of $M$. Contrarily, if the discriminant is small (regime A), the factor $e^{n^{2/\mathbf{b}}}$ in $M$ becomes dominant. Therefore, the block size b needs to be increased, resulting in a larger complexity.

To summarize, for large discriminants, it is the probability of sampling smooth elements that is the bottleneck of the algorithm, whereas for small discriminants it is the run time of BKZ.

**21.4. Provable running time of this paper.** We revisit the running time of the $\mathbb{S}$-unit group computing algorithm, but now without heuristics and only assuming the Generalized Riemann hypothesis. The provable running time depends again on the parameters $n$ and $\log |\Delta_K|$ and fall into three regimes. Regime A are the number fields for which $n \le \log |\Delta_K| \le n^{3/2}$, regime B the number fields satisfying $n^{3/2} \le \log |\Delta_K| \le n^2$ and regime C the number fields for which $n^2 \le \log |\Delta_K| < \infty$ (see the red 'Provable' line in Figure 2). In the following we show how these different regimes arise.

In the algorithm of this paper the sampling probability for smooth elements has a provable lower bound from Part 1 (see Theorem 9.5)

$$p_{M,B} \ge \frac{1}{\rho_K} \cdot e^{-\tilde{O}\left(\frac{\log M}{\log B}\right)} \quad (\text{provable})$$

where $\rho_K = \lim_{s \to 1} (s-1)\zeta_K(s)$ is the residue of the Dedekind zeta function at $s=1$. Additionally, in Part 2, we prove that taking

$$R = \tilde{O}(B) \quad (\text{provable})$$

is indeed sufficient to generate the full $\mathbb{S}$-unit group. Instantiating the rest of the parameters like in the heuristic version (Section 21.3), we obtain the same running time, with an extra factor $\rho_K$.

$$\exp\left(\tilde{O}\left(\mathbf{b} + \log(B) + \log(\rho_K) + \frac{n^2/\mathbf{b} + \log|\Delta_K|}{\log(B)}\right)\right)$$

**Regime C.** As we have $\log(\rho_K) \le n \log(\log(|\Delta_K|)/n)$ [52], we can deduce, with the same reasoning as in Section 21.3 that the run time is bounded by $\exp(\log^{1/2} |\Delta_K|)$ whenever $\log |\Delta_K| \ge n^2$. Then, namely, $\log \rho_K \le \tilde{O}(\log^{1/2} |\Delta_K|)$ and therefore $\rho_K$ has essentially no significant influence on the running time. This explains the complexity of $\exp(\tilde{O}(\log^{1/2} |\Delta_K|))$ for regime C in Figure 2.

<footnote n="31">³¹A lower bound of this complexity is $\exp(\tilde{O}(\log^{1/2} |\Delta_K|))$, which is achieved when $\log B = \mathbf{b} = \log^{1/2} |\Delta_K|$ and $n^2/\mathbf{b} \le \log |\Delta_K|$, i.e., $n^2 \le \log^{3/2} |\Delta_K|$. This explains the running time for 'regime B', in which $n^{4/3} \le \log |\Delta_K|$.</footnote>

<footnote>In 'regime A', we have $n^{4/3} \ge \log |\Delta_K|$, for which a lower bound for the complexity is $\exp(\tilde{O}(n^{2/3}))$ which is achieved by taking $\log(B) = \mathbf{b} = n^{2/3}$.</footnote>
Regime B. When $\log|\Delta_K| \le n^2$, the running time of the provable algorithm possibly depends on $\rho_K$. As $\rho_K$ can be exponentially large in $n$, the worst-case running time for this regime is $\exp(O(n))$. Note, however, that for this regime, depending on the magnitude of $\rho_K$, the running time can lie anywhere in the gray area of Figure 2.

Regime A. Whenever the discriminant is sufficiently small, namely, $\log|\Delta_K| \le n^{3/2}$, one can apply a trick to significantly diminish the influence of the residue $\rho_K$ on the running time.

Instead of sampling random elements in $O_K$, one samples random elements co-prime with some modulus ideal $\mathfrak{m}_0 \subseteq O_K$ that is the product of all primes below some bound $X$. This sampling is done in a specific way, namely, by first sampling $\tau \in (O_K/\mathfrak{m}_0)^\times$ and then sampling a random element equivalent to $\tau$ modulo $\mathfrak{m}_0$. This causes the sampling probability of smooth elements (coprime with $\mathfrak{m}_0$) to increase by a factor $N(\mathfrak{m}_0)/\phi(\mathfrak{m}_0)$, but it also causes the maximum norm $M$ of the sampled elements to increase$^{32}$ by a factor $N(\mathfrak{m}_0)$, i.e.,

$$p_{M,B} \ge \frac{N(\mathfrak{m}_0)}{\phi(\mathfrak{m}_0) \cdot \rho_K} \cdot e^{-\tilde{O}\left(\frac{\log M + \log N(\mathfrak{m}_0)}{\log B}\right)} \quad (\text{provable}) \quad (134)$$

with $M = 2^{n^2/b}|\Delta_K|$. Using the fact that $\frac{N(\mathfrak{m}_0)}{\phi(\mathfrak{m}_0) \cdot \rho_K} \ge \exp(-\tilde{O}(\log|\Delta_K|/\sqrt{X}))$ (see Proposition 11.2), and $N(\mathfrak{m}_0) \approx \exp(\tilde{O}(X + \log|\Delta_K| \cdot \sqrt{X}))$ (see Lemma 11.4), we can rewrite Equation (134):

$$p_{M,B} \ge e^{-\tilde{O}\left(\frac{\log|\Delta_K| + n^{2/b} + \log|\Delta_K| + X + \log|\Delta_K| + \sqrt{X}}{\log B}\right)} \quad (\text{provable}). \quad (135)$$

Plugging in this probability lower bound into the general formula, the logarithm of the running time becomes, asymptotically,

$$\tilde{O}\left( b + \log(B) + \frac{n^{2/b} + \log|\Delta_K| \cdot \sqrt{X}}{\log(B)} + \frac{\log|\Delta_K|}{\sqrt{X}} \right). \quad (136)$$

This has as asymptotic lower bound $\tilde{O}(\log^{2/3} |\Delta_K|)$, attained when $X = \log^{2/3} |\Delta_K|$ and $\log(B) = \log^{2/3} |\Delta_K|$. Note that this trick is only useful whenever $\log^{2/3} |\Delta_K| \le \log \rho_K \le n \log(\log|\Delta_K|/n)$, otherwise the approach as in regime B (whose running time depends on $\rho_K$) would be faster. So, surely whenever $\log^{2/3} |\Delta_K| \le n$, i.e., $\log|\Delta_K| \le n^{3/2}$, this trick could outperform regime B (if $\rho_K$ is large), which explains regime A of the provable running time (see Figure 2).

## 21.5. Discussion.

Is the dependency of the running time on $\rho_K$ innate? The (dominant parts of the) provable expected running time of our $S$-unit computation algorithm is depicted in Figure 2 depending on the parameters $\log(\rho_K)$ and $\log|\Delta_K|$ compared to the degree $n$. For a fixed number field with $\log|\Delta_K| = n^\delta$ for $\delta \in [1, 2]$ the provable expected running time can be anywhere where the line $x = n^\delta$ intersects the shaded area, depending on the size of $\rho_K$. For small $\rho_K$, this running time can be equal to the heuristic one (the bottom blue line), whereas for large $\rho_K$, it might be equal to

<footnote>$^{32}$Because, instead of sampling in $O_K$, we now have to sample in the shifted lattice $\tau + \mathfrak{m}_0$, which has covolume $N(\mathfrak{m}_0)$ times the covolume of $O_K$.</footnote>
the worst-case provable one (the top red line). As this quantity $\rho_K$ is computable by Euler products.

The main question in this discussion is: does $\rho_K$ really have this influence on the running time or is it merely an artifact of the lack of tight bounds on smooth ideal densities?

Namely, there are asymptotic formulae [74] (see also Equation (103)) indicating that, for $u = \log(x)/\log(B)$,

$$\delta_{S_B}[x] \geq u^{-u}$$

but, generally, nothing is said about what the smallest $x \in \mathbb{R}_{>0}$ is for which this holds. For our purposes, we would like this smallest $x$ to be at most $O(|\Delta_K|)$ (and $B = \exp(O(\log^{1/2}(|\Delta_K|)))$). This is not something we could deduce from asymptotic results. Therefore, we chose to use a combinatorial result (Lemma 14.1), which shows that, for every $x > \log(B) \geq 2 \log \log |\Delta_K|$,

$$\delta_{S_B}[x] \geq \frac{1}{\rho_K \cdot B \cdot (4 \log(B))^u} u^{-u}.$$

This lower bound has as an advantage that it is explicit and holds for small values of $x$ (in particular the range around $|\Delta_K|$ we need). The disadvantage is the extra factor $\frac{1}{\rho_K}$, which increases, for large $\rho_K$, the provable running time of our algorithm drastically.

We could ask the main question of this discussion differently:

Are there bounds $B = \exp(O(\log^{1/2}(|\Delta_K|)))$, $X = O(|\Delta_K|)$, and $C^{-1} = \text{poly}(B, \exp(\log^{1/2}(|\Delta_K|)))$ such that for all $x \geq X$, and for $u = \log(x)/\log(B)$, the inequality

$$\delta_{S_B}[x] = \frac{|\{\mathbf{a} \in S_B \mid \mathcal{N}(\mathbf{a}) \leq x\}|}{\rho_K \cdot x} \geq C \cdot u^{-u}$$

holds?

If the answer is yes, our algorithm would reach the heuristic running time proposed by [10]. If the answer is no, it is likely that the heuristic algorithm of [10] does not achieve its claimed running time, and instead has the same dependence on $\rho_K$ as our algorithm.

*The use of variants of the Riemann Hypothesis.* An interesting follow-up question would be how the algorithms in this paper would perform without assuming variants of the Riemann Hypothesis. To aid such research we now identify which type of Riemann Hypothesis is used for which task and discuss the possible impact of letting go of these hypotheses.

(1) **Random Walk Theorem.** In Theorem 6.4, the Riemann Hypothesis for all Hecke L-functions associated with a Hecke-character over a number field $K$ (with fixed modulus $m$) is assumed. The Riemann Hypothesis in this form here seems indispensable for this proof, due to its influence on the bound on the Hecke eigenvalues (see Equation (171)).

Without the Riemann Hypothesis, one might have to resort to an alternative, weaker bound, optimistically maybe of the following form, inspired by bounds [73, 30] for the prime counting function:

$$\lambda_{\chi} = O \left( c_{K,m} \cdot e^{-\sqrt{\log(B)}} \right). \qquad (137)$$
Here, $c_{K,m}$ is some constant depending on $K$ and $m$, and the big-O is, as it is throughout the entire present work, absolute. A bound as Equation (137) for all eigenvalues of Hecke characters under Hecke operators, of which we do not know a proof and what the constant $c_{K,m}$ then might be, implies then that we are required to choose

$$B = O(e^{\log^2(c_{K,m})}),$$

which might or might not be useful, depending on the value of $c_{K,m}$.

(2) **Estimation of the factor $N(m_0)/\phi(m_0)$**. In Section 11, the Riemann hypothesis for the Dedekind zeta function of $K$ is assumed to estimate the factor $N(m_0)/\phi(m_0)$. This estimation is used to diminish the impact of $\rho_K$ on the running time of the $\mathbb{S}$-unit computation algorithm. To be more precise, this estimate on this factor allows for making the running time depend on $\rho_K^{\text{cut}}$ instead of $\rho_K$ (see Theorem 21.2, also the left-hand down-sloping part of the red graph in Figure 2).

Not assuming the Riemann hypothesis for the Dedekind zeta function of $K$ might impact the bound in Proposition 11.2 as well as the bound in Lemma 11.4. Hence, the precise implications of letting go of the Riemann hypothesis is not totally clear, but might heavily impact the dependency of the provable running time on $\rho_K$.

(3) **Density of smooth ideals.** In Section 14, a combinatorial bound is given for the density of smooth ideals, in which bounds on the number of prime ideals in a number field are used. Letting go of the Riemann Hypothesis here might have as a consequence that heavier restrictions on the numbers $B_{sm}$ and $A$ are required.

(4) **Computation of an approximation of $\rho_K$**. In multiple parts of the $\mathbb{S}$-unit computation algorithm an approximation of the Dedekind zeta function residue $\rho_K$ is required. In Algorithm 3, one uses this approximation whenever $\rho_K$ is large, to apply the 'modulus trick' in order to diminish the influence of $\rho_K$ on the running time. In the full algorithm, Algorithm 6, an approximation of $\rho_K$ (or equivalently, of $R_K \cdot h_K$) is needed to decide whether the algorithm indeed found the full logarithmic $\mathbb{S}$-unit lattice (see Section 19.5). The knowledge of an approximation of $\rho_K$ thus allows to change the full algorithm from a Las Vegas algorithm (i.e., the run time is a random variable but the answer of the algorithm is always correct) into a Monte Carlo algorithm (i.e., the run time is bounded but the answer might be wrong or inconclusive with a certain fixed small probability).

If the Riemann hypothesis for the Dedekind zeta function of $K$ is not assumed, longer Euler products are required to approximate $\rho_K$. Depending on the length of these Euler products compared to the running time of the rest of the entire algorithm (which is already at least $L_{|\Delta_K|}(1/2)$), letting go of the Riemann hypothesis might or might not influence the running time of the algorithm.
# Provable lattice reduction techniques

## 22. INTRODUCTION

Roughly, this last part of the current paper can be divided into two main subjects: The post-processing part, which is about processing the generators of the log-$\mathcal{S}$-unit lattice into a basis thereof (Sections 23 to 25); and the BKZ-algorithm part on approximate bases, which is needed to find short vectors in ideal lattices (Sections 26 to 28).

22.1. **Post-processing.** The first subject is the post-processing of the generating matrix of the log-$\mathcal{S}$-unit lattice in order to get a basis (and hence a fundamental set of $\mathcal{S}$-units) of this log-$\mathcal{S}$-unit lattice, see also Section 19.

In this post-processing stage, one consecutively computes the *rank*, the *determinant* and a well-conditioned *basis* of the lattice generated by the (approximate) generating matrix. The rank and determinant are computed first in order to check if the generating matrix indeed generates the entire log-$\mathcal{S}$-unit lattice (and not a sublattice thereof).

This post-processing makes use of the Buchmann-Kessler-Pohst algorithm, an algorithm that, roughly said, LLL-reduces a real-valued basis of one which only knows a sufficiently good approximation of. Though, in the work of Buchmann, Kessler and Pohst [17], it is assumed that the rank and the determinant of the generated lattice is *known*. In our application, though, these quantities are not known but instead need to be computed.

Hence, a slight modification of the analysis of Buchmann, Kessler and Pohst is treated in Section 23 in order to show that one can indeed *compute* the rank and a 'relatively well conditioned' approximate basis of the generated lattice with use of the Buchmann-Kessler-Pohst algorithm. This relatively well conditioned approximate basis can then be used to compute an approximation of the determinant (see Section 24).

The entire compound result with the exact precision needed, applied to our $\mathcal{S}$-unit computation algorithm of Part 2, is then treated in Section 25.

22.2. **The BKZ-algorithm on ideal lattices.** As we aim for a provable running time in this paper, we use a variant of the BKZ-algorithm [38] with a proven upper bound on the run time. The challenge with the lattices occurring in this paper, is that only an approximate basis of them are known. Hence, to make use of this variant of the BKZ-algorithm, we have to prove that this variant behaves well on small changes of the input.

In order to do so, a preliminary section about lattices is required (Section 26). After that, the running time of the variant of the BKZ-algorithm [38] on *integer* bases is analyzed, following a sketch of [38, Section 3, Cost of BKZ'] (Section 27). Lastly,
this BKZ-variant is applied on an approximate basis, with use of the Buchmann-Kessler-Pohst algorithm (Section 28).

## 23. BUCHMANN-KESSLER-POHST ALGORITHM

23.1. **Introduction.** In this section, we will treat a slightly modified analysis of the algorithm of Buchmann, Pohst and Kessler [17, 18]. The original algorithm allows to compute an approximate basis of a lattice $\Lambda$ from an approximate generating matrix of a lattice (i.e., a matrix whose rows generate the lattice), provided that the approximation of this generating matrix is good enough. In this original algorithm the rank and the determinant of the lattice generated by the generating matrix are assumed to be known.

In our case, computing (a fundamental system of) $\mathbb{S}$-units, the rank and the determinant of the lattice of the exact generating matrix are not known. Rather, we would like to approximately compute these quantities, in order to deduce whether the generating matrix generates the entire logarithmic $\mathbb{S}$-unit lattice or not.

Exactly this lack of knowing the rank and determinant of the lattice (spanned by the exact generating matrix) requires us to slightly modify the analysis of Buchmann, Pohst and Kessler. In this modified analysis, the algorithm of Buchmann, Pohst and Kessler is actually applied twice (this was already suggested in [17, p. 9, remark after Theorem 4.2]). These two applications of the same algorithm serve two different goals.

During the first application of the Buchmann-Kessler-Pohst algorithm, one computes an (approximate) basis of the lattice at hand. From this approximate basis one can directly obtain the rank of the lattice. This first (approximate) basis, though, might have bad conditioning properties and too long vectors. It is exactly the purpose of the second application of the Buchmann-Kessler-Pohst algorithm to transform this approximate basis in a well-conditioned approximate basis, with reasonably short vectors (close to what LLL can achieve).

This well-conditioning of the (approximate) basis allows to approximate the determinant of this basis within reasonable precision. This will be the subject of Section 24. Knowing the determinant and the rank of the resulting basis allows to verify whether the basis is an actual basis of the logarithmic $\mathbb{S}$-unit lattice or not (as there are formulas to compute the rank and the covolume of the logarithmic $\mathbb{S}$-unit lattice).

## 23.2. Preliminaries.

23.2.1. On the quasi-norm $\|\mathbf{A}\|_{2,\infty}$. In order to phrase the results of [17] more succinctly, we introduce the following norm-like function on matrices. It is just the maximum over the 2-norms of the rows of the matrix.

**Definition 23.1.** For any $k \times m$-matrix $\mathbf{A}$, we denote

$$ \|\mathbf{A}\|_{2,\infty} := \max_{1 \le j \le k} \|\mathbf{a}_j\|, $$

where $\mathbf{a}_j$ are the rows of $\mathbf{A}$, and where $\| \cdot \|$ is the Euclidean norm on the row vectors.

This is not a matrix norm as it is not submultiplicative, but it is almost submultiplicative:
**Lemma 23.2.** For a real $m \times l$-matrix $M'$ and a real $l \times k$-matrix $M$, we have

$$ \|M'M\|_{2,\infty} \le \sqrt{l} \cdot \|M'\|_{2,\infty} \|M\|_{2,\infty} $$

*Proof.* Take the 2-norm of the t-th row in $M'M$, which equals

$$ \| \sum_{j=1}^{l} m'_{tj} \mathbf{M}_j \| \le \sum_{j=1}^{l} |m'_{tj}| \| \mathbf{M}_j \| \le \| \mathbf{M}'_t \| \cdot \left( \sum_{j=1}^{l} \| \mathbf{M}_j \|^2 \right)^{1/2} \le \| \mathbf{M}'_t \| \cdot \sqrt{l} \cdot \| \mathbf{M} \|_{2,\infty} $$

where $m'_{tj}$ is the $tj$-th entry in $M'$, $\mathbf{M}_j$ is the $j$-th row of $M$ and $\mathbf{M}'_t$ is the $t$-th row of $M'$. The first inequality is the triangle inequality, the second inequality follows from the Cauchy-Schwarz inequality and the third from the inequality between 2-norms and infinity norms. As this holds for any row in $M'M$, we conclude that

$$ \|M'M\|_{2,\infty} \le \sqrt{l} \cdot \|M'\|_{2,\infty} \|M\|_{2,\infty}. \quad \square $$

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

**23.2.2.** *Rounding in the Buchmann-Kessler-Pohst algorithm.* In the original analysis of the Buchmann-Kessler-Pohst algorithm [17], the input approximate generating matrix $\mathbf{A} \in \mathbb{R}^{k \times n}$ (consisting of rows $\mathbf{a}_j \in \mathbb{R}^n$) is scaled up by $2^q$ and rounded entry-wise to the nearest integer, thus obtaining an integer matrix $\hat{\mathbf{A}} \in \mathbb{Z}^{k \times n}$ (consisting of rows $\hat{\mathbf{a}}_j \in \mathbb{Z}^n$) [17, Section 2]. This is done this way because then the LLL-algorithm can be applied to $\hat{\mathbf{A}}$ (the LLL-algorithm is generally only applied on integer (or rational) matrices). As a result, such an integer matrix $\hat{\mathbf{A}}$ satisfies $\|\hat{\mathbf{A}} - 2^q \mathbf{A}\|_{2,\infty} \le \sqrt{n}/2$ [17, Equation (1)].

In our analysis, we deviate from this. Going over the result of Buchmann and Kessler [17], one can verify that the only requirements on $\hat{\mathbf{A}}$ for their algorithm to work is:

* Closeness to $2^q \mathbf{A}$, i.e., $\|\hat{\mathbf{A}} - 2^q \mathbf{A}\|_{2,\infty} \le \sqrt{n}/2$ for some sufficiently large $q \in \mathbb{N}$, see [17, Equation (1)].

* Being able to call LLL on $\hat{\mathbf{A}}$; so, in fact $\hat{\mathbf{A}}$ is allowed be a rational matrix, as long as the denominators not too large.

By choosing, for example, $\hat{\mathbf{A}} \in \frac{1}{2} \mathbb{Z}^{k \times n}$, the inequality $\|\hat{\mathbf{A}} - 2^q \mathbf{A}\|_{2,\infty} \le \sqrt{n}/2$ can be easily achieved, using a sufficiently good approximation of $\mathbf{A}$ to construct $\hat{\mathbf{A}}$.

Summarizing, for our purposes it is not required that $\hat{\mathbf{A}}$ is integral (rationals with small common denominators will suffice, too) nor that $\hat{\mathbf{A}}$ is obtained by rounding $2^q \mathbf{A}$. For this reason, the following notation turns out to be useful.

**Notation 23.3** (Binary approximation). A matrix $\tilde{\mathbf{A}} \in \mathbb{Q}^{k \times n}$ is called a binary approximation of $\mathbf{A} \in \mathbb{R}^{k \times n}$ with precision $\varepsilon_0$ if $2^q \cdot \tilde{\mathbf{A}} \in \mathbb{Z}^{k \times n}$ for some $q \in \mathbb{N}$ and $\|\mathbf{A} - \tilde{\mathbf{A}}\|_{2,\infty} \le \varepsilon_0$.

Note that we can choose $q = \log_2(\varepsilon_0 \cdot n)$ in above notation, as that precision is sufficient to obtain the approximation $\|\mathbf{A} - \tilde{\mathbf{A}}\|_{2,\infty} \le \varepsilon_0$. As a result, there always exists such a matrix $\tilde{\mathbf{A}} \in \mathbb{Q}^{k \times n}$ whose bit-size is bounded by $q^2 \cdot k \cdot n \cdot \log(\|\mathbf{A}\|_{2,\infty}) = \log_2(\varepsilon_0 n)^2 \cdot k \cdot n \cdot \log(\|\mathbf{A}\|_{2,\infty})$ (each coefficient of $\tilde{\mathbf{A}}$ is a rational number with numerator bounded by $2^q \cdot \|\mathbf{A}\|_{2,\infty}$ and denominator bounded by $2^q$). Moreover, from any rational matrix $\tilde{\mathbf{A}}'$ satisfying $\|\mathbf{A} - \tilde{\mathbf{A}}'\|_{2,\infty} \le \varepsilon_0/2$, one can compute in polynomial time a matrix $\tilde{\mathbf{A}}$ with bit-size as above (polynomial in $n, k, \log(1/\varepsilon_0)$ and such that $\log\|\mathbf{A}\|_{2,\infty}$) and $\|\mathbf{A} - \tilde{\mathbf{A}}'\|_{2,\infty} \le \varepsilon_0$.
**23.3. The algorithm of Buchmann, Pohst and Kessler.** In the following lemma, we start by updating slightly the analysis of [17, Theorem 4.1], to make it compatible with our matrix norm, and also take into account the fact that the rank and determinant of our lattice are not known. In the later theorem (Theorem 23.5) we will apply this lemma twice, first to obtain just any basis of the lattice, and the second time to obtain a well-conditioned basis consisting of reasonably short vectors.

**Lemma 23.4.** Let $\Lambda \subseteq \mathbb{Z}^{n_1} \times \mathbb{R}^{n_2}$ be a lattice with $\lambda_1(\Lambda) \ge \mu$ and rank($\Lambda) \le r_0$. Let $\mathbf{A}$ be a $k \times (n_1+n_2)$-matrix whose rows generate the lattice $\Lambda$ with $k \ge n_2 \ge 1$, let

$$C := 2^{4k} \cdot \left( \frac{r_0 \cdot \|\mathbf{A}\|_{2,\infty}}{\mu} \right)^{r_0+1},$$

and let $\tilde{\mathbf{A}}$ be a binary approximation of $\mathbf{A}$ satisfying $\|\tilde{\mathbf{A}} - \mathbf{A}\|_{2,\infty} < \frac{1}{4}\mu \cdot C^{-1}$.

Then there exists an algorithm that, on input $\tilde{\mathbf{A}}, \mu, r_0$, computes a matrix $\mathbf{M} \in \mathbb{Z}^{k \times r}$ with $r = \text{rank}(\Lambda)$ in time polynomial in $k, n_1, n_2, \log\|\mathbf{A}\|_{2,\infty}, \log(1/\mu)$ and the bit-size of its input, and such that

(i) $\mathbf{MA} = \mathbf{B}$ is a basis of $\Lambda$.

(ii) $\|\mathbf{M}\|_{2,\infty} \le C/\sqrt{k} \le C$,

(iii) $\|\mathbf{B}\|_{2,\infty} \le 4^k \cdot \|\mathbf{A}\|_{2,\infty}$.

(iv) Writing $\tilde{\mathbf{B}} = \mathbf{M}\tilde{\mathbf{A}}$, we have $\|\tilde{\mathbf{B}} - \mathbf{B}\|_{2,\infty} \le C \cdot \|\tilde{\mathbf{A}} - \mathbf{A}\|_{2,\infty}$.

Additionally, if $\mathbf{A}$ happened itself to be a basis of $\Lambda$, i.e., $k = r = \text{rank}(\Lambda)$, we have, for all $j \in \{1, \dots, r\}$,

$$\|\mathbf{b}_j\| \le (\sqrt{rn_2} + 2)2^{\frac{r-1}{2}} \cdot \lambda_j(\Lambda),$$

where $\mathbf{b}_j$ are the rows of $\mathbf{B} = (\mathbf{b}_1, \dots, \mathbf{b}_r)$.

**Proof. Constructing the matrix $\hat{\mathbf{A}}$ from $\tilde{\mathbf{A}}$.** Using the discussion after Notation 23.3, we can also replace the matrix $\tilde{\mathbf{A}}$ by a matrix with bounded bit-size (in time polynomial in the bit-size of $\tilde{\mathbf{A}}$). Hence, in the rest of the proof, we will assume without loss of generality that the bit-size of $\tilde{\mathbf{A}}$ is polynomial in $k, n_1, n_2, \log\|\mathbf{A}\|_{2,\infty}, \log(1/\mu)$, and $\tilde{\mathbf{A}}$ satisfies $\|\mathbf{A} - \tilde{\mathbf{A}}\|_{2,\infty} \le 1/4 \cdot \mu \cdot C^{-1}$.

The algorithm first creates the matrix $\hat{\mathbf{A}}$ defined by $\hat{\mathbf{A}}_{ij} = \frac{1}{2}[2^{q+1}\tilde{\mathbf{A}}_{ij}]$ with $q = \lfloor \log_2(T) \rfloor$, where $\lfloor \cdot \rfloor$ denotes rounding to the nearest integer, $\lfloor \cdot \rfloor$ denotes rounding down, and

$$T = \frac{2^{3k}}{\mu} \cdot \left( \frac{r_0 \cdot \|\mathbf{A}\|_{2,\infty}}{\mu} \right)^{r_0} = \frac{2^{-k}}{\mu} \cdot \left( \frac{r_0 \cdot \|\mathbf{A}\|_{2,\infty}}{\mu} \right)^{-1} \cdot C \le C/(2\mu). \quad (138)$$

Note that computing $\hat{\mathbf{A}}$ can be done in time polynomial in $q$ and in the bit-size of $\tilde{\mathbf{A}}$. The entries of $\hat{\mathbf{A}}$ lie in $\frac{1}{2}\mathbb{Z}$, and the matrix $\hat{\mathbf{A}}$ satisfies

$$\|\hat{\mathbf{A}} - 2^q \mathbf{A}\|_{2,\infty} \le \underbrace{\|\hat{\mathbf{A}} - 2^q \tilde{\mathbf{A}}\|_{2,\infty}}_{\le \sqrt{n_2}/4} + \underbrace{\|2^q \tilde{\mathbf{A}} - 2^q \mathbf{A}\|_{2,\infty}}_{\le 2^q \cdot \frac{1}{2} \cdot \mu/C \le 1/4} \le \sqrt{n_2}/2.$$

According to the discussion in Section 23.2.2 this is sufficient to apply the Buchmann-Kessler-Pohst algorithm.

**Applying Buchmann-Kessler-Pohst to $[I | \hat{\mathbf{A}}]$.** This Buchmann-Kessler-Pohst algorithm [17, Theorem 4.1] essentially consists of applying LLL-reduction to the
matrix $[I | \hat{A}]$ consisting of the horizontal concatenation of $\hat{A}$ and $I$, the $k \times k$ identity matrix.

Put,<fnref n="33" /> in order to satisfy the prerequisites of [17, Proposition 3.2],

$$ \lambda := 2^k \cdot \left( \frac{r_0 \|\mathbf{A}\|_{2,\infty}}{\mu} \right)^{r_0} \ge \left( \frac{1}{2} k \sqrt{n_2} + \sqrt{k} \right) \cdot \frac{\|\mathbf{A}\|_{2,\infty}^r}{\mathrm{Vol}(\Lambda)} \quad (139) $$

where $r = \mathrm{rank}(\Lambda) \le r_0$; in the inequality we made use of Minkowski's inequality<fnref n="34" /> and the fact that $2^k \ge \frac{1}{2}k\sqrt{n_2} + \sqrt{k}$ (since we assumed $k \ge n_2$).

Note that $q = \lfloor \log_2(\hat{T}) \rfloor$ satisfies [17, Equation 7], since we have

$$ 2^q \ge \frac{1}{2} \cdot \frac{2^{3k}}{\mu} \cdot \left( \frac{r_0 \cdot \|\mathbf{A}\|_{2,\infty}}{\mu} \right)^{r_0} = \frac{1}{2} \cdot \frac{2^{2k}}{\mu} \cdot \lambda \\ > (\sqrt{n_2}k + 2) \cdot 2^{\frac{k-3}{2}} \cdot \frac{\lambda}{\mu}, $$

by Equation (139) and because $\frac{1}{2} \cdot 2^{2k} > (\sqrt{n_2}k + 2)2^{\frac{k-3}{2}}$ for all $k \ge n_2 \ge 1$.

With these parameters $\lambda$ and $q$, one can apply [17, Theorem 4.1]: LLL-reducing $[I | \hat{A}]$ yields an integral matrix $(\mathbf{R}^{\top}, \mathbf{M}^{\top})^{\top}$ such that

$$ \begin{bmatrix} \mathbf{R} \\ \mathbf{M} \end{bmatrix} \cdot [I \ \hat{A}] = \begin{bmatrix} \mathbf{R} & \mathbf{R}\hat{A} \\ \mathbf{M} & \mathbf{M}\hat{A} \end{bmatrix} = \begin{bmatrix} \mathbf{R} & \hat{\mathbf{E}} \\ \mathbf{M} & \hat{\mathbf{B}} \end{bmatrix} \quad (140) $$

for which holds $\mathbf{R}\mathbf{A} = \mathbf{0}$, and $\mathbf{M}\mathbf{A} = \mathbf{B}$, a basis of $\Lambda$. Furthermore, every row $\hat{\mathbf{e}}$ of $\hat{\mathbf{E}}$ satisfies ([17, Theorem 4.1, first equation on page 8])

$$ \|\hat{\mathbf{e}}\| \le 2^{\frac{k-1}{2}} \lambda $$

and every row $\hat{\mathbf{b}}$ of $\hat{\mathbf{B}}$ satisfies ([17, Proposition 3.1])

$$ \|\hat{\mathbf{b}}\| > 2^{\frac{k-1}{2}} \lambda. $$

**Identifying M and B, proving (i).** This gives means to distinguish where in the output matrix of Equation (140) the approximate basis elements $\hat{\mathbf{B}}$ are. Also, this gives us a way to identify $\mathbf{M}$, as it shares the same rows as $\hat{\mathbf{B}}$. Therefore, we can compute an $\mathbf{M}$ that satisfies part (i) of the lemma.

$$ \left( \frac{r_0 \|\mathbf{A}\|_{2,\infty}}{\mu} \right)^{r_0} \ge \left( \frac{r \|\mathbf{A}\|_{2,\infty}}{\mu} \right)^{r} \ge \frac{\|\mathbf{A}\|_{2,\infty}^r}{\mathrm{Vol}(\Lambda)} $$

<footnote n="33">³³We replaced $\alpha$ in [17, Proposition 3.2] here by $\|\mathbf{A}\|_{2,\infty}$. As $\alpha \in \mathbb{R}_{>0}$ is required to be an upper bound on the 2-norms of the rows of $\mathbf{A}$, $\|\mathbf{A}\|_{2,\infty} = \max_j \|\mathbf{g}_j\|$ clearly suffices.</footnote>

<footnote n="34">³⁴Minkowski's inequality states that $1/\mathrm{Vol}(\Lambda) \le (r/\lambda_1(\Lambda))^r \le (r/\mu)^r$ with $r = \mathrm{rank}(\Lambda)$. By the fact that $\|\mathbf{A}\|_{2,\infty}/\mu \ge 1$ and $r_0 \ge r$, we can conclude that</footnote>
**Bounds on M, B and $||B - \tilde{B}||_{2,\infty}$**. By [17, Theorem 4.1, Equation 9, bottom inequality], we have,<fnref n="35" /> since $2^q \le T$ (see Equation (138)),

$$ \|\mathbf{m}\| \le 2^{\frac{k-1}{2}+q+1} \cdot \|\mathbf{A}\|_{2,\infty} = 2^{\frac{k+1}{2}} \cdot \|\mathbf{A}\|_{2,\infty} \cdot T \quad (141) $$

$$ \le 2^{\frac{k+1}{2}} \cdot \|\mathbf{A}\|_{2,\infty} \cdot \frac{2^{3k}}{\mu} \cdot \left( \frac{r_0 \cdot \|\mathbf{A}\|_{2,\infty}}{\mu} \right)^{r_0} \quad (142) $$

$$ \le \frac{2^{4k}}{\sqrt{k}} \cdot \left( \frac{r_0 \cdot \|\mathbf{A}\|_{2,\infty}}{\mu} \right)^{r_0+1} \quad (143) $$

$$ \le \frac{C}{\sqrt{k}} \le C \quad \text{for all rows } \mathbf{m} \text{ of } \mathbf{M}, \quad (144) $$

where we used $2^{\frac{k+1}{2}} \le 2^k/\sqrt{k}$ for all $k \in \mathbb{Z}_{>0}$. Additionally, by [17, Theorem 4.1, Equation 10], we have,

$$ \|\mathbf{b}\| \le (\sqrt{kn_2} + 2)2^{\frac{k-1}{2}} \cdot \|\mathbf{A}\|_{2,\infty} \quad (145) $$

$$ \le 2^{2k} \cdot \|\mathbf{A}\|_{2,\infty} \quad \text{for all rows } \mathbf{b} \text{ of } \mathbf{B}, \quad (146) $$

which prove (ii) and (iii), as $\|\mathbf{M}\|_{2,\infty}$ and $\|\mathbf{B}\|_{2,\infty}$ are just the maximum 2-norm of the rows of the respective matrices.

For part (iv) use the ‘almost submultiplicativity’ of $\|\cdot\|_{2,\infty}$ (Lemma 23.2) and Equation (144), to obtain

$$ \|\tilde{\mathbf{B}} - \mathbf{B}\|_{2,\infty} = \|\mathbf{M}(\tilde{\mathbf{A}} - \mathbf{A})\|_{2,\infty} \le \sqrt{k} \cdot \|\mathbf{M}\|_{2,\infty} \cdot \|\tilde{\mathbf{A}} - \mathbf{A}\|_{2,\infty} \le C \cdot \|\tilde{\mathbf{A}} - \mathbf{A}\|_{2,\infty}. $$

**LLL-alike bounds for B when A is itself a basis of Λ.** In the case that A itself happens to be a basis, sharper bounds on B can be established, as can be deduced<fnref n="36" /> from [17, Theorem 4.1, Equation 10]. Applying this bound yields, for all $j \in \{1, \dots, r\}$,

$$ \|\mathbf{b}_j\| \le (\sqrt{kn_2} + 2)2^{\frac{k-1}{2}} \cdot \lambda_j(\Lambda) $$

where $\mathbf{b}_j$ is the j-th row of B.

**Running time.** For the running time, note that the most costly part of the algorithm is to run the LLL algorithm on the matrix $[\mathbf{I} | \tilde{\mathbf{A}}]$. This can be done in polynomial time in the bit-size of the matrix, which is polynomial in $k, n_1, n_2, \log\|\mathbf{A}\|_{2,\infty}$ and $\log(1/\mu)$, as desired. □

**Theorem 23.5** (Buchmann-Kessler-Pohst). Let $\Lambda \subseteq \mathbb{Z}^{n_1} \times \mathbb{R}^{n_2}$ be a lattice with $\lambda_1(\Lambda) \ge \mu$ and $\text{rank}(\Lambda) \le r_0$. Let A be a $k \times (n_1+n_2)$-matrix whose rows generate the lattice $\Lambda$ with $k \ge n_2 \ge 1$, let

$$ C_0 = 2^{8k} \cdot \left( \frac{r_0 \cdot 4^k \cdot \|\mathbf{A}\|_{2,\infty}}{\mu} \right)^{2(r_0+1)}, $$

and let $\tilde{\mathbf{A}}$ be a binary approximation of A that satisfies $\|\tilde{\mathbf{A}} - \mathbf{A}\|_{2,\infty} < \frac{1}{4} \cdot \mu \cdot C_0^{-1}$.

<footnote n="35">³⁵In [17, Eq. 10], the lattice successive minima $\lambda_j(L_r)$ of the lattice $L_r$ are used; this lattice $L_r$ is any lattice spanned by $r$ rows of A. So these successive minima $\lambda_j(L_r)$ are trivially bounded by $\alpha$, the uniform bound on the lengths of the rows of A. Additionally, we replaced $\alpha$ by $\|\mathbf{A}\|_{2,\infty}$ again.</footnote>

<footnote n="36">³⁶We substitute $k = r$ (as B consists of $r$ rows) and $L_r = \Lambda$. Here $L_r$ is defined as any lattice defined by any $r$ row vectors from B. As B consists of only $r$ row vectors and is a basis of $\Lambda$, we have $L_r = \lambda$.</footnote>
Then, there exists an algorithm that, on input $\tilde{\mathbf{A}}, \mu, r_0$, computes in time polynomial in $k, n_1, n_2, \log\|\mathbf{A}\|_{2,\infty}, \log(1/\mu)$ and the bit-size of its input, a matrix $\mathbf{N} \in \mathbb{Z}^{r \times k}$ with $r = \text{rank}(\Lambda)$ such that

(i) $\|\mathbf{N}\|_{2,\infty} \le C_0$

(ii) $\mathbf{B} = \mathbf{N}\mathbf{A}$ is a basis of $\Lambda$, whose rows satisfy, for $j \in \{1, \dots, r\}$,

$$ \|\mathbf{b}_j\| \le (\sqrt{rn_2} + 2) \cdot 2^{\frac{r-1}{2}} \cdot \lambda_j(\Lambda) $$

(iii) The approximate basis $\tilde{\mathbf{B}} = \mathbf{N}\tilde{\mathbf{A}}$ satisfies $\|\tilde{\mathbf{B}} - \mathbf{B}\|_{2,\infty} \le C_0 \cdot \|\tilde{\mathbf{A}} - \mathbf{A}\|_{2,\infty}$.

*Proof.* We will apply the Buchmann-Kessler-Pohst algorithm as in Lemma 23.4 twice: the first time we apply it to $\tilde{\mathbf{A}}$ to obtain an approximate basis $\tilde{\mathbf{B}}_0$ of $\Lambda$, and the second time we apply it to $\tilde{\mathbf{B}}_0$ to obtain an approximate good basis $\tilde{\mathbf{B}}$ of $\Lambda$. This basis $\tilde{\mathbf{B}}$ is called ‘good’ because it is an approximation of a basis $\mathbf{B}$ with a guarantee on the shortness of its basis vectors.

**First application of Lemma 23.4.**

We have that $C_0 > 2^{4k} \cdot \left(\frac{r_0 \cdot \|\mathbf{A}\|_{2,\infty}}{\mu}\right)^{r_0+1} = C$ from Lemma 23.4. Therefore, the approximation $\tilde{\mathbf{A}}$ of $\mathbf{A}$ is sufficiently good to apply Lemma 23.4, and compute $\mathbf{M} \in \mathbb{Z}^{k \times r}$ such that $\mathbf{M}\mathbf{A} = \mathbf{B}_0$ is a basis of $\Lambda$. Additionally, this $\mathbf{M}$ and $\mathbf{B}_0$ satisfy

$$ \|\mathbf{M}\|_{2,\infty} \le C \quad \text{and} \quad \|\mathbf{B}_0\|_{2,\infty} \le 4^k \cdot \|\mathbf{A}\|_{2,\infty}, \qquad (147) $$

and $\tilde{\mathbf{B}}_0 := \mathbf{M}\tilde{\mathbf{A}}$ satisfies

$$ \|\tilde{\mathbf{B}}_0 - \mathbf{B}_0\|_{2,\infty} \le C \cdot \|\tilde{\mathbf{A}} - \mathbf{A}\|_{2,\infty} \le C \cdot \mu \cdot C_0^{-1} \qquad (148) $$

Moreover, the bit-size of $\tilde{\mathbf{B}}_0$ is polynomially bounded by the bit-size of $\tilde{\mathbf{A}}$, and the bit-size of $\mathbf{M}$, the latter being polynomially bounded by $k, n_1, n_2, \log\|\mathbf{A}\|_{2,\infty}$ and $\log(1/\mu)$.

**Second application of Lemma 23.4.**

By Equation (148) we deduce that $\|\tilde{\mathbf{B}}_0 - \mathbf{B}_0\|_{2,\infty} < \mu(C_0/C)^{-1}$; since $\tilde{\mathbf{B}}_0 = \mathbf{M}\tilde{\mathbf{A}}$, this matrix $\tilde{\mathbf{B}}_0$ is a binary approximation of $\mathbf{B}_0$. In order to apply Lemma 23.4, we need to show that $C_0/C \ge 2^{4r} \cdot \left(\frac{r \cdot \|\mathbf{B}_0\|_{2,\infty}}{\mu}\right)^{r+1} =: C'$, i.e., that the precision of $\tilde{\mathbf{B}}_0$ is good enough. By the choice of $C_0$, the bound $4^k \cdot \|\mathbf{A}\|_{2,\infty} \ge \|\mathbf{B}_0\|_{2,\infty}$ (Equation (147)), $r_0 \ge r$ and $k \ge r$, we have

$$ \frac{C_0}{C} = \frac{2^{8k} \cdot \left( \frac{r_0 \cdot 4^k \cdot \|\mathbf{A}\|_{2,\infty}}{\mu} \right)^{2(r_0+1)}}{2^{4k} \cdot \left( \frac{r_0 \cdot \|\mathbf{A}\|_{2,\infty}}{\mu} \right)^{r_0+1}} \ge 2^{4k} \cdot \left( \frac{r_0 \cdot 4^k \cdot \|\mathbf{A}\|_{2,\infty}}{\mu} \right)^{r_0+1} \qquad (149) $$

$$ \ge 2^{4k} \cdot \left( \frac{r_0 \cdot \|\mathbf{B}_0\|_{2,\infty}}{\mu} \right)^{r_0+1} \ge 2^{4r} \cdot \left( \frac{r \cdot \|\mathbf{B}_0\|_{2,\infty}}{\mu} \right)^{r+1} =: C' \qquad (150) $$

Therefore, we can apply Lemma 23.4 again, but now with $k = r$ and $C'$ as in Equation (150), and with input $(\tilde{\mathbf{B}}_0, \mu, r)$ (note that $r$ is now known, and we still have $\mu \le \lambda_1(\Lambda)$). This yields $\mathbf{M}'$ such that $\mathbf{M}'\mathbf{B}_0 = \mathbf{B}$ is a basis of $\Lambda$,

$$ \|\mathbf{M}'\|_{2,\infty} \le C'/\sqrt{r} \qquad (151) $$

and for all $j \in \{1, \dots, r\}$ we have

$$ \|\mathbf{b}'_j\| \le (\sqrt{rn_2} + 2) \cdot 2^{\frac{r-1}{2}} \cdot \lambda_j(\Lambda), $$
which proves (ii), putting $N = M'M$.

For (i), we apply the 'almost submultiplicativity' (Lemma 23.2) to $N = M'M$, which yields, by Equation (151) and Equation (150) ($C_0/C \ge C'$),

$$ \|N\|_{2,\infty} \le \sqrt{r} \|M'\|_{2,\infty} \|M\|_{2,\infty} \le C' \cdot C \le C_0. $$

For (iii), we note that, by the results of Lemma 23.4,

$$ \|\tilde{\mathbf{B}} - \mathbf{B}\|_{2,\infty} \le C' \cdot \|\tilde{\mathbf{B}}_0 - \mathbf{B}_0\|_{2,\infty} \le C' \cdot C \cdot \|\tilde{\mathbf{A}} - \mathbf{A}\|_{2,\infty} \le C_0 \cdot \|\tilde{\mathbf{A}} - \mathbf{A}\|_{2,\infty} $$

For the running time of the algorithm, note that we applied the algorithm of Lemma 23.4 twice, once with $(\mathbf{A}, \mu, r_0)$ and once with $(\mathbf{B}_0, \mu, r)$. Recall that the bit-size of $\mathbf{B}_0$ is polynomially bounded by $k$, $n_1$, $n_2$, $\log\|\mathbf{A}\|_{2,\infty}$ and $\log(1/\mu)$ and by the bit-size of $\tilde{\mathbf{A}}$. Using Lemma 23.4 gives the desired upper bound on the total running time of the algorithm. $\square$

## 24. COMPUTING THE DETERMINANT OF AN APPROXIMATE BASIS

**24.1. Preliminaries.** In this section we will use the induced 2-norm on matrices, which is defined (for $m \times n$-matrices $\mathbf{A}$) by the rule,

$$ \|\mathbf{A}\|_2 := \sup\{\|\mathbf{A}\mathbf{x}\| \mid \mathbf{x} \in \mathbb{C}^n \text{ with } \|\mathbf{x}\| = 1\}. $$

It satisfies the following inequalities

$$ \|\mathbf{A}\|_2 \le \|\mathbf{A}\|_F := \left(\sum_{i,j} |A_{ij}|^2\right)^{1/2}, $$

where $\|\mathbf{A}\|_F$ is the Frobenius norm. As a result, a $m \times n$ matrix $\mathbf{E}$ with $E_{ij} \le \varepsilon$ for all $i, j$, satisfies

$$ \|\mathbf{E}\|_2 \le \|\mathbf{E}\|_F \le \sqrt{nm} \cdot \varepsilon. $$

We will use the fact that $\|\mathbf{A}\|_2$ corresponds to the largest singular value of $\mathbf{A}$, which gives us

$$ \|\mathbf{A}^{\top}\|_2 = \|\mathbf{A}\|_2. \qquad (152) $$

**24.2. The main result of this section.** This section is about the following problem. Suppose we have a rank-$n$ lattice $\Lambda \subseteq \mathbb{R}^m$ of which we can approximate the determinant, say $D \approx \text{Vol}(\Lambda)$. Suppose furthermore that we have an approximate basis $\tilde{\mathbf{B}}' \approx \mathbf{B}'$ of a sublattice $\Lambda' \subseteq \Lambda$ (with the same rank $n$). The task is to decide whether $\Lambda' = \Lambda$, using only the approximations $\tilde{\mathbf{B}}'$ and $D$.

A straightforward way is to compute $\sqrt{\det((\tilde{\mathbf{B}}')^{\top}\tilde{\mathbf{B}}')} \approx \text{Vol}(\Lambda')$ and compare it with $D \approx \text{Vol}(\Lambda)$. If the approximations are sufficiently good and $D$ and $\sqrt{\det((\tilde{\mathbf{B}}')^{\top}\tilde{\mathbf{B}}')}$ are sufficiently close, we can conclude $\Lambda' = \Lambda$. If they are not close, we can conclude $\Lambda' \ne \Lambda$.

This section treats how well $\tilde{\mathbf{B}}'$ needs to approximate $\mathbf{B}'$ (the exact basis of $\Lambda'$) and how well $D$ needs to approximate $\text{Vol}(\Lambda)$ in order to make this reasoning correct. The main result of this section is the following statement.

**Theorem 24.1.** Let $\Lambda \subset \mathbb{R}^m$ be a rank-$n$ lattice (for some $m \ge n \ge 1$). Let $\mathbf{B}' \in \mathbb{R}^{m \times n}$ be a basis of a rank-$n$ sublattice $\Lambda' \subseteq \Lambda \subseteq \mathbb{R}^m$ and let $\tilde{\mathbf{B}}' \in \mathbb{Q}^{m \times n}$ be
an approximation of $\mathbf{B}'$ where the entry-wise error is less than

$$ \varepsilon = 2^{-6} \cdot n^{-(n+4)} \cdot m^{-1} \cdot \left( \prod_j \frac{\|\mathbf{b}'_j\|}{\lambda_j(\Lambda')} \right)^{-2} \cdot \lambda_1(\Lambda')^2 / \|\mathbf{B}'\|_2, $$

and let $D \in [\frac{3}{4}, \frac{5}{4}] \text{Vol}(\Lambda) \cap \mathbb{Q}$.

Then we can decide whether $\Lambda' = \Lambda$ or not, using only $\tilde{\mathbf{B}}'$ and $D$, in time polynomial in the bit-sizes of $\tilde{\mathbf{B}}'$ and $D$.

**24.3. Some preliminary lemmas.** Before proving Theorem 24.1, we will prove some intermediary lemmas. The first lemma gives an upper bound on the size of the inverse of a square matrix $\mathbf{A}$ that is the basis of a lattice (the upper bound depends on some quantities related to $\mathbf{A}$, which quantify how well-conditioned $\mathbf{A}$ is). This will be used in the second lemma to prove that if two rectangular matrices $\mathbf{B}$ and $\tilde{\mathbf{B}}$ are close coefficient-wise, then the determinants of the square matrices $\mathbf{B}^\top\mathbf{B}$ and $\tilde{\mathbf{B}}^\top\tilde{\mathbf{B}}$ are close too. This second lemma will be central in the proof of Theorem 24.1.

**Lemma 24.2.** Suppose $\mathbf{A} = (\mathbf{a}_1, \dots, \mathbf{a}_n) \in \mathbb{R}^{n \times n}$ is a square real matrix and a basis of a lattice $\Lambda \subset \mathbb{R}^n$. Then

$$ \|\mathbf{A}^{-1}\|_2 \le n^{n/2+1} \cdot \lambda_1(\Lambda)^{-1} \cdot \left( \prod_{j=1}^{n} \frac{\|\mathbf{a}_j\|}{\lambda_j(\Lambda)} \right). $$

*Proof.* For $j \in \{1, \dots, n\}$, define $C_j = \frac{\|\mathbf{a}_j\|}{\lambda_j(\Lambda)}$. We have that $\mathbf{A}^{-1} = \frac{1}{\det \mathbf{A}} \text{adj}(\mathbf{A})$. We have that $\text{adj}(\mathbf{A})_{ij}$ is defined by the determinant of the minor of $\mathbf{A}$ where the $i$-th row and $j$-th column are deleted. By the Hadamard bound and subsequently by Minkowski's second theorem (see, e.g., [53, Theorem 1.5]),

$$ \begin{aligned} |\text{adj}(\mathbf{A})_{ij}| &\le \prod_{k \ne i} \|\mathbf{a}_k\| = \prod_{k \ne i} C_k \cdot \lambda_k(\Lambda) \\ &\le n^{n/2} \cdot \left( \prod_{k \ne i} C_k \right) \cdot \frac{\text{Vol}(\Lambda)}{\lambda_i(\Lambda)} \le n^{n/2} \left( \prod_{k=1}^{n} C_k \right) \cdot \frac{\text{Vol}(\Lambda)}{\lambda_1(\Lambda)}. \end{aligned} $$

Therefore, by observing that $\det(\mathbf{A}) = \text{Vol}(\Lambda)$, we obtain

$$ \|\mathbf{A}^{-1}\|_2 \le \|\mathbf{A}^{-1}\|_F \le \frac{1}{\det(\mathbf{A})} \cdot n \cdot \max_{ij} |\text{adj}(\mathbf{A})_{ij}| \le n^{n/2+1} \cdot \left( \prod_{k=1}^{n} C_k \right) / \lambda_1(\Lambda) $$

□

**Lemma 24.3.** Let $\mathbf{B} \in \mathbb{R}^{m \times n}$ be a basis of a rank-$n$ lattice $\Lambda \subset \mathbb{R}^m$ (for some $m \ge n \ge 1$), and let $\tilde{\mathbf{B}}$ be an approximation of $\mathbf{B}$ where the entry-wise error satisfies $s |\mathbf{B}_{ij} - \tilde{\mathbf{B}}_{ij}| \le \varepsilon$ for every $i \in \{1, \dots, m\}, j \in \{1, \dots, n\}$, where

$$ \varepsilon = 2^{-6} \cdot n^{-(n+4)} \cdot m^{-1} \cdot \left( \prod_j \frac{\|\mathbf{b}_j\|}{\lambda_j(\Lambda)} \right)^{-2} \cdot \lambda_1(\Lambda)^2 / \|\mathbf{B}\|_2. \quad (153) $$

Then

$$ \det(\tilde{\mathbf{B}}^\top \tilde{\mathbf{B}}) \in [\frac{7}{8}, \frac{9}{8}] \cdot \det(\mathbf{B}^\top \mathbf{B}). $$
*Proof.* We have, by [42, Corollary 2.14], for $n \times n$ complex matrices $\mathbf{A}, \mathbf{E}$, where $\mathbf{A}$ is non-singular,

$$ \frac{|\det(\mathbf{A} + \mathbf{E}) - \det(\mathbf{A})|}{|\det(\mathbf{A})|} \leq (\|\mathbf{A}^{-1}\|_2 \|\mathbf{E}\|_2 + 1)^n - 1 \\ \leq 2n \|\mathbf{A}^{-1}\|_2 \|\mathbf{E}\|_2 \quad \text{if } \|\mathbf{A}^{-1}\|_2 \|\mathbf{E}\|_2 \leq 1/n. \quad (154) $$

The last inequality here easily follows from $(x+1)^n - 1 \leq (e^x)^n - 1 \leq 2nx$ for $nx \leq 1$.

We instantiate this inequality with $\mathbf{A} = \mathbf{B}^\top \mathbf{B}$ and $\mathbf{E} = \tilde{\mathbf{B}}^\top \tilde{\mathbf{B}} - \mathbf{B}^\top \mathbf{B}$, so that $\mathbf{A} + \mathbf{E} = \tilde{\mathbf{B}}^\top \tilde{\mathbf{B}}$ (note that $\mathbf{A}$ is non-singular since $\mathbf{B}$ is of rank $n$, so the instantiation is valid). In order to obtain a meaningful upper bound, let us compute bounds on the two quantities $\|\mathbf{A}^{-1}\|_2$ and $\|\mathbf{E}\|_2$.

We can rewrite $\mathbf{E}$ as

$$ \begin{aligned} \mathbf{E} &= (\mathbf{B} + (\tilde{\mathbf{B}} - \mathbf{B}))^\top \cdot (\mathbf{B} + (\tilde{\mathbf{B}} - \mathbf{B})) - \mathbf{B}^\top \mathbf{B} \\ &= \mathbf{B}^\top \cdot (\tilde{\mathbf{B}} - \mathbf{B}) + (\tilde{\mathbf{B}} - \mathbf{B})^\top \cdot \mathbf{B} + (\tilde{\mathbf{B}} - \mathbf{B})^\top \cdot (\tilde{\mathbf{B}} - \mathbf{B}). \end{aligned} $$

Using the sub-multiplicativity of the induced 2-norm and Equation (152), we obtain

$$ \|\mathbf{E}\|_2 \leq 2 \cdot \|\mathbf{B}\|_2 \cdot \|\tilde{\mathbf{B}} - \mathbf{B}\|_2 + \|\tilde{\mathbf{B}} - \mathbf{B}\|_2^2. $$

By assumption on the entry-wise error, we know that $\|\tilde{\mathbf{B}} - \mathbf{B}\|_2 \leq \|\tilde{\mathbf{B}} - \mathbf{B}\|_F \leq \sqrt{nm} \cdot \varepsilon$. Moreover, it holds that $\|\mathbf{B}\|_2 \geq \|\mathbf{b}_1\| \geq \lambda_1(\Lambda) \geq \lambda_1(\Lambda)^2 / \|\mathbf{B}\|_2 \geq \varepsilon$ (where $\mathbf{b}_1$ is the first column vector of $\mathbf{B}$, and see Equation (153)). This yields

$$ \|\mathbf{E}\|_2 \leq 3 \cdot n \cdot m \cdot \varepsilon \cdot \|\mathbf{B}\|_2. \quad (155) $$

Let us now compute an upper bound on $\|\mathbf{A}^{-1}\|_2 = \|(\mathbf{B}^\top \mathbf{B})^{-1}\|_2$. Let $(\mathbf{Q}, \mathbf{R})$ be the QR-decomposition of $\mathbf{B}$, with $\mathbf{Q} \in \mathbb{R}^{m \times m}$ orthogonal and $\mathbf{R} \in \mathbb{R}^{m \times n}$ upper triangular, i.e., $\mathbf{B} = \mathbf{Q}\mathbf{R}$. Since $m \geq n$, we have $\mathbf{R} = \begin{pmatrix} \mathbf{C} \\ 0 \end{pmatrix}$ for some invertible matrix $\mathbf{C} \in \mathbb{R}^{n \times n}$. It then holds, by orthogonality of $\mathbf{Q}$, that $\mathbf{C}^\top \mathbf{C} = \mathbf{B}^\top \mathbf{B}$; that $\|\mathbf{b}_i\| = \|\mathbf{c}_i\|$ for all $1 \leq i \leq n$; and that $\lambda_i(\Lambda) = \lambda_i(\Lambda_C)$ for all $i$'s, where $\Lambda_C$ is the lattice spanned by the columns of $\mathbf{C}$. This gives us

$$ \begin{aligned} \|\mathbf{A}^{-1}\|_2 &= \|(\mathbf{B}^\top \mathbf{B})^{-1}\|_2 = \|(\mathbf{C}^\top \mathbf{C})^{-1}\|_2 \\ &\leq \|(\mathbf{C}^{-1})^\top\|_2 \cdot \|\mathbf{C}^{-1}\|_2 \\ &= \|\mathbf{C}^{-1}\|_2^2 \\ &\leq \left( n^{n/2+1} \cdot \lambda_1(\Lambda_C)^{-1} \cdot \left( \prod_{j=1}^n \frac{\|\mathbf{c}_j\|}{\lambda_j(\Lambda_C)} \right) \right)^2 \\ &= n^{n+2} \cdot \lambda_1(\Lambda)^{-2} \cdot \left( \prod_{j=1}^n \frac{\|\mathbf{b}_j\|}{\lambda_j(\Lambda)} \right)^2, \end{aligned} \quad (156) $$

where we used Equation (152) for the third line and Lemma 24.2 on $\mathbf{C}$ (which is $n$ by $n$ as required) for the fourth line.
Combining the bounds Equations (154) to (156) and observing that $\|\mathbf{A}^{-1}\|_2 \cdot \|\mathbf{E}\|_2 \le 1/n$ by choice of $\varepsilon$, we obtain

$$ \frac{|\det(\tilde{\mathbf{B}}^{\top}\tilde{\mathbf{B}}) - \det(\mathbf{B}^{\top}\mathbf{B})|}{|\det(\mathbf{B}^{\top}\mathbf{B})|} \le 2n \cdot \|\mathbf{A}^{-1}\|_2 \cdot \|\mathbf{E}\|_2 \\ \le 2n \cdot n^{n+2} \cdot \lambda_1(\Lambda)^{-2} \cdot \underbrace{\left(\prod_{j=1}^{n} \frac{\|\mathbf{b}_j\|}{\lambda_j(\Lambda)}\right)^2}_{\|\mathbf{A}^{-1}\|_2} \cdot \underbrace{3 \cdot n \cdot m \cdot \varepsilon \cdot \|\mathbf{B}\|_2}_{\|\mathbf{E}\|_2} \\ \le 1/8, $$

which precisely means that $\det(\tilde{\mathbf{B}}^{\top}\tilde{\mathbf{B}}) \in [\frac{7}{8}, \frac{9}{8}] \cdot \det(\mathbf{B}^{\top}\mathbf{B})$. $\square$

**24.4. Proving the main result.** We are now equipped to prove Theorem 24.1. The proof is quite short once we have Lemma 24.3.

*Proof of Theorem 24.1.* Let $\ell = [\Lambda : \Lambda']$ be the index of $\Lambda'$ in $\Lambda$. Then $\ell \ge 1$ is an integer, and we know that $\det((\mathbf{B}')^{\top}\mathbf{B}')/\mathrm{Vol}(\Lambda)^2 = \ell^2$. Our objective is to determine whether $\ell^2 = 1$ (i.e., $\Lambda' = \Lambda$) or $\ell^2 \ge 4$ (i.e., $\Lambda' \subsetneq \Lambda$).

By the choice of $\varepsilon$, we can apply Lemma 24.3 to $\tilde{\mathbf{B}}'$, which proves that $\det((\tilde{\mathbf{B}}')^{\top}\tilde{\mathbf{B}}') \in [\frac{7}{8}, \frac{9}{8}] \cdot \det((\mathbf{B}')^{\top}\mathbf{B}')$. Recall that by assumption, $D \in [\frac{3}{4}, \frac{5}{4}] \cdot \mathrm{Vol}(\Lambda)$. From these two inequalities, we obtain that

$$ \frac{\det((\tilde{\mathbf{B}}')^{\top}\tilde{\mathbf{B}}')}{D^2} \in [\frac{16}{25} \cdot \frac{7}{8}, \frac{16}{9} \cdot \frac{9}{8}] \cdot \frac{\det((\mathbf{B}')^{\top}\mathbf{B}')}{\mathrm{Vol}(\Lambda)^2} = [\frac{14}{25}, 2] \cdot \ell^2. $$

If $\Lambda = \Lambda'$, then $\ell = 1$ and we have $\frac{\det((\tilde{\mathbf{B}}')^{\top}\tilde{\mathbf{B}}')}{D^2} \le 2$. Otherwise, $\ell \ge 2$ and we have $\frac{\det((\tilde{\mathbf{B}}')^{\top}\tilde{\mathbf{B}}')}{D^2} > 2.2$. We can then distinguish the two cases by computing the quantity $\det((\tilde{\mathbf{B}}')^{\top}\tilde{\mathbf{B}}')$ and checking whether is it $\le 2 \cdot D^2$ or $> 2 \cdot D^2$.

For the running time, we only need to compute the determinant of the rational matrix $(\tilde{\mathbf{B}}')^{\top}\tilde{\mathbf{B}}'$, and then compare it with the rational number $2 \cdot D^2$. This can be done in polynomial time in the bit-sizes of the $\tilde{\mathbf{B}}'$ and $D$ (see, e.g., [44] for an algorithm that computes the determinant of integer matrices in polynomial time). $\square$

**25. POST-PROCESSING IN THE $\mathbb{S}$-UNIT COMPUTATION**

**Theorem 19.1.** Let $K$ be a number field with degree $n$, and let $G = \{\eta_1, \dots, \eta_k\} \subseteq \mathcal{O}_{K,\mathbb{S}}^\times$ a finite set of $\mathbb{S}$-units. There exists an algorithm that takes as input the set $G^{37}$ and computes a system of fundamental $\mathbb{S}$-units for the subgroup $\langle G \rangle \subseteq \mathcal{O}_{K,\mathbb{S}}^\times$ generated by $G$ in compact representation, i.e., a pair $(\mathbf{N}, G)$ with $\mathbf{N} \in \mathbb{Z}^{r \times k}$ such that $v_j = \prod_{i=1}^k \eta_i^{\mathbf{N}_{ji}}$ for $j \in \{1, \dots, r\}$ form a system of fundamental $\mathbb{S}$-units for $\langle G \rangle$.

Additionally, this algorithm decides whether $\langle G \rangle = \mathcal{O}_{K,\mathbb{S}}^\times$ or not, and runs in time polynomial in $k$, $\log|\Delta_K|$, $|\mathbb{S}|$, $\log(\max_j \|\mathrm{Log}_{\mathbb{S}}(\eta_j)\|)$ and $\max_j(\mathrm{size}(\eta_j))$.

<footnote>37The elements $\eta_i \in K$ are represented as vectors of rational coordinates in a fixed $\mathcal{O}_K$-basis, as explained in Section 2.6.</footnote>
**Proof. Part I: Setting up the log-matrix and assembling properties of the log-S-unit lattice.** Define $A = \max_j \|\text{Log}_S(\eta_j)\|$ and $\mu = (1000 \cdot \sqrt{n} \cdot \log(n)^3)^{-1}$. We know from Lemma 15.6 that $\mu \le \lambda_1(\text{Log}_S(\mathcal{O}_{K,S}^\times))$. Note that this lower bound is automatically also a lower bound for the first minimum of any sublattice of $\text{Log}_S(\mathcal{O}_{K,S}^\times)$.

Consider the exact matrix $\mathbf{G}$ where the rows consist of $\text{Log}_S(\eta_j)$ with $j \in \{1, \dots, k\}$, and compute an approximation $\tilde{\mathbf{G}} \in \mathbb{Q}^{k \times (n+|\mathbb{S}|)}$, with $\|\tilde{\mathbf{G}}_j - \mathbf{G}_j\| \le \varepsilon$ for each row, where we put

$$ \varepsilon = \mu \cdot 2^{-8k} \cdot \underbrace{\left( \frac{k \cdot 4^k \cdot A}{\mu} \right)^{-2(k+1)}}_{\le C_0^{-1} \text{ as in Theorem 23.5 (Buchmann-Kessler-Pohst)}} \cdot \underbrace{\frac{2^{-6} \cdot (n + |\mathbb{S}|)^{-(k+6)}}{\text{Determinant approximation}} \cdot 2^{-(2k+1)(k+2)} \cdot A^{-1} \cdot \mu}_{\le \frac{1}{4} \cdot \mu \cdot C_0^{-1}} \quad (157) $$

Note that from the exact representation of the $\eta_i$'s, one can compute approximations of the $\text{Log}_S(\eta_i)$'s with arbitrary precision $\varepsilon$ in time polynomial in size($\eta_i$), in $\log(\|\text{Log}_S(\eta_i)\|)$ and in $\log(1/\varepsilon)$. From our choice of $\varepsilon$, this is polynomial in $k$, $\log|\Delta_K|$, $\log(\max_j \|\text{Log}_S(\eta_j)\|) = \log(A)$, $|\mathbb{S}|$, and $\max_i(\text{size}(\eta_i))$ as expected. Moreover, the bit-size of the resulting matrix $\tilde{\mathbf{G}}$ is also polynomial in these quantities.

The quantity $\varepsilon$ is chosen such that the left part of the product in Equation (157) counteracts the loss in precision due to the Buchmann-Kessler-Pohst algorithm (Theorem 23.5), whereas the right part is the minimum precision required to make the determinant approximation work (as in Theorem 24.1).

**Part II: Applying the Buchmann-Kessler-Pohst algorithm.** We apply Theorem 23.5 to $\tilde{\mathbf{G}}$ with $r_0 = k$, $\mu \le \lambda_1(\text{Log}_S(\langle G \rangle))$ (as defined above) and we note that, by definition, $\|\mathbf{G}\|_{2,\infty} \le A$ which implies $\varepsilon < \frac{1}{4} \cdot \mu \cdot C_0^{-1}$ (for $C_0$ as in Theorem 23.5), so the prerequisites of the theorem are satisfied.

So, the algorithm of Theorem 23.5 outputs an $\mathbf{N}$ such that $\mathbf{B} := \mathbf{NG}$ is a basis of $\text{Log}_S(\langle G \rangle)$ and $\tilde{\mathbf{B}} := \mathbf{N}\tilde{\mathbf{G}}$ satisfies

$$ \|\mathbf{B} - \tilde{\mathbf{B}}\|_{2,\infty} \le C_0 \cdot \varepsilon \le 2^{-6} \cdot (n + |\mathbb{S}|)^{-(k+6)} \cdot 2^{-(2k+1)(k+2)} \cdot A^{-1} \cdot \mu^2 \quad (158) $$

Additionally, the rows $\mathbf{b}_j$ of $\mathbf{B}$ satisfy

$$ \|\mathbf{b}_j\| \le (\sqrt{rn} + 2) \cdot 2^{\frac{r-1}{2}} \cdot \lambda_j(\text{Log}_S(\langle G \rangle)), \quad (159) $$

where $r$ is the rank of the lattice $\text{Log}_S(\langle G \rangle)$.

Note that the pair $(\mathbf{N}, G)$ encodes a fundamental system of units of $\text{Log}_S(\langle G \rangle)$ in compact representation.

The Buchmann-Kessler-Pohst algorithm computes the rank $r$ of $\text{Log}_S(\langle G \rangle)$; we proceed only to Part III if this rank equals the rank of $\text{Log}_S(\mathcal{O}_{K,S}^\times)$, namely $n_{\mathbb{R}} + n_{\mathbb{C}} + |\mathbb{S}| - 1$. It thus remains to decide whether $\text{Log}_S(\langle G \rangle) = \text{Log}_S(\mathcal{O}_{K,S}^\times)$ or not. This is done by approximating determinants.

**Part III: Computing the determinant.** In order to apply Theorem 24.1 to the matrix $\tilde{\mathbf{B}}$ obtained, we need upper bounds on the quantities $\prod_{j=1}^r \frac{\|\mathbf{b}_j\|}{\lambda_j(\text{Log}_S(\langle G \rangle))}$ and $\|\mathbf{B}\|_2$, and a lower bound on the quantity $\lambda_1(\text{Log}_S(\langle G \rangle))$. Since $\text{Log}_S(\langle G \rangle)$ is a sublattice of $\text{Log}_S(\mathcal{O}_{K,S}^\times)$, we have already seen that $\lambda_1(\text{Log}_S(\langle G \rangle)) \ge \mu$.
By Equation (159), the output basis of the Buchmann-Kessler-Pohst algorithm satisfies

$$ \frac{\|\mathbf{b}_j\|}{\lambda_j(\mathrm{Log}_S(\langle G \rangle))} \le (\sqrt{rn} + 2) \cdot 2^{\frac{r-1}{2}} \le 2^{k+2}, $$

where the last inequality holds because $k \ge r$ and $r = n_\mathbb{R} + n_\mathbb{C} - 1 \ge n/2 - 1$ (since we proceeded to Part III). So, $\prod_{j=1}^r \frac{\|\mathbf{b}_j\|}{\lambda_j(\mathrm{Log}_S(\langle G \rangle))} \le 2^{k(k+2)}$.

Finally, we observe that

$$ \|\mathbf{B}\|_2 \le r \cdot \max_j \|\mathbf{b}_j\| \le r \cdot \max_j \left( \frac{\|\mathbf{b}_j\|}{\lambda_j(\mathrm{Log}_S(\langle G \rangle))} \right) \cdot \lambda_r(\mathrm{Log}_S(\langle G \rangle)) \le r \cdot 2^{k+2} \cdot A, $$

where for the last inequality we used the bound on $\frac{\|\mathbf{b}_j\|}{\lambda_j(\mathrm{Log}_S(\langle G \rangle))}$ computed above, and the fact that $A = \max_j \|\mathrm{Log}_S(\eta_j)\|$ is an upper bound on the last minimum of the lattice generated by the $\eta_j$'s.

Combining these bounds with Equation (158) (and using the fact that $k \ge r$ and $n + |\mathbb{S}| \ge r$), we obtain, using $(n + |\mathbb{S}|)^{-(k+6)} \cdot r \le (n + |\mathbb{S}|)^{-1} \cdot (n + |\mathbb{S}|)^{-(k+5)} \cdot r \le (n + |\mathbb{S}|)^{-1} \cdot r^{-(r+4)}$,

$$ \begin{aligned} \|\mathbf{B} - \tilde{\mathbf{B}}\|_{2,\infty} & \le 2^{-6} \cdot (n + |\mathbb{S}|)^{-(k+6)} \cdot 2^{-(2k+1)(k+2)} \cdot A^{-1} \cdot \mu^2 \\ & \le 2^{-6} \cdot (n + |\mathbb{S}|)^{-(k+6)} \cdot \underbrace{2^{-2k(k+2)}}_{\le (\prod_j \|\mathbf{b}_j\|/\lambda_j)^{-2}} \cdot \underbrace{r \cdot r^{-1} \cdot 2^{-(k+2)}}_{\le \|\mathbf{B}\|_2^{-1}} \cdot \underbrace{A^{-1}}_{\le \lambda_1^2} \cdot \underbrace{\mu^2}_{\le \lambda_1^2} \\ & \le 2^{-6} \cdot r^{-(r+4)} \cdot (n + |\mathbb{S}|)^{-1} \cdot \left( \prod_j \frac{\|\mathbf{b}_j\|}{\lambda_j(\mathrm{Log}_S(\langle G \rangle))} \right)^{-2} \cdot \lambda_1(\mathrm{Log}_S(\langle G \rangle))^2 / \|\mathbf{B}\|_2, \end{aligned} $$

as needed to apply Theorem 24.1 to the matrix $\tilde{\mathbf{B}}$. We conclude that from the knowledge of $\tilde{\mathbf{B}}$ and a rational number $D \in [\frac{3}{4}, \frac{5}{4}] \cdot \mathrm{Vol}(\mathrm{Log}_S(\mathcal{O}_{K,\mathbb{S}}^\times))$, we can decide whether $\mathrm{Log}_S(\langle G \rangle) = \mathrm{Log}_S(\mathcal{O}_{K,\mathbb{S}}^\times)$ or not.

**Part IV: The running time.** For the running time, we go through each part. For Part I, we have already seen that $\tilde{\mathbf{G}}$ can be computed in time polynomial in the desired quantities, and that its bit-size is also polynomial. For Part II, note that we applied the Buchmann-Kessler-Pohst algorithm as in Theorem 23.5, which takes time polynomial in $k$, $(n + |\mathbb{S}|)$, $\log(\|\mathbf{G}\|_{2,\infty})$, $\log(1/\mu)$ and the bit-size of $\tilde{\mathbf{G}}$. By definition of $\mu$, this is polynomial in the desired quantities. Moreover, the bit-size of the output matrix $\tilde{\mathbf{B}}$ is also polynomial in those same quantities.

For Part III, we first compute a rational $D \in [\frac{3}{4}, \frac{5}{4}] \cdot \mathrm{Vol}(\mathrm{Log}_S(\mathcal{O}_{K,\mathbb{S}}^\times))$, which can be done in time polynomial in $\log|\Delta_K|$ from Proposition 2.9 and Lemma 15.5. We then apply Theorem 24.1 to the matrix $\tilde{\mathbf{B}}$ and the rational number $D$. This takes time polynomial in the bit-sizes of $\tilde{\mathbf{B}}$ and $D$, which is polynomial in all the desired quantities. This concludes the proof. $\square$

## 26. LATTICE PRELIMINARIES

In this section, we succinctly treat lattice preliminaries required for understanding the next two sections (Sections 27 and 28) about a BKZ-variant by Hanrot, Stehlé and Pujol. This includes the Gram-Schmidt orthogonalization of a basis,
the potential of a basis, HKZ-reduced bases, Banaszczyk's transference theorem and the definition of a dually exponentially reduced basis.

## 26.1. Gram-Schmidt orthogonalization in $\mathbb{Z}$-bases.

**Notation 26.1.** For a basis $\mathbf{B} \in \mathbb{R}^{n \times n}$ we denote its Gram-Schmidt orthogonalization by $\mathbf{B}^* = (\mathbf{b}_1^*, \dots, \mathbf{b}_n^*)$. We denote the dual basis of $\mathbf{B}$ by $\mathbf{D} = (\mathbf{B}^{-1})^\top$ := $\mathbf{B}^{-\top} = (\mathbf{d}_1, \dots, \mathbf{d}_n) = (\mathbf{b}_1^\vee, \dots, \mathbf{b}_n^\vee)$. If $\mathbf{B}$ is a basis of $\Lambda$, then $\mathbf{D}$ is a basis of the dual lattice $\Lambda^\vee$ of $\Lambda$.

**Notation 26.2.** By a tilde, we generally denote an approximation. In this section, often a real-valued $\mathbf{B}$ is approximated by a basis $\tilde{\mathbf{B}}$ with rational coefficients. Likewise, an approximation of the dual basis $\tilde{\mathbf{D}}$ is denoted by $\tilde{\mathbf{D}}$.

**Notation 26.3.** For a basis $\mathbf{B} = (\mathbf{b}_1, \dots, \mathbf{b}_n) \in \mathbb{R}^{m \times n}$ we denote by $\mathbf{B}_{[j:k]}$ the basis $(\pi_{j-1}(\mathbf{b}_j), \dots, \pi_{j-1}(\mathbf{b}_k)) \in \mathbb{R}^{m \times (k+1-j)}$, where $\pi_{j-1} = \pi(\mathbf{b}_1, \dots, \mathbf{b}_{j-1})^\perp$ is the projection orthogonal to the linear subspace generated by $(\mathbf{b}_1, \dots, \mathbf{b}_{j-1})$. Note that $\mathbf{B}_{[1:k]}$ is just $(\mathbf{b}_1, \dots, \mathbf{b}_k)$.

**Definition 26.4** (Potential of a basis). For a basis $\mathbf{B} \in \mathbb{R}^{m \times n}$ we denote the potential by

$$P(\mathbf{B}) = \prod_{j=1}^{n} \|\mathbf{b}_j^*\|^{n+1-j} = \prod_{j=1}^{n} \mathrm{Vol}(\mathcal{L}(\mathbf{b}_1, \dots, \mathbf{b}_j)),$$

where $\mathcal{L}(\mathbf{b}_1, \dots, \mathbf{b}_j)$ is the lattice generated by $(\mathbf{b}_1, \dots, \mathbf{b}_j)$.

**Lemma 26.5.** Let $\mathbf{B} = (\mathbf{b}_1, \dots, \mathbf{b}_n) \in \mathbb{Z}^{m \times n}$ be a basis of the lattice $\Lambda$, then $\mathrm{Vol}(\mathcal{L}(\mathbf{b}_1, \dots, \mathbf{b}_{j-1}))^2 \cdot \mathbf{B}_{[j:n]} \in \mathbb{Z}^m$. In particular, $\mathrm{Vol}(\mathcal{L}(\mathbf{b}_1, \dots, \mathbf{b}_{j-1}))^2 \cdot \mathbf{b}_j^* \in \mathbb{Z}^m$ and hence $P(\mathbf{B})^2 \cdot \mathbf{B}^* \in \mathbb{Z}^{m \times n}$.

*Proof.* By the determinant formula for orthonormal projection [33, Vol. 1, Chapter IX, §4, Equation (21)] we have that, for $D_j := \det(\mathbf{B}_{[1:j-1]}^\top \mathbf{B}_{[1:j-1]})$, $D_j \mathbf{B}_{[j:n]} \in \mathbb{Z}^m$. In particular $D_j \mathbf{b}_j^* \in \mathbb{Z}^m$. Note that $D_j = \mathrm{Vol}(\mathcal{L}(\mathbf{b}_1, \dots, \mathbf{b}_{j-1}))^2$ by definition.

As a result, we certainly deduce that for $P(\mathbf{B})^2 = (\prod_{j=2}^n D_j) \cdot \mathrm{Vol}(\mathcal{L}(\mathbf{B}))^2$ we have $P(\mathbf{B})^2 \cdot \mathbf{b}_k^* \in \mathbb{Z}^m$ for any $k \in \{1, \dots, n\}$ (here, we use that $D_j \in \mathbb{Z}$ since $\mathbf{B} \in \mathbb{Z}^{m \times n}$). That is, $P(\mathbf{B})^2 \cdot \mathbf{B}^* \in \mathbb{Z}^{m \times n}$. $\square$

**Lemma 26.6.** Let $\mathbf{B} = (\mathbf{b}_1, \dots, \mathbf{b}_n) \in \mathbb{Z}^{m \times n}$ be a basis of the lattice $\Lambda$, then $\|\mathbf{b}_j^*\| \le \mathrm{Vol}(\mathcal{L}(\mathbf{b}_1, \dots, \mathbf{b}_j)) \le P(\mathbf{B})$.

*Proof.* We know that $\mathrm{Vol}(\mathcal{L}(\mathbf{b}_1, \dots, \mathbf{b}_j)) = \mathrm{Vol}(\mathcal{L}(\mathbf{b}_1, \dots, \mathbf{b}_{j-1})) \cdot \|\mathbf{b}_j^*\|$. Moreover, since $\mathbf{B}$ is integral, then $\mathrm{Vol}(\mathcal{L}(\mathbf{b}_1, \dots, \mathbf{b}_{j-1}))^2 \in \mathbb{Z}$, and so it is $\ge 1$ (because $\mathbf{B}$ is a basis, so its vectors are linearly independent). The inequality $\|\mathbf{b}_j^*\| \le \mathrm{Vol}(\mathcal{L}(\mathbf{b}_1, \dots, \mathbf{b}_j))$ follows. $\square$

**Definition 26.7.** We call a basis $\mathbf{B} = (\mathbf{b}_1, \dots, \mathbf{b}_n) \in \mathbb{R}^{m \times n}$ size-reduced if for all $0 < i < j \le n$

$$|\langle \mathbf{b}_i^*, \mathbf{b}_j \rangle| \le \frac{1}{2} \| \mathbf{b}_i^* \|^2.$$

**Lemma 26.8.** Let $\mathbf{B} \in \mathbb{Z}^{m \times n}$ be a size reduced basis of a lattice $\Lambda$. Then, for all $j \in \{1, \dots, n\}$,

$$\|\mathbf{b}_j\| \le \frac{\sqrt{n}}{2} \max_i \|\mathbf{b}_i^*\|.$$
*Proof.* Size reduced means that any basis vector $\mathbf{b}_j$ can be written as $\sum_{i=1}^{n} c_{ij} \mathbf{b}_i^*$ for $|c_{ij}| \le 1/2$. Hence, by the Pythagorean theorem, we have

$$ \|\mathbf{b}_j\|^2 = \sum_{i=1}^{n} c_{ij}^2 \|\mathbf{b}_i^*\|^2 \le \frac{n}{4} \max_j \|\mathbf{b}_i^*\|^2, $$

from which the claim follows. $\square$

**Corollary 26.9.** Let $\mathbf{B} \in \mathbb{Z}^{m \times n}$ be a size reduced basis of a lattice $\Lambda$. Then each coefficient in $\mathbf{B}$, $\mathbf{B}^*$ and $\mathbf{B}_{[j:k]}$ (for $k > j \in \mathbb{N}$) can be represented in $5 \log_2(n \cdot P(\mathbf{B})) + 3$ bits.

*Proof.* Each vector in $\mathbf{B}$ and $\mathbf{B}^*$ is bounded in Euclidean norm by $\sqrt{n} \cdot P(\mathbf{B})/2$, which is also an upper bound on the absolute value of each coefficient. Moreover, $\mathbf{B}$ is integral and the denominators occurring in $\mathbf{B}^*$ can be maximally $P(\mathbf{B})^2$. Every coefficient of $\mathbf{B}$ and $\mathbf{B}^*$ is then a rational number which can be represented by a fraction $a/b$ with $a, b$ integers, $|a| \le \sqrt{n} \cdot P(\mathbf{B})^3/2$ and $0 < b \le P(\mathbf{B})^2$. They can be represented by respectively by $\lceil \log_2(\sqrt{n} \cdot P(\mathbf{B})^3 + 1) \rceil$ and $\lceil \log_2(P(\mathbf{B})^2) \rceil$ bits.

Precisely the same reasoning can be used for $\mathbf{B}_{[i:j]}$, since $\mathrm{Vol}(\mathcal{L}(\mathbf{b}_1, \dots, \mathbf{b}_{j-1}))^2$. $\mathbf{B}_{[j:n]} \in \mathbb{Z}^m$ by Lemma 26.5 (and $\mathbf{B}_{[j:k]}$ consists of just the first $k-j+1$ vectors of $\mathbf{B}_{[j:n]}$). $\square$

## 26.2. HKZ reduction.

**Definition 26.10 (HKZ-reduced basis).** A basis $\mathbf{B} \in \mathbb{R}^{m \times n}$ of a lattice $\Lambda$ is called HKZ-reduced if it is size reduced and if

$$ \|\mathbf{b}_j^*\| = \lambda_1(\mathbf{B}_{[j:n]}) \text{ for all } j \in \{1, \dots, n\}, $$

i.e., if the Gram-Schmidt vector $\mathbf{b}_j^*$ attains the minimum of the projected lattice $\pi(\mathbf{b}_1, \dots, \mathbf{b}_{j-1})^\perp(\Lambda)$ for every $j \in \{1, \dots, n\}$.

**Lemma 26.11.** Let $\mathbf{B}$ be a HKZ-reduced basis of $\Lambda$, then

$$ P(\mathbf{B}) \le n^{2n^2} \min_{\mathbf{C}} P(\mathbf{C}), $$

where the minimum over the potential $P(\cdot)$ is over all bases $\mathbf{C}$ of $\Lambda$.

*Proof.* The HKZ reduced basis $\mathbf{B}$ satisfies $\frac{4}{i+3}\lambda_i(\Lambda)^2 \le \|\mathbf{b}_i\|^2 \le \frac{i+3}{4} \cdot \lambda_i(\Lambda)^2$ [47], hence (using $\frac{i+3}{4} \le i$ for $i \ge 1$),

$$ \begin{align} P(\mathbf{B}) &= \prod_{j=1}^{n} (\|\mathbf{b}_1^*\| \cdots \|\mathbf{b}_j^*\|) \le \prod_{j=1}^{n} (\|\mathbf{b}_1\| \cdots \|\mathbf{b}_j\|) \le \prod_{j=1}^{n} j^j (\lambda_1(\Lambda) \cdots \lambda_j(\Lambda)) \nonumber \\ &\le \prod_{j=1}^{n} j^j \cdot j^j \min_{\Lambda_j} \mathrm{Vol}(\Lambda_j) \le n^{2n^2} \prod_{j=1}^{n} \min_{\Lambda_j} \mathrm{Vol}(\Lambda_j) \le n^{2n^2} \min_{\mathbf{C}} P(\mathbf{C}). \tag{160} \end{align} $$

where the minimum $\min_{\Lambda_j}$ is over all $j$-dimensional sublattices $\Lambda_j \subseteq \Lambda$ and where the minimum $\min_{\mathbf{C}}$ is over all bases of $\Lambda$.

The third inequality of Equation (160) might require some explanation. Any $i$-dimensional sublattice $\Lambda_i \subseteq \Lambda$ satisfies $\lambda_j(\Lambda) \le \lambda_j(\Lambda_i)$ for all $j \in \{1, \dots, i\}$. Therefore, by Minkowski's second inequality,

$$ \lambda_1(\Lambda) \cdots \lambda_i(\Lambda) \le \lambda_1(\Lambda_i) \cdots \lambda_i(\Lambda_i) \le i^i \mathrm{Vol}(\Lambda_i). $$

$\square$
This lemma has as a consequence that applying the HKZ algorithm can only increase the potential of a basis by a factor $n^{2n^2}$.

**Corollary 26.12.** Let $\mathbf{B} \in \mathbb{R}^{m \times n}$ be a basis of the $n$-dimensional lattice $\Lambda$ and let $\mathbf{B}' = \text{HKZ}(\mathbf{B})$ be a HKZ-reduced basis of $\Lambda$. Then

$$P(\mathbf{B}') \leq n^{2n^2} P(\mathbf{B}).$$

*Proof.* We have $P(\mathbf{B}') \leq n^{2n^2} \cdot \min_{\mathbf{C}} P(\mathbf{C}) \leq n^{2n^2} P(\mathbf{B})$. $\square$

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

The following lemma is for when a *block* of $\mathbf{B}$ is being HKZ-reduced, which happens in the BKZ-algorithm.

**Corollary 26.13.** Let $\mathbf{B} \in \mathbb{R}^{m \times n}$ be a basis of a lattice $\Lambda$, let $\mathbf{b} \in \{2, \dots, n\}$, and let $\mathbf{C} = \mathbf{B}_{[k:k+b-1]}$ be a projected sub-block of $\mathbf{B}$. Suppose $\mathbf{U} \in GL_b(\mathbb{Z})$ is such that $\mathbf{C}' = \mathbf{CU}$ is HKZ-reduced and write $\mathbf{B}' = \mathbf{B}\bar{\mathbf{U}}$, where $\bar{\mathbf{U}}$ acts as $\mathbf{U}$ on the basis elements $(\mathbf{b}_k, \dots, \mathbf{b}_{k+b-1})$ and leaves the rest intact. Then

$$P(\mathbf{B}') \leq \mathbf{b}^{2\mathbf{b}^2} P(\mathbf{B}),$$

*Proof.* The action of $\mathbf{B}' = \mathbf{B}\bar{\mathbf{U}}$ only changes the vectors $(\mathbf{b}_k, \dots, \mathbf{b}_{k+b-1})$, but does not change the space spanned by $(\mathbf{b}_k, \dots, \mathbf{b}_{k+b-1})$. Hence, the Gram-Schmidt vectors $\mathbf{b}_j^*$ for $j \notin \{k, \dots, k+b-1\}$ also remain intact, as well as the volume $\text{Vol}(\mathcal{L}(\mathbf{b}_k, \dots, \mathbf{b}_{k+b-1})) = \prod_{j=k}^{k+b-1} \|\mathbf{b}_j^*\| = \prod_{j=k}^{k+b-1} \|(\mathbf{b}_j^*)^*\|$. So,

$$\frac{P(\mathbf{B}')}{P(\mathbf{B})} = \frac{\prod_{j=1}^{n} \|(\mathbf{b}_j^*)^*\|^{n+1-j}}{\prod_{j=1}^{n} \|\mathbf{b}_j^*\|^{n+1-j}} = \frac{\prod_{j=k}^{k+b-1} \|(\mathbf{b}_j^*)^*\|^{n+1-j}}{\prod_{j=k}^{k+b-1} \|\mathbf{b}_j^*\|^{n+1-j}} = \frac{\prod_{j=0}^{\mathbf{b}-1} \|(\mathbf{b}_j^*)^*\|^{\mathbf{b}-j}}{\prod_{j=0}^{\mathbf{b}-1} \|\mathbf{b}_j^*\|^{\mathbf{b}-j}} \\ = \frac{P(\mathbf{C}')}{P(\mathbf{C})} \leq \mathbf{b}^{2\mathbf{b}^2}.$$

where the last inequality follows from Corollary 26.12 and where the third equality follows from dividing by $\prod_{j=k}^{k+b-1} \|\mathbf{b}_j^*\|^{(n+1)-(b+k)}$ so that

$$\prod_{j=k}^{k+b-1} \|\mathbf{b}_j^*\|^{n+1-j} = \prod_{j=k}^{k+b-1} \|\mathbf{b}_j^*\|^{(b+k)-j} = \prod_{j=0}^{\mathbf{b}-1} \|\mathbf{b}_j^*\|^j,$$

and similarly for $(\mathbf{b}_j^*)^*$, where we use that $\prod_{j=k}^{k+b-1} \|\mathbf{b}_j^*\| = \prod_{j=k}^{k+b-1} \|(\mathbf{b}_j^*)^*\|$. $\square$

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

### 26.3. Reduction of dual bases.

**Definition 26.14** (A dually exponentially reduced basis). A square basis $\mathbf{B} \in \mathbb{R}^{n \times n}$ of a lattice $\Lambda$ is T-dually exponentially reduced (for $T \geq 1$) if the dual basis $\mathbf{D} = \mathbf{B}^{-\top}$ satisfies $\|\mathbf{d}_j\| \leq 2^{Tn} \lambda_j(\Lambda^\vee)$, where $\Lambda^\vee$ denotes the dual lattice of $\Lambda$.

26.4. **Transference theorems.** Banaszczyk proved the following transference theorem, relating the successive minima of a lattice $\Lambda$ with the ones of its dual lattice $\Lambda^\vee$.

**Theorem 26.15** ([6, Theorem 2.1]). Let $\Lambda$ be an arbitrary lattice of rank $n$ in $\mathbb{R}^m$, for some $m \geq n \geq 1$. Then, for all $1 \leq i \leq n$ it holds that

$$1 \leq \lambda_i(\Lambda) \cdot \lambda_{n-i+1}(\Lambda^\vee) \leq n.$$
*Proof.* The upper bound is exactly [6, Theorem 2.1]. The lower bound comes from the following standard argument. Let $v_1, \dots, v_i$ be $i$ linearly independent vectors of $\Lambda$ with euclidean norm $\le \lambda_i(\Lambda)$, and $w_1, \dots, w_{n-i+1}$ be $(n-i+1)$ linearly independent vectors of $\Lambda^\vee$ with euclidean norm $\le \lambda_{n-i+1}(\Lambda^\vee)$. Let $V$ be the vector space spanned by the $(v_j)_j$ and $W$ be the vector space spanned by the $(w_j)_j$. Both spaces live in span($\Lambda$), which has dimension $n$. Moreover, $\dim(V) + \dim(W) = n+1$. Hence, $V$ and $W$ cannot be orthogonal, which means that there should exist $v_k$ and $w_\ell$ such that $\langle v_k, w_\ell \rangle \ne 0$. By definition of the dual, this implies that $|\langle v_k, w_\ell \rangle| \ge 1$ (because the inner product must be an integer). And so, $1 \le |\langle v_k, w_\ell \rangle| \le \|v_k\| \cdot \|w_\ell\| \le \lambda_i(\Lambda) \cdot \lambda_{n-i+1}(\Lambda^\vee)$. $\square$

## 27. THE BKZ ALGORITHM ON INTEGER BASES

27.1. **Introduction.** In this section, we show that the variant of BKZ from Hanrot, Pujol and Stehlé [38, Algorithm 2] (which we call BKZ' in the rest of this section) does not cause coefficient explosion in integer basis matrices. Hence, BKZ' is suitable for integer lattice bases and one can obtain a bound on the bit-complexity of the algorithm, and not only the number of tours needed. This was already discussed in [38, Section 3, Cost of BKZ'], where the authors explained the big lines of the reasoning. In this section, we make this discussion fully formal.

Concretely, applying the **b-BKZ**' algorithm of Hanrot, Pujol and Stehlé on an integer basis **B** of a lattice **Λ** yields a new basis **C** = ($c_1, \dots, c_n$) of **Λ** satisfying $\|c_1\| \le 2 \cdot b^{\frac{n-1}{2(b-1)} + \frac{3}{2}} \cdot \text{Vol}(\Lambda)^{1/n}$. Furthermore, this algorithm runs in time $\text{poly}(n, \log \max_j \|\mathbf{b}_j\|) \cdot \mathbf{b}^b$.

*Approach.* In [38], the authors give an upper bound on the number of tours needed for the BKZ' algorithm, in order to have a provable upper bound on the short vector output by the algorithm. To obtain a total and provable bit-complexity for the time of the **b-BKZ**' variant for integer matrices, we need to show that no coefficient explosion occurs and that the **b-HKZ** algorithm on the sub-blocks runs in time about $\mathbf{b}^b$.

To show that no coefficient explosion occurs, we rely on standard techniques using the potential $P(\mathbf{B})$ of a basis. Namely, it is a fact that the bit sizes of the coefficients occurring in a size-reduced basis **B** and its Gram-Schmidt basis $\mathbf{B}^*$ are bounded by $O(\log_2(nP(\mathbf{B})))$ (see Corollary 26.9). Hence, it is enough to sufficiently bound the potential.

In the BKZ' algorithm of Hanrot, Pujol and Stehlé, only size-reduction and HKZ-reduction in dimension **b** occur (see Algorithm 7). As size-reduction does not change the potential, only the influence of HKZ-reduction on the potential needs to be examined. It can be shown that **b-HKZ-reduction** can only increase the potential of a basis by a factor $\mathbf{b}^{2b^2}$ (see Corollary 26.12). Hence, all coefficients remain sufficiently bounded, whenever the number of HKZ-reductions is polynomially bounded. But the latter is true by the fact that the number of 'BKZ tours' (essentially $n$ times a **b-HKZ-reduction**) is bounded; this is what Hanrot, Pujol and Stehlé show in their work [38, Theorem 1].

For the HKZ-reduction algorithm in dimension **b**, that is used as a subroutine in the BKZ-algorithm, we use the provable Kannan-algorithm [39] on integer matrices with a run time of about $\mathbf{b}^b$ (disregarding the size of the basis matrix). Note that the projected sub-blocks of the matrix are rational, but can be scaled up to be
integral. This does not significantly increase the bit-size, because the denominators can be shown to be bounded by the potential.

27.2. **The BKZ' algorithm of Hanrot, Pujol and Stehlé.** We restate the algorithm of Hanrot, Pujol and Stehlé [38, Algorithm 2] and their result on the upper bound on the number of tours required to obtain a sufficiently short non-zero vector of the input lattice.

**Algorithm 7** The BKZ' algorithm of Hanrot, Pujol and Stehlé, for integer bases

**Require:**

* A basis $\mathbf{B} = (\mathbf{b}_1, \dots, \mathbf{b}_n) \in \mathbb{Z}^{m \times n}$

* A block size $b \in \{1, \dots, n\}$.

**Ensure:** A basis of $\mathcal{L}(\mathbf{B})$.

1: **repeat**

2: **for** $k$ from $1$ to $n-b+1$ **do**

3: Modify $(\mathbf{b}_i)_{k \le i < k+b}$ so that $(\pi_{k-1}(\mathbf{b}_i))_{k \le i < k+b}$ is HKZ-reduced;

4: Size-reduce $(\mathbf{b}_1, \dots, \mathbf{b}_n)$.

5: **end for**

6: **until** no changes occur or termination is requested.

7: **return** $(\mathbf{b}_1, \dots, \mathbf{b}_n)$.

**Theorem 27.1** (Theorem 1 of [38]). There exists an absolute constant $C > 0$ such that the following holds for all $n$ and $b$. Let $\mathbf{B} = (\mathbf{b}_1, \dots, \mathbf{b}_n)$ be a basis of a lattice $\Lambda$, given as input to the modified BKZ algorithm (Algorithm 7) with block-size $b$. If terminated after

$$ \tau_{\text{BKZ}} = C \frac{n^3}{b^2} (\log n + \log \log \max_i \frac{\|\mathbf{b}_i\|}{\text{Vol}(\Lambda)^{1/n}}) $$

calls to an HKZ-reduction in dimension $b$, the output $\mathbf{C} = (\mathbf{c}_1, \dots, \mathbf{c}_n)$ is a basis of $\Lambda$ that satisfies

$$ \|\mathbf{c}_1\| \le 2b^{\frac{n-1}{2(b-1)} + \frac{3}{2}} \cdot \text{Vol}(\Lambda)^{1/n}. $$

**Remark 27.2.** In the original theorem statement [38, Theorem 1], the last line reads: "If $\Lambda \subseteq \mathbb{Q}^n$, then the overall cost$^{38}$ is $\le \text{poly}(n, \text{size}(\mathbf{B})) \cdot \text{Cost}_{\text{HKZ}}(b)$."

It is precisely this statement in the last line that we prove in this section. This, because the authors [38] only gave a sketch of how to show this ([38, Section 3, Cost of BKZ']). In this section we will follow their sketch and prove this statement rigorously.

27.3. **Applying BKZ' to integral bases.**

**Proposition 27.3.** Let $\mathbf{B} \in \mathbb{Z}^{m \times n}$ be a basis of a lattice $\Lambda$, with $m \ge n \ge 2$. Let $b \in \{2, \dots, n\}$ be a block-size parameter. Then the BKZ' algorithm of Hanrot, Pujol and Stehlé on input $\mathbf{B}$ and $b$ has a bit-complexity

$$ \text{poly}(\text{size}(\mathbf{B}), m) \cdot b^b $$

<footnote>$^{38}$Here, $\text{size}(\mathbf{B}) = \sum_{ij} \text{size}(\mathbf{B}_{ij})$ and $\text{size}(a/b) = \log |a| + \log |b|$ for reduced fractions $a/b$. The number $\text{Cost}_{\text{HKZ}}(b)$ is the cost of applying HKZ in dimension $b$.</footnote>
and outputs a basis $\mathbf{C} = (\mathbf{c}_1, \dots, \mathbf{c}_n)$ satisfying

$$ \|\mathbf{c}_1\| \le 2 \cdot \mathbf{b}^{\frac{n-1}{2(\mathbf{b}-1)} + \frac{3}{2}} \cdot \mathrm{Vol}(\Lambda)^{1/n} \le 2 \cdot \mathbf{b}^{2n/\mathbf{b}} \cdot \lambda_n(\Lambda). \quad (161) $$

*Proof.* We instantiate Theorem 27.1 with the integral basis $\mathbf{B}$, yielding the shortness bound<fnref n="39" /> in Equation (161) and an upper bound on the number of HKZ-reductions $\tau_{\text{BKZ}}$ in dimension $\mathbf{b}$. Note that $\tau_{\text{BKZ}}$ is $\text{poly}(n, \text{size}(\mathbf{B}))$, according to Theorem 27.1.

For the $\mathbf{b}$-HKZ reduction algorithm we use the provable Kannan-algorithm [39, Theorem 2]: on input an integral basis $\mathbf{M}$ of a rank-$\mathbf{b}$ lattice $L \subseteq \mathbb{Z}^m$, this algorithm runs in time $\text{poly}(\text{size}(\mathbf{M}), m) \cdot \mathbf{b}^{b/(2e)+o(\mathbf{b})} = \text{poly}(\text{size}(\mathbf{M}), m) \cdot \mathbf{b}^b$ and outputs an HKZ-reduced basis of $L$. We will apply this algorithm to the projected bases $\mathbf{B}_{[k:k+\mathbf{b}-1]}$ occurring in the BKZ' algorithm. Even though these bases are rational, this is still possible just by multiplying out the denominators of the coefficients (and revert that process after the lattice reduction). For this to be feasible, we will of course need to show that these coefficients are sufficiently small in size (i.e., have sufficiently small numerator and denominator).

Concluding, if we can show that all sizes of the coefficients occurring in the subblocks of all intermediately computed matrices in Algorithm 7 remain sufficiently bounded, say $\le \text{poly}(\text{size}(\mathbf{B}), m)$, we can indeed conclude that Algorithm 7 has bit-complexity $\text{poly}(\text{size}(\mathbf{B}), m)$.

So, indeed, it remains to show that all (rational) coefficients of the occurring bases, their Gram-Schmidt bases and the sub-blocks $\mathbf{B}_{[j:j+\mathbf{b}-1]}$ remain bounded in bit-size by $\text{poly}(\text{size}(\mathbf{B}), m)$. We distinguish some cases

* The very first time that a HKZ-reduction is applied is just on the basis $\mathbf{B}_{[1:\mathbf{b}]}$, whose coefficient sizes are clearly bounded by $\text{poly}(\log P(\mathbf{B}))$.

* After this very first time, we can, by line 4 always assume that the basis at hand, which we call $\mathbf{B}^{(0)}$ for now, is size-reduced right before line 3. Hence, the coefficients of $(\pi_{k-1}((\mathbf{b}_i^{(0)}))_{k \le i < k+\mathbf{b}}$ are bounded in size by $\text{poly}(\log P(\mathbf{B}^{(0)}))$, by Corollary 26.9. Hence Kannan's HKZ algorithm can reasonably applied in time $\text{poly}(\log(P(\mathbf{B}^{(0)})), m) \cdot \mathbf{b}^b$.

* Right after line 3 but before line 4, the new matrix $\mathbf{B}^{(1)} = \mathbf{B}^{(0)}\mathbf{U}$ (where $\mathbf{U}$ only changes $(\mathbf{b}_i^{(0)})_{k \le i < k+\mathbf{b}}$ is not size-reduced anymore. But we do know, by Corollary 26.12, that $P(\mathbf{B}^{(1)}) \le \mathbf{b}^{2\mathbf{b}^2} P(\mathbf{B}^{(0)})$. Since $(\pi_{k-1}(\mathbf{b}_i^{(1)}))_{k \le i < k+\mathbf{b}}$ is HKZ-reduced (and thus size-reduced by definition), we know that the coefficients of $\mathbf{B}_{[k:k+\mathbf{b}-1]}$ are bounded by $\text{poly}(\log(P(\mathbf{B}^{(1)})), m)$, by Corollary 26.9. Since for $i \notin \{k, \dots, k+\mathbf{b}-1\}$, $\mathbf{b}_i^{(0)}$ are unaffected by $\mathbf{U}$, we know that these still satisfy $\text{size}(\mathbf{b}_i^{(0)}) \le \text{poly}(\log(P(\mathbf{B}^{(0)})), m)$. Hence, we can certainly find a lift (by using Babai's nearest plane algorithm) of $\mathbf{B}^{(1)}_{[k:k+\mathbf{b}-1]}$ to $\mathbf{B}^{(1)}$ for which the coefficient sizes of $(\mathbf{b}_i^{(1)})_{k \le i < k+\mathbf{b}}$ are bounded by $\text{poly}(\log(P(\mathbf{B}^{(0)})), \log(P(\mathbf{B}^{(1)})), m) = \text{poly}(\log(P(\mathbf{B}^{(0)})) + \mathbf{b}, m)$. (Note that this lift does not affect the potential of $\mathbf{B}^{(1)}$.

Note that in the previous reasoning we see that in each HKZ-reduction, the potential of the basis the algorithm is working on is maximally increased by a factor $\mathbf{b}^{2\mathbf{b}^2}$.

<footnote n="39">³⁹The additional shortness bound in terms of $\lambda_n(\Lambda)$ comes from the fact that $\lambda_n(\Lambda)^n \ge \prod_{j=1}^n \lambda_j(\Lambda) \ge \mathrm{Vol}(\Lambda)$. For the simplification into $\mathbf{b}^{n/\mathbf{b}}$, one can observe that $(n-1)\mathbf{b}+3(\mathbf{b}-1)\mathbf{b} \le 4n(\mathbf{b}-1)$ for all $\mathbf{b}$ satisfying $2 \le \mathbf{b} \le n$. Dividing by $2(\mathbf{b}-1)\mathbf{b}$ yields the simplification.</footnote>
But we know that the maximum number of HKZ reductions in the entire algorithm is at most $\tau_{BKZ} \cdot n = \text{poly}(\text{size}(\mathbf{B}), m)$ (where $\tau_{BKZ}$ is the number of tours). Hence, the bases occurring in the algorithm can maximally have log potential of

$$ \log(\mathbf{B}_{\text{occurring}}) \le \log(b^{2b^2}) \cdot \tau_{\text{BKZ}} \cdot n + \log(P(\mathbf{B})) \le \text{poly}(\text{size}(\mathbf{B}), m). $$

Hence all occurring bases $\mathbf{B}_{\text{occurring}}$ have a logarithmic potential bounded by $\text{poly}(\text{size}(\mathbf{B}), m)$, which has as an immediate consequence that all bases, Gram-Schmidt bases and projected bases have coefficient sizes bounded by $\text{poly}(\text{size}(\mathbf{B}), m)$, which finishes the proof. $\square$

**Corollary 27.4.** Let $\mathbf{B} \in \mathbb{Z}^{m \times n}$ be a basis of a lattice $\Lambda$, with $m \ge n \ge 2$ and let $\mathbf{b} \in \{2, \dots, n\}$. Then there exists an algorithm that takes as input $\mathbf{B}$ and $\mathbf{b}$, has bit-complexity

$$ \text{poly}(m, \text{size}(\mathbf{B})) \cdot b^b $$

and outputs a basis $\mathbf{C} = (\mathbf{c}_1, \dots, \mathbf{c}_n)$ of $\Lambda$ satisfying

$$ \|\mathbf{c}_j\| \le n \cdot b^{2n/b} \cdot \lambda_n(\Lambda) \quad \text{for all } j \in \{1, \dots, n\}. \qquad (162) $$

*Proof.* We apply the provable BKZ' algorithm of Hanrot, Pujol and Stehlé as in Proposition 27.3, recursively to

$$ \mathbf{B}, \det(\mathbf{B}_{[1:1]})^2 \cdot \mathbf{B}_{2:n}, \dots, \det(\mathbf{B}_{[1:j]})^2 \cdot \mathbf{B}_{j+1:n}, \dots, \det(\mathbf{B}_{[1:n-b]})^2 \cdot \mathbf{B}_{n-b+1:n}. $$

Here, we keep using the notation $\mathbf{B}$ after an application of BKZ'. After these applications, we backwards recursively lift this sequence into a size-reduced basis of $\mathcal{L}(\mathbf{B})$.

More precisely we apply the following steps:

* Apply BKZ' to $\mathbf{B}$, call the result $\mathbf{B}$.

* Construct the basis $\det(\mathbf{B}_{[1:1]})\mathbf{B}_{[2:n]}$ (integral, by Lemma 26.5) and apply BKZ' to it, call the result again $\det(\mathbf{B}_{[1:1]})\mathbf{B}_{[2:n]}$.

* ...

* Construct the basis $\det(\mathbf{B}_{[1:j]})\mathbf{B}_{[j+1:n]}$ (integral) and apply BKZ' to it, call the result again $\det(\mathbf{B}_{[1:j]})\mathbf{B}_{[j+1:n]}$.

* ...

* Construct the basis $\det(\mathbf{B}_{[1:n-b]})^2 \cdot \mathbf{B}_{n-b+1:n}$ (integral) and apply BKZ' to it, call the result again $\det(\mathbf{B}_{[1:j]})\mathbf{B}_{[j+1:n]}$.

* Going backwards, add $c_k \mathbf{b}_{n-b}^*$ with $c_k \in [-1/2, 1/2)$ to each vector in $\mathbf{B}_{n-b+1:n}$ to reconstruct a short basis $\mathbf{B}_{n-b:n}$.

* ...

* Add $c_k \mathbf{b}_j^*$ with $c_k \in [-1/2, 1/2)$ to each vector in $\mathbf{B}_{j+1:n}$ to reconstruct a short basis $\mathbf{B}_{j:n}$.

* ...

* Add $c_k \mathbf{b}_j^*$ with $c_k \in [-1/2, 1/2)$ to each vector in $\mathbf{B}_{2:n}$ to reconstruct a short basis $\mathbf{B}$.

Since a BKZ'-reduction as in Proposition 27.3 consists of $\tau_{BKZ}$ HKZ-reductions, each BKZ' reduction can maximally increase the potential by a factor $b^{2b^2 \cdot \tau_{BKZ}}$ (see Corollary 26.12). Hence the $n-b$ BKZ'-reductions in above procedure can at most result in intermediate potentials of size

$$ b^{2b^2 \cdot \tau_{\text{BKZ}} \cdot n} \cdot P(\mathbf{B}_{\text{init}}), $$
where $\mathbf{B}_{\text{init}}$ is the starting basis. Since $\det(\mathbf{B}_{[1:k]})$ divide $P(\mathbf{B})$ (the potential of the same basis), and since $\mathbf{B}_{[k+1:n]}$ has size bounded in $O(\log(n \cdot P(\mathbf{B})))$ (see Corollary 26.9), we can immediately deduce that in above procedure, all bit sizes remain within (for the bound on $\tau_{\text{BKZ}}$ see Theorem 27.1)

$$ \log (nb^{2b \cdot \tau_{\text{BKZ}} \cdot n} \cdot P(\mathbf{B}_{\text{init}})) = \text{poly}(m, \text{size}(\mathbf{B}_{\text{init}})). $$

In the resulting basis, we have, by construction,

$$ \|\mathbf{b}_j^*\| \le 2 \cdot b^{2n/b} \cdot \lambda_n(\Lambda) \quad \text{for all } j \in \{1, \dots, n\}, $$

where we use that $\lambda_{n-j}(\mathcal{L}(\mathbf{B}_{j+1:n})) \le \lambda_n(\Lambda)$ and $b^{2(n-j)/b} \le b^{2n/b}$. For the last b vectors, we have this shortness guarantee from the b-HKZ reduction (see [47] or the proof of Lemma 26.11).

Hence, by the size-reduced-like way the basis $\mathbf{B}$ is constructed, we have $\mathbf{b}_j = \mathbf{b}_j^* + \sum_{i<j} c_i \mathbf{b}_i^*$ with $c_i \in [-1/2, 1/2)$, and we obtain

$$ \|\mathbf{b}_j\| \le 2n \cdot b^{2n/b} \cdot \lambda_n(\Lambda) \quad \text{for all } j \in \{1, \dots, n\}, $$

as required.

□

## 28. THE BKZ ALGORITHM ON APPROXIMATE BASES

28.1. **Introduction.** In this section, we will show that there exists a provable algorithm that runs essentially in time $O(b^b)$ that computes a basis of an ideal lattice $xa$ whose Gram-Schmidt lengths are at most $b^{O(n/b)} \lambda_n(xa)$, which is sufficient for the needs of this paper (see Sections 8.3 and 8.5). We assume throughout this entire section that an LLL-reduced basis of $O_K$ is given; in the end result, Lemma 8.5, this assumption is again explicitly mentioned.

In all this section, the ideal lattices $xa$ we considered will be represented exactly. To do so, we will restrict ourselves to elements $x \in K_{\mathbb{R}}^\times$ that have all their complex coordinates of the form $a + ib$, with $a, b \in \mathbb{Q}$. In other words, we consider the intersection of $K_{\mathbb{R}}$ with the subset $(\mathbb{Q} + i\mathbb{Q})^n$ of $\mathbb{C}^n$. The ideal $a$ is a fractional ideal, and will be represented by a $\mathbb{Z}$-basis, consisting of $n$ elements $(\alpha_1, \dots, \alpha_n)$ of $K$ (which can be exactly represented in a fixed basis of $O_K$).

Even though we have a way to represent the ideal lattice $xa$ exactly, we can only compute an *approximate basis* of the corresponding lattice, due to the (irrational) Minkowski embedding of $xa$ into $K_{\mathbb{R}}$ (even whenever $x \in K_{\mathbb{R}}^\times$ itself is rational). In this section we settle these precision issues by applying the basis reduction algorithms (LLL, BKZ') on rational approximations of the bases of $xa$.

The algorithm and its analysis consists of the following steps. These steps (i) - (v) will correspond with Sections 28.2 to 28.6

(i) **Computing an (approximate) dual basis of the basis of $xa$.** For the algorithm to succeed, the basis that we start with is required to be *dually reduced*. For the purpose of reducing it, we therefore first compute the dual basis of the input basis of $xa$ (which we may assume to be in some Hermite Normal form).
(ii) **Apply the Buchmann-Pohst-Kessler algorithm to this approximate dual basis.** To make the dual basis reduced, we apply the Buchmann-Pohst-Kessler algorithm [17, 18] (see also Section 23). We apply the inverse-transposed transformation to the original basis of $xa$, to obtain a dually exponentially reduced basis (see Definition 26.14). This part is treated in Section 28.3.

(iii) **Apply the variant of BKZ by Hanrot, Pujol and Stehlé [38].** Applying a variant of BKZ with provable running time on this dually exponentially reduced (approximate) basis of $xa$ yields an approximate basis of $xa$ with BKZ-like shortness guarantees on the basis vectors.

(iv) **Apply the closeness-lemma.** By computing an initial approximate basis with sufficiently good precision, the same unimodular transformation that makes this approximate basis have BKZ-like qualities, will also make the exact basis of $xa$ satisfy these shortness properties. Note that the unimodular transform can be actually exactly (that is, not approximately) applied to a $\mathbb{Z}$-basis of $xa$ which consists of elements $(x \cdot \alpha_1, \dots, x \cdot \alpha_n) \in K_{\mathbb{R}}$, where $\alpha_j \in K$.

(v) **Concluding.** Applying the compositions of the unimodular transformations in each step to the initial basis $(x \cdot \alpha_1, \dots, x \cdot \alpha_n)$ of $xa$ yields a new basis of $xa$ that has BKZ-like shortness guarantees.

## 28.2. Computing an (approximate) dual basis of the basis of $xa$.

*Introduction.* Computing the dual basis of an approximate basis $\tilde{\mathbf{B}}_{xa} \approx \mathbf{B}_{xa}$ of $xa$ is done by inverting and transposing the matrix: $\tilde{\mathbf{D}} = \mathbf{B}_{xa}^{-\top}$. The precision loss in numerical approximation of inversion is proportional to $\|\mathbf{B}_{xa}^{-1}\|$, the matrix norm of the inverse of the basis. Hence, we would like to upper bound this matrix norm.

We do that by applying Lemma 24.2, which bounds this matrix norm in terms of how far the basis vectors $\mathbf{B}_{xa}$ are from attaining the successive minima $\lambda_j(xa)$. Since we generally assume that ideals are given in a Hermite Normal Form (HNF) in coordinates of an LLL-reduced $\mathbb{Z}$-basis of $O_K$ (see Section 2.6), a reasonable upper bound on the basis vectors $\mathbf{B}_{xa}$ can be achieved. On the other hand, a lower bound on $\lambda_j(xa)$ can be achieved by using ideal lattice properties from Lemma 2.13.

To obtain these results, the following lemma will turn out useful.

**Lemma 28.1.** Let $x \in K_{\mathbb{R}}^{\times}$ and $a \in I_K$. Let $\mathbf{B}_{xa} = (x\alpha_1, \dots, x\alpha_n) \in K_{\mathbb{R}}^n$ a basis of $xa$, where the basis $(\alpha_1, \dots, \alpha_n)$ is assumed to be in HNF form whenever written in terms of an LLL-reduced basis of $O_K$ (see Section 2.6). Then

(i) For all $j \in \{1, \dots, n\}$, we have $\|xa_j\| \le 2^{\text{size}(xa)} \cdot n^{3/2} \cdot 2^n \cdot |\Delta_K|^{1/n}$.

(ii) $N(xa) \le 2^{n \cdot \text{size}(xa)}$.

(iii) $N(xa)^{-1} \le 2^{n \cdot \text{size}(xa)}$.

(iv) $\lambda_1(xa)^{-1} \le 2^{\text{size}(xa)}$.

where size is defined in Section 2.6.

*Proof.* For (i), we make use of the assumption that $a$ is represented by a rational HNF basis in terms of an LLL-reduced $\mathbb{Z}$-basis $(\beta_1, \dots, \beta_n)$ of $O_K$ (for which thus holds $\|\beta_j\| \le 2^n \cdot \sqrt{n} \cdot |\Delta_K|^{1/n}$ by Lemma 2.13). More precisely, $\alpha_j = \sum_{i=1}^n a_{ij}\beta_i$, where $(a_{ij})_{ij} \in \mathbb{Q}^{n \times n}$ is an HNF-reduced basis. By definition of the size of an ideal (see Section 2.6), we have that $\text{size}(a) \ge \text{size}(a_{ij})$. Recall that the size of rational numbers $a/b$ with $\text{gcd}(a, b) = 1$ is equal to $\log_2|a| + \log_2|b|$. Hence, using
$$ \text{size}(x\mathfrak{a}) = \text{size}(x) + \text{size}(\mathfrak{a}) $$

$$ \|x\alpha_j\| \le n \cdot \max_j |x_j| \cdot \max_{ij} 2^{\text{size}(a_{ij})} \cdot \underbrace{\max_j \|\beta_j\|}_{\le 2^n \cdot \sqrt{n} \cdot |\Delta_K|^{1/n}} \le 2^{\text{size}(x\mathfrak{a})} \cdot n^{3/2} \cdot 2^n \cdot |\Delta_K|^{1/n}. $$

For (ii) note that $N(x\mathfrak{a})$ is equal to $\det((a_{ij})_{ij}) \cdot \prod_j x_j$. By Hadamard's bound, $\det((a_{ij})_{ij}) \le \prod_j \|(a_{ij})_i\|_2 \le \prod_j (\sum_i |a_{ij}|)$ (by the inequality between 1 and 2-norms) and the latter can be bounded by $(\sum_i |a_{ij}|)^n$ and hence $\log_2 N(x\mathfrak{a}) \le n \text{ size}(x) + n \log_2(\sum_i |a_{ij}|) \le n \text{ size}(x) + n \text{ size}(\mathfrak{a}) = n \text{ size}(x\mathfrak{a})$.

Item (iii) can be proven as follows. Because $N(x\mathfrak{a}) = |N(x)| \cdot N(\mathfrak{a})$ and $|N(x)|^{-1} = \prod_{j=1}^n |x_j|^{-1} \le 2^{\text{size}(x)}$, we only need to show that $N(\mathfrak{a})^{-1} \le 2^{n \text{ size}(\mathfrak{a})}$. Write $\mathfrak{a} = \frac{1}{d} \cdot \mathfrak{b}$ with $d$ a minimal positive integer and $\mathfrak{b}$ an integral ideal. Since $d$ minimally clears the denominators of $\mathfrak{a}$, we certainly have $\text{size}(d) \le \text{size}(\mathfrak{a})$. Now $N(\mathfrak{a})^{-1} = N(\mathfrak{a}^{-1}) = |N(d)| \cdot N(\mathfrak{b})^{-1} \le |N(d)| = d^n \le 2^{n \text{ size}(d)} \le 2^{n \text{ size}(\mathfrak{a})}$.

Item (iv) holds because $x\mathfrak{a}$ is an ideal lattice, which implies $\lambda_1(x\mathfrak{a}) \ge N(x\mathfrak{a})^{1/n}$ due to item (i) from Lemma 2.13. Hence $\lambda_1(x\mathfrak{a})^{-1} \le N(x\mathfrak{a})^{-1/n}$ and the result follows from item (iii) $\square$

Bounding the matrix norm of $\mathbf{B}_{x\mathfrak{a}}^{-1}$. We start by bounding the matrix norm of the exact inverse of $\mathbf{B}_{x\mathfrak{a}}$.

**Lemma 28.2.** Let $x \in K_{\mathbb{R}}^{\times}$ and $\mathfrak{a} \in \mathcal{I}_K$. Let $\mathbf{B}_{x\mathfrak{a}} = (x\alpha_1, \dots, x\alpha_n) \in K_{\mathbb{R}}^n$ a basis of $x\mathfrak{a}$, where the basis $(\alpha_1, \dots, \alpha_n)$ is assumed to be in HNF form whenever written in terms of an LLL-reduced basis of $\mathcal{O}_K$ (see Section 2.6). Then

$$ \|\mathbf{B}_{x\mathfrak{a}}^{-1}\|_2 \le n^{2n+1} \cdot 2^{n^2} \cdot |\Delta_K|^{1/2} \cdot 2^{(2n+1) \text{ size}(x\mathfrak{a})}. $$

*Proof.* We apply Lemma 24.2 to obtain

$$ \begin{aligned} \|\mathbf{B}_{x\mathfrak{a}}^{-1}\|_2 &\le n^{n/2+1} \cdot \lambda_1(x\mathfrak{a})^{-1} \cdot \left( \prod_{j=1}^n \frac{\|x\alpha_j\|}{\lambda_j(x\mathfrak{a})} \right) \\ &\le n^{n/2+1} \cdot \lambda_1(x\mathfrak{a})^{-1} \cdot |\Delta_K|^{-1/2} \cdot N(x\mathfrak{a})^{-1} \cdot \prod_{j=1}^n \|x\alpha_j\|. \quad (163) \end{aligned} $$

where we used $\prod_{j=1}^n \lambda_j(x\mathfrak{a}) \ge \text{Vol}(x\mathfrak{a}) = N(x\mathfrak{a}) |\Delta_K|^{1/2}$ in the last inequality.

Using that $N(x\mathfrak{a})^{-1} \le 2^{n \text{ size}(x\mathfrak{a})}$, $\lambda_1(x\mathfrak{a})^{-1} \le 2^{\text{size}(x\mathfrak{a})}$ and $\|x\alpha_j\| \le 2^{\text{size}(x\mathfrak{a})} \cdot n^{3/2} \cdot 2^n \cdot |\Delta_K|^{1/n}$ for all $j \in \{1, \dots, n\}$ (see Lemma 28.1(iii), (iv) and (i)), and applying it to Equation (163), we obtain

$$ \begin{aligned} \|\mathbf{B}_{x\mathfrak{a}}^{-1}\|_2 &\le n^{n/2+1} \cdot \lambda_1(x\mathfrak{a})^{-1} \cdot |\Delta_K|^{-1/2} \cdot N(x\mathfrak{a})^{-1} \cdot \prod_{j=1}^n \|x\alpha_j\| \\ &\le n^{n/2+1} \cdot 2^{\text{size}(x\mathfrak{a})} \cdot |\Delta_K|^{-1/2} \cdot 2^{n \text{ size}(x\mathfrak{a})} \cdot (2^{\text{size}(x\mathfrak{a})} \cdot n^{3/2} \cdot 2^n \cdot |\Delta_K|^{1/n})^n \\ &\le n^{2n+1} \cdot 2^{n^2} \cdot |\Delta_K|^{1/2} \cdot 2^{(2n+1) \text{ size}(x\mathfrak{a})}. \end{aligned} \quad \square $$

We can therefore conclude that the loss in precision by inverting an approximate basis of $x\mathfrak{a}$ can be reasonably upper bounded.
**Lemma 28.3.** Let $\tilde{\mathbf{B}}_{xa} \in \mathbb{Q}^{n \times n}$ be an approximation of $\mathbf{B}_{xa}$, then

$$ \log_2 \|\tilde{\mathbf{B}}_{xa}^{-1} - \mathbf{B}_{xa}^{-1}\|_2 \le \log_2 \|\tilde{\mathbf{B}}_{xa} - \mathbf{B}_{xa}\|_2 + 5n^2 + \frac{1}{2} \log_2 |\Delta_K| + 3n \text{ size}(xa), $$
under the assumption that $\log_2 \|\mathbf{B}_{xa} - \tilde{\mathbf{B}}_{xa}\|_2 \le -(5n^2 + \frac{1}{2} \log_2 |\Delta_K| + 3n \text{ size}(xa))$. 

*Proof.* By [7, Cor. 7.2, Eq. 7.46], we have that

$$ \|\mathbf{B}^{-1} - \tilde{\mathbf{B}}^{-1}\|_2 \le 2\|\mathbf{B}^{-1}\|_2^2 \cdot \|\mathbf{B} - \tilde{\mathbf{B}}\|_2, $$

as long as $2\|\mathbf{B}^{-1}\|_2 \cdot \|\mathbf{B} - \tilde{\mathbf{B}}\|_2 \le 1$. Instantiating with $\mathbf{B} = \mathbf{B}_{xa}$, $\tilde{\mathbf{B}} = \tilde{\mathbf{B}}_{xa}$ and the bound of Lemma 28.2, we obtain the claim, using the following computation:

$$ \begin{aligned} \log_2(2\|\mathbf{B}_{xa}^{-1}\|) &\le 1 + (2n+1)\log_2(n) + n^2 + \frac{1}{2}\log|\Delta_K| + (2n+1)\text{size}(xa) \\ &\le 2n + 2n^2 + n^2 + \frac{1}{2}\log|\Delta_K| + (2n+1)\text{size}(xa) \\ &\le 5n^2 + \frac{1}{2}\log|\Delta_K| + 3n\text{ size}(xa) \end{aligned} $$

using the fact that for any positive integer $n$ it holds that $2n \le 2n^2$, $\log_2(n) \le n$ and $\log_2(n) + 1 \le 2n$. The condition $2\|\mathbf{B}^{-1}\|_2 \cdot \|\mathbf{B} - \tilde{\mathbf{B}}\|_2 \le 1$ holds by the assumption in the lemma's statement. $\square$

Hence, the inversion of the approximate basis $\tilde{\mathbf{B}}_{xa}$ only yields a polynomial (in the size of the input) loss of bit precision.

**Lemma 28.4.** Let $\tilde{\mathbf{B}}_{xa}$ be an approximation of a T-dually exponentially reduced basis $\mathbf{B}_{xa}$ with $\log\|\tilde{\mathbf{B}}_{xa} - \mathbf{B}_{xa}\|_2 \le -(9n^2 + \frac{5}{2} \log_2 |\Delta_K| + 5n \text{ size}(xa) + n(T+2))$. Then $\tilde{\mathbf{B}}_{xa}$ is $(T+3)$-dually exponentially reduced.

*Proof.* Let us write $(\mathbf{d}_1, \dots, \mathbf{d}_n) = \mathbf{D} = \mathbf{B}_{xa}^{-\top}$ and $(\tilde{\mathbf{d}}_1, \dots, \tilde{\mathbf{d}}_n) = \tilde{\mathbf{D}} = \tilde{\mathbf{B}}_{xa}^{-\top}$. Let us also define $\varepsilon$ such that $\log_2(1/\varepsilon) = 4n^2 + 2 \log_2 |\Delta_K| + 2n \text{ size}(xa)$. By Lemma 28.3 (and since transposing does not change the 2-norm of matrices), we have

$$ \begin{aligned} \log_2 \|\mathbf{D} - \tilde{\mathbf{D}}\|_2 &\le \log_2 \|\tilde{\mathbf{B}}_{xa} - \mathbf{B}_{xa}\|_2 + 5n^2 + \frac{1}{2} \log_2 |\Delta_K| + 3n \text{ size}(xa) \\ &\le -(4n^2 + 2 \log_2 |\Delta_K| + 2n \text{ size}(xa)) \le \log(\varepsilon). \end{aligned} $$

Then, we have, for all $j$ that $\|\tilde{\mathbf{d}}_j - \mathbf{d}_j\| = \|(\mathbf{D} - \tilde{\mathbf{D}})\mathbf{e}_j\| \le \|\mathbf{D} - \tilde{\mathbf{D}}\|_2 \le \varepsilon$, which implies that

$$ \|\tilde{\mathbf{d}}_j\| = \|\mathbf{d}_j\| + \varepsilon \le 2^{Tn} \lambda_j((xa)^{\vee}) + \varepsilon \le (2^{Tn} + 1)\lambda_j((xa)^{\vee}) \le 2^{(T+1)n} \lambda_j((xa)^{\vee}), \quad (164) $$

where, in the second inequality, we used the fact that $\varepsilon \le \lambda_1((xa)^{\vee})$. This inequality comes from combining the transference bound (Theorem 26.15) with items (ii) and (iv) from Lemma 2.13 and item (ii) of Lemma 28.1

$$ \begin{aligned} \lambda_1((xa)^{\vee}) &\ge \lambda_n(xa)^{-1} \ge (\sqrt{n} \cdot |\Delta_K|^{3/2} \cdot \mathcal{N}(xa)^{1/n})^{-1} \\ &\ge (\sqrt{n} \cdot |\Delta_K|^{3/2} \cdot 2^{\text{size}(xa)})^{-1} \ge \varepsilon \end{aligned} $$

Writing $\tilde{\Lambda}$ for the lattice generated by the approximation $\tilde{\mathbf{B}}_{xa}$, it suffices to show that $\lambda_j((xa)^{\vee}) \le 2n\lambda_j(\tilde{\Lambda}^{\vee})$ for all $j$, to show that $\tilde{\mathbf{B}}_{xa}$ is $(T+2)$-dually exponentially reduced. Indeed, then, by Equation (164), we have $\|\tilde{\mathbf{d}}_j\| \le 2^{(T+1)n}\lambda_j((xa)^{\vee}) \le 2^{(T+3)n}\lambda_j(\tilde{\Lambda}^{\vee})$ for all $j$.
By transference (see Theorem 26.15), we have

$$ \frac{1}{n} \le \frac{\lambda_j(\tilde{\Lambda}^\vee) \cdot \lambda_{n-j}(\tilde{\Lambda})}{\lambda_j(\tilde{\Lambda}^\vee) \cdot \lambda_{n-j}(\tilde{\Lambda})} \le n $$

hence $\lambda_j(\tilde{\Lambda}^\vee) \le n \frac{\lambda_{n-j}(\tilde{\Lambda})}{\lambda_{n-j}(\tilde{\Lambda})} \cdot \lambda_j(\tilde{\Lambda}^\vee) \le 2n \cdot \lambda_j(\tilde{\Lambda}^\vee)$, if one shows that $\frac{\lambda_{n-j}(\tilde{\Lambda})}{\lambda_{n-j}(\tilde{\Lambda})} \le 2$, i.e., $\lambda_j(\tilde{\Lambda}) \le 2\lambda_j(\tilde{\Lambda})$ for all $j$. This latter statement is what we finish the proof with.

Write $\mathbf{x}_j \in \mathbf{x}\mathbf{a} = \Lambda$ for the vector attaining $\lambda_j(\mathbf{x}\mathbf{a})$. Then $\mathbf{x}_j = \mathbf{B}_{\mathbf{x}\mathbf{a}}\mathbf{u}_j$ for some $\mathbf{u}_j \in \mathbb{Z}^n$. By the closeness lemma (Lemma 28.6), we must have $\|\mathbf{u}_j\| \le 2^{(T+2)n} \cdot \lambda_j(\mathbf{x}\mathbf{a})/\lambda_1(\mathbf{x}\mathbf{a}) \le 2^{(T+2)n} \cdot |\Delta_K|^{1/n}$ (by Lemma 2.13). Hence $\tilde{\mathbf{x}}_j = \tilde{\mathbf{B}}_{\mathbf{x}\mathbf{a}}\mathbf{u}_j = \mathbf{x}_j + (\mathbf{B}_{\mathbf{x}\mathbf{a}} - \tilde{\mathbf{B}}_{\mathbf{x}\mathbf{a}})\mathbf{u}_j$ satisfy the property that $\{\tilde{\mathbf{x}}_1, \dots, \tilde{\mathbf{x}}_j\}$ span a $j$-dimensional space, and therefore surely

$$ \begin{aligned} \lambda_j(\tilde{\Lambda}) &\le \lambda_j(\mathbf{x}\mathbf{a}) + \|\mathbf{B}_{\mathbf{x}\mathbf{a}} - \tilde{\mathbf{B}}_{\mathbf{x}\mathbf{a}}\|_2 \cdot 2^{(T+2)n} \cdot |\Delta_K|^{1/n} \\ &\le \lambda_j(\mathbf{x}\mathbf{a}) + \lambda_1(\mathbf{x}\mathbf{a}) \le 2 \cdot \lambda_j(\mathbf{x}\mathbf{a}), \end{aligned} $$

since $\|\mathbf{B}_{\mathbf{x}\mathbf{a}} - \tilde{\mathbf{B}}_{\mathbf{x}\mathbf{a}}\|_2 \le 2^{-n \text{ size}(\mathbf{x}\mathbf{a}) - \log |\Delta_K| - (T+2)n} \le \mathcal{N}(\mathbf{x}\mathbf{a})^{1/n} \cdot |\Delta_K|^{-1/n} \cdot 2^{-(T+2)n} \le \lambda_1(\mathbf{x}\mathbf{a}) \cdot 2^{-(T+2)n} \cdot |\Delta_K|^{-1/n}$ (where we used item (i) from Lemma 2.13). $\square$

**28.3. Applying Buchmann-Pohst-Kessler to the approximate dual basis.** We apply Theorem 23.5 with $k = r_0 = n_2 = [K : \mathbb{Q}] =: n$, $n_1 = 0$, $\mathbf{A} = \mathbf{B}_{\mathbf{x}\mathbf{a}}^{-\top}$ and $\tilde{\mathbf{A}} = \tilde{\mathbf{B}}_{\mathbf{x}\mathbf{a}}^{-\top}$. To satisfy the initial conditions, we must have $\log_2 \|\mathbf{B}_{\mathbf{x}\mathbf{a}}^{-\top} - \tilde{\mathbf{B}}_{\mathbf{x}\mathbf{a}}^{-\top}\|_{2,\infty} < \log_2(1/4 \cdot \mu \cdot C_0^{-1})$, where$^{40}$ $\mu = \mathcal{N}(\mathbf{x}\mathbf{a})^{-1/n} \cdot n^{-1/2} \cdot |\Delta_K|^{-3/2n} \le \lambda_n(\mathbf{x}\mathbf{a})^{-1} \le \lambda_1((\mathbf{x}\mathbf{a})^\vee)$. And

$$ C_0 = 2^{8n} \cdot \left( \frac{n \cdot 4^n \cdot \|\mathbf{B}_{\mathbf{x}\mathbf{a}}^{-\top}\|_{2,\infty}}{\mu} \right)^{2(n+1)} $$

By Lemma 28.2, we have that $\|\mathbf{B}_{\mathbf{x}\mathbf{a}}^{-\top}\|_{2,\infty} \le \|\mathbf{B}_{\mathbf{x}\mathbf{a}}^{-\top}\|_2 \le n^{2n+1} 2^{n^2} |\Delta_K|^{1/2} \cdot 2^{2n \text{ size}(\mathbf{x}\mathbf{a})}$. Hence, $-\log_2(1/4 \cdot \mu \cdot C_0^{-1}) = O(n^3+n \log |\Delta_K|+n^2 \text{ size}(\mathbf{x}\mathbf{a}))$, and a precision polynomial in $n, \log |\Delta_K|$ and size($\mathbf{x}\mathbf{a}$) is sufficient to apply Buchmann-Pohst-Kessler. Hence we obtain a unimodular transformation $\mathbf{U}$ such that the basis elements of $\mathbf{B}_{\mathbf{x}\mathbf{a}}^{-\top} \cdot \mathbf{U}$ have an LLL-like shortness quality compared to the successive minima of $(\mathbf{x}\mathbf{a})^\vee$. More precisely, the basis elements $(\mathbf{c}_1, \dots, \mathbf{c}_n) = \mathbf{B}_{\mathbf{x}\mathbf{a}}^{-\top} \cdot \mathbf{U}$ satisfy

$$ \|\mathbf{c}_j\| \le (n+2)^{\frac{n-1}{2}} \cdot \lambda_j(\mathbf{x}\mathbf{a}^\vee) \le 2^{3n} \cdot \lambda_j(\mathbf{x}\mathbf{a}^\vee), $$

hence, the basis $\mathbf{C}_{\mathbf{x}\mathbf{a}} := (\mathbf{B}_{\mathbf{x}\mathbf{a}}^{-\top} \cdot \mathbf{U})^{-\top} = \mathbf{B}_{\mathbf{x}\mathbf{a}} \mathbf{U}^{-\top}$ is $T$-dually exponentially reduced with $T := 3$ (see Definition 26.14). For this last computation, note that both inverse and transpose switch positions, hence doing them both keeps the positions of the matrices.

We can conclude with the following proposition.

**Proposition 28.5.** There exists an algorithm that computes a 3-dually exponentially reduced $\mathbb{Z}$-basis $(x\alpha_1, \dots, x\alpha_n)$ of an ideal lattice $\mathbf{x}\mathbf{a}$ in time polynomial in $n, \log |\Delta_K|$ and size($\mathbf{x}\mathbf{a}$).

*Proof.* Computing $\tilde{\mathbf{B}}_{\mathbf{x}\mathbf{a}}$ with sufficient precision of order $O(n^3+n \log |\Delta_K|+n^2 \text{ size}(\mathbf{x}\mathbf{a}))$ allows for computing the dual basis $\tilde{\mathbf{B}}_{\mathbf{x}\mathbf{a}}^{-\top} = (\tilde{\mathbf{B}}_{\mathbf{x}\mathbf{a}}^{-1})^{\top}$ and applying the Buchmann-Kessler-Pohst algorithm (see Lemma 28.3 and the discussion above). Hence, by applying the inverse transpose $\mathbf{U}^{-\top}$ of the unimodular matrix $\mathbf{U}$ that is the output

<footnote>$^{40}$We have $\lambda_n(\mathbf{x}\mathbf{a}) \le \sqrt{n} \cdot |\Delta_K|^{3/2n} \cdot \mathcal{N}(\mathbf{x}\mathbf{a})^{1/n}$ by items (ii) and (iv) of Lemma 2.13.</footnote>
of the Buchmann-Kessler-Pohst algorithm to the initial $\mathbb{Z}$-basis $(x\alpha_1, \dots, x\alpha_n)$ of $xa$ yields a 3-dually exponentially reduced basis of $xa$. $\square$

**28.4. Applying the variant of BKZ by Hanrot, Pujol and Stehlé.** By clearing the denominators in the (new, dually exponentially reduced) matrix $\tilde{\mathbf{B}}_{xa}$, we obtain an integer basis on which we can apply Algorithm 7, a variant of the BKZ algorithm from Hanrot, Pujol and Stehlé. By Corollary 27.4, this algorithm outputs in time$^{41}$ poly$(n, \text{size}(\tilde{\mathbf{B}}_{xa})) \cdot \mathbf{b}^b$ a basis $\tilde{\mathbf{C}}_{xa} = (\mathbf{c}_1, \dots, \mathbf{c}_n)$ of $xa$ that satisfies

$$ \|\mathbf{c}_j\| \le n \cdot \mathbf{b}^{2n/b} \cdot \lambda_n(xa). $$

**28.5. The closeness lemma.**

**Lemma 28.6.** Let $\mathbf{B} \in \mathbb{R}^{m \times n}$ be basis of a rank-$n$ lattice $\Lambda$ that is T-dually exponentially reduced as in Definition 26.14 and let $\mathbf{v} \in \Lambda$ be any lattice vector, with $\mathbf{v} = \mathbf{B}\mathbf{u}$ for some integral vector $\mathbf{u}$. Then

$$ \|\mathbf{u}\|^2 \le n^3 \cdot 2^{nT} \cdot \|\mathbf{v}\|^2 / \lambda_1(\Lambda)^2 \le 2^{n(T+2)} \cdot \|\mathbf{v}\|^2 / \lambda_1(\Lambda)^2. $$

*Proof.* Write $\mathbf{Q} = \mathbf{B}^\top\mathbf{B}$ for the quadratic form associated to $\mathbf{B}$; then $\mathbf{Q}^{-1} = (\mathbf{B}^\top\mathbf{B})^{-1} = \mathbf{B}^{-1}\mathbf{B}^{-\top} = \mathbf{D}^\top\mathbf{D}$ is the quadratic form associated to the dual basis $\mathbf{D} = \mathbf{B}^{-\top} = (\mathbf{d}_1, \dots, \mathbf{d}_n)$ of $\mathbf{B}$.

Denote $\Lambda^\vee$ for the dual lattice of $\Lambda$. By $\mathbf{B}$ being T-dually exponentially reduced, we have $(\mathbf{Q}^{-1})_{jj} = \|\mathbf{d}_j\|^2 \le 2^{Tn} \cdot \lambda_j(\Lambda^\vee)^2 \le n^2 \cdot 2^{T \cdot n} / \lambda_{n-j+1}(\Lambda)^2$ by Banaszczyk's transference theorem (Theorem 26.15). Therefore

$$ \mathrm{Tr}(\mathbf{Q}^{-1}) = \sum_{i=1}^{n} (\mathbf{Q}^{-1})_{ii} \le n^2 \cdot 2^{Tn} \sum_{i=1}^{n} \frac{1}{\lambda_i(\Lambda)^2} \le n^3 \cdot 2^{Tn} / \lambda_1(\Lambda)^2. $$

Write $\mu_1, \dots, \mu_n > 0$ for the eigenvalues of the positive definite matrix $\mathbf{Q}$. Then, for all $i \in \{1, \dots, n\}$, $\frac{1}{\mu_i} \le \mathrm{Tr}(\mathbf{Q}^{-1}) \le n^3 \cdot 2^{Tn} / \lambda_1(\Lambda)^2$, since all eigenvalues of $\mathbf{Q}$ are positive. Therefore, the inverse of any eigenvalue of $\mathbf{Q}$ is upper bounded by $n^3 \cdot 2^{Tn} / \lambda_1(\Lambda)^2$,

Write $\mathbf{v} = \mathbf{B}\mathbf{u}$, then

$$ \|\mathbf{u}\|^2 = \mathbf{u}^\top \mathbf{u} \le \frac{\mathbf{u}^\top \mathbf{Q} \mathbf{u}}{\min_i \mu_i} \le \|\mathbf{v}\|^2 \cdot \frac{n^3 \cdot 2^{Tn}}{\lambda_1(\Lambda)^2} $$

which, together with the fact that $n^3 \le 2^{2n}$, proves the claim. $\square$

**Corollary 28.7.** Let $\tilde{\mathbf{B}}$ and $\mathbf{B} \in \mathbb{R}^{m \times n}$ be T-dually exponentially reduced bases of rank-$n$ lattices $\tilde{\Lambda}$ and $\Lambda$ respectively.

Then

$$ \left( 1 - \frac{2^{(T+2)n} \cdot \|\tilde{\mathbf{B}} - \mathbf{B}\|_2}{\min(\lambda_1(\Lambda), \lambda_1(\tilde{\Lambda}))} \right) \le \frac{\lambda_j(\Lambda)}{\lambda_j(\tilde{\Lambda})} \le \left( 1 + \frac{2^{(T+2)n} \cdot \|\tilde{\mathbf{B}} - \mathbf{B}\|_2}{\min(\lambda_1(\Lambda), \lambda_1(\tilde{\Lambda}))} \right) \\ \text{and } |\lambda_1(\tilde{\Lambda}) - \lambda_1(\Lambda)| \le 2^{(T+2)n} \cdot \|\tilde{\mathbf{B}} - \mathbf{B}\|_2. $$

<footnote>$^{41}$Clearing denominators in a basis $\mathbf{B} \in \mathbb{Q}^{m \times n}$ at most increases the size of that basis by $2 \cdot m \cdot n$. Since $d\mathbf{B}$ for $d = \prod_{ij} d_{ij}$ (where $d_{ij}$ is the denominator of $\mathbf{B}_{ij}$) has size $mn \cdot \text{size}(d) + \text{size}(\mathbf{B}) \le (mn+1) \cdot \text{size}(\mathbf{B}) \le 2mn \cdot \text{size}(\mathbf{B})$</footnote>
**Proof.** Write $\mathbf{U} \in \mathbb{Z}^{n \times n} \cap \text{GL}_n(\mathbb{R})$ for the (not necessarily unimodular) transformation such that $\mathbf{C} = \mathbf{B}\mathbf{U}$ attains the successive minima, i.e., $\|\mathbf{c}_j\| = \lambda_j(\Lambda)$, and the vectors $\mathbf{c}_j$ are linearly independent. By Lemma 28.6, we know that $\|\mathbf{u}_j\| \le 2^{(T+2)n} \cdot \lambda_j(\Lambda)/\lambda_1(\Lambda)$.

Since $\mathbf{U}$ is non-singular, then $\tilde{\mathbf{C}} := \tilde{\mathbf{B}}\mathbf{U} = \tilde{\mathbf{B}}(\mathbf{u}_1, \dots, \mathbf{u}_n)$ consists of $n$ independent vectors. Hence $\lambda_j(\tilde{\Lambda}) \le \max_{1 \le k \le j} \|\tilde{\mathbf{c}}_k\|$, but we have

$$ \|\tilde{\mathbf{c}}_k\| \le \|\tilde{\mathbf{c}}_k - \mathbf{c}_k\| + \|\mathbf{c}_k\| \le \|\tilde{\mathbf{B}} - \mathbf{B}\|_2 \cdot \|\mathbf{u}_k\| + \lambda_k(\Lambda) \le \lambda_k(\Lambda) \left( 1 + \frac{2^{(T+2)n} \cdot \|\tilde{\mathbf{B}} - \mathbf{B}\|_2}{\lambda_1(\Lambda)} \right), $$

hence, by applying the same reasoning but interchanging $\Lambda$ and $\tilde{\Lambda}$,

$$ \lambda_j(\tilde{\Lambda}) \le \lambda_j(\Lambda) \left( 1 + \frac{2^{(T+2)n} \cdot \|\tilde{\mathbf{B}} - \mathbf{B}\|_2}{\lambda_1(\Lambda)} \right) \quad \text{and} \quad \lambda_j(\Lambda) \le \lambda_j(\tilde{\Lambda}) \left( 1 + \frac{2^{(T+2)n} \cdot \|\tilde{\mathbf{B}} - \mathbf{B}\|_2}{\lambda_1(\tilde{\Lambda})} \right). $$

Instantiating this with $j=1$, shows $|\lambda_1(\tilde{\Lambda}) - \lambda_1(\Lambda)| \le 2^{(T+2)n} \cdot \|\tilde{\mathbf{B}} - \mathbf{B}\|_2$. Applying the inequality $1-x \le 1/(1+x)$ (which holds for all $x \ge 0$) and replacing $\lambda_1(\Lambda)$ and $\lambda_1(\tilde{\Lambda})$ by their minimum, we obtain the final claim

$$ \left( 1 - \frac{2^{(T+2)n} \cdot \|\tilde{\mathbf{B}} - \mathbf{B}\|_2}{\min(\lambda_1(\Lambda), \lambda_1(\tilde{\Lambda}))} \right) \le \frac{\lambda_j(\Lambda)}{\lambda_j(\tilde{\Lambda})} \le \left( 1 + \frac{2^{(T+2)n} \cdot \|\tilde{\mathbf{B}} - \mathbf{B}\|_2}{\min(\lambda_1(\Lambda), \lambda_1(\tilde{\Lambda}))} \right). $$

□

**Corollary 28.8.** Let $\tilde{\mathbf{B}}$ and $\mathbf{B} \in \mathbb{R}^{m \times n}$ be T-dually exponentially reduced bases of rank-n lattices $\tilde{\Lambda}$ and $\Lambda$ respectively. Let $\tilde{\mathbf{C}} = \tilde{\mathbf{B}}\mathbf{U}$ be a basis of $\tilde{\Lambda}$ satisfying

$$ \|\tilde{\mathbf{c}}_j\| \le q_j \cdot \lambda_n(\tilde{\Lambda}) \quad \text{for all } j \in \{1, \dots, n\}, $$

for $q_j \in \mathbb{R}_{>0}$. Suppose $\|\tilde{\mathbf{B}} - \mathbf{B}\|_2 \le \frac{1}{4} \cdot 2^{-(T+2)n} \cdot \min(\lambda_1(\Lambda), \lambda_1(\tilde{\Lambda}))$ and write $\mathbf{C} = \mathbf{B}\mathbf{U}$. Then,

$$ \|\mathbf{c}_j\| \le 2 \cdot q_j \cdot \lambda_n(\Lambda) \quad \text{for all } j \in \{1, \dots, n\}. $$

**Proof.** We have $\|\mathbf{u}_j\| \le 2^{(T+2)n} \|\tilde{\mathbf{c}}_j\|/\lambda_1(\tilde{\Lambda})$ by Lemma 28.6, and hence

$$ \begin{align*} \|\mathbf{c}_j\| & \le \|\mathbf{c}_j - \tilde{\mathbf{c}}_j\| + \|\tilde{\mathbf{c}}_j\| \le \|\tilde{\mathbf{B}} - \mathbf{B}\|_2 \cdot \|\mathbf{u}_j\| + \|\tilde{\mathbf{c}}_j\| \\ & \le \|\tilde{\mathbf{c}}_j\| \left( 1 + \frac{\|\tilde{\mathbf{B}} - \mathbf{B}\|_2 \cdot 2^{(T+2)n}}{\lambda_1(\tilde{\Lambda})} \right) \le q_j \cdot \lambda_n(\tilde{\Lambda}) \cdot \left( 1 + \frac{\|\tilde{\mathbf{B}} - \mathbf{B}\|_2 \cdot 2^{(T+2)n}}{\lambda_1(\tilde{\Lambda})} \right) \\ & \le q_j \cdot \lambda_n(\Lambda) \cdot \left( 1 + \frac{\|\tilde{\mathbf{B}} - \mathbf{B}\|_2 \cdot 2^{(T+2)n}}{\min(\lambda_1(\tilde{\Lambda}), \lambda_1(\Lambda))} \right)^2 \le 2 \cdot q_j \cdot \lambda_n(\Lambda), \end{align*} $$

where in the penultimate inequality, we used Corollary 28.7 and in the last inequality we used the assumed upper bound on $\|\tilde{\mathbf{B}} - \mathbf{B}\|_2$. □

## 28.6. Conclusion.

**Lemma 8.5.** Let $K$ be a number field of degree $n$. Let $xa$ be an ideal lattice where $x \in K_\mathbb{R}^\times$ is represented by rational numbers, and where $a \in \mathcal{I}_K$ is represented by a rational Hermite Normal Form matrix $M_a$ with respect to a given LLL-reduced basis of $\mathcal{O}_K$.

Then there exists an algorithm that computes a $\mathbb{Z}$-basis $(x\alpha_1, \dots, x\alpha_n)$ of $xa$ with $\alpha_i \in K$ such that

$$ \|x \cdot \alpha_i\| \le 2n \cdot b^{2n/b} \cdot \lambda_n(x \cdot a), $$
using time at most $T = \text{poly}(b^b, \text{size}(\mathfrak{a}), \log |\Delta_K|, \text{size}(x))$.

*Proof.* Using the HNF rational matrix $M_{\mathfrak{a}}$, we have a sequence of elements $(\alpha_1^{(0)}, \dots, \alpha_n^{(0)})$ generating $\mathfrak{a}$. The exact Minkowski basis is given by $\mathbf{B}_{x\mathfrak{a}} = (\sigma(\alpha_j^{(0)}))_{\sigma,j}$, i.e., the columns of $\mathbf{B}_{x\mathfrak{a}}$ are the Minkowski embeddings of $\alpha_j^{(0)}$ into $K_{\mathbb{R}}$.

Due to the fact that these numbers are irrational in general, the basis $\mathbf{B}_{x\mathfrak{a}}$ can only be approximated; we call this approximation $\tilde{\mathbf{B}}_{x\mathfrak{a}}$. Note that the values of $\sigma(\alpha_j^{(0)})$ can reasonably be approximated by computing the roots of the defining polynomial of the number field $K$. This can be done efficiently by, for example, Newton iteration; this costs time polynomial in the desired bit precision. Hence, if the final required bit precision is polynomial in the size of the input (which we indeed will show to be the case), approximation is not going to have a significant influence on the running time.

**Computing the dual.** So, suppose we have a rational approximation $\tilde{\mathbf{B}}_{x\mathfrak{a}}$ of $\mathbf{B}_{x\mathfrak{a}}$ within polynomial bits of precision. By Lemma 28.3, computing the dual basis of $\tilde{\mathbf{B}}_{x\mathfrak{a}}$ only looses $O(n^2 + \log |\Delta_K| + (n+2) \text{size}(x\mathfrak{a}))$ bits of precision. Therefore we can assume that the dual basis of $\tilde{\mathbf{B}}_{x\mathfrak{a}}$ approximates the dual basis of $\mathbf{B}_{x\mathfrak{a}}$ with polynomial bits of precision.

**Applying Buchmann-Kessler-Pohst on the approximate dual basis.** Using the Buchmann-Kessler-Pohst algorithm on the approximate dual basis, we have Proposition 28.5, which states we can compute efficiently a $\mathbb{Z}$-basis $(x\alpha_1^{(1)}, \dots, x\alpha_n^{(1)})$ that is ‘3-dually exponentially reduced’ (see Definition 26.14). That means the dual basis $(\mathbf{d}_1, \dots, \mathbf{d}_n)$ of this new basis satisfies $\|\mathbf{d}_j\| \le 2^{3n} \cdot \lambda_j((x\mathfrak{a})^\vee)$, where $(x\mathfrak{a})^\vee$ is the dual lattice of $x\mathfrak{a}$.

This new basis $(x\alpha_1^{(1)}, \dots, x\alpha_n^{(1)})$ is exact and we can re-approximate the associated basis $\mathbf{B}_{x\mathfrak{a}}^{(1)}$ by $\tilde{\mathbf{B}}_{x\mathfrak{a}}^{(1)}$. By Lemma 28.4, a sufficient (polynomial) approximation $\tilde{\mathbf{B}}_{x\mathfrak{a}}^{(1)}$ can be shown to be 6-dually exponentially reduced as well.

**Applying Hanrot-Pujol-Stehlé.** Without loss of generality, we can clear the denominators in $\tilde{\mathbf{B}}_{x\mathfrak{a}}^{(1)}$. Then, we apply the BKZ version of Hanrot-Pujol-Stehlé with provable bounds on the number of tours. Using Corollary 27.4, we conclude that there exists an algorithm using time $\text{poly}(n, \text{size}(\tilde{\mathbf{B}}_{x\mathfrak{a}}^{(1)}), b^b) = \text{poly}(\log |\Delta_K|, \text{size}(x\mathfrak{a}), b^b)$ that outputs a new basis $(\tilde{\mathbf{b}}_1^{(2)}, \dots, \tilde{\mathbf{b}}_n^{(2)}) = \tilde{\mathbf{B}}_{x\mathfrak{a}}^{(2)} = \tilde{\mathbf{B}}_{x\mathfrak{a}}^{(1)} = \tilde{\mathbf{B}}_{x\mathfrak{a}}^{(1)} \cdot \mathbf{U}$ of the lattice $\mathcal{L}(\tilde{\mathbf{B}}_{x\mathfrak{a}}^{(1)})$ that satisfies

$$ \|\tilde{\mathbf{b}}_j^{(2)}\| \le n \cdot b^{2n/b} \cdot \lambda_n(\mathcal{L}(\tilde{\mathbf{B}}_{x\mathfrak{a}}^{(1)})) $$

But we would like the new exact basis $(x\alpha_1^{(2)}, \dots, x\alpha_n^{(2)})$, obtained by applying $\mathbf{U}$ to $(x\alpha_1^{(1)}, \dots, x\alpha_n^{(1)})$ to satisfy above claim. For this we need the *closeness lemma*.

**Applying the closeness lemma.** Note that $\tilde{\mathbf{B}}_{x\mathfrak{a}}^{(2)} = \tilde{\mathbf{B}}_{x\mathfrak{a}}^{(1)} \mathbf{U}$ is an approximation of $\mathbf{B}_{x\mathfrak{a}}^{(2)} = \mathbf{B}_{x\mathfrak{a}}^{(1)} \mathbf{U}$, the exact Minkowski-basis of the $\mathbb{Z}$-basis $(x\alpha_1^{(2)}, \dots, x\alpha_n^{(2)})$. Since $\tilde{\mathbf{B}}_{x\mathfrak{a}}^{(1)}$ and $\mathbf{B}_{x\mathfrak{a}}^{(1)}$ are both $T$-dually exponentially reduced (with $T = 6$ and $3$ respectively), we can apply Corollary 28.8. A sufficient (polynomial bit precision) approximation $\tilde{\mathbf{B}}_{x\mathfrak{a}}^{(1)}$ of $\mathbf{B}_{x\mathfrak{a}}^{(1)}$ then suffices to deduce that the vectors of $\mathbf{B}_{x\mathfrak{a}}^{(2)}$ satisfy the same BKZ-like bounds (with a blow-up factor of 2), hence,

$$ \|x\alpha_j^{(2)}\| \le 2n \cdot b^{2n/b} \cdot \lambda_n(x\mathfrak{a}) \text{ for all } j \in \{1, \dots, n\}. $$

□
REFERENCES

[1] D. Aggarwal, J. Li, P. Q. Nguyen, and N. Stephens-Davidowitz. Slide reduction, revisited - filling the gaps in SVP approximation. In *CRYPTO*, 2020.

[2] T. Apostol. *Introduction to Analytic Number Theory*. Undergraduate Texts in Mathematics. Springer New York, 1998.

[3] M. F. Atiyah and I. G. MacDonald. *Introduction to commutative algebra*. Addison-Wesley-Longman, 1969.

[4] E. Bach. Explicit bounds for primality testing and related problems. *Mathematics of Computation*, 55(191):355–380, 1990.

[5] E. Bach. Improved approximations for Euler products. *Number Theory: Fourth Conference of the Canadian Number Theory Association, July 2-8, 1994, Dalhousie University, Halifax, Nova Scotia, Canada*, 15, 1995.

[6] W. Banaszczyk. New bounds in some transference theorems in the geometry of numbers. *Mathematische Annalen*, 296(4):625–636, 1993.

[7] L. Beilina, E. Karchevskii, and M. Karchevskii. *Numerical Linear Algebra: Theory and Applications*. Springer, 09 2017.

[8] M. Bhargava, A. Shankar, T. Taniguchi, F. Thorne, J. Tsimerman, and Y. Zhao. Bounds on 2-torsion in class groups of number fields and integral points on elliptic curves. *Journal of the American Mathematical Society*, 33(4):1087–1099, Oct. 2020.

[9] J.-F. Biasse. Subexponential time relations in the class group of large degree number fields. *Adv. Math. Commun.*, 8(4):407–425, 2014.

[10] J.-F. Biasse and C. Fieker. Subexponential class group and unit group computation in large degree number fields. *LMS Journal of Computation and Mathematics*, 17:385–403, 1 2014.

[11] J.-F. Biasse and F. Song. A polynomial time quantum algorithm for computing class groups and solving the principal ideal problem in arbitrary degree number fields. In *SODA*, 2016.

[12] K. de Boer. *Random Walks on Arakelov Class Groups*. PhD thesis, Mathematical Institute (MI), Faculty of Science, Leiden University, 2022.

[13] K. de Boer, L. Ducas, and S. Fehr. On the quantum complexity of the continuous hidden subgroup problem. In *Annual International Conference on the Theory and Applications of Cryptographic Techniques*, pages 341–370. Springer, 2020.

[14] K. de Boer, L. Ducas, A. Pellet-Mary, and B. Wesolowski. Random self-reducibility of ideal-svp via arakelov random walks. In D. Micciancio and T. Ristenpart, editors, *Advances in Cryptology - CRYPTO 2020*, pages 243–273, Cham, 2020. Springer International Publishing.

[15] K. de Boer and C. Pagano. Calculating the power residue symbol and ibeta. In *ISSAC*, volume 68, pages 923–934, 2017.

[16] J. Buchmann. A subexponential algorithm for the determination of class groups and regulators of algebraic number fields. *Séminaire de théorie des nombres, Paris*, 1989:28–41, 1988.

[17] J. Buchmann and V. Kessler. Computing a reduced lattice basis from a generating system. *Unpublished Manuscript*, 08 1996.

[18] J. Buchmann and M. Pohst. Computing a lattice basis from a system of generating vectors. In *Proceedings of the European Conference on Computer Algebra*, EUROCAL '87, pages 54–63, London, UK, UK, 1989. Springer-Verlag.

[19] J. A. Buchmann and H. W. Lenstra. Approximating rings of integers in number fields. *Journal de Théorie des Nombres de Bordeaux*, 6(2):221–260, 1994.

[20] J. Cassels. *An Introduction to the Geometry of Numbers*. Classics in Mathematics. Springer Berlin Heidelberg, 2012.

[21] H. Cohen. *A course in computational algebraic number theory*, volume 8. Springer-Verlag Berlin, 1993.

[22] H. Cohen. *Advanced Topics in Computational Number Theory*. Graduate Texts in Mathematics. Springer New York, 1999.

[23] H. Cohen and F. Diaz Y Diaz. A polynomial reduction algorithm. *Journal de théorie des nombres de Bordeaux*, 3(2):351–360, 1991.

[24] H. Cohen, F. Diaz Y Diaz, and M. Olivier. Subexponential algorithms for class group and unit computations. *Journal of Symbolic Computation*, 24(3-4):433–441, 1997.

[25] H. Cohen and P. Stevenhagen. Computational class field theory, 2008.
[26] S. D. Conte and C. W. De Boor. *Elementary Numerical Analysis: an Algorithmic Approach*. International Series in Pure and Applied Mathematics. McGraw-Hill, New York, NY, third edition, 1980.

[27] T. M. Cover and J. A. Thomas. *Elements of Information Theory 2nd Edition (Wiley Series in Telecommunications and Signal Processing)*. Wiley-Interscience, 7 2006.

[28] R. Cramer, L. Ducas, and B. Wesolowski. Mildly short vectors in cyclotomic ideal lattices in quantum polynomial time. *J ACM*, 2021.

[29] K. Eisenträger, S. Hallgren, A. Kitaev, and F. Song. A quantum algorithm for computing the unit group of an arbitrary degree number field. In *STOC*, pages 293–302. ACM, 2014.

[30] K. Ford. Vinogradov's integral and bounds for the riemann zeta function. *Proceedings of the London Mathematical Society*, 85(3):565–633, 2002.

[31] E. Friedman. Analytic formulas for the regulator of a number field. *Inventiones mathematicae*, 98:599–622, 1989.

[32] N. Gama and P. Q. Nguyen. Finding short lattice vectors within mordell's inequality. In *Proceedings of the fortieth annual ACM symposium on Theory of computing*, pages 207–216. ACM, 2008.

[33] F. R. Gantmacher. *The Theory of Matrices, Vol. I, II*. Chelsea Publishing Comp., New York, 1959.

[34] A. Gélin and A. Joux. Reducing number field defining polynomials: an application to class group computations. *LMS Journal of Computation and Mathematics*, 19(A):315–331, 2016.

[35] C. Gentry, C. Peikert, and V. Vaikuntanathan. Trapdoors for hard lattices and new cryptographic constructions. In *STOC*, pages 197–206, 2008.

[36] L. Grenié and G. Molteni. Explicit versions of the prime ideal theorem for Dedekind zeta functions under GRH. *Mathematics of Computation*, 85(298):889–906, Oct 2015.

[37] J. L. Hafner and K. S. McCurley. A rigorous subexponential algorithm for computation of class groups. *Journal of the American mathematical society*, 2(4):837–850, 1989.

[38] G. Hanrot, X. Pujol, and D. Stehlé. Analyzing blockwise lattice algorithms using dynamical systems. In *CRYPTO*, 2011.

[39] G. Hanrot and D. Stehlé. Improved analysis of Kannan's shortest lattice vector algorithm. pages 170–186, 08 2007.

[40] I. Haviv and O. Regev. *On the Lattice Isomorphism Problem*, pages 391–404.

[41] R. Horn and C. Johnson. *Matrix Analysis*. Cambridge University Press, 2012.

[42] I. C. F. Ipsen and R. Rehman. Perturbation bounds for determinants and characteristic polynomials. *SIAM Journal on Matrix Analysis and Applications*, 30(2):762–776, 2008.

[43] H. Iwaniec and E. Kowalski. *Analytic Number Theory*. American Mathematical Society, 2004.

[44] E. Kaltofen and G. Villard. On the complexity of computing determinants. *Computational complexity*, 13(3-4):91–130, 2005.

[45] V. Kessler. On the minimum of the unit lattice. *Séminaire de Théorie des Nombres de Bordeaux*, 3(2):377–380, 1991.

[46] J. Lagarias and A. Odlyzko. Effective versions of the Chebotarev density theorem. In *Algebraic number fields: L-functions and Galois properties (Proc. Sympos., Univ. Durham, Durham, 1975)*, pages 409–464. Academic Press, London, 1977.

[47] J. C. Lagarias, H. W. Lenstra Jr., and C.-P. Schnorr. Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice. *Combinatorica*, 10(4):333–348, 1990.

[48] S. Lang. *Algebraic Number Theory*. Graduate Texts in Mathematics. Springer, 1994.

[49] S. Lang. *Algebra*. Graduate Texts in Mathematics. Springer New York, 2005.

[50] A. K. Lenstra, H. W. Lenstra Jr., et al. *The development of the number field sieve*, volume 1554. Springer Science & Business Media, 1993.

[51] A. K. Lenstra, H. W. Lenstra Jr., and L. Lovász. Factoring polynomials with rational coefficients. *Mathematische Annalen*, 261(4):515–534, December 1982.

[52] S. Louboutin. Explicit bounds for residues of Dedekind zeta functions, values of L-functions at $s=1$, and relative class numbers. *Journal of Number Theory*, 2000.

[53] D. Micciancio and S. Goldwasser. *Complexity of Lattice Problems: a cryptographic perspective*, volume 671 of *The Kluwer International Series in Engineering and Computer Science*. Kluwer Academic Publishers, Boston, Massachusetts, 2002.

[54] D. Micciancio and O. Regev. Worst-case to average-case reductions based on gaussian measures. *SIAM J. Comput.*, 37(1):267–302, Apr. 2007.

[55] H. Minkowski. *Gesammelte Abhandlungen*. Chelsea, New York, 1967.
[56] T. Miyake and Y. Maeda. *Modular Forms*. Springer Monographs in Mathematics. Springer Berlin Heidelberg, 2006.

[57] J. Neukirch and N. Schappacher. *Algebraic Number Theory*. Grundlehren der mathematischen Wissenschaften. Springer Berlin Heidelberg, 2013.

[58] P. Q. Nguyen and D. Stehlé. An LLL algorithm with quadratic complexity. *SIAM Journal on Computing*, 39(3):874–903, 2009.

[59] M. Overholt. *A Course in Analytic Number Theory*. Graduate Studies in Mathematics. American Mathematical Society, 2014.

[60] L. Pardo. *Statistical Inference Based on Divergence Measures*. CRC Press, Abingdon, 2005.

[61] C. Peikert and A. Rosen. Lattices that admit logarithmic worst-case to average-case connection factors. Cryptology ePrint Archive, Paper 2006/444, 2006.

[62] A. Pellet-Mary, G. Hanrot, and D. Stehlé. Approx-SVP in ideal lattices with pre-processing. In *Eurocrypt*, pages 685–716. Springer, 2019.

[63] M. Plançon and T. Prest. Exact lattice sampling from non-Gaussian distributions. In J. A. Garay, editor, *Public-Key Cryptography – PKC 2021*, pages 573–595, Cham, 2021. Springer International Publishing.

[64] C. Pomerance. Fast, rigorous factorization and discrete logarithm algorithms. In D. S. Johnson, T. Nishizeki, A. Nozaki, and H. S. Wilf, editors, *Discrete Algorithms and Complexity*, pages 119–143. Academic Press, 1987.

[65] S. Rabinowitz. The volume of an n-simplex with many equal edges. *Missouri Journal of Mathematical Sciences*, 1, 01 1989.

[66] J. B. Rosser and L. Schoenfeld. Approximate formulas for some functions of prime numbers. *Illinois Journal of Mathematics*, 6(1):64–94, 1962.

[67] C.-P. Schnorr. A hierarchy of polynomial time lattice basis reduction algorithms. *Theor. Comput. Sci.*, 53:201–224, 1987.

[68] R. Schoof. Computing Arakelov class groups. In *Algorithmic Number Theory: Lattices, Number Fields, Curves and Cryptography*, pages 447–495. Cambridge University Press, 2008.

[69] M. Seysen. A probabilistic factorization algorithm with quadratic forms of negative discriminant. *Mathematics of computation*, 48(178):757–780, 1987.

[70] V. Shoup. A new polynomial factorization algorithm and its implementation. *Journal of Symbolic Computation*, 20(4):363–397, 1995.

[71] A. Storjohann and G. Labahn. Asymptotically fast computation of Hermite normal forms of integer matrices. In *Proceedings of the 1996 International Symposium on Symbolic and Algebraic Computation*, ISSAC '96, page 259–266, New York, NY, USA, 1996. Association for Computing Machinery.

[72] J. E. Sunley. On the class numbers of totally imaginary quadratic extensions of totally real fields. *Bulletin of the American Mathematical Society*, 78(1):74–76, 1972.

[73] T. Trudgian. Updating the error term in the prime number theorem. *The Ramanujan Journal*, 39(2):225–234, Feb 2016.

[74] U. von Krause et al. Abschätzungen für die funktion $\omega k$ (x, y) in algebraischen zahlkörpern. *Manuscripta mathematica*, 69(1):319–331, 1990.

[75] J. von zur Gathen and J. Gerhard. *Modern Computer Algebra*. Cambridge University Press, 1999.

[76] J. von zur Gathen and D. Panario. Factoring polynomials over finite fields: A survey. *Journal of Symbolic Computation*, 31(1):3–17, 2001.

[77] B. P. Wesolowski. *Arithmetic and geometric structures in cryptography*. PhD thesis, École Polytechnique Fédérale de Lausanne, 11 2018.
# Appendix

## A.1. PROOF OF THEOREM 6.4, THE RANDOM WALK THEOREM

This following proof of Theorem 6.4 is put in the appendix because it is very similar to proofs in other work [14, Section 3] [12, Chapter 4], with the difference that it is here generalized to arbitrary moduli $\mathfrak{m}$ and finite-index subgroups of $\mathrm{Pic}^0_{\mathfrak{m}}$, and a slight change of the definition of the log-space $H$.

**Theorem 6.4** (Random Walks in finite-index subgroups of the Arakelov Ray Class Group, ERH). Let $\varepsilon > 0$ and $s > 0$ be any positive real numbers and let $k \in \mathbb{R}_{>0}$ be a positive real number as well. Let $G \subseteq \mathrm{Pic}^0_{\mathfrak{m}}$ be a finite-index subgroup of the Arakelov ray class group. Putting$^{42}$ $\tilde{s} = \min(\sqrt{2} \cdot s, 1/\eta_1(\mathrm{Log}(\mathcal{O}_{\mathfrak{K}^{\times,1}}^{\times}))),$ there exists a bound

$$B = \tilde{O}([\mathrm{Pic}^0_{\mathfrak{K}^m} : G]^2 \cdot n^{2k} [n^2(\log \log(1/\varepsilon))^2 + n^2(\log(1/\tilde{s}))^2 + (\log(|\Delta_K|\mathcal{N}(\mathfrak{m})))^2])$$
such that for any integer

$$N \ge \left[ \frac{1}{2k \log n} \cdot (\mathfrak{r} \cdot \log(1/\tilde{s}) + 2 \log(1/\varepsilon) + \log|\mathrm{Pic}^0_{\mathfrak{K}^m}| - \log[\mathrm{Pic}^0_{\mathfrak{K}^m} : G] + 2) \right], \quad (24)$$

the random walk distribution $[\mathcal{W}_G(B, N, s)]$ is $\varepsilon$-close to uniform in $L_1(G)$, i.e.,

$$\| [\mathcal{W}_G(B, N, s)] - \mathcal{U}(G) \|_1 \le \varepsilon,$$

where $\mathcal{N}(\mathfrak{m}) = \mathcal{N}(\mathfrak{m}_0) \cdot 2^{|\mathfrak{m}_R|}$, $\mathfrak{r} = \dim(H) = n_{\mathbb{R}} + n_{\mathbb{C}} - 1$ and $|\mathfrak{m}_{\mathbb{R}}|$ is the number of different real places dividing $\mathfrak{m}$ (see Section 2.4).

We follow the proof of [14, Section 3], with small adaptations.

### The Hecke operator, characters and eigenvalues

Recall that $G \subseteq \mathrm{Pic}^0_{\mathfrak{K}^m}$ is a finite-index subgroup of $\mathrm{Pic}^0_{\mathfrak{K}^m}$ where we try to randomize over. Putting $\mathcal{P} = \{\mathfrak{p} \text{ prime ideal of } K \mid \mathcal{N}(\mathfrak{p}) \le B, [d^0(\mathfrak{p})] \in G \text{ and } \mathfrak{p} \nmid \mathfrak{m}\}$, we define the Hecke operator $\mathcal{H} : L^2(G) \to L^2(G)$ by the following rule, for $f \in L^2(G)$.

$$\mathcal{H}(f)(x) := \frac{1}{|\mathcal{P}|} \sum_{\mathfrak{p} \in \mathcal{P}} f(x - [d^0(\mathfrak{p})]).$$

This Hecke operator has the characters $\chi \in \hat{G}$ as eigen functions, with eigenvalues $\lambda_{\chi} \in \mathbb{C}$ satisfying $|\lambda_{\chi}| \le 1$ [14, Section 3.2]. The trivial character $\mathbf{1} \in \hat{G}$ can be

<footnote>$^{42}$Recall that for any lattice $\Lambda$, we write $\Lambda^{\vee}$ for its dual, and $\eta_1(\Lambda)$ for its smoothing parameter (see page 18).</footnote>
shown to have eigenvalue $\lambda_1 = 1$.

$$ \mathcal{H}(\chi)(\cdot) := \frac{1}{|\mathcal{P}|} \sum_{\mathfrak{p} \in \mathcal{P}} \chi(\cdot - [d^0(\mathfrak{p})]) = \chi(\cdot) \cdot \underbrace{\frac{1}{|\mathcal{P}|} \sum_{\mathfrak{p} \in \mathcal{P}} \chi(-[d^0(\mathfrak{p})])}_{\lambda_{\chi}} $$

For a fixed $\chi \in \hat{G}$, there are $[\text{Pic}_{K^m}^0 : G]$ extensions of this character to $\theta \in \widehat{\text{Pic}_{K^m}^0}$. These characters satisfy the following identity, which can be proved by using standard character orthogonality techniques.

$$ [\text{Pic}_{K^m}^0 : G]^{-1} \sum_{\substack{\theta \in \widehat{\text{Pic}_{K^m}^0} \\ \theta|_G = \chi}} \theta(-[d^0(\mathfrak{p})]) = \begin{cases} \chi(-[d^0(\mathfrak{p})]) & \text{if } [d^0(\mathfrak{p})] \in G \\ 0 & \text{otherwise} \end{cases} \quad (165) $$

Putting $\bar{\mathcal{P}} = \{\mathfrak{p} \text{ prime ideal of } K \mid \mathcal{N}(\mathfrak{p}) \le B \text{ and } \mathfrak{p} \nmid \mathfrak{m}\}$ (note the absence of the class condition on $\mathfrak{p}$), we thus have, for any fixed $\chi \in \hat{G}$, using Equation (165),

$$ \lambda_{\chi} = \frac{1}{|\mathcal{P}|} \sum_{\mathfrak{p} \in \mathcal{P}} \chi(-[d^0(\mathfrak{p})]) = \frac{1}{|\mathcal{P}| \cdot [\text{Pic}_{K^m}^0 : G]} \sum_{\substack{\mathfrak{p} \in \bar{\mathcal{P}} \\ \theta \in \widehat{\text{Pic}_{K^m}^0} \\ \theta|_G = \chi}} \theta(-[d^0(\mathfrak{p})]) \quad (166) $$

$$ = \frac{|\bar{\mathcal{P}}|}{|\mathcal{P}|} \cdot \frac{1}{[\text{Pic}_{K^m}^0 : G]} \sum_{\substack{\theta \in \widehat{\text{Pic}_{K^m}^0} \\ \theta|_G = \chi}} \frac{1}{|\bar{\mathcal{P}}|} \sum_{\mathfrak{p} \in \bar{\mathcal{P}}} \theta(-[d^0(\mathfrak{p})]) \quad (167) $$

Assuming the Extended Riemann Hypothesis (as formulated in [43, §5.7]), one can use results from analytic number theory [43, Theorem 5.15] to derive the following asymptotic bound for non-constant characters $\theta \in \widehat{\text{Pic}_{K^m}^0}$ (see [14, Section 3.3]).

$$ \frac{1}{|\bar{\mathcal{P}}|} \sum_{\mathfrak{p} \in \bar{\mathcal{P}}} \theta(-[d^0(\mathfrak{p})]) = O\left( \frac{\log(B) \log(B^n \cdot |\Delta_K| \cdot \mathcal{N}(\mathfrak{m}) \cdot \mathfrak{q}_{\infty}(\theta))}{B^{1/2}} \right), \quad (168) $$

where $\mathfrak{q}_{\infty}(\chi)$ is the infinite part of the analytic conductor of the character $\chi$ (cf. [43, Eq. (5.6)]), The proof of this result uses the Abel summation formula and is almost the same as in [14, Section 3.3] or [77, Corollary 2.3.5] (see also [12, Section 4.3.3]), with the sole difference that the analytic conductor gets an extra factor $\mathcal{N}(\mathfrak{m}) = \mathcal{N}(\mathfrak{m}_0) \cdot 2^{|\mathfrak{m}_R|}$.

By applying Equation (166) for $\chi = 1 \in \hat{G}$, the trivial character, one can get an upper bound on the fraction $|\bar{\mathcal{P}}|/|\mathcal{P}|$. By the fact that $\lambda_1 = 1$, we obtain, from Equation (168)

$$ \frac{|\mathcal{P}| \cdot [\text{Pic}_{K^m}^0 : G]}{|\bar{\mathcal{P}}|} = 1 + O\left( \frac{[\text{Pic}_{K^m}^0 : G] \cdot \log(B) \log(B^n \cdot |\Delta_K| \cdot \mathcal{N}(\mathfrak{m}) \cdot \mathfrak{q}_{\infty}(1))}{B^{1/2}} \right). \quad (169) $$
Hence, choosing $B$ such that the value of the big-O of Equation (169) is strictly bounded by a half$^{43}$, we obtain

$$ \frac{|\bar{\mathcal{P}}|}{|\mathcal{P}|} \cdot \frac{1}{[\mathrm{Pic}_{K^m}^0 : G]} \le 2 \qquad (170) $$

Combining Equations (167), (168) and (170), we obtain that the eigen value $\lambda_\chi$ for non-constant characters $\chi \in \hat{G}$ under the Hecke operator $\mathcal{H}$ satisfies

$$ \lambda_{\chi} = O \left( \frac{[\mathrm{Pic}_{K^m}^0 : G] \cdot \log(B) \log(B^n \cdot |\Delta_K| \cdot \mathcal{N}(\mathfrak{m}) \cdot \mathfrak{q}_{\infty}(\chi))}{B^{1/2}} \right), \qquad (171) $$

### The infinite analytic conductor $\mathfrak{q}_{\infty}$

The infinite analytic conductor $\mathfrak{q}_{\infty}(\chi) \in \mathbb{R}_{>0}$ is a number quantifying the amount of oscillation of the character $\chi \in \hat{G}$. By restricting a character $\chi \in \hat{G}$ to the ray unit torus$^{44}$ $T^m = H/\mathrm{Log}(\mathcal{O}_K^\times \cap K^{m,1}) \subseteq G$, one gets a character on $T^m$, which can be uniquely associated with a dual lattice point $\ell^* \in \mathrm{Log}(\mathcal{O}_{K^{m,1}}^\times)^\vee$, where $\mathrm{Log}(\mathcal{O}_{K^{m,1}}^\times) = \mathrm{Log}(\mathcal{O}_K^\times \cap K^{m,1})$. The infinite part of the analytic conductor is in that case equal to$^{45}$ (see [43, Equation (5.3), (5.4), (5.7)] and [56, Equation (3.3.6), (3.3.12)] or [14, Section 3.4] or [12, Section 4.3.4])

$$ \mathfrak{q}_{\infty}(\chi) = \prod_{\nu \text{ real}} (3 + |2\pi\ell_{\nu}^*|) \prod_{\nu \text{ complex}} (3 + |2\pi\ell_{\nu}^*|)(3 + |i2\pi\ell_{\nu}^* + 1|) \qquad (172) $$

Here, the components of the dual lattice point in the ray logarithmic unit lattice $\mathrm{Log}(\mathcal{O}_{K^{m,1}}^\times)^\vee$ are parametrized by the places $\nu$. As a result, by applying the geometric and arithmetic inequality for vector norms, we obtain the following bound on the infinite analytic conductor.

$$ \mathfrak{q}_{\infty}(\chi) \le (4 + 4\pi \|\ell^*\| / \sqrt{n})^n, $$

where $\ell^* \in \mathrm{Log}(\mathcal{O}_{K^{m,1}}^\times)^\vee$ is the unique dual logarithmic ray unit lattice point associated with the character $\chi|_{T^m} \in \hat{T}^m$.

### Fourier analysis of the Gaussian

Since the initial distribution of the random walk is a Gaussian $g_s : H \to \mathbb{R}, x \mapsto e^{-\pi\|x\|^2/s^2}$ over the hyperplane $H = \log K_0^0$, we are particularly interested in the behavior of the distribution resulting from applying the Hecke operator $N$ times, i.e., $\mathcal{H}^N(g_s)$. By standard Fourier computations, one can prove that periodized

<footnote>$^{43}$Notice that, in order the bound Equation (171) to be non-trivial (i.e., smaller than 1), we already need $B$ to satisfy this condition, so it does not add an extra requirement on $B$. In Equation (168), the analytic conductor satisfies $\mathfrak{q}_{\infty}(\theta) \le 4^n$ for extensions $\theta$ of the unit character on $G$, as $T^m \subseteq G$. This follows from the definition of the analytic conductor [43, Eq. (5.7)] (denoted $\mathfrak{q}(f) = \mathfrak{q}(f, 0)$ there), and the fact that the local parameters (denoted $\kappa_j$ in [43]) are zero for characters trivial on $T^m$.</footnote>

<footnote>$^{44}$Due to the fact that $[\mathrm{Pic}_{K^m}^0 : G]$ is finite and the ray unit torus satisfies $T^m \subseteq \mathrm{Pic}_{K^m}^0$, it is also included in $G$.</footnote>

<footnote>$^{45}$This definition of the infinite part of the analytic conductor is slightly different to that of Kowalski & Iwaniec [43, Equation (5.7)] (with $s = 1$) which is due to the difference in definitions of the real and the complex $L$-functions (see also [12, Remark 4.13]). This difference is solved by putting $L_{\mathbb{R}}(s)L_{\mathbb{R}}(s+1) = L_{\mathbb{C}}(s)$, (see [57, Chapter 7, Proposition 4.3(iv)]).</footnote>
Gaussian function$^{46}$ $s^{-r}g_s|^{T^m} \in L^2(T^m)$ satisfies

$$s^{-r}g_s|^{T^m} = \sum_{\ell^* \in \text{Log}(\mathcal{O}_{K^{\text{m},1}}^{\times})^{\vee}} a_{\ell^*} \chi_{\ell^*} \quad (173)$$

where $a_{\ell^*} = \frac{1}{\text{Vol}(T^m)}g_{1/s}(\ell^*)$, where $\text{Log}(\mathcal{O}_{K^{\text{m},1}}^{\times})^{\vee}$ is the dual lattice of the log ray unit lattice $\text{Log}(\mathcal{O}_{K^{\text{m},1}}^{\times})$, and where $\chi_{\ell^*}(x) = e^{-2\pi i \langle x, \ell^* \rangle}$ is a function on $T^m$, i.e., $\chi_{\ell^*} \in \hat{T}^m$.

By standard character arguments, one can simply write each $\chi_{\ell^*} \in \hat{G}$ (which is zero everywhere except on $T^m \subseteq G$) as an average of all characters in $\hat{G}$ that restrict to $\chi_{\ell^*}$ on $T^m$. This results in the following identity (see also [14, §3.6]), where $\chi' \in \hat{G}$ ranges over the characters of $G \subseteq \text{Pic}_{K^m}^0$.

$$s^{-r}g_s|^{T^m} = \frac{1}{|G|} \sum_{\chi_{\ell^*} \in \widehat{T^m}} g_{1/s}(\ell^*) \sum_{\chi'|_{T^m} = \chi_{\ell^*}} \chi'. \quad (174)$$

## Splitting up the sum

By splitting up the sum of Equation (174) into a 'unit part', a 'low frequency part' where $\|\ell^*\| < r$ and a 'high frequency part' where $\|\ell^*\| \ge r$, we obtain the following decomposition, for any $r > 0$, where $\chi' \in \hat{G}$ ranges over the characters of $G \subseteq \text{Pic}_{K^m}^0$.

$$|G| \cdot s^{-r} \cdot g_s|^{T^m} = \underbrace{\mathbf{1}_G}_{\substack{\text{Unit character} \\ \|\ell^*\| < r}} + \underbrace{\sum_{\substack{\chi_{\ell^*} \in \widehat{T^m} \\ \chi'_{|T^m} = \chi_{\ell^*}}} g_{1/s}(\ell^*) \sum_{\substack{\chi' \ne \mathbf{1} \\ \chi'_{|T^m} \ge r}} \chi' + \underbrace{\sum_{\substack{\chi_{\ell^*} \in \widehat{T^m} \\ \chi'_{|T^m} = \chi_{\ell^*}}} g_{1/s}(\ell^*) \sum_{\substack{\chi' \ne \chi_{\ell^*} \\ \chi'_{|T^m} = \chi_{\ell^*}}} \chi',}_{\substack{\text{Low frequency characters} \\ \text{High frequency characters}}}$$

Now, applying the Hecke operator $\mathcal{H}^N$ times to this equation, and taking the absolute value of $|G| \cdot \mathcal{H}^N(g_s|^{T^m}) - \mathbf{1}_G$, we obtain, by the Pythagorean theorem (using that $\|\chi'\chi'\|_2^2 = |G|$),

$$\| |G| \cdot \mathcal{H}^N(s^{-r}g_s|^{T^m}) - \mathbf{1}_G \|^2 = |G| \underbrace{\sum_{\substack{\chi_{\ell^*} \in \widehat{T^m} \\ \|\ell^*\| < r}} g_{1/s}^2(\ell^*) \sum_{\substack{\chi'_{|T^m} = \chi_{\ell^*} \\ \chi' \ne \mathbf{1}}} |\lambda_{\chi'}|^{2N}}_{\text{Low frequency}} \quad (175)$$

$$+ |G| \underbrace{\sum_{\substack{\chi_{\ell^*} \in \widehat{T^m} \\ \|\ell^*\| \ge r}} g_{1/s}^2(\ell^*) \sum_{\substack{\chi'_{|T^m} = \chi_{\ell^*} \\ \chi' \ne \mathbf{1}}} |\lambda_{\chi'}|^{2N}}_{\text{High frequency}} \quad (176)$$

<footnote>$^{46}$The periodization is defined as follows: $g_s|^{T^m}(x) := \sum_{\ell \in \text{Log}(\mathcal{O}_{K^{\text{m},1}}^{\times})} g_s(x+\ell)$.</footnote>
We will bound the parts Equation (175) and Equation (176) separately. For the latter, we have

$$|G| \sum_{\substack{\chi_{\ell^*} \in \widehat{T^m} \\ \|\ell^*\| \ge r}} g_{1/s}^2(\ell^*) \sum_{\substack{\chi' \in T^m \\ \chi_{\ell^*} = \chi_{\ell^*}}} |\lambda_{\chi'}|^{2N} \le |G| \cdot |G/T^m| \sum_{\substack{\ell^* \in \operatorname{Log}(\mathcal{O}_{K^{\mathrm{m},1}}^{\times})^{\vee} \\ \|\ell^*\| \ge r}} g_{\frac{1}{\sqrt{2s}}}^{\frac{1}{\sqrt{2s}}}(\ell^*) \quad (177)$$

$$\le |G| \cdot |G/T^m| \cdot \beta_{\sqrt{2rs}}^{(r)} \cdot g_{\frac{1}{\sqrt{2s}}}^{\frac{1}{\sqrt{2s}}} (\operatorname{Log}(\mathcal{O}_{K^{\mathrm{m},1}}^{\times})^{\vee}), \quad (178)$$

where the last inequality follows from Banaszczyk's tail bound [6] and the assumption that $rs > \sqrt{r/(4\pi)}$, where $\beta_z^{(n)} := \left(\frac{2\pi e z^2}{n}\right)^{n/2} e^{-\pi z^2}$, for which holds $\beta_t^{(n)} \le e^{-t^2}$ for all $t \ge \sqrt{n}$ (see also [14, §3.6]).

To bound the share of the low-frequency characters, we use the bound from Equation (171), $|\lambda_{\chi'}| \le O\left(\frac{[\operatorname{Pic}_{K^m}^0 : G] \cdot \operatorname{log}(B) \operatorname{log}(B^n \cdot |\Delta_K| \cdot \mathcal{N}(\mathfrak{m}) \cdot q_{\infty}(\chi'))}{B^{1/2}}\right)$. Since these characters have a 'low frequency', their analytic conductor $q_{\infty}(\chi')$ is bounded, namely, $q_{\infty}(\chi') \le (4 + 2\pi r/\sqrt{n})^n$ for any $\chi' \in \widehat{G}$ such that $\chi'|_{T^m} = \chi_{\ell^*}$ for some $\ell^* \in \operatorname{Log}(\mathcal{O}_{K^{\mathrm{m},1}}^{\times})^{\vee}$ with $\|\ell^*\| < r$. Therefore,

$$|\lambda_{\chi'}| \le c = O\left(\frac{[\operatorname{Pic}_{K^m}^0 : G] \cdot \operatorname{log}(B) \operatorname{log}(B^n \cdot |\Delta_K| \cdot \mathcal{N}(\mathfrak{m}) \cdot (4 + 4\pi r/\sqrt{n})^n)}{B^{1/2}}\right).$$

We then obtain

$$|G| \sum_{\substack{\ell^* \le r \\ \|\ell^*\| \le r}} g_{1/s}^2(\ell^*) \sum_{\substack{\chi' \in T^m \\ \chi_{\ell^*} = \chi_{\ell^*} \\ \le |G/T^m| \cdot c^{2N}}} |\lambda_{\chi'}|^{2N} \le |G| \cdot |G/T^m| \cdot c^{2N} \cdot g_{\frac{1}{\sqrt{2s}}}^{\frac{1}{\sqrt{2s}}} (\operatorname{Log}(\mathcal{O}_{K^{\mathrm{m},1}}^{\times})^{\vee}) \quad (179)$$

We obtain the following bound by combining Equations (177) and (179), dividing by $|G|$ (which accounts to dividing by $|G|^2$ under the square 2-norm) and using the identity $|G| = |G/T^m| \cdot \operatorname{Vol}(T^m)$. Assuming the Extended Riemann Hypothesis for Hecke L-functions (e.g., [43, §5.7]), and for all $r, s > 0$ with $rs > \sqrt{\frac{r}{4\pi}}$, we have

$$\left\| \mathcal{H}^N(s^{-n} g_s |T^m) - \frac{1}{|G|} \mathbf{1}_G \right\|^2 \le \frac{g_{\frac{1}{\sqrt{2s}}} (\operatorname{Log}(\mathcal{O}_{K^{\mathrm{m},1}}^{\times})^{\vee})}{\operatorname{Vol}(T^m)} \left( c^{2N} + \beta_{\sqrt{2rs}}^{(r)} \right) \quad (180)$$

$$\text{with } c = O\left( \frac{[\operatorname{Pic}_{K^m}^0 : G] \cdot \operatorname{log}(B) \operatorname{log}(B^n \cdot |\Delta_K| \cdot \mathcal{N}(\mathfrak{m}) \cdot (4 + 4\pi r/\sqrt{n})^n)}{B^{1/2}} \right).$$

### Tuning parameters

Let $1 > \varepsilon > 0$, $s > 0$ and $k \in \mathbb{R}_{>0}$ be given. We have $g_{\frac{1}{\sqrt{2s}}}(\operatorname{Log}(\mathcal{O}_{K^{\mathrm{m},1}}^{\times})^{\vee}) \le g_{1/s}(\operatorname{Log}(\mathcal{O}_{K^{\mathrm{m},1}}^{\times})^{\vee}) \le 2 \operatorname{Vol}(\operatorname{Log}(\mathcal{O}_{K^{\mathrm{m},1}}^{\times}))/\tilde{s}^r$ by smoothing arguments (see Lemma 2.20). Using that inequality and Hölder's inequality (i.e., $\|f \cdot 1\|_1 \le \|f\|_2 \|1\|_2$), noting that $\|1_G\|_2 = |G|$, we obtain, for each $r > \sqrt{r/(\sqrt{2}s)}$,

$$\|\mathcal{W}_G(B, N, s) - \mathcal{U}(G)\|_1^2 \quad (181)$$

$$\le |G| \cdot \left\| \mathcal{H}^N(s^{-r} g_s |T^m) - \frac{1}{|G|} \mathbf{1}_G \right\|_2^2 \quad (182)$$

$$\le |G/T^m| \cdot g_{\frac{1}{\sqrt{2s}}} (\operatorname{Log}(\mathcal{O}_{K^{\mathrm{m},1}}^{\times})^{\vee}) \cdot (c^{2N} + \beta_{\sqrt{2rs}}^{(r)}) \quad (183)$$

$$\le 2 \cdot |G| \cdot \tilde{s}^{-r} \cdot (c^{2N} + \beta_{\sqrt{2rs}}^{(r)}) \quad (184)$$
Here, $c = O(\frac{[\mathrm{Pic}_{K^m}^0 : G]\cdot\log(B)\log(B^n\cdot|\Delta_K|\cdot\mathcal{N}(\mathfrak{m})(4+2\pi r/\sqrt{n})^n)}{B^{1/2}})$. We proceed by bounding the two summands in Equation (184) separately.

* By putting$^{47}$ $r$ equal to

$$ \frac{1}{\sqrt{2s}} \cdot \max \left( \sqrt{r}, \sqrt{2 + r \log(1/\tilde{s}) + 2 \log(1/\varepsilon) + \log|G|} \right) $$

we deduce that $2 \cdot |G| \cdot \tilde{s}^{-r} \cdot \beta^{(r)}_{\sqrt{2rs}} \le \varepsilon^2/2$.

* Subsequently, choose$^{48}$ a $B = \tilde{O}([\mathrm{Pic}_{K^m}^0 : G]^2 \cdot n^{2k} [\log(|\Delta_K|\mathcal{N}(\mathfrak{m}))^2 + n^2 \log(r)^2])$, i.e.,

$$ B = \tilde{O}([\mathrm{Pic}_{K^m}^0 : G]^2 \cdot n^{2k} \cdot [\log(|\Delta_K|\mathcal{N}(\mathfrak{m}))^2 + n^2 \log(1/\tilde{s})^2 + n^2 \log(\log(1/\varepsilon))^2]) $$

such that $c \le 1/n^k$, where $c = O(\frac{[\mathrm{Pic}_{K^m}^0 : G]\cdot\log(B)\log(B^n\cdot|\Delta_K|\cdot\mathcal{N}(\mathfrak{m})(4+4\pi r/\sqrt{n})^n)}{B^{1/2}})$.

Lastly, taking any integer $N \ge \frac{1}{2k\log n} \cdot (r \cdot \log(1/\tilde{s}) + 2\log(1/\varepsilon) + \log|G| + 2)$

and noting that $c^{\frac{1}{k\log n}} \le 1/e$, we deduce that $2 \cdot |G| \cdot \tilde{s}^{-r} \cdot c^{2N} \le \varepsilon^2/2$.

Combining, we can bound the right-hand side of Equation (184) by $\varepsilon^2$. Taking square roots gives the final result. □

## A.2. SAMPLING OF RANDOM PRIME IDEALS

In this section we show how to sample prime ideals $\mathfrak{p}$ that are coprime with $\mathfrak{m}$ and whose class $[d^0(\mathfrak{p})]$ fall into $G \subseteq \mathrm{Pic}_{K^m}^0$, using an oracle that can check whether an ideal $\mathfrak{a}$ satisfies $[d^0(\mathfrak{p})] \in G$ or not. The algorithm doing this is a slight generalization of the algorithm sampling prime ideals in [14, Lemma 2.2]. Before giving this algorithm (together with its properties), we first need the following result on the number of prime ideals that are coprime with $\mathfrak{m}$.

**Lemma A.2.1 (ERH).** Let $\mathfrak{m} \subseteq \mathcal{O}_K$ be an ideal modulus and denote

$$ \pi_K^{\mathfrak{m}}(x) = |\{\mathfrak{p} \in \mathcal{I}_K^{\mathfrak{m}} \mid \mathfrak{p} \text{ prime and } \mathcal{N}(\mathfrak{p}) \le x\}| $$

for the number of prime ideals not dividing $\mathfrak{m}$ and having norm bounded by $x \in \mathbb{R}$. Let $\omega(\mathfrak{m})$ denote the number of different prime ideal divisors of $\mathfrak{m}$.

Then, there exists $x_0 \in \tilde{O}(\log^2|\Delta_K| + \omega(\mathfrak{m}))$ such that for all $x \ge x_0$ we have

$$ \pi_K^{\mathfrak{m}}(x) \ge \frac{x}{4 \log x}. $$

*Proof.* Denote $\pi_K(x) = |\{\mathfrak{p} \in \mathcal{I}_K \mid \mathfrak{p} \text{ prime and } \mathcal{N}(\mathfrak{p}) \le x\}|$, i.e., whenever $\mathfrak{m} = \mathcal{O}_K$. We will prove the statement for this specific case first. By simplifying an explicit result of Grenié and Molteni [36, Corollary 1.4], we obtain, under the

<footnote>$^{47}$We use the bound $\beta_{\alpha}^{(r)} \le e^{-\alpha^2}$ for $\alpha \ge \sqrt{r}$</footnote>

<footnote>$^{48}$In this bound on $B$ one would expect an additional $\log \log|G| \le \log \log|\mathrm{Pic}_{K^m}^0|$. But as it is bounded by $\log(\log(|\Delta_K|\mathcal{N}(\mathfrak{m})))$ (see Lemma 5.1), it can be put in the hidden polylogarithmic factors.</footnote>
Extended Riemann Hypothesis<sup>49</sup>,

$$ \left| \pi_K(x) - \pi_K(3) - \int_3^x \frac{du}{\log u} \right| \le \sqrt{x}[6 \log |\Delta_K| + 4n \log x + 14]. $$

Therefore, we have

$$ \begin{aligned} \pi_K(x) &\ge \int_3^x \frac{du}{\log u} - \sqrt{x}[6 \log |\Delta_K| + 4n \log x + 14] \\ &\ge \frac{x}{\log x} - \sqrt{x} \log(x)[6 \log |\Delta_K| + 4n + 14] \\ &= \frac{x}{\log x} \left( 1 - \frac{\log(x)^2(6 \log |\Delta_K| + 4n + 14)}{\sqrt{x}} \right) \ge \frac{x}{2 \log x} \end{aligned} $$

where the first inequality follows from omitting $\pi_K(3)$ and the second inequality from $\int_3^x \frac{du}{\log u} \ge \frac{x}{\log x}$ and from the assumption that $x > x_0$, where $x_0 \in \tilde{O}(\log^2 |\Delta_K|)$ such that $\frac{\log(x_0)^2(6 \log |\Delta_K| + 4n + 14)}{\sqrt{x_0}} < 1/2$.

For the general case of $\mathfrak{m} \neq \mathcal{O}_K$, we need to avoid $\mathfrak{m}$; so writing $\omega(\mathfrak{m})$ for the number of different prime ideals dividing $\mathfrak{m}$, we obtain

$$ \pi_K^{\mathfrak{m}}(x) \ge \pi_K(x) - \omega(\mathfrak{m}) \ge \frac{x}{2 \log x} \left( 1 - \frac{2 \cdot \omega(\mathfrak{m}) \cdot \log x}{x} \right) \ge \frac{x}{4 \log x}. $$

Where the last inequality can be deduced from the fact that $x > x_0$ and where $x_0 = \tilde{O}(\log^2 |\Delta_K| + \omega(\mathfrak{m}))$ is chosen such that $\frac{2 \cdot \omega(\mathfrak{m}) \cdot \log x_0}{x_0} < 1/2$. $\square$

The following lemma is a slight generalization of [14, Lemma 2.2], where we demand the Arakelov ray class of the sampled prime ideals to be lying in $G$, some subgroup of $\text{Pic}_{K^{\mathfrak{m}}}^0$.

**Lemma 5.4** (Uniform sampling of prime ideals, ERH). Let a basis of $\mathcal{O}_K$ be known, and let $\mathfrak{m}_0 \subseteq \mathcal{O}_K$ be a modulus. Let $G \subseteq \text{Pic}_{K^{\mathfrak{m}}}^0$ a finite-index subgroup and let $\mathcal{O}_G$ be an oracle that on input an ideal $\mathfrak{c}$ returns whether $[d^0(\mathfrak{c})] \in G$ or not. Let $\mathcal{P}_B = \{\mathfrak{p} \text{ prime ideal of } K \mid \mathcal{N}(\mathfrak{p}) \le B, \mathfrak{p} \nmid \mathfrak{m}_0 \text{ and } [d^0(\mathfrak{p})] \in G\}$.

There exists a bound

$$ B_0 = \tilde{O}\left(\left(\text{Pic}_{K^{\mathfrak{m}}}^0 : G\right)^2 \cdot \left[n^2(\log \log(1/\epsilon))^2 + n^2(\log(1/\tilde{s}))^2 + (\log(|\Delta_K| \cdot \mathcal{N}(\mathfrak{m})))^2\right]\right) $$

such that for all $B \ge B_0$, one can sample uniformly from $\mathcal{P}_B$ in expected time $O([\text{Pic}_{K^{\mathfrak{m}}}^0 : G] \cdot n^3 \log^2 B)$ and using $O([\text{Pic}_{K^{\mathfrak{m}}}^0 : G] \cdot n \log B)$ queries to $\mathcal{O}_G$.

*Proof.* The algorithm can be described as follows. Sample a uniform integer from $[0, B]$ and check if it is prime (if not, output ‘failure’). If it is, name the prime $p$, factor $p\mathcal{O}_K$ into prime ideals of $\mathcal{O}_K$ and list the different prime factors $\{\mathfrak{p}_1, \dots, \mathfrak{p}_k\}$ that have norm bounded by $B$, do not divide $\mathfrak{m}_0$ and satisfy $[d^0(\mathfrak{p}_j)] \in G$. If this set is empty, output ‘failure’; otherwise, choose one $\mathfrak{p}_j$ uniformly at random in $\{\mathfrak{p}_1, \dots, \mathfrak{p}_k\}$ and output it with probability $k/n$. Otherwise, output ‘failure’.

Let $\mathfrak{q} \in \mathcal{P}_B$ be arbitrary, and let $p = \mathfrak{q} \cap \mathbb{Z}$ the prime ‘below’ $\mathfrak{q}$. Then the probability of sampling this $\mathfrak{q}$ equals $\frac{1}{nB}$, namely, $\frac{1}{n}$ times the probability of sampling $p$.

<footnote n="49"><sup>49</sup>In the paper of Grenié and Molteni [36, Corollary 1.4], only the Dedekind zeta function $\zeta_K(s) = \sum_a \mathcal{N}(a)^{-s}$ needs to satisfy the condition that all of its non-trivial zeroes lie at the vertical line $\Re(s) = 1/2$.</footnote>
So, the probability of sampling successfully (that is, no failure) equals

$$ \frac{|\mathcal{P}_B|}{nB} \geq \frac{1}{8 \cdot [\text{Pic}_{K^m}^0 : G] \cdot n \log B} $$

since, by Equation (169), denoting $\bar{\mathcal{P}}_B = \{\mathfrak{p} \text{ prime ideal of K} \mid \mathcal{N}(\mathfrak{p}) \leq B, \mathfrak{p} \nmid m_0\}$,

$$ \frac{|\mathcal{P}_B|}{|\bar{\mathcal{P}}_B|} \geq \frac{1}{2 \cdot [\text{Pic}_{K^m}^0 : G]}, $$

and by Lemma A.2.1, we have $|\bar{\mathcal{P}}_B| \geq \frac{B}{4\log B}$ (by adequately increasing $B_0$ so that $B_0 \geq x_0$ from Lemma A.2.1).

The most costly part of the algorithm is the factorization of a prime $p \leq B$ in $O_K$. This can be performed using Kummer-Dedekind algorithm, which essentially amounts to factoring a degree $n$ polynomial modulo $p$. Using Shoup's algorithm [70] (which has complexity $O(n^2 + n \log p)$ [76, §4.1]) and the fact that the algorithm needs to repeat $[\text{Pic}_{K^m}^0 : G] \cdot n \log B$ times to get constant success probability, yields the complexity claim and the query complexity for $O_G$. $\square$

### A.3. UPPER BOUND ON THE nTH SUCCESSIVE MINIMUM OF $O_K$ BY BHARGAVA ET AL.

The following theorem and its proof is a copy of that of Bhargava et al. [8, Theorem 3.1], with the difference that it is applied to the infinity norm and has explicit constants everywhere. A similar result, but also without explicit constants, can be found in an article by Peikert and Rosen [61, Lemma 5.4].

**Theorem A.3.1** (Bhargava et al. [8]). Let $K$ be any number field of degree $n$ and let $O_K$ be its ring of integers. Let $O_K \subseteq K_\mathbb{R}$ have the structure of a lattice via the Minkowski embedding (see Section 2), and denote $\lambda_j^\infty(O_K)$ for the j-th successive minimum with respect to the infinity norm in $K_\mathbb{R}$. Then

$$ \lambda_n^\infty(O_K) \leq |\Delta_K|^{1/n}. $$

*Proof.* Let $\alpha_j \in O_K$ attain the successive minima for the infinity norm $\lambda_j^\infty(O_K)$ for $j \in \{1, \dots, n\}$, with $\alpha_1 = 1$. For any element $\beta \in O_K$, we write $\beta = \sum_{j=1}^n [\beta]_j \alpha_j$, i.e., $[\beta]_j$ are the coordinates of $\beta$ with respect to $(\alpha_1, \dots, \alpha_n)$.

For $2 \leq k, l \leq n-1$ consider the $(n-2) \times (n-2)$-matrix $C = ([\alpha_k \alpha_l]_n)$, i.e., the matrix consisting of the coordinates of $\alpha_k \alpha_l$ with respect to $\alpha_n$. We will show at the end of this proof that this is a non-degenerate matrix, implying that there are no zero rows or columns. In other words, there exists a permutation $\pi : \{2, \dots, n-1\} \to \{2, \dots, n-1\}$ such that $[\alpha_k \alpha_{\pi(k)}]_n \neq 0$ for all $k \in \{2, \dots, n-1\}$.

So, the product $\alpha_k \alpha_{\pi(k)} \in O_K$ extends $\{\alpha_1, \dots, \alpha_{n-1}\}$ to a $n$-dimensional lattice; therefore we have $\|\alpha_k\|_\infty \|\alpha_{\pi(k)}\|_\infty \geq \|\alpha_k \alpha_{\pi(k)}\|_\infty \geq \lambda_n^\infty(O_K)$. Taking products over all $k \in \{2, \dots, n-1\}$ we obtain

$$ \prod_{k=2}^{n-1} \|\alpha_k\|_{\infty}^{2} = \prod_{k=2}^{n-1} \|\alpha_k\|_{\infty} \|\alpha_{\pi(k)}\|_{\infty} \geq (\lambda_n^\infty(O_K))^{n-2}. $$

Multiplying above equation by $\|\alpha_1\|_\infty^2 = 1$ and $\|\alpha_n\|_\infty^2 = \lambda_n^\infty(O_K)^2$, and using Minkowski's second inequality$^{50}$ [20, Chap. VIII, Thm. 5] $\prod_{k=1}^n \lambda_k^\infty(\Lambda) \leq \text{Vol}(\Lambda)$,

<footnote>$^{50}$Note that Minkowski's second inequality as stated in [20, Chap. VIII, Thm. 5] only states that $\prod_{k=1}^n \lambda_k^\infty(\Lambda) \cdot \text{Vol}(B) \leq 2^n \cdot \text{Vol}(\Lambda)$, where $B = \{x \in K_\mathbb{R} \mid \|x\|_\infty \leq 1\}$ ($B$ is a ball of dimension</footnote>