distribution over $\mathrm{Div}_{K^m}^0$ with a close distribution $\mathcal{D}_U$ whose 'folded analogue' $[\mathcal{D}_U]$ in $\mathrm{Pic}_{K^m}^0$ is uniform.

**Lemma 9.8** (The 'continuous version of Algorithm 2' mimicks a random walk). Let $\mathfrak{m}$ a modulus, let $N, B, s$ and $r$ as in Algorithm 2 and let $W_G = W_G(N, B, s)$ be the random walk distribution on $G \subseteq \mathrm{Pic}_{K^m}^0$ (see Definition 6.1). Let $W_r$ be the distribution on $(\alpha, \mathbf{a}) \in K_{\mathbb{R}} \times \mathrm{Div}_{K^m}^0$ obtained by sampling $\mathbf{a} \leftarrow W_G(N, B, s) + d^0(\mathbf{b}) + b$ with $b = \mathrm{Log}(y)$ where $y \in K_{\mathbb{R}}^0$ followed by sampling

$$ \alpha \in \mathrm{Exp}(\mathbf{a})_\tau \cap r\mathcal{B}_\infty $$

uniformly. Then the pair $((\beta) \cdot \bar{\mathbf{b}}^{-1}, \beta) \in \mathcal{I}_K^m \times \mathbf{b}$ obtained by running Algorithm 2 where lines 4 and 5 are replaced by Equation (63) (coined the 'continuous version'), follows the same distribution as $((\alpha) \cdot \mathrm{Exp}(-\mathbf{a}), \alpha \cdot \mathrm{Exp}_\infty(-\mathbf{a}_\infty))$ with $(\alpha, \mathbf{a}) \leftarrow W_r$.

**Proof.** Both the distribution $W_G$ and the 'continuous version of Algorithm 2' (where lines 4 and 5 are replaced by Equation (63), as in the proof of Theorem 9.5) involve the following two random processes: picking $N$ uniformly random primes from $\{\mathfrak{p} \in \mathcal{I}_K^m \text{ prime} \mid \mathcal{N}(\mathfrak{p}) \le B \text{ and } [d^0(\mathfrak{p})] \in G\}$ and sampling a Gaussian $a = (a_\nu)_\nu \in H$; both with the exact same parameters. Without loss of generality, we can therefore focus on one fixed sample $\{\mathfrak{p}_j \mid 1 \le j \le N\}$ of primes and one fixed vector $a = (a_\nu)_\nu \in H$. This means that we consider the fixed $\mathbf{a} = \sum_{j=1}^N d^0(\mathfrak{p}_j) + a + d^0(\mathbf{b}) + b \in \mathrm{Div}_{K^m}^0$ for the procedure involving $W_r$ and the fixed ideal $\bar{\mathbf{b}} = \mathbf{b} \prod_{j=1}^N \mathfrak{p}_j$ and distortion $\mathrm{Exp}(a+b) = (e^{n_{\nu_\sigma}^{-1}(a_{\nu_\sigma}+b_{\nu_\sigma})})_\sigma$ (recall that $(y_\sigma)_\sigma = (e^{n_{\nu_\sigma}^{-1}b_{\nu_\sigma}})_\sigma$; note that, by Lemma 9.4, we may assume that the entries of $y_\sigma$ are all positive) for the procedure involving the 'continuous version of Algorithm 2'. Then, writing $\bar{b} = \mathcal{N}(\bar{\mathbf{b}})^{1/n}$ and $\bar{\mathbf{b}} = \mathrm{Exp}(\mathbf{a}_f)$, we have

$$ \mathrm{Exp}(\mathbf{a})_\tau = \mathrm{Exp}(a+b)(\bar{\mathbf{b}} \cap \tau K^{m,1})/\bar{b} \quad \text{and} \quad \mathrm{Exp}_\infty(\mathbf{a}_\infty) = \mathrm{Exp}(a+b)/\bar{b} $$

Thus, $\alpha \mathrm{Exp}(-\mathbf{a}_\infty)$ for uniformly random $\alpha \in \mathrm{Exp}(\mathbf{a})_\tau \cap r\mathcal{B}_\infty$ is distributed as

$$ \mathrm{Exp}_\infty(-\mathbf{a}_\infty) \cdot \mathcal{U}(\mathrm{Exp}(\mathbf{a})_\tau \cap r\mathcal{B}_\infty) \quad (64) $$

$$ = \underbrace{\mathrm{Exp}(-a-b) \cdot \bar{b}}_{\mathrm{Exp}_\infty(-\mathbf{a}_\infty)} \cdot \mathcal{U} \left( \underbrace{\mathrm{Exp}(a+b)(\bar{\mathbf{b}} \cap \tau K^{m,1})/\bar{b}}_{\mathrm{Exp}(\mathbf{a})_\tau} \cap r\mathcal{B}_\infty \right) \quad (65) $$

$$ = \mathcal{U}((\bar{\mathbf{b}} \cap \tau K^{m,1}) \cap \mathrm{Exp}(-a-b) \cdot \bar{b} \cdot r\mathcal{B}_\infty) \quad (66) $$

which is exactly the distribution of $\beta \in \bar{\mathbf{b}}$ in Algorithm 2 for fixed $\bar{\mathbf{b}}$ and $(a_\nu)_\nu$. It follows that

$$ (\alpha) \mathrm{Exp}(-\mathbf{a}) = (\alpha) \mathrm{Exp}_\infty(-\mathbf{a}_\infty) \mathrm{Exp}_f(-\mathbf{a}_f) = (\alpha) \mathrm{Exp}_\infty(-\mathbf{a}_\infty)/\bar{\mathbf{b}} $$

is distributed as $(\beta)\bar{\mathbf{b}}^{-1}$, which finishes the proof. $\square$

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

We will need the following 'lifting' lemma, which states that the random walk distribution $W_G(N, B, s)$ over $\mathrm{Div}_{K^m}^0$ is close to a distribution $\mathcal{D}$ such that the class $[\mathcal{D}]$ is uniform over a coset $G \subseteq \mathrm{Pic}_{K^m}^0$.

**Lemma 9.9** (Lifting property of distributions). Let $G \subseteq \mathrm{Pic}_{K^m}^0$ be a finite-index subgroup and suppose that a distribution $\mathcal{D}: \mathrm{Div}_{K^m}^0 \to \mathbb{R}_{\ge 0}$ satisfies $\|\mathcal{D}\| - \mathcal{U}(G + [\mathbf{b}])\|_1 < \varepsilon$ for some coset $G + [\mathbf{b}]$, where $\mathbf{b} \in \mathrm{Pic}_{K^m}^0$. Then there exists a 'lifted' distribution $\mathcal{D}_U: \mathrm{Div}_{K^m} \to \mathbb{R}_{\ge 0}$ such that $[\mathcal{D}_U] = \mathcal{U}(G + [\mathbf{b}])$ and $\|\mathcal{D} - \mathcal{D}_U\|_1 < \varepsilon$.
Proof. Put

$$ \mathcal{D}_U(\mathbf{a}) = \begin{cases} \frac{1}{\mathrm{Vol}(G)} \cdot \frac{\mathcal{D}(\mathbf{a})}{[\mathcal{D}]([\mathbf{a}])} & \text{if } [\mathcal{D}]([\mathbf{a}]) \neq 0 \\ u & \text{otherwise} \end{cases}, $$

for some $u: \mathrm{Div}_{K^m}^0 \to \mathbb{R}_{\ge 0}$ that satisfies $[u] = \frac{1}{\mathrm{Vol}(G)} \cdot 1_G \in L_1(\mathrm{Pic}_{K^m}^0)$. Then, one can check that $[\mathcal{D}_U] = \frac{1}{\mathrm{Vol}(G)} \cdot 1_G$ is uniform on $G + [\mathbf{b}]$. Furthermore, writing $F$ for a fundamental domain in $\mathrm{Div}_{K^m}^0$ for $\mathrm{Pic}_{K^m}^0$, we have

$$ \begin{aligned} \|\mathcal{D} - \mathcal{D}_U\|_1 &= \int_{\mathbf{a} \in F} \sum_{\alpha \in K^{m,1}/\mu_{K^{m,1}}} |\mathcal{D}(\mathbf{a} + (\|\alpha\|)) - \mathcal{D}_U(\mathbf{a} + (\|\alpha\|))| d\mathbf{a} \\ &= \int_{[\mathbf{a}] \in \mathrm{Pic}_{K^m}^0} \left| [\mathcal{D}]([\mathbf{a}]) - \frac{1_{G+[\mathbf{b}]}([\mathbf{a}])}{\mathrm{Vol}(G)} \right| d([\mathbf{a}]) = \|[\mathcal{D}] - \mathcal{U}(G + [\mathbf{b}])\|_1 \le \varepsilon. \end{aligned} $$

The first equation holds by definition, the second equation by the fact that the sign of $(\mathcal{D}(\mathbf{a} + (\|\alpha\|)) - \mathcal{D}_U(\mathbf{a} + (\|\alpha\|)))$ depends (by construction) solely on the coset $[\mathbf{a}]$. $\square$

### 9.4. Statistical distance between the ‘continuous variant’ and the ordinary variant of Algorithm 2.
In this subsection we show that there is only a small statistical distance between the output distributions of the ‘continuous variant of Algorithm 2’ (where lines 4 and 5 are replaced by Equation (63)) and the ordinary variant of Algorithm 2 (with no changes). This result is used in the proof of part (A) of Theorem 9.5 and in the proof that Algorithm 2 is almost-Lipschitz in the later Lemma 10.6.

To prove the closeness of these two distributions, we fix all the input parameters and compare the two output distributions; where we note that we may assume that $y \in K_{\mathbb{R}}^0$ and that the entries of $y$ are positive, by Lemma 9.4. By the law of total probability, it is enough to show the closeness of these two distributions for a fixed sample of the primes $\{\mathfrak{p}_j\}$ (as in line 3), and hence a fixed ideal $\bar{\mathfrak{b}}$. Indeed, the difference between the two distributions can be attributed solely to the way the Gaussian $a = (a_\nu)_\nu \in H$ (discrete or continuous) is sampled and the influence it bears on the uniform distribution of $\beta$.

Though the input of Algorithm 2 is given in terms of an ideal $\mathfrak{b}$ and an element $y = \mathrm{Exp}((b_\nu)_\nu) \in K_{\mathbb{R}}^0$ with $b \in H$ we will often consider the divisor $\mathbf{a} = d^0(\mathfrak{b}) + b$ as input instead. As this is a one-to-one correspondence, and is used only theoretically (for cleanness of notation), no harm is done.

By a similar computation as in the proof of Lemma 9.8, one can deduce that the output $\beta$ is distributed as (denoting $b = \mathrm{Log}(y) \in H$)

$$ \mathcal{U}((\bar{\mathfrak{b}} \cap \tau K^{m,1}) \cap \mathrm{Exp}(-\mathrm{Log}((A_\sigma)_\sigma) - b) \cdot \mathcal{N}(\bar{\mathfrak{b}})^{1/n} \cdot r\mathcal{B}_\infty) \quad (67) $$

$$ = y^{-1} \cdot \mathcal{U}((y \cdot (\bar{\mathfrak{b}} \cap \tau K^{m,1})) \cap \mathrm{Exp}(-\mathrm{Log}((A_\sigma)_\sigma)) \cdot \mathcal{N}(\bar{\mathfrak{b}})^{1/n} \cdot r\mathcal{B}_\infty) \quad (68) $$

$$ = y^{-1} \cdot \mathcal{U}((y \cdot (\bar{\mathfrak{b}}_{m0} + \gamma)) \cap \mathrm{Exp}(-\mathrm{Log}((A_\sigma)_\sigma)) \cdot \mathcal{N}(\bar{\mathfrak{b}})^{1/n} \cdot r\mathcal{B}_\infty^\tau) \quad (69) $$

both in the ‘continuous version’ as in the ordinary version (since the definition of $(A_\sigma)_\sigma \in K_{\mathbb{R}}$ changes accordingly). Equation Equation (69) follows from Lemma 8.11; where $\mathcal{B}_\infty^\tau = \mathcal{B}_\infty \cap \tau K^{m0}$ (see Notation 9.2). Note that from Equation (69) follows that $(A_\sigma)_\sigma$ has only an influence on the shape (‘skewness’) of the box $\mathcal{N}(\bar{\mathfrak{b}})^{1/n} \cdot r\mathcal{B}_\infty^\tau$ where the uniform sampling takes place. All other things are equal; hence we introduce the following notation.
**Notation 9.10.** For $a \in H$, we denote $\mathcal{U}_a$ for the uniform distribution over the set $(y(\bar{\mathfrak{b}}\mathfrak{m}_0+\gamma))\cap\mathrm{Exp}(a)\cdot\mathcal{N}(\bar{\mathfrak{b}})^{1/n}\cdot r\mathcal{B}_{\infty}^{\tau}$, where $r = 48\cdot\omega\cdot\mathfrak{b}^{2n/b}\cdot n^{7/2}\cdot|\Delta_K|^{\frac{3}{2n}}\cdot\mathcal{N}(\mathfrak{m}_0)^{\frac{1}{n}}$ with $\omega \in \mathbb{Q}_{\ge 1}$; as in Algorithm 2, i.e.,

$$ \mathcal{U}_a := \mathcal{U}((y(\bar{\mathfrak{b}}\mathfrak{m}_0+\gamma))\cap\mathrm{Exp}(a)\cdot\mathcal{N}(\bar{\mathfrak{b}})^{1/n}\cdot r\mathcal{B}_{\infty}^{\tau}) = \mathcal{U}((y(\bar{\mathfrak{b}}\mathfrak{m}_0+\gamma))\cap\mathrm{Exp}(a)\cdot r_0\mathcal{B}_{\infty}^{\tau}). $$

where we write $r_0 := \mathcal{N}(\bar{\mathfrak{b}})^{1/n} \cdot r = 48 \cdot \omega \cdot \mathfrak{b}^{2n/b} \cdot n^{7/2} \cdot |\Delta_K|^{\frac{3}{2n}} \cdot \mathcal{N}(\bar{\mathfrak{b}}\mathfrak{m}_0)^{\frac{1}{n}}$. Note that, for $y\beta \in y(\bar{\mathfrak{b}}\mathfrak{m}_0 + \gamma) \cap \tau K_{\mathbb{R}}^{\mathfrak{m}_{\infty}}$, we have that

$$ \mathcal{U}_a[y\beta] > 0 \iff \log|\sigma_{\nu}(y\beta)| \le \log r_0 + n_{\nu}^{-1}a_{\nu} \text{ for all } \nu $$

where $n_{\nu} = 2$ if $\nu$ is complex and 1 otherwise. We denote

$$ S_{y\beta} = \{a \in H \mid n_{\nu}^{-1}a_{\nu} \ge \log|\sigma_{\nu}(y\beta)| - \log r_0 \text{ for all } \nu\}. $$

I.e., we have, for $y\beta \in y(\bar{\mathfrak{b}}\mathfrak{m}_0 + \gamma) \cap \tau K_{\mathbb{R}}^{\mathfrak{m}_{\infty}}$ and $a \in H$,

$$ a \in S_{y\beta} \iff y\beta \in \mathrm{Exp}(a) \cdot r_0 \mathcal{B}_{\infty}^{\tau} \iff \mathcal{U}_a[\beta] > 0. $$

We denote $\partial S_{y\beta}$ for the boundary of $S_{y\beta}$; note that this boundary is a subset of $\mathbb{r} = \dim(H)$ hyperplanes in $H$ of dimension $\mathbb{r} - 1$.

In the ordinary variant of Algorithm 2, an approximation $(A_{\sigma})_{\sigma}$ of $(e^{n_{\nu_{\sigma}}^{-1}\tilde{a}_{\nu_{\sigma}}})_{\sigma}$ with $\tilde{a} \in \ddot{H}$ is computed, hence leading to a slight error. For ease of notation we denote $(A_{\sigma})_{\sigma} = \mathrm{Exp}(\tilde{a}) = (e^{n_{\nu_{\sigma}}^{-1}\tilde{a}_{\nu_{\sigma}}})_{\sigma}$. By construction (see line 4) we have (for $\delta < 1/2$)

$$ \|\ddot{a} - \tilde{a}\|_2 \le n \max_{\sigma} |\log(A_{\sigma}) - \log(e^{n_{\nu_{\sigma}}^{-1}\tilde{a}_{\nu_{\sigma}}})| = n \max_{\nu} |\log(A_{\sigma_{\nu}}/e^{n_{\nu_{\sigma}}^{-1}\tilde{a}_{\nu}})| \quad (70) $$

$$ \le n \max_{\sigma} \log|1 - \delta| \le 2n \cdot \delta/(2n) = \delta. \quad (71) $$

So, the ordinary variant of Algorithm 2, with fixed choices of primes $\{\mathfrak{p}_j\}$ leading to $\bar{\mathfrak{b}}$, has output distribution

$$ \sum_{\ddot{a} \in \ddot{H}} \mathcal{U}_{\ddot{a}} \mathcal{G}_{\ddot{H},s}(\ddot{a}) = \sum_{\ddot{a} \in \dot{H}} \mathcal{U}_{\dot{a}}(-) \cdot \mathcal{G}_{\dot{H},s}(\dot{a}), $$

whereas the ‘continuous variant of Algorithm 2’ (with the same choices of $\{\mathfrak{p}_j\}$), has output distribution

$$ \int_{a \in H} \mathcal{U}_a \mathcal{G}_{H,s}(a) = \int_{a \in H} \mathcal{U}_a(-) \cdot \mathcal{G}_{H,s}(a). $$

**Lemma 9.11.** Using Notation 9.10, let $\delta > 0$ be a distance parameter and denote $B_{\delta}(a) \subseteq H$ for the 2-ball of radius $\delta$ around $a \in H$ (where we denote $B_{\delta} := B_{\delta}(0)$). Then, for $a \notin \bigcup_{y\beta \in y(\bar{\mathfrak{b}}\mathfrak{m}_0+\gamma)}(\partial S_{y\beta} \boxplus B_{\delta})$ and $a' \in B_{\delta}(a)$,

$$ \mathcal{U}_a = \mathcal{U}_{a'}. $$

*Proof.* For $a \notin \partial S_{y\beta} \boxplus B_{\delta}$ holds that $B_{\delta}(a) \cap \partial S_{y\beta} = \emptyset$. Hence for all $a' \in B_{\delta}$, the status of $y\beta \in e^{a+a'} \cdot \mathcal{N}(\bar{\mathfrak{b}})^{1/n} \cdot r_0\mathcal{B}_{\infty}^{\tau}$ (where $r_0 = \mathcal{N}(\bar{\mathfrak{b}})^{1/n} \cdot r$) does not change. Hence, if $a \notin \bigcup_{y\beta \in y(\bar{\mathfrak{b}}\mathfrak{m}_0+\gamma)}(\partial S_{y\beta} \boxplus B_{\delta})$, the entire distribution $\mathcal{U}_{a-a'} = \mathcal{U}_a$ is constant for $a' \in B_{\delta}$. This concludes the proof. $\square$
**Proposition 9.12.** Using the notation of Notation 9.10, let $1/(2n) > \varepsilon > 0$ be an error parameter. Let $s > 0$ be a Gaussian parameter and let $\ddot{H} \subseteq H$ be a full-rank lattice whose Voronoi domain $F$ satisfies

$$ \delta := \max_{a \in \ddot{F}} \|a\| \le \frac{\varepsilon^{4n^2s+1} \cdot s}{\omega^n \cdot e^{10n^2} \cdot |\Delta_K| \cdot \sqrt{n \log(2n/\varepsilon)}} \quad (72) $$

Then

$$ \left\| \int_{a \in H} \mathcal{U}_x \mathcal{G}_{H,s}(a) da - \sum_{\ddot{a} \in \ddot{H}} \mathcal{U}_{\ddot{a}} \mathcal{G}_{\ddot{H},s}(\ddot{a}) \right\|_1 \le 9\varepsilon $$

*Proof.* Writing $F$ for the Voronoi fundamental domain of the lattice $\ddot{H}$, using the identity $AB - A'B' = (A - A')B + A'(B - B')$, the triangle inequality and the fact that $\|\mathcal{U}_{\ddot{a}}\|_1 = 1$, we obtain

$$ \begin{aligned} & \left\| \int_{a \in H} \mathcal{U}_x \mathcal{G}_{H,s}(a) da - \sum_{\ddot{a} \in \ddot{H}} \mathcal{U}_{\ddot{a}} \mathcal{G}_{\ddot{H},s}(\ddot{a}) \right\|_1 \\ & \le \left\| \int_{a \in F} \sum_{\ddot{a} \in \ddot{H}} \mathcal{U}_{\ddot{a}+a} \mathcal{G}_{H,s}(\ddot{a}+a) - \mathcal{U}_{\ddot{a}} \frac{\mathcal{G}_{\ddot{H},s}(\ddot{a})}{\mathrm{Vol}(F)} da \right\|_1 \\ & \le \underbrace{\int_{a \in F} \sum_{\ddot{a} \in \ddot{H}} \|\mathcal{U}_{\ddot{a}+a} - \mathcal{U}_{\ddot{a}}\|_1 \mathcal{G}_{H,s}(\ddot{a}+a) da}_{(I)} + \underbrace{\int_{a \in F} \sum_{\ddot{a} \in \ddot{H}} \left| \mathcal{G}_{H,s}(\ddot{a}+a) - \frac{\mathcal{G}_{\ddot{H},s}(\ddot{a})}{\mathrm{Vol}(F)} \right| da}_{(II)} \end{aligned} \quad (73) $$

We will bound the parts (I) and (II) separately, starting with (I).

**Bound on (I).**

In the following sequence of inequalities we use respectively Lemma 9.11 (in combination with Equation (70)), $\mathrm{cov}(\ddot{H}) = \max_{x \in F} \|x\| = \delta$ and the fact that total variation distances are always bounded by 2. Also, we use a Gaussian tail bound (see Lemma 2.19) with radius $R := s\sqrt{n \log(2n/\varepsilon)} > 2\delta > 0$ (since we can deduce that $\delta < s/2$ from the assumption in Equation (72)). Combining this, writing $T_\delta = \bigcup_{y\beta \in y(\bar{b}m_0+\gamma)} (\partial S_{y\beta} \boxplus B_\delta)$, we obtain

$$ (I) \le \int_{a \in F} \sum_{\ddot{a} \in \ddot{H}} \|\mathcal{U}_{\ddot{a}+a} - \mathcal{U}_{\ddot{a}}\|_1 \mathcal{G}_{H,s}(\ddot{a}+a) da \le 2 \int_{a \in F} \sum_{\ddot{a} \in \ddot{H}} \mathcal{G}_{H,s}(\ddot{a}+a) da \quad (74) $$

$$ \le 2 \int_{a \in T_{2\delta}} \mathcal{G}_{H,s}(a) da \le \varepsilon + 2 \int_{a \in T_{2\delta} \atop \|a\|<R} \mathcal{G}_{H,s}(a) da \quad (75) $$

The third inequality follows from the observation that $\ddot{a}+a \in \partial S_{y\beta} \boxplus B_{2\delta}$ if $\ddot{a} \in \partial S_{y\beta} \boxplus B_\delta$ (since $a \in F \subseteq B_\delta$).

If $a \in \partial S_{y\beta} \boxplus B_{2\delta}$ and $\|a\| < R$, then (for all $\nu$) $n_\nu^{-1}a_\nu \ge \log|\sigma_\nu(y\beta)| - \log r_0 - R$ (since $R > 2\delta$), and hence $\log|\sigma_\nu(y\beta)| \le n_\nu^{-1}a_\nu + \log r_0 + R$, i.e., $\max_\sigma |\sigma(y\beta)| \le r_0 \cdot \exp(\max_\nu a_\nu)e^R \le r_0e^{2R}$ (since we assumed $\|a\| < R$). Recall, by definition, $r_0 = \mathcal{N}(\bar{b})^{1/n} \cdot r$. Hence, by the condition $\|a\| < R$, we may take the union $T_{2\delta} = \bigcup_{y\beta \in y(\bar{b}m_0+\gamma)} (\partial S_{y\beta} \boxplus B_{2\delta})$ only over those $y\beta$ satisfying $y\beta \in r_0e^{2R}B_\infty$.
We concentrate for the moment on the Gaussian weight on a single $S_{y\beta} \boxplus B_{2\delta}$ in the union of $T_{2\delta}$. Note that $\partial S_{y\beta}$ lies in a union of $\mathbb{r} = \dim(H) \le n$ hyperplanes in $H$. Denoting $P$ for a hyperplane in $H$ of dimension $\dim(H) - 1$ that goes through the origin, we have, for all $y\beta \in y(\mathfrak{b}\mathbf{m}_0 + \gamma)$,

$$ \int_{a \in \partial S_{y\beta} \boxplus B_{2\delta}} \mathcal{G}_{H,s}(a) da \le n \int_{a \in P \boxplus B_{2\delta}} \mathcal{G}_{H,s}(a) da \le n \cdot \operatorname{erf}(2\delta/s) \le 4n \cdot \delta/s, \quad (76) $$

where erf is the standard error function of the standard normal distribution that satisfies erf($x$) $\le \frac{2}{\sqrt{\pi}}x$. The inequality in Equation (76) holds because the hyper-plane $P \subseteq H$ going through the origin is the one where $P \boxplus B_{2\delta}$ has the largest Gaussian weight.

Writing $e^{2nR} \cdot N_0$ for an upper bound for $|(y(\bar{\mathfrak{b}}\mathbf{m}_0 + \gamma)) \cap r_0 e^{2R} \mathcal{B}_{\infty}|$ for which we will instantiate $N_0$ later, we combine Equation (75) and Equation (76), and the assumption in Equation (72) on $\delta$, to obtain

$$ (I) \le \varepsilon + 2 \int_{\substack{a \in \bigcup_{\beta \in \mathfrak{b}} (\partial S_{y\beta} \boxplus B_{2\delta}) \\ \|a\| < R}} \mathcal{G}_{H,s}(a) da \le \varepsilon + \frac{8n \cdot e^{2nR} \cdot N_0 \cdot \delta}{s} \le 2\varepsilon. \quad (77) $$

It remains to show that $\delta$ as in the assumptions of this proposition indeed satisfies $\delta \le \varepsilon \cdot s \cdot (8n)^{-1} e^{-2nR} \cdot N_0^{-1}$. We have $\exp(-2nR) = \exp(-2n^{3/2}s\sqrt{\log(2n/\varepsilon)}) \ge \exp(-4n^2s\log(1/\varepsilon)) = \varepsilon^{4n^2s}$ (where we use that $\varepsilon < 1/(2n)$). Also, by a similar reasoning as in Section 7.2.2, using $r_0 = \mathcal{N}(\bar{\mathfrak{b}})^{1/n}r$, and the definition $r = 48 \cdot \omega \cdot \mathfrak{b}^{2n/\mathfrak{b}} \cdot n^{7/2} \cdot |\Delta_K|^{3/2n} \cdot \mathcal{N}(\mathfrak{m}_0)^{1/n}$, we have

$$ \begin{aligned} N_0 &\in [e^{-1/4}, e^{1/4}] \cdot \frac{\mathcal{N}(\bar{\mathfrak{b}}) \cdot 2^{n_{\mathbb{R}}} \cdot (2\pi)^{n_{\mathbb{C}}} \cdot r^n}{\mathcal{N}(\bar{\mathfrak{b}}\mathbf{m}_0) \cdot \sqrt{|\Delta_K|}} \\ &\in [e^{-1/4}, e^{1/4}] \cdot 48^n \cdot \omega^n \cdot 2^{n_{\mathbb{R}}} \cdot (2\pi)^{n_{\mathbb{C}}} \cdot \mathfrak{b}^{2n^2/\mathfrak{b}} \cdot n^{7n/2} \cdot |\Delta_K| \end{aligned} $$

And hence $N_0 \le \omega^n \cdot e^{6n^2} \cdot |\Delta_K|$ since $48^n \cdot \mathfrak{b}^{2n^2/\mathfrak{b}} \cdot n^{7n/2} \le e^{n \log(48)+2n^2/e+7n \log(n)/2} \le e^{6n^2}$ (because $\log(48) + (2/e) \cdot n + 7 \log(n)/2 \le 6n$ for all $n > 0$). Therefore, indeed,

$$ \begin{aligned} \delta &\le \frac{\varepsilon^{4n^2s+1} \cdot s}{\omega^n \cdot e^{10n^2} \cdot |\Delta_K| \cdot \sqrt{n \log(2n/\varepsilon)}} \\ &= \varepsilon \cdot s \cdot e^{-4n^2} \cdot \varepsilon^{4n^2s} \cdot \omega^{-n} \cdot e^{-6n^2} \cdot |\Delta_K|^{-1} \cdot (n \log(2n/\varepsilon))^{-1/2} \quad (78) \\ &\le \varepsilon \cdot s \cdot (8n)^{-1} e^{-2nR} \cdot N_0^{-1} \end{aligned} $$

## Bound on (II)

We still write $F$ for the Voronoi domain of $\ddot{H}$. We apply Lemma 9.13 to obtain a bound on (II). Indeed, by putting $\Lambda = \ddot{H}$ and noting that $\lambda_n(\ddot{H}) \le 2\delta = 2 \operatorname{cov}_2(\ddot{H})$ (see Lemma 2.3) we surely have

$$ \lambda_n(\ddot{H}) \le 2\delta \le 2 \cdot \frac{\varepsilon^{4n^2s+1} \cdot s}{e^{10n^2} \cdot |\Delta_K| \cdot \sqrt{n \log(2n/\varepsilon)}} \le \frac{\varepsilon \cdot s}{5\pi n \cdot 2 \cdot \sqrt{n \log(2n/\varepsilon)}} $$

where we use that $e^{10n^2} > 20\pi n$ for $n \ge 1$. Now, since $2 \cdot \sqrt{n \log(2n/\varepsilon)} > \sqrt{n \log(4n/\varepsilon)}$ the parameter $s$ satisfies the assumptions of Lemma 9.13, hence we can bound (II) by $7\varepsilon$.
Combining Equation (73) and the bound on (II), we obtain

$$ \left\| \int_{a \in H} \mathcal{U}_x \mathcal{G}_{H,s}(a) da - \sum_{\ddot{a} \in \ddot{H}} \mathcal{U}_{\ddot{a}} \mathcal{G}_{\ddot{H},s}(\ddot{a}) \right\|_1 \le 9\epsilon, $$

as required.

□

**Lemma 9.13.** Let $\Lambda \subseteq V$ be a full-rank lattice, let $F$ be the Voronoi domain of $\Lambda$, let $\epsilon < 1/2$ be some error parameter and let $s > 5\pi \cdot \sqrt{n \log(4n/\epsilon)} \cdot \epsilon^{-1} \cdot n \cdot \lambda_n(\Lambda)$. Then

$$ \int_{x \in F} \sum_{\ell \in \Lambda} |\mathcal{G}_{V,s}(\ell + x) - |F|^{-1} \mathcal{G}_{\Lambda,s}(\ell)| dx \le 7\epsilon $$

*Proof.* Note that $\mathrm{cov}_2(\Lambda) = \max_{x \in F} \|x\| \le n \cdot \lambda_n(\Lambda)/2$ (see Lemma 2.3). Using smoothing arguments, (using that $s > \sqrt{\log(2n(1+1/\epsilon))/\pi} \cdot \lambda_n(\Lambda)$) writing $d = \dim(V)$, we see that (see Lemma 2.20)

$$ |F|^{-1} \cdot \mathcal{G}_{\Lambda,s}(\ell) = g_s(\ell) \cdot \frac{1}{|F| \cdot g_s(\Lambda)} \in [1-2\epsilon, 1+2\epsilon] \cdot s^{-d} \cdot g_s(\ell) = [1-2\epsilon, 1+2\epsilon] \cdot \mathcal{G}_{V,s}(\ell), $$

where we used that $1-2\epsilon \le (1+\epsilon)^{-1} \le (1-\epsilon)^{-1} \le 1+2\epsilon$ for $\epsilon < 1/2$. Using this, in combination with the tail bound (both using Corollary 2.18 and Lemma 2.19) with tail cut parameter $R := s\sqrt{n \log(2n/\epsilon)} > \mathrm{cov}_2(\Lambda)$, we obtain

$$ \int_{x \in F} \sum_{\ell \in \Lambda} |\mathcal{G}_{V,s}(\ell + x) - |F|^{-1} \mathcal{G}_{\Lambda,s}(\ell)| dx \quad (79) $$

$$ \le 2\epsilon + \int_{x \in F} \sum_{\substack{\ell \in \Lambda \\ \|\ell\| \le 2R}} |\mathcal{G}_{V,s}(\ell + x) - |F|^{-1} \cdot \mathcal{G}_{\Lambda,s}(\ell)| dx $$

$$ \le 2\epsilon + 4\epsilon + \int_{a \in F} \sum_{\substack{\ell \in \Lambda \\ \|\ell\| \le 2R}} |\mathcal{G}_{V,s}(\ell + x) - \mathcal{G}_{V,s}(\ell)| dx $$

$$ \le 6\epsilon + \int_{x \in F} \sum_{\substack{\ell \in \Lambda \\ \|\ell\| \le 2R}} \mathcal{G}_{V,s}(\ell + x) |1 - e^{5\pi \cdot \mathrm{cov}_2(\Lambda) \cdot R/s^2}| dx \quad (80) $$

$$ \le 6\epsilon + \frac{10\pi \mathrm{cov}_2(\Lambda)R}{s^2} \le 6\epsilon + \frac{5\pi n \lambda_n(\Lambda)R}{s^2} < 7\epsilon. \quad (81) $$

The inequality in Equation (80) follows from the fact that

$$ \begin{aligned} -\frac{s^2}{\pi} \log g_s(\ell + x) &= \|\ell + x\|^2 = \|\ell\|^2 + 2\langle\ell, x\rangle + \|x\|^2 \\ &\in [\|\ell\|^2 - 4R \mathrm{cov}_2(\Lambda), \|\ell\|^2 + 5R \mathrm{cov}_2(\Lambda)] \end{aligned} $$

which follows by Cauchy-Schwarz and the fact that $\max_{x \in F} \|x\| \le \mathrm{cov}_2(\Lambda) \le R$. The last inequalities in Equation (81) follow from $|1 - e^x| \le 2x$ for $x < 1/2$, and

$$ \frac{5\pi n \lambda_n(\Lambda)R}{s^2} = \frac{5\pi n \lambda_n(\Lambda)\sqrt{n \log(2n/\epsilon)}}{s} < \epsilon. $$

□
**9.5. The sampling theorem in arbitrary orders of a number field.** The sampling theorem (Theorem 9.5) is not restricted to the ring of integers $O_K$ of a number field $K$. Below we give a quick sketch how to amend the reasoning as to obtain a similar result for arbitrary orders within $K$.

Write $R \subseteq O_K$ for an order, $f_R = \{x \in K \mid xO_K \subseteq R\}$ for its conductor and $\Delta_R$ for its discriminant. Then we can in fact apply the sampling algorithm (Algorithm 2) for $R$ in place of $O_K$ if $f_R \mid \mathfrak{m}$. Indeed, for all ideals and elements involved are assumed to be coprime with $f_R$, there is a one-to-one correspondence between ideal arithmetic in $R$ and $O_K$, by the maps $\mathfrak{A} \mapsto \mathfrak{A}O_K$ and $\mathfrak{a} \mapsto \mathfrak{a} \cap R$ for ideals $\mathfrak{A}$ of $R$ and ideals $\mathfrak{a}$ of $O_K$. These maps are compatible with ideal multiplication, as long as all ideals involved are coprime to $f_R$ (e.g., combine [57, Chapter I, Proposition 12.10] and [3, Chapter 1, Extension and Contraction]).

**Lemma 9.14.** Let $R \subseteq O_K$ an order of a number field $K$ with conductor $f_R$. Suppose that $f_R \mid \mathfrak{m}$ and that $\tau \in R$. Then replacing every occurring ideal $\mathfrak{a}$ (that is, $\mathfrak{b}, \mathfrak{p}_j, \mathfrak{m}_0$) by the ideal $\mathfrak{A} = \mathfrak{a} \cap R$ in Algorithm 2 and using only arithmetic in $R$, does not change the output distribution.

*Proof.* We go through every step of Algorithm 2, where we will use that $\mathfrak{b}$ and the primes $\mathfrak{p}_j$ are coprime with $\mathfrak{m}_0$. In step 3 we multiply $\mathfrak{B} = \mathfrak{b} \cap R$ by random prime ideals $\mathfrak{P}_j = \mathfrak{p}_j \cap R$ satisfying $[d^0(\mathfrak{p}_j)] \in G$. Hence we obtain $\mathfrak{B} = \mathfrak{b} \cap R$ with $\mathfrak{b} = \mathfrak{b} \cdot \prod_j \mathfrak{p}_j$. The Gaussian distortion in step 4, is not affected by the specific order $R$.

In step 6, we have $\mathfrak{b} \cap \tau K^{m,1} = (\mathfrak{b}\mathfrak{m}_0 + \tilde{\tau}) \cap \tau K_{\mathbb{R}}^{m\infty}$ for $\tilde{\tau} \in \mathfrak{b}$ satisfying $\tilde{\tau} \equiv \tau \mod \mathfrak{m}_0$ (see Lemma 8.11). Since $f_R \mid \mathfrak{m}_0$, we have that $\mathfrak{M}_0 := \mathfrak{m}_0 \cap R = \mathfrak{m}_0$, by the very definition of the conductor; it is the largest ideal of $O_K$ that is also an ideal in $R$. Therefore, $\tilde{\tau} \in \tau + \mathfrak{m}_0 \subseteq R$, as $\tau$ is assumed to be in $R$.

So, $\mathfrak{b} \cap \tau K^{m,1} \cap R = (\mathfrak{b}\mathfrak{m}_0 + \tilde{\tau}) \cap R$. Since $f_R \mid \mathfrak{m}_0$, we have that $\tilde{\mathfrak{B}}\tilde{\mathfrak{M}}_0 = (\mathfrak{b}\mathfrak{m}_0) \cap R = \mathfrak{b}\mathfrak{m}_0$. Hence, $\mathfrak{b}\mathfrak{m}_0 + \tilde{\tau} = \tilde{\mathfrak{B}}\tilde{\mathfrak{M}}_0 + \tilde{\tau} \subseteq R$.

Then it follows that the sampling an output distribution of steps 6 and 7 are the same as in the original algorithm. $\square$

**Remark 9.15.** Note that, if only a sub-order $R \subseteq O_K$ is known, the call to Algorithm 1 in line 6 of Algorithm 2 cannot be done with $r = 48 \cdot \omega \cdot \mathfrak{b}^{2n/b} \cdot n^{7/2} \cdot |\Delta_K|^{3/n} \cdot \mathcal{N}(\mathfrak{m}_0)^{1/n}$. Instead, the larger $r = 48 \cdot \omega \cdot \mathfrak{b}^{2n/b} \cdot n^{7/2} \cdot |\Delta(R)|^{3/n} \cdot \mathcal{N}(\mathfrak{m}_0)^{1/n}$ must then be used, where $|\Delta(R)| = [O_K : R]^2 |\Delta_K|$ is the discriminant of $R$.

## 10. PROPERTIES OF THE IDEAL SAMPLING ALGORITHM

**10.1. Introduction.** In this section we will treat several important properties of the ideal sampling algorithm (Algorithm 2). These properties are phrased in terms of the output distribution of Algorithm 2, that is, the distribution of $\beta \in K$ on line 5. This distribution has three important properties: having the shifting property, being bounded and being almost Lipschitz continuous.

The boundedness and the shifting property are useful to show certain randomness properties of the output distribution of Algorithm 2 on a random input. In Part 2 of this paper, we will use Algorithm 2 on a 'Gaussian' input to rigorously compute $\mathfrak{S}$-unit groups. For this, these two properties will be of fundamental importance to show that sampling sufficiently many 'relations' will eventually lead to the full $\mathfrak{S}$-unit group.
The (almost-) Lipschitz continuous property is there to show that rounding or slightly disturbing the input of the ideal sampling algorithm does not impact the output of this algorithm significantly (this concerns the variable $Log(y) = b = (b_ν)_ν ∈ H$). From this one can conclude that rounding or finite precision issues do not play a role at all for the input of Algorithm 2.

By Lemma 9.4, the output distribution of Algorithm 2 is independent on the norm of $y ∈ K_{ℝ}^×$ and the signs of the entries. Hence, in theoretical arguments, we are always allowed to replace $y$ by $y^0 = y/|N(y)|^{1/n} ∈ K_{ℝ}^0$ and to assume that the entries of $y^0$ are positive. In the actual running algorithm we will not do this, because in general $y^0$ does not consist of rational numbers.

**The shifting property.** The shifting property of Algorithm 2 relates a certain change in the input to a similar change in the output. For this property to be phrased succinctly it is useful to consider the input of the algorithm to be the zero-degree Arakelov divisor $a = d^0(\mathfrak{b}) + b$ (one retrieves $\mathfrak{b} = \text{Exp}(a_f)$ and $b = a - d^0(\mathfrak{b})$, where $b = \text{Log}(y)$; here we use $H ⊆ \text{Div}_{K^m}^0$).

Shifting the input $a$ by a principal divisor, yielding $a + (|\alpha|)$ (with $\alpha ∈ K^{m,1}$), has as a result that the output distribution of Algorithm 2 is ‘multiplied’ by $\alpha$. More precisely, the probability of sampling $\eta ∈ K$ in the ideal sampling algorithm on input divisor $a$ is precisely the same as the probability of sampling $\alpha \cdot \eta$ on input $a + (|\alpha|)$. Writing $D_a$ for the output distribution of Algorithm 2 (see Notation 10.1) this can be more succinctly written as:

$$D_a(\eta) = D_{a+(|\alpha|)}(\alpha \cdot \eta).$$

This is called the ‘shifting’ property because a shift of the input divisor by a principal divisor ($|\alpha|$) causes the output distribution to ‘shift’ (multiplicatively) by the same element $\alpha$.

This property of Algorithm 2 is proven in Section 10.3.

**Boundedness.** The output distribution of Algorithm 2 being bounded means here that the output cannot exceed a certain size. This property is almost immediate by the fact that the output element is sampled in a (slightly) distorted box, where the distortion is dictated by a truncated discrete Gaussian (see Lemma 2.22). Exactly the dimensions of this box give the upper bound on the size of the elements; this is proven in Section 10.4.

**Lipschitz continuous.** The output distribution being almost-Lipschitz is useful when one considers the input to be discretized or rounded. Again, using the notation $D_a$ for the output distribution of Algorithm 2 on input divisor $a$ (see Notation 10.1), being almost Lipschitz means that the total variation distance between $D_a$ and $D_{a+a}$ with $a = (a_ν)_ν ∈ H$ is linearly upper bounded by $||a||$, allowing some slack by adding a small error. More precisely, there exist $L ∈ ℝ_{>0}$ and a small $\eta ∈ [0, 1)$ such that for all $a, a ∈ H$,

$$||D_{a+a} - D_a||_1 \le L \cdot ||a|| + \eta.$$

This fact is proven in Section 10.5.
**10.2. Preliminaries.** The input of Algorithm 2 is given in terms of an ideal **b** and an element $y = \text{Exp}((b_\nu)_\nu) \in K_\mathbb{R}^0$ with $b \in H$. In this section about properties of this algorithm, it is cleaner to use an Arakelov divisor $\mathbf{a} = d^0(\mathbf{b}) + b$ as input instead<fnref n="9" />.

**Notation 10.1 (Output distribution).** For a fixed number field $K$, with modulus $\mathfrak{m}$, finite-index subgroup $G \subseteq \text{Pic}_{K^\mathfrak{m}}^0$, element $\tau \in \mathcal{O}_K$ coprime with $\mathfrak{m}_0$ and fixed error parameter $\varepsilon > 0$, block size $\mathbf{b}$, $\omega \in \mathbb{Q}_{\ge 1}$ and $\mathbf{a} = d^0(\mathbf{b}) + b \in \text{Div}_{K^\mathfrak{m}}^0$ (where $b$ is understood via the inclusion $H \subseteq \text{Div}_{K^\mathfrak{m}}^0$), we denote

$$ \mathcal{D}_{\mathbf{a}} \in L_1(K^*) $$

for the output distribution of $\beta$ from Algorithm 2 on input $\mathbf{b}$ (coprime with $\mathfrak{m}_0$) and $y = \text{Exp}(b) \in K_\mathbb{R}^0$. We will use the notation $\mathcal{D}_{\mathbf{a}}(\alpha)$ for the probability of sampling $\alpha \in K$ from $\mathcal{D}_{\mathbf{a}}$.

$$ \mathcal{D}_{\mathbf{a}}(\alpha) = \mathbb{P}_{x \leftarrow \mathcal{D}_{\mathbf{a}}} [x = \alpha]. $$

**10.3. Shifting Property.** In order to prove the shifting property of Algorithm 2, we first start by the following lemma, that shows what impact multiplication by an element $\alpha \in K^*$ has on a $(\tau$-equivalent) ideal lattice $\text{Exp}(\mathbf{a})_\tau$. This will then be used to show that the output distribution of Algorithm 2 ‘shifts’ (i.e., multiplies) by $\alpha$ if the input divisor is shifted by the principal divisor $(\|\alpha\|)$ in Lemma 10.3.

**Lemma 10.2.** For all $\mathbf{a} \in \text{Div}_{K^\mathfrak{m}}^0$, multiplication by $\alpha \in K^{\mathfrak{m},1}$ gives an additive group isomorphism

$$ \text{Exp}(\mathbf{a})_\tau \to \text{Exp}(\mathbf{a} + (\|\alpha\|)_f)_\tau, \quad \gamma \mapsto (\sigma(\alpha))_\sigma \cdot \gamma $$

and additionally, restricted to $r\mathcal{B}_\infty$, a bijection

$$ \text{Exp}(\mathbf{a})_\tau \cap r\mathcal{B}_\infty \to \text{Exp}(\mathbf{a} + (\|\alpha\|)_f)_\tau \cap \text{Exp}(-\|\alpha\|)_\infty \cdot r\mathcal{B}_\infty. $$

*Proof.* Very similar as in Lemma 7.5 part (i), multiplication by $(\sigma(\alpha))_\sigma \in K_\mathbb{R}$ yields a bijection from $\text{Exp}(\mathbf{a})_\tau$ to $\text{Exp}(\mathbf{a} + (\|\alpha\|)_f) \text{Exp}(-\|\alpha\|)_\infty = \text{Exp}(\mathbf{a} + (\|\alpha\|)_f)_\tau$. Multiplication by an element is straightforwardly a group morphism, so the first claim follows by the fact that bijective group morphisms are isomorphisms.

For the second part, observe that multiplication by $(\sigma(\alpha))_\sigma$ transforms the box $r\mathcal{B}_\infty$ into $(\sigma(\alpha))_\sigma \cdot r\mathcal{B}_\infty = (|\sigma(\alpha)|)_\sigma \cdot r\mathcal{B}_\infty = \text{Exp}_\infty(-\|\alpha\|)_\infty \cdot r\mathcal{B}_\infty$. $\square$

**Lemma 10.3.** For all degree-zero Arakelov divisors $\mathbf{a} \in \text{Div}_{K^\mathfrak{m}}^0$, the distribution $\mathcal{D}_{\mathbf{a}}$ satisfies the following shifting property for all $\alpha \in K^{\mathfrak{m},1}$,

$$ \mathcal{D}_{\mathbf{a}+(\|\alpha\|)}(-\alpha) = \mathcal{D}_{\mathbf{a}}(-\alpha) $$

*Proof.* Take an arbitrary $\mathbf{a} \in \text{Div}_{K^\mathfrak{m}}^0$ and write $\mathbf{a} = d^0(\mathbf{b}) + b \in \text{Div}_{K^\mathfrak{m}}^0$ for an ideal $\mathbf{b}$ and an $b = (b_\nu)_\nu \in H$ (where we see $b \in H \subseteq \text{Div}_{K^\mathfrak{m}}^0$). To prove the statement it is enough to show for every $\beta \in K^\mathfrak{m}$

$$ \mathcal{D}_{\mathbf{a}+(\|\alpha\|)}(\beta \cdot \alpha) = \mathcal{D}_{\mathbf{a}}(\beta) $$

<footnote n="9">⁹This is interchangeable, as the ideal $\mathbf{b} = \text{Exp}(\mathbf{a}_f)$ and element $b = \mathbf{a} - d^0(\mathbf{b})$ are readily retrieved (where $b = \text{Log}(y)$). It is important to note, however, that $\text{Exp}(\mathbf{a}) \neq y \cdot \mathbf{b}$. Instead, $\text{Exp}(\mathbf{a}) \cdot \mathcal{N}(\mathbf{b})^{1/n} = y \cdot \mathbf{b}$. We chose for this convention to make $\mathbf{a}$ a degree-zero Arakelov divisor.</footnote>
As can be proved in the same fashion as in Lemma 9.8, the distribution $\mathcal{D}_a$ is
the same as the distribution resulting from

$$
\alpha \leftarrow \operatorname{Exp}_{\infty} \left(-\left(\mathbf{a}+\mathbf{b}\right)_{\infty}\right) \cdot \mathcal{U}\left(\operatorname{Exp}\left(\mathbf{a}+\mathbf{b}\right)_{\tau} \cap r \mathcal{B}_{\infty}\right) \text { with } \mathbf{b}=d^{0}\left(\prod_{j} \mathbf{p}_{j}\right)+a,
$$

where $\mathbf{p}_j$ are sampled according to step 2 and $a = \text{Log}((A_\sigma)_\sigma)$ is sampled from a discrete Gaussian, as in step 4. Note that this $a$ is slightly distorted, due to the computation of $(A_\sigma)_\sigma$, but that is not problematic; the property used here is that this $a$ is distributed independently of the value of $\mathbf{a}$. We write $\mathbf{b} = d^0(\prod_j \mathbf{p}_j) + a$. This divisor corresponds to the ‘random walk part’ of the algorithm.

We seek to compare the distributions $\mathcal{D}_a$ and $\mathcal{D}_{a+(\|\alpha\|)}$. By the law of total probability, since the sampling of $\mathbf{b} = d^0(\prod_j \mathbf{p}_j) + a$ is independent of $\mathbf{a}$ and $(\|\alpha\|)$, it is sufficient to consider a fixed sample $\mathbf{b} = d^0(\prod_j \mathbf{p}_j) + a$ and compare the resulting distributions. These resulting distributions, for a fixed $\mathbf{b}$, denoted $\mathcal{D}_{\mathbf{a}|\mathbf{b}}$ and $\mathcal{D}_{\mathbf{a}+(\|\alpha\|)|\mathbf{b}}$, are

$$
\mathcal{D}_{\mathbf{a}|\mathbf{b}} = \mathrm{Exp}_{\infty}(-\langle \mathbf{b} + \mathbf{a} \rangle_{\infty}) \cdot \mathcal{U}(\mathrm{Exp}(\mathbf{b} + \mathbf{a})_{\tau} \cap r\mathcal{B}_{\infty}) \quad (82)
$$

and

$$
\begin{align}
\mathcal{D}_{\mathbf{a}+(\|\alpha\|)|\mathbf{b}} &= \operatorname{Exp}_{\infty}(-\langle \mathbf{b} + \mathbf{a} + (\|\alpha\|) \rangle_{\infty}) \cdot \mathcal{U}(\operatorname{Exp}(\mathbf{b} + \mathbf{a} + (\|\alpha\|) \rangle_{\tau}) \cap r\mathcal{B}_{\infty}) \tag{83} \\
&= \operatorname{Exp}_{\infty}(-\langle \mathbf{b} + \mathbf{a} \rangle_{\infty}) \cdot \mathcal{U}(\operatorname{Exp}(\mathbf{b} + \mathbf{a} + (\|\alpha\|)_{\mathrm{f}}) \cap \operatorname{Exp}_{\infty}(-\langle \|\alpha\| \rangle_{\infty}) \cdot r\mathcal{B}_{\infty}) \tag{84}
\end{align}
$$

$$
\begin{align}
&= \operatorname{Exp}_{\infty}(-\langle \mathbf{b} + \mathbf{a} \rangle_{\infty}) \cdot \mathcal{U}\left( (\sigma(\alpha))_{\sigma} \cdot \left( \operatorname{Exp}(\mathbf{b} + \mathbf{a})_{\tau} \cap r\mathcal{B}_{\infty} \right) \right) \tag{85} \\
&= (\sigma(\alpha))_{\sigma} \cdot \mathcal{D}_{\mathbf{a}|\mathbf{b}} \tag{86}
\end{align}
$$

where the first equality holds by definition, the second equality follows from pulling
$\mathrm{Exp}_{\infty}(-\langle\|\alpha\|\rangle_{\infty})$ into the uniform distribution and using the relation $\langle\|\alpha\|\rangle = \langle\|\alpha\|\rangle_f + \langle\|\alpha\|\rangle_{\infty}$, the third equality follows from Lemma 10.2 and the last equality by Lemma 9.8.

The result quickly follows from the law of total probability and the fact that
multiplying by $(\sigma(\alpha))_\sigma$ and $\alpha$ is the same in $K_\mathbb{R}$. $\square$

**Lemma 10.4 (Post-selection shifting lemma).** Let $S$ be a set of ideals coprime with $m_0$ and let $\mathcal{D}_a^S$ be the distribution obtained by running Algorithm 2 on input $\mathbf{a}$ and only outputting $\beta$ if $\beta/\bar{\beta} \in S$ and otherwise outputting $\perp$.

Then, this distribution satisfies

$$
\mathcal{D}_{\mathbf{a} + \|\alpha\|}^{S} (- \cdot \alpha) = \mathcal{D}_{\mathbf{a}}^{S} (-),
$$

for all $\alpha \in K^{\mathbb{m},1}$.

Proof. This uses the same proof structure as Lemma 10.3, again using Lemma 9.8. Reusing the notation $\mathcal{D}_{\mathbf{a}|\mathbf{b}}$ for $\mathbf{b} = d^0(\prod_j \mathbf{p}_j) + a$ as in Lemma 10.3, we proved that, for a fixed sample $\mathbf{b}$, we have

$$
\mathcal{D}_{\mathbf{a}|\mathbf{b}}(-) = \mathcal{D}_{\mathbf{a}+(\|\alpha\|)|\mathbf{b}}(\alpha - ). \quad (87)
$$

The ideal $\beta/\bar{\beta}$ (where $\beta, \bar{\beta}$ are from Algorithm 2 on input $\mathbf{a}$) is distributed as$^{10}$
$\mathrm{Exp}_f(-\mathbf{a}_f) \cdot \gamma$ with $\gamma \leftarrow \mathcal{D}_{\mathbf{a}|\mathbf{b}}$ (on input $\mathbf{a}$ with fixed $\mathbf{b}$).

<footnote>$^{10}$The distribution $\mathcal{D}_{\mathbf{a}|\mathbf{b}}$ concerns the right part $\alpha \operatorname{Exp}_{\infty}(-\mathbf{a}_{\infty})$ of Lemma 9.8, whereas $\beta/\bar{\beta}$ concerns $\alpha \operatorname{Exp}(-\mathbf{a}) = \alpha \operatorname{Exp}_{\infty}(-\mathbf{a}_{\infty}) \operatorname{Exp}_f(-\mathbf{a}_f)$.</footnote>
But replacing **a** with **a** + (|**α**|) here yields that the distribution of **β**/ **b̄** of Algorithm 2 on input **a** + (|**α**|) is equal to (for a fixed sample **b**)

$$ \mathrm{Exp}_f(-\langle \mathbf{a} + (\|\alpha\|)_f \rangle \cdot \gamma \text{ with } \gamma \leftarrow \mathcal{D}_{\mathbf{a} + (\|\alpha\|)|\mathbf{b}} $$

which is, by Equation (87), equal to

$$ \mathrm{Exp}_f(-\langle \mathbf{a} + (\|\alpha\|)_f \rangle \cdot \alpha \cdot \gamma \text{ with } \gamma \leftarrow \mathcal{D}_{\mathbf{a}|\mathbf{b}} $$

which is, by manipulation, equal to

$$ \mathrm{Exp}_f(-\mathbf{a}_f) \cdot \gamma \text{ with } \gamma \leftarrow \mathcal{D}_{\mathbf{a}|\mathbf{b}}. $$

So, for a fixed sample of **b** = $d^0(\prod_j \mathfrak{p}_j) + a$ the probabilities of obtaining $\beta/\bar{\mathfrak{b}}$ are the same, no matter whether the input was **a** or **a** + (|**α**|).

As a result, $\mathcal{D}_{\mathbf{a}|\mathbf{b}}^S = \alpha \cdot \mathcal{D}_{\mathbf{a}+\langle\alpha\rangle|\mathbf{b}}^S$, where $\mathcal{D}_{\mathbf{a}|\mathbf{b}}^S$ denotes the output distribution of Algorithm 2 on input **a** with fixed sample **b** $\leftarrow W(N, B, s)$ and the additional post-selection (i.e., outputting $\beta$ whenever $\beta/\bar{\mathfrak{b}} \in S$ and $\perp$ otherwise).

By the law of total probability the distributions of $\beta/\bar{\mathfrak{b}}$ for **a** or **a** + (|**α**|) are the same; and, thus the rejection of $\beta/\bar{\mathfrak{b}}$ for not being in $S$ happens for the same occurrences. Therefore, $\mathcal{D}_{\mathbf{a}+\langle\alpha\rangle}^S(-\cdot\alpha) = \mathcal{D}_{\mathbf{a}}^S(-)$ for all $\alpha \in K^{\mathfrak{m},1}$. $\square$

**10.4. Boundedness Property.** In this section we show that the output distribution $\mathcal{D}_{\mathbf{a}}$ is bounded, i.e., no arbitrarily large inputs occur. This can be seen by the fact that the output is sampled from a distorted box, where the distortion is distributed as a truncated discrete Gaussian (a bounded distribution by itself). Thus, the output must be confined to a certain box, slightly larger than the dimensions of the original undistorted box. This is made more formal in the following text.

Recall the Euclidean distance notion on $\mathrm{Div}_K$ in Section 2.8.

**Lemma 10.5.** Let **a** = $d^0(\mathfrak{b}) + b \in \mathrm{Div}_K^0$ with **b** ∈ $\mathcal{I}_K$ and $b = \mathrm{Log}(y) \in H$ and let $B, N, s, r, \varepsilon$ be as defined in Algorithm 2. Then, we have, for $\beta \leftarrow \mathcal{D}_{\mathbf{a}}$,

$$ \|\langle\beta\rangle\| \le 5 \log(B^N \cdot r^n) + \|\mathbf{a}\| + s \cdot \sqrt{n \log(8n^2/\varepsilon)}. $$

*Proof.*

**Bound on the norm of $\beta$.**

We start with a bound on $|\mathcal{N}(\beta)|$, which is of use for the rest of the proof. The output of $\beta \leftarrow \mathcal{D}_{\mathbf{a}}$ with $\mathbf{a} = d^0(\mathfrak{b})+b$ lies in the box $\mathrm{Exp}(-a-b) \cdot r \cdot \mathcal{N}(\bar{\mathfrak{b}})^{1/n} \cdot \mathcal{B}_\infty \subseteq K_\mathbb{R}$ (see lines 6 and 7 in Algorithm 2), where $a = (a_\nu)_\nu = \mathrm{Log}((A_\sigma)_\sigma) \in H$ is an approximation a sample of a (truncated) Gaussian distribution (see line 4 and 5 of Algorithm 2); and $b = (b_\nu)_\nu = \mathrm{Log}(y)$. Hence, since $a, b \in H$ do not change the norm (we may assume this by Lemma 9.4), we obtain $|\mathcal{N}(\beta)| \le \mathcal{N}(\bar{\mathfrak{b}}) \cdot r^n \le B^N \cdot r^n \cdot \mathcal{N}(\mathfrak{b})$; a bound on the norm of $\beta$.

**Split the bound on $\|\langle\beta\rangle\|$ into three parts.**

We have, by the triangle inequality,

$$ \|\langle\beta\rangle\| \le \|\langle\beta\rangle - \mathbf{a}\| + \|\mathbf{a}\|. \quad (88) $$

We seek to bound $\|\langle\beta\rangle\|$. To do so, we concentrate on $\|\langle\beta\rangle - \mathbf{a}\|$, which we can split in a ‘finite part’, a ‘constant part’ and an ‘infinite part’.

$$ \langle\beta\rangle - \mathbf{a} = \underbrace{\sum_{\mathfrak{p}} m_{\mathfrak{p}} \cdot \langle\mathfrak{p}\rangle}_{\text{finite part } \mathfrak{f}} - \underbrace{\sum_{\nu} \frac{n_{\nu} \log \mathcal{N}(\prod_{\mathfrak{p}} \mathfrak{p}^{m_{\mathfrak{p}}})}{n} \langle\nu\rangle}_{\text{constant part } \mathbf{c}} + \underbrace{\sum_{\nu} \iota_{\nu} \langle\nu\rangle}_{\text{infinite part } \mathbf{i}} . \quad (89) $$
where $n_ν = 2$ if $ν$ is complex and 1 otherwise.

**Bounding the finite part f and constant part c.**

Since $β ∈ \bar{b} ⊆ b$, we see that $(β) = a · b$ for an integral ideal $a$ (recall that $b = \text{Exp}(a_f)$). Hence, $\sum_p m_p · d^0(p) = d^0(a)$, has only positive coefficients $m_p ≥ 0$. Since $N(a) = |N(β)|/N(b) ≤ B^N · r^n$ by the norm bound on $β$ in the very beginning of this proof, we quickly deduce

$$B^N · r^n ≥ N(a) ≥ \prod_p N(p)^{m_p} ≥ 2^{\sum_p |m_p|} ≥ 2^{(\sum_p |m_p|^2)^{1/2}},$$

which implies

$$\|f\| ≤ (\sum_p |m_p|^2)^{1/2} ≤ \log(B^N · r^n)/\log(2) ≤ 2\log(B^N · r^n) \quad (90)$$

Similarly, for the constant part c, using $a = \prod_p p$, we have,

$$\|c\| ≤ \sqrt{\sum_{\nu} n_{\nu}^2} \cdot \frac{\log(N(a))}{n} ≤ \log(N(a)) ≤ \log(B^N \cdot r^n) \quad (91)$$

**Bounding the infinite part i.**

By definition (see Equation (89)), and by the inclusion of $H ⊆ \text{Div}_{K^m}^0$ we have

$$\iota_{\nu} = -n_{\nu} \log |\sigma_{\nu}(\beta)| + n_{\nu} \frac{\log(|N(\beta)|)}{n} - b_{\sigma} \in H \quad (92)$$

since $a = d^0(b) + b$. By the fact that $β$ lies in the box $\text{Exp}(-a-b) \cdot r \cdot N(\bar{b})^{1/n} \cdot \mathcal{B}_{\infty}$, we have $\log |\sigma_{\nu}(\beta)| ≤ -n_{\nu}^{-1}a_{\sigma} - n_{\nu}^{-1}b_{\sigma} + \log r + \log(N(\bar{b})^{1/n})$. Therefore,

$$-\log |\sigma(\beta)| ≥ n_{\nu}^{-1}a_{\sigma} + n_{\nu}^{-1}b_{\sigma} - \log r - \log(N(\bar{b})^{1/n}) \quad (93)$$

Hence, substituting Equation (93) into Equation (92), and using that $β ∈ \bar{b}$ (and hence $|N(β)| ≥ N(\bar{b}))$, we obtain

$$\iota_{\nu} ≥ a_{\nu} + n_{\nu} \log(|N(\beta)|^{1/n} \cdot N(\bar{b})^{-1/n} \cdot r^{-1}) ≥ a_{\nu} - n_{\nu} \log(r).$$

So, writing $ι - a ∈ H$, it satisfies $\sum_{\nu}(ι - a)_{\nu} = 0$ and $ι_{\nu} - a_{\nu} ≥ -n_{\nu} \log(r)$ for all $ν$. Then $\|ι - a\| = \sqrt{\sum_{\nu} |ι_{\nu} - a_{\nu}|^2}$ is bounded by<fnref n="11" /> $2\sqrt{n(n-1)}\log(r) ≤ 2\log(r^n)$. Hence, writing $i = (ι_{\nu})_{\nu}$, we have

$$\|i\| = \|ι\| ≤ \|a\| + 2\log(r^n) ≤ \|a\| + 2\log(B^N \cdot r^n). \quad (94)$$

<footnote n="11">¹¹Suppose a sequence $(x_1, \dots, x_n)$ satisfies $\sum_{j=1}^n x_j = 0$ and $x_j ≥ -t$ for all $j ∈ \{1, \dots, n\}$ for some $t ∈ \mathbb{R}_{>0}$. Then $\sum_{j=1}^n x_j^2 ≤ n(n-1)t^2$. This maximum is attained by, for example, $x_1 = (n-1)t$ and $x_j = -t$ for $1 < j ≤ n$.</footnote>

<footnote>We prove this by induction, where the case $n = 1$ is trivial (since then $x_1^2 = x_1 = 0 ≤ n(n-1)t^2$). For $n > 1$, we can assume that a non-zero sequence $(x_1, \dots, x_n)$ has a positive co-ordinate (by the zero-sum requirement). Moreover, we can assume it has only a single positive co-ordinate. Indeed, if there are multiple positive coordinates, say $x_1, x_2$, then the sequence $(y_1, \dots, y_{n-1}) = (x_1 + x_2, x_3, \dots, x_n)$ satisfies $\sum_{j=1}^{n-1} y_j = 0$ and $y_j ≥ -t$. Hence, $\sum_{j=1}^n x_j^2 ≤ \sum_{j=1}^{n-1} y_j^2 ≤ (n-1)(n-2)t^2 ≤ n(n-1)t^2$, by induction. For a single positive co-ordinate it is clear that $x_1 = (n-1)t$ and $x_j = -t$ for $1 < j ≤ n$ is the optimal solution.</footnote>

<footnote>Applying this to the sequence $q_{\sigma} = n_{\nu}^{-1}(ι_{\nu_{\sigma}} - a_{\nu_{\sigma}})$, we see that $\|ι - a\| ≤ 2\|(q_{\sigma})_{\sigma}\| ≤ 2\sqrt{n(n-1)\log(r)}$.</footnote>
**Combining the bounds on $||\mathbf{i}||$ and $||\mathbf{f}||$.**

Concluding, by combining Equations (88) to (91) and (94), we obtain

$$ \|\langle\beta\rangle\| \le \|\langle\beta\rangle - \mathbf{a}\| + \|\mathbf{a}\| \le \|\mathbf{f}\| + \|\mathbf{c}\| + \|\mathbf{i}\| + \|\mathbf{a}\| \quad (95) $$

$$ \le 5 \log(B^N \cdot r^n) + \|a\| + \|\mathbf{a}\|. \quad (96) $$

The final bound then comes from the fact that $a = (a_\nu)_\nu \in H$ is (an approximation of a) discrete Gaussian distributed with deviation $s$ computed according to the algorithm in Lemma 2.22 with $\varepsilon_G := \varepsilon/4$ (see 4 of Algorithm 2). Hence, $\|a\| \le s \cdot \sqrt{n \log(8n^2/\varepsilon)}$. $\square$

**10.5. (Almost)-Lipschitz Property.** The almost-Lipschitz-continuous property of the output distribution of Algorithm 2 implies that it does not matter too much if the input parameter $y = \text{Exp}(b) \in K_{\mathbb{R}}^0$ is slightly inaccurate or rounded to a vector of rational numbers due to machine precision.

This is relevant for Part 2 of this paper, where we will feed Algorithm 2 $y = \text{Exp}((b_\nu)_\nu)$ with a continuous Gaussian distributed $b \in H$. The Lipschitz-continuous property in this subsection essentially implies that using a discrete Gaussian distribution instead for $b \in H$ will only cause a very small error overhead.

**Lemma 10.6.** The output distribution of the sampling algorithm (Algorithm 2) is $\varepsilon$-almost Lipschitz continuous in the input parameter $b \in H$ with $y = \text{Exp}(b)$. That is, for $\mathbf{a} = d^0(\mathbf{b}) + b$ and $\mathbf{a}' = d^0(\mathbf{b}) + b' = \mathbf{a} + (b' - b)$ we have

$$ \frac{1}{2} \|\mathcal{D}_{\mathbf{a}} - \mathcal{D}_{\mathbf{a}'}\|_1 \le \frac{n^2}{2} \|b - b'\| + \varepsilon, $$

where $\frac{1}{2} \|\mathcal{D}_{\mathbf{a}} - \mathcal{D}_{\mathbf{a}'}\|_1$ is the total variation distance of the two distributions.

*Proof.* In this proof, like in the proof of Theorem 9.5, we will again assume that line 4 in Algorithm 2 is replaced by the line in Equation (63), and assume that $y \in K_{\mathbb{R}}^0$. Again we will refer to this as the ‘continuous version of Algorithm 2’. This proof will be structured as follows. First we will show that this ‘continuous version of Algorithm 2’ is actually Lipschitz continuous with Lipschitz constant $n^2/2$. After that we will use Proposition 9.12 to show that the Lipschitz continuity also ‘almost’ holds for the ordinary version of Algorithm 2, with an additional error of $\varepsilon$.

In the following, we will reason about the ‘continuous version of Algorithm 2’. The input $b \in H$ is only used in Algorithm 2 (as $b = \text{Log}(y)$) in combination with the variable $a = (a_\nu)_\nu \in H$, which sampled according to a continuous Gaussian distribution with deviation $s = 1/n^2$. The sum $a+b$ is then used combined in the rest of the algorithm.

So, for two different inputs $b, b' \in H$, the only thing that differs in the algorithm are the distributions of $a+b$ and $a'+b'$, for which $a, a'$ are (independently) sampled according to the same Gaussian distribution.

We denote the distributions respectively $\mathcal{G}_b$ and $\mathcal{G}_{b'}$; these are Gaussian distributions with deviation $s = 1/n^2$ centered at $b$ and $b'$ respectively (see Section 2.9).

Therefore, by the data processing inequality (Theorem 2.16), one immediately deduces that the statistical distance between the output distribution of the ‘continuous version of Algorithm 2’ on input $\mathbf{b}, b$ and $\mathbf{b}, b'$ is bounded above by

$$ \frac{1}{2} \|\mathcal{G}_{H,b} - \mathcal{G}_{H,b'}\|_1. $$
The total variation distance of two continuous (multivariate) Gaussian distributions with different centers can be bounded by the Kullback-Leibler divergence [60, Ch. 1, Ex. 11],

$$ \begin{aligned} \frac{1}{2} \| \mathcal{G}_{H,b} - \mathcal{G}_{H,b'} \|_1 &\le \frac{1}{2} \sqrt{\frac{1}{2} D_{KL}(\mathcal{G}_{H,b} \| \mathcal{G}_{H,b'})} \\ &\le \frac{1}{2} \sqrt{\frac{1}{4} \|b-b'\|^2/s^2} = \frac{\|b-b'\|}{4 \cdot s} = \frac{n^2 \cdot \|b-b'\|}{4} \end{aligned} $$

The last equality is obtained by instantiating $s = 1/n^2$.

As sketched in the introduction of this proof, we use that the ordinary version and the continuous version of Algorithm 2 only differ by $\varepsilon/2$, by the very same argument as in the proof of Theorem 9.5. Hence, the statistical distance between the ordinary version of Algorithm 2 input $b, b'$ and $b, b'$ is bounded by $\frac{n^2}{2} \cdot \|b-b'\| + \varepsilon$, as required. $\square$

In most use-cases, Algorithm 2 is repeated until success, for which the following lemma is more useful: it shows that the output distribution of the algorithm conditioned on a successful outcome is also almost-Lipschitz. This distribution conditioned on a successful outcome is exactly the same as the output distribution resulting from repeating the algorithm until success.

**Lemma 10.7.** The output distribution $D_{\mathbf{a}}^{\text{suc}}$, resulting from repeating the sampling algorithm (Algorithm 2) until success, is $\frac{\varepsilon}{\delta_S[r^n]}$-almost Lipschitz continuous in the input parameter $b \in H$ with $y = \text{Exp}(b)$. That is, for $\mathbf{a} = d^0(\mathbf{b}) + b$ and $\mathbf{a}' = d^0(\mathbf{b}) + b' = \mathbf{a} + (b' - b)$ we have

$$ \frac{1}{2} \| D_{\mathbf{a}}^{\text{suc}} - D_{\mathbf{a}'}^{\text{suc}} \|_1 \le \frac{n^2}{2\delta_S[r^n]} \cdot \|b-b'\| + \frac{\varepsilon}{\delta_S[r^n]}, $$

where $\frac{1}{2} \| D_{\mathbf{a}}^{\text{suc}} - D_{\mathbf{a}'}^{\text{suc}} \|_1$ is the total variation distance of the two distributions.

*Proof.* For this we apply the next Lemma 10.8 with the lower bound $\delta_S[r^n]$ on the success probability. $\square$

**Lemma 10.8.** Let $\mathcal{A}$ be a randomized algorithm that can have input $y$ and $y'$. Denote $\mathcal{A}_y$ respectively $\mathcal{A}_{y'}$ for the algorithm using $y$ respectively $y'$ as input. Assume that both $\mathcal{A}_y$ and $\mathcal{A}_{y'}$ have success probability at least $p \in (0, 1]$.

Now denote $\mathcal{B}_y$ for the algorithm running $\mathcal{A}_y$ until it outputs a successful output, and similarly denote $\mathcal{B}_{y'}$ for the algorithm running $\mathcal{A}_{y'}$ until success. By abuse of notation, denote $\mathcal{B}_y, \mathcal{B}_{y'}, \mathcal{A}_y, \mathcal{A}_{y'}$ for the output distributions of these algorithms. Then the total variation distances are related by

$$ \frac{1}{2} \| \mathcal{B}_y - \mathcal{B}_{y'} \|_1 \le \frac{\frac{1}{2} \| \mathcal{A}_y - \mathcal{A}_{y'} \|_1}{p}. $$

*Proof.* Denote $X \cup \{\perp\}$ for the output space of $\mathcal{A}$, where $\perp$ denotes failure (unsuccessful output) and where $x \in X$ are all successful outputs.

The output distribution $\mathcal{B}_x$ is the output distribution of $\mathcal{A}_x$ conditioned on a successful output. Hence, denoting $\mathcal{A}_x^{\text{success}}$ (and similarly for $x'$) for this conditional distribution, we have

$$ \| \mathcal{B}_x - \mathcal{B}_{x'} \|_1 = \| \mathcal{A}_x^{\text{success}} - \mathcal{A}_{x'}^{\text{success}} \|_1 = \sum_{x \in X} | \mathcal{A}_y^{\text{success}}[x] - \mathcal{A}_{y'}^{\text{success}}[x] |, $$
where $X$ is the probability space of the algorithm $\mathcal{A}$. The conditional probability of $\mathcal{A}$ outputting $x$ conditioned on a successful output (which are all of $x \in X$) then must equal $\frac{\mathcal{A}_y[x]}{p_0}$ with $p_0 = \mathbb{P}[\mathcal{A}_y$ gives successful output]; and similarly for input $y'$. Note that $|p_0 - p_1| \le \|\mathcal{A}_y - \mathcal{A}_{y'}\|_1$. Hence, writing $p = \min(p_0, p_1)$ and noting that $p_1 = \sum_{x \in X} \mathcal{A}_{y'}[x]$,

$$ \begin{aligned} & \sum_{x \in X} |\mathcal{A}_y^{\text{success}}[x] - \mathcal{A}_{y'}^{\text{success}}[x]| = \sum_{x \in X} \left| \frac{\mathcal{A}_y[x]}{p_0} - \frac{\mathcal{A}_{y'}[x]}{p_1} \right| \\ & \le \sum_{x \in X} \left| \frac{\mathcal{A}_y[x]}{p_0} - \frac{\mathcal{A}_{y'}[x]}{p_0} \right| + \sum_{x \in X} \left| \frac{\mathcal{A}_{y'}[x]}{p_0} - \frac{\mathcal{A}_{y'}[x]}{p_1} \right| \\ & \le \frac{1}{p_0} \sum_{x \in X} |\mathcal{A}_y[x] - \mathcal{A}_{y'}[x]| + \frac{1}{p_0} |p_1 - p_0| = \frac{1}{p_0} \sum_{x \in X \cup \{\perp\}} |\mathcal{A}_{y'}[x] - \mathcal{A}_{y'}[x]| \\ & \le \frac{\|\mathcal{A}_y - \mathcal{A}_{y'}\|_1}{p}. \end{aligned} $$

□

## 11. ESTIMATION OF THE FACTOR $\mathcal{N}(\mathfrak{m}_0)/\phi(\mathfrak{m}_0)$

**Lemma 11.1.** Let $K$ be a number field and let $\mathfrak{m}_0 \subseteq \mathcal{O}_K$ be an integral ideal. Then we have

$$ \frac{\mathcal{N}(\mathfrak{m}_0)}{\phi(\mathfrak{m}_0)} = \prod_{\mathfrak{p}|\mathfrak{m}_0} \frac{1}{1 - \mathcal{N}(\mathfrak{p})^{-1}}. $$

where $\phi(\mathfrak{m}_0) = |K^{\mathfrak{m}_0}/K^{\mathfrak{m}_0,1}|$ and where $\mathfrak{p}$ ranges over the prime ideals of $K$ dividing $\mathfrak{m}_0$.

*Proof.* If $\mathfrak{m}_0 = \mathcal{O}_K$, we have $\phi(\mathfrak{m}_0) = 1$. Otherwise $\phi(\mathfrak{m}_0) = |(\mathcal{O}_K/\mathfrak{m}_0)^\times|$. Writing $\mathfrak{m}_0 = \prod_{\mathfrak{p}|\mathfrak{m}_0} \mathfrak{p}^{v_{\mathfrak{p}}(\mathfrak{m}_0)}$, we have, by multiplicativity of the norm $\mathcal{N}$ and the (generalized) Euler totient function $\phi$ (which follows from the Chinese remainder theorem),

$$ \mathcal{N}(\mathfrak{m}_0) = \prod_{\mathfrak{p}|\mathfrak{m}_0} \mathcal{N}(\mathfrak{p})^{v_{\mathfrak{p}}(\mathfrak{m}_0)} \quad \text{and} \quad \phi(\mathfrak{m}_0) = \prod_{\mathfrak{p}|\mathfrak{m}_0} \mathcal{N}(\mathfrak{p})^{v_{\mathfrak{p}}(\mathfrak{m}_0)-1}(\mathcal{N}(\mathfrak{p}) - 1) $$

The quotient $\mathcal{N}(\mathfrak{m}_0)/\phi(\mathfrak{m}_0)$ then equals $\prod_{\mathfrak{p}|\mathfrak{m}_0} \frac{\mathcal{N}(\mathfrak{p})}{\mathcal{N}(\mathfrak{p})-1} = \prod_{\mathfrak{p}|\mathfrak{m}_0} \frac{1}{1-\mathcal{N}(\mathfrak{p})^{-1}}$. □

**Proposition 11.2 (ERH).** Let $K$ be a number field and let $\mathfrak{m}_0 = \prod_{\mathcal{N}(\mathfrak{p})<x} \mathfrak{p}$ be the product of all prime ideals with norm below $x \ge 10$. Then there exists $c_0 \in [-8, 8]$ and $c_1 \in [0, 2]$ such that

$$ \frac{\mathcal{N}(\mathfrak{m}_0)}{\phi(\mathfrak{m}_0) \cdot \rho_K} = \log(x) \cdot \exp \left( c_1 + c_0 \cdot \frac{\log |\Delta_K| + n \log x}{\sqrt{x}} \right). $$

*Proof.* Write, as in Bach's paper [5, §6],

$$ A(x) := \prod_{p<x} \frac{1-p^{-1}}{\prod_{\mathfrak{p}|p} (1-\mathcal{N}(\mathfrak{p})^{-1})}, \qquad (97) $$
for which we have the bound<fnref n="12" /> [5, Thm. 6.2 & Table 2]

$$|\log(\rho_K) - \log A(x)| \le 8 \cdot \left( \frac{\log |\Delta| + n \log x}{\sqrt{x}} \right), \qquad (98)$$

assuming the Riemann Hypothesis for the Dedekind zeta function of K.
By Lemma 11.1 and Equation (97), we have

$$\frac{\mathcal{N}(\mathfrak{m}_0)}{\phi(\mathfrak{m}_0)} = \prod_{\mathfrak{p}|\mathfrak{m}_0} \frac{1}{1 - \mathcal{N}(\mathfrak{p})^{-1}} = \prod_{p<x} \frac{1}{1 - p^{-1}} \cdot A(x) \qquad (99)$$

By taking logarithms of Equation (99) and subsequently applying Bach's bound (Equation (98)), we obtain

$$\log \left( \frac{\mathcal{N}(\mathfrak{m}_0)}{\phi(\mathfrak{m}_0)} \right) - \log(\rho_K) = \log\left(\prod_{p<x} \frac{1}{1-p^{-1}}\right) + \log A(x) - \log(\rho_K) \qquad (100)$$

$$= \log\left(\prod_{p<x} \frac{1}{1-p^{-1}}\right) + c_0 \cdot \left( \frac{\log |\Delta| + n \log x}{\sqrt{x}} \right), \qquad (101)$$

for some $c_0 \in [-8, 8]$, by Equation (98). Apply Lemma 11.3 for the left-hand side of Equation (101), to obtain $\prod_{p<x} \frac{1}{1-p^{-1}} \in [e^0, e^2] \cdot \log x$. Exponentiating the expression yields the final result. $\square$

**Lemma 11.3.** For $x \ge 2$, we have

$$\log x \le \prod_{p<x} \frac{1}{1-p^{-1}} \le 6 \cdot \log x,$$

where the product ranges over all prime numbers up to x.

*Proof.* By the Euler product formula, we certainly have

$$\prod_{p<x} \frac{1}{1-p^{-1}} \ge \sum_{n<x} \frac{1}{n} \ge \log x.$$

For the upper bound, we invoke an explicit version of Mertens' third theorem of Rosser and Schoenfeld [66, Corollary 1, Equation 3.30],

$$\prod_{p<x} \frac{1}{1-p^{-1}} < \log(x) \cdot e^{\gamma} \cdot (1 + \frac{1}{\log(x)^2}).$$

Here, $\gamma \le 0.578$ is the Euler-Mascheroni constant. Instantiating with $x = 2$ and explicitly computing $e^{\gamma}$ yields a bound of $6 \cdot \log(x)$. $\square$

The following result is a simplified version of a result by Grenié-Molteni [36, Cor. 1.4].

**Lemma 11.4 (ERH, Grenié-Molteni).** Let K be a number field, with degree n, discriminant $\Delta_K$, and ring of integers $O_K$. Let $\mathfrak{m}_0 = \prod_{\mathfrak{p} \in \mathcal{N}(\mathfrak{p}) < x} \mathfrak{p}$ be the product of all prime ideals with norm below $x > 100$. We have

$$\log \mathcal{N}(\mathfrak{m}_0) \le x + \sqrt{x} \left( \left( \frac{\log x}{2\pi} + 2 \right) \log |\Delta_K| + \left( \frac{(\log x)^2}{8\pi} + 2 \right) n \right) \\ = x + O \left( \sqrt{x} \log(x) (\log |\Delta_K| + n \log x) \right).$$

<footnote n="12">¹²In his theorem, Bach writes $\zeta_K(1)$ for the residue $\rho_K$ at $s = 1$ of the Dedekind zeta function $\zeta_K$ [5, Thm. 6.2].</footnote>
PART 2

Rigorous computation of
class groups and unit groups

12. INTRODUCTION

In this second part of the article, we present the first algorithm for computing class
groups and unit groups of arbitrary number fields that provably runs in probabilis-
tic subexponential time, assuming the Extended Riemann Hypothesis. Let $K$ be a
number field of degree $n$ and discriminant $\Delta_K$. The determination of the structure
of its class group $\text{Cl}(K)$, together with a system of fundamental units, is one of
the main problems of computational number theory [21, p. 217]. Previous subex-
ponential algorithms were either restricted to imaginary quadratic fields, or relied
on several heuristic assumptions that have long resisted rigorous analysis.

12.1. **The Log-$\mathcal{S}$-unit lattice.** While we stated our main result as an algorithm for computing units and class groups in Theorem 1.3, our algorithm actually does slightly more than that: it computes the so-called Log-$\mathcal{S}$-unit lattice for any finite set $\mathcal{S}$ of prime ideals. For such a set $\mathcal{S}$ of prime ideals of $K$, we consider the group $\text{Div}_{K,\mathcal{S}} = \coprod_{\mathfrak{p} \in \mathcal{S}} \mathbb{Z} \times \coprod_{\nu} \mathbb{R}$, where $\nu$ ranges over all infinite places of $K$. The Log-$\mathcal{S}$-unit lattice $\text{Log}_{\mathcal{S}}(\mathcal{O}_{K,\mathcal{S}}^{\times})$ is a lattice living in $\text{Div}_{K,\mathcal{S}}$ generated by all vectors of the form $(v, -\text{Log}(\alpha))$ with $\text{Log} : K^{\times} \to \coprod_{\nu} \mathbb{R}$ the logarithmic embedding of $K$, where $\alpha \in K$ and $v = (v_p)_{p \in \mathcal{S}} \in \mathbb{Z}^{\mathcal{S}}$ are such that $\alpha \cdot \mathcal{O}_K = \coprod_{\mathfrak{p} \in \mathcal{S}} p^{v_p}$. Such elements $\alpha$ are called $\mathcal{S}$-units, hence the name of the lattice. See Section 15 for more details. The main result of this part is the following theorem.

**Theorem 12.1 (ERH).** There is a probabilistic algorithm which, on input a number field $K$ of degree $n$ and discriminant $\Delta_K$, an LLL-reduced basis of its ring of integers $\mathcal{O}_K$ and a finite set of prime ideals $\mathcal{S}$, computes the Log-$\mathcal{S}$-unit lattice and runs in expected time polynomial in the length of the input, in $L_{|\Delta_K|}(1/2)$, in $L_{n^n}(2/3)$, and in $\min(\rho_K, L_{|\Delta_K|}(2/3 + o(1)))$, where $\rho_K$ is the residue at 1 of the Dedekind zeta function $\zeta_K$.

The Log-$\mathcal{S}$-unit lattice computed by the algorithm is represented exactly by
elements $\alpha_i \in K$ and vectors $v_i \in \mathbb{Z}^{\mathcal{S}}$ such that the vectors $((v_i, -\text{Log } \alpha_i))_i$ form a
basis of $\text{Log}_{\mathcal{S}}(\mathcal{O}_{K,\mathcal{S}}^{\times})$. These elements $\alpha_i \in K$ are represented by a so-called compact
representation, i.e., as a product of smaller elements $\beta_j \in K$ (see Section 2.6). Even
though this is called a compact representation (and it is indeed more compact than
representing the $\alpha_i$ in a basis of $\mathcal{O}_K$), the bit-size of this representation of the $\alpha_i$
might be about as large as the running time of the algorithm.

12.2. **Previous work.** Shanks proposed in 1968 the first algorithm to compute the structure of the class group. His method, described for quadratic number fields, had an exponential running time $O_{\varepsilon}(|\Delta_K|^{1/4+\varepsilon})$ (or $O_{\varepsilon}(|\Delta_K|^{1/5+\varepsilon})$ assuming ERH). In
1989, Hafner and McCurley [37] proposed the first subexponential time probabilistic algorithm to compute the class group of imaginary quadratic number fields. Assuming ERH, they prove that the expected running time is $L_{|Δ_K|}(1/2, \sqrt{2})$. The case of imaginary quadratic number fields distinguishes itself by the finiteness of the unit group, and the existence of a *reduced* ideal in each class, two properties that proved helpful for a rigorous analysis of the algorithm.

In 1990, Buchmann [16] generalized this algorithm to fields of arbitrary degree. The analysis proved much more delicate, requiring several heuristic assumptions, notably on the distribution of smooth ideals. From these assumptions, Buchmann argued that the expected running time is $L_{|Δ_K|}(1/2, 1.7)$ when the degree of the field is constant. Practical improvements ensued, notably by Cohen, Diaz Y Diaz and Olivier [24]. In 2014, Biasse and Fieker [10] proposed an algorithm capable of dealing with fields of varying degree: under heuristic assumptions, they argue that the algorithm computes class groups in subexponential time $L_{|Δ_K|}(2/3 + \varepsilon)$ for arbitrary families of number fields, even with growing degree (and $L_{|Δ_K|}(1/2)$ whenever $n \le (\log |Δ_K|)^{3/4-\varepsilon}$, matching Buchmann’s claimed complexity for fixed-degree fields). In the meantime, no progress was made towards a rigorous analysis.

On the quantum computing side, a non-heuristic (assuming ERH) quantum polynomial time algorithm for computing $\mathbb{S}$-units and class groups was developed in 2016 by Biasse and Song [11], for any number field. The structure of this algorithm is different from the classical algorithms mentioned above: it relies on a quantum polynomial time algorithm solving the Continuous Hidden Subgroup Problem over $\mathbb{R}^m$ [29, 13]. In the present article, we only consider classical algorithms.

**12.3. The blueprint of a 'classical' Log-$\mathbb{S}$-unit lattice algorithm.** For the sake of simplicity we limit ourselves in this overview to the computation of the class group of a number field. The situation for the Log-$\mathbb{S}$-unit lattice is, at this high level, very similar.

Classical algorithms computing the class group proceed by generating many class group relations of the shape $[\prod_p \mathfrak{p}^{a_p}] = 1$, where the prime factors $\mathfrak{p}$ in the ideal $\prod_p \mathfrak{p}^{a_p}$ have norm bounded by $B$, i.e., the product is a $B$-smooth ideal. Since there are only finitely many generators $\mathfrak{p}$, enough ‘sufficiently independent’ relations of this shape then yield a description of the (finite) class group.

Such a relation $[\prod_p \mathfrak{p}^{a_p}] = 1$ is generally found by taking a random smooth ideal $\mathfrak{s} = \prod_p \mathfrak{p}^{b_p}$, and repeatedly sampling random elements $\alpha \in \mathfrak{s}$ until $(\alpha)\mathfrak{s}^{-1} = \prod_p \mathfrak{p}^{c_p}$ is also a smooth ideal. This gives the relation $1 = [\alpha] = [\prod_p \mathfrak{p}^{a_p}]$ with $a_p = b_p + c_p$.

*Heuristics in previous work.* The usual heuristics for class group algorithms (and Log-$\mathbb{S}$-unit lattice algorithms) are twofold. The first kind of heuristic assumption concerns a lower bound on the probability of the random ideal $(\alpha)\mathfrak{s}^{-1}$ to be smooth, see for instance [9, Heuristic 1, 2]. This allows one to bound the expected running time of sampling a single relation of the shape $[\prod_p \mathfrak{p}^{a_p}] = 1$. This smoothness probability is typically assumed to match the *density* of smooth ideals in the set of all ideals, a somewhat well-understood quantity related to the Dickman function.

The second kind of heuristic assumption concerns the number of such relations required in order to get the class group (rather than a larger group, of which the class group would be a quotient), see for instance [9, Heuristic 3]. The heuristic running time is then obtained as the product of the running time per relation and the required number of relations.
12.4. **Why our algorithm is rigorous.** We would like to stress that the following overview of our proof makes substantial simplifications for expository purposes (in particular, we ignore complex embeddings, which in the full proof play a similar role to prime ideals).

To circumvent the first heuristic about the cost of finding one relation, we use a special sampling algorithm (Algorithm 2) from Part 1 of this paper. This algorithm samples an element $\alpha \in \mathfrak{a}$ in such a way that the success probability of $(\alpha)\mathfrak{a}^{-1}$ being smooth is actually provably lower bounded by the density of smooth ideals in the set of all ideals (up to a multiplicative constant). This yields an upper bound on the expected cost of finding one class group relation. The sampling algorithm is the object of Part 1; this algorithm, together with its properties is used here as a black-box.

The remaining challenge addressed in the current part is circumventing the second heuristic, concerning the number of sampled group relations $[\prod_{\mathfrak{p}} \mathfrak{p}^{a_{\mathfrak{p}}}] = 1$ required to compute the class group (rather than an extension). To achieve that goal, we investigate the lattice of class group relations, which consists of those vectors $(a_{\mathfrak{p}})_{\mathfrak{p}}$ for which $[\prod_{\mathfrak{p}} \mathfrak{p}^{a_{\mathfrak{p}}}] = 1$.

**The class group lattice.** Denoting $\mathbb{S}$ for the set of prime ideals with norm bounded by $B$, we can construct the class group lattice $L_{\text{Cl}} = \{(a_{\mathfrak{p}})_{\mathfrak{p} \in \mathbb{S}} \in \mathbb{Z}^{\mathbb{S}} | [\prod_{\mathfrak{p} \in \mathbb{S}} \mathfrak{p}^{a_{\mathfrak{p}}}] = 1\} \subseteq \mathbb{Z}^{\mathbb{S}}$. In this paper we will construct (here treated quite informally) a randomized algorithm $\mathcal{A}: \mathbb{Z}^{\mathbb{S}} \to \mathbb{Z}^{\mathbb{S}}$ which has the following two properties.

(i) For $u \leftarrow \mathcal{A}(z)$, we have $u + z \in L_{\text{Cl}}$ and $\|v\| < E$ for some bound $E$.

(ii) The distribution of $\mathcal{A}(z)$ only depends on the coset $z + L_{\text{Cl}}$, i.e., $\mathcal{A}(z')$ and $\mathcal{A}(z)$ have the same distribution for any $z' \in z + L_{\text{Cl}}$.

This algorithm $\mathcal{A}$ uses the sampling algorithm from Part 1 mentioned above. We will use algorithm $\mathcal{A}$ to sample vectors of $L_{\text{Cl}}$ in such a way that we can prove that they will generate the full lattice with sufficiently good probability.

**Gaussians over the class group lattice.** Let $\mathcal{G}_{X,s}$ denote the discrete Gaussian distribution with parameter $s$ over the discrete set $X \subseteq \mathbb{R}^s$. We will make use of the following observation: when the deviation $s$ is large enough, sampling from $\mathcal{G}_{\mathbb{Z}^s,s}$ is indistinguishable from sampling first a uniform $c \in \mathbb{Z}^s/L_{\text{Cl}}$, then sampling from $c + \mathcal{G}_{L_{\text{Cl}},s}$.

For such $z \leftarrow c + \mathcal{G}_{L_{\text{Cl}},s}$ for $c \in \mathbb{Z}^s/L_{\text{Cl}}$ uniformly distributed, we see by property (ii) of $\mathcal{A}$ that

$$ \mathcal{A}(z) + z \sim \mathcal{A}(c) + (c + \mathcal{G}_{L_{\text{Cl}},s}) = (\mathcal{A}(c) + c) + \mathcal{G}_{L_{\text{Cl}},s} $$

By property (i) of $\mathcal{A}$, the distribution $\mathcal{A}(c)+c$ is bounded, i.e., for all $z \leftarrow \mathcal{A}(c)+c$ we have $\|z\| < E'$ with overwhelming probability for some bounded $E'$ (which depends on $E$ and on the covering radius of the lattice $L_{\text{Cl}}$). Then the variable $\mathcal{A}(z) + z$ is distributed as a Gaussian over $L_{\text{Cl}}$ with some independent 'noise' of size $E'$ caused by $\mathcal{A}(c)+c$. By taking the standard deviation $s$ (of all discrete Gaussians involved) much larger than this 'noise' of size $E'$, one can deduce that, for $z \leftarrow \mathcal{G}_{\mathbb{Z}^s,s}$,

$$ \mathcal{A}(z) + z \approx \mathcal{G}_{L_{\text{Cl}},s}. $$

Summarizing, sampling $z \leftarrow \mathcal{G}_{\mathbb{Z}^s,s}$ with large enough $s$ and computing $\mathcal{A}(z) + z$ allows to compute close to Gaussian samples from the class group lattice $L_{\text{Cl}}$. There
are well-known bounds for the number of samples required to generate the entire
lattice $L_{\text{Cl}}$ for such (close to) Gaussian samples.

The algorithm $\mathcal{A}$. The algorithm $\mathcal{A}: \mathbb{Z}^S \to \mathbb{Z}^S$ satisfying the properties (i) and (ii), is defined as follows. For $z \in \mathbb{Z}^S$, compute $\mathfrak{a} = \prod_{\mathfrak{p} \in \mathbb{S}} \mathfrak{p}^{z_{\mathfrak{p}}}$. Sample $\alpha \in \mathfrak{a}$ according to a not-too-wide discrete Gaussian and put $\mathfrak{b} = (\alpha) \cdot \mathfrak{a}^{-1}$. Then, use the sampling algorithm from Part 1 to find a representative $\prod_{\mathfrak{p} \in \mathbb{S}} \mathfrak{p}^{u_{\mathfrak{p}}} \in [\mathfrak{b}] = [\mathfrak{a}]^{-1} = [\prod_{\mathfrak{p} \in \mathbb{S}} \mathfrak{p}^{-z_{\mathfrak{p}}}]$, and output $u \in \mathbb{Z}^S$. We have that $u+z \in L_{\text{Cl}}$ and that $u$ is bounded (by properties of the sampling algorithm), so property (i) of algorithm $\mathcal{A}$ is true.

Property (ii) follows from the fact that the sample $\mathfrak{b} = (\alpha) \cdot \mathfrak{a}^{-1}$ only depends on the class $[\mathfrak{a}]$ of $\mathfrak{a}$, and not of the representation thereof<fnref n="13" />. Therefore, the output $u$ only depends on the class, i.e., the coset $z + L_{\text{Cl}}$ of the input $z$.

*Technicalities involving the infinite places.* In the general case of the Log-$\mathbb{S}$-unit lattice, there is also a *continuous* part involving the logarithmic unit lattice. Essentially the same proof structure applies, with additional technicalities introduced by the numerical approximation of the real numbers involved.

**12.5. More algorithmic problems.** Once we have an algorithm computing the Log-$\mathbb{S}$-unit lattice for any set of prime ideals $\mathbb{S}$, it is well known that one can use it to obtain other quantities, such as the units of the number field, or the structure of the class group. Combined with Theorem 17.7, which allows to decompose any integral ideal as an equivalent product of prime ideals in a sufficiently large set $\mathbb{S}$, this can also be used to solve other algorithmic problems, such as the principal ideal problem, or the class group discrete logarithm problem.

*Units.* To obtain the units of a number field $K$, one computes the Log-$\mathbb{S}$-unit lattice with an empty set $\mathbb{S}$. The output elements $\alpha_i$ of the algorithm is then a fundamental system of units of the number field. Note that these elements $\alpha_i$, even when they are represented in compact representation (see Section 2.6), might have a large bit-size (as large as the running time of the algorithm). Note also that computing a fundamental system of units of $K$ only describes the units modulo the roots of unity of $K$. Computing the roots of unity of $K$ can be done efficiently using, e.g., [21, Section 4.9.4], and is not related to the algorithm we describe here.

*Class group.* In order to obtain the structure of the class group, one chooses a set $\mathbb{S}$ generating the class group. It is known that under the extended Riemann hypothesis, there are such sets $\mathbb{S}$ of size polynomial in $\log|\Delta_K|\ll 4$. Given a basis $(\alpha_i, v_i)$ of the Log-$\mathbb{S}$-unit lattice, one then only keeps the rank $|\mathbb{S}|$ lattice $L$ generated by the vectors $v_i$. The class group of $K$ is then isomorphic to $\mathbb{Z}^S/L$. Note that $L$ is an integral lattice whose determinant is the class-number $h_k$ of $K$. Hence, the HNF basis of $L$ has bit-size polynomial in $|\mathbb{S}|$ and $\log h_k$, which is polynomial in $\log|\Delta_K|$. This means that the output size of the algorithm computing the class group is polynomially bounded in $\log|\Delta_K|$.

<footnote n="13">¹³This is actually false when considering the class group alone. To apply this 'independence of representation' technique, the infinite places (i.e., complex embeddings) must be included in the logarithmic embedding. The Log-$\mathbb{S}$-unit lattice accounts for the infinite places, so this technique applies.</footnote>
**Class group discrete logarithm.** The class group discrete logarithm problem asks, given as input any integral ideal $\mathfrak{a}$ and a set of prime ideals $\mathcal{S}$, to compute $\alpha \in K$ and $v \in \mathbb{Z}^\mathcal{S}$ such that $\mathfrak{a} = \alpha \cdot \mathcal{O}_K \cdot \prod_{\mathfrak{p} \in \mathcal{S}} \mathfrak{p}^{-v_{\mathfrak{p}}}$. Solving the class group discrete logarithm problem is exactly what is done by Algorithm 3, provided that the set $\mathcal{S}$ contains sufficiently many ideals of small norm. In order to solve the class group discrete logarithm problem for smaller sets $\mathcal{S}$, one can set $\mathcal{S}'$ to be the minimal set containing $\mathcal{S}$ and sufficiently many small prime ideals so that Theorem 17.7 applies. One can then solve the class group discrete logarithm problem in $\mathcal{S}'$ and compute the log-$\mathcal{S}'$-unit lattice. Solving the class group discrete logarithm in the smaller set $\mathcal{S}$ can then be performed efficiently by linear algebra, using the knowledge of the log-$\mathcal{S}'$-unit lattice to replace primes of $\mathcal{S}' \setminus \mathcal{S}$ by a product of primes of $\mathcal{S}$.

**Principal ideal problem.** The principal ideal problem is the problem of computing a generator $\alpha$ of a principal integral ideal $\mathfrak{a}$ (represented by an HNF basis). Again, this can be solved by choosing a set $\mathcal{S}'$ containing sufficiently many ideals of small norm and solving the class group discrete logarithm problem with respect to $\mathfrak{a}$ and this set $\mathcal{S}'$ using Algorithm 3. Then, computing the log-$\mathcal{S}'$-unit lattice allows one to solve the principal ideal problem by linear algebra. The size of the computed generator $\alpha$, even in compact representation (see Section 2.6), might be as large as the running time of the algorithm.

**12.6. Road map.** We start in Section 13 by specializing the ideal sampling theorem of Part 1 to our needs. Then, a lower bound is given on the density of smooth ideals, by means of a combinatorial technique, in Section 14. After that, some preliminaries on $\mathcal{S}$-units are treated in Section 15, and useful properties of $\mathcal{S}$-unit lattices are analyzed in Section 16.

Applying both the specialized sampling theorem and the density of the smooth ideals, we obtain an algorithm that samples a single $\mathcal{S}$-unit in Section 17.

In order to have an algorithm that outputs sufficiently ‘random’ $\mathcal{S}$-units, as to generate the entire $\mathcal{S}$-unit group, we combine two results. One is a bound on the ‘generating radius’ $\rho(\mathrm{Log}_{\mathcal{S}}(\mathcal{O}_{K,\mathcal{S}}^\times))$ of the log-$\mathcal{S}$-unit lattice that is polynomial in $\log|\Delta_K|$, which is proven in Section 16. This is combined with the properties of the sampling algorithm (see Section 10 in Part 1), to build an algorithm that indeed outputs ‘sufficiently random’ $\mathcal{S}$-units, as proved in Section 18.

After gathering many such $\mathcal{S}$-units, we would like to compute a set of fundamental $\mathcal{S}$-units, which can be seen as the multiplicative analogue of a basis of the log-$\mathcal{S}$-unit lattice. This is done in Section 19 by ‘post-processing’ the many $\mathcal{S}$-units, which essentially consists in applying the Buchmann-Kessler-Pohst algorithm.

Part 2 is then concluded in Section 21 with the final theorem on the complexity of the $\mathcal{S}$-unit algorithm.

## 13. SPECIALIZED IDEAL SAMPLING ALGORITHM

In this section, we specialize the main result from Part 1 to $G = \mathrm{Pic}_{K^m}^0$.

**Definition 13.1.** We denote by $S_B$ the set of $B$-smooth ideals, i.e.,

$$S_B = \{ \mathfrak{a} \text{ integral ideal of } \mathcal{O}_K \mid \text{ for any prime factor } \mathfrak{p} \text{ of } \mathfrak{a} \text{ we have } \mathcal{N}(\mathfrak{p}) \le B \}$$

We also extend the notion of smoothness to sets $\mathcal{S}$ of prime ideals: we say that $\mathfrak{a} \subseteq \mathcal{O}_K$ is $\mathcal{S}$-smooth if all its prime factors belong to $\mathcal{S}$: $S_{\mathcal{S}}$ is the set of $\mathcal{S}$-smooth
ideals. Recall that the local density of a set of ideals $\mathcal{S}$ is defined (Definition 2.11) as

$$ \delta_{\mathcal{S}}[x] = \min_{t \in [x/e^n, x]} \frac{|\mathcal{S}(t)|}{\rho_K \cdot t} = \min_{t \in [x/e^n, x]} \frac{|\{\mathfrak{b} \in \mathcal{S} \mid \mathcal{N}(\mathfrak{b}) \le t\}|}{\rho_K \cdot t}, $$

where, $\rho_K = \lim_{s \to 1} (s - 1)\zeta_K(s)$ (see Equation (4)).

Theorem 13.2 below is a specialization of Theorem 9.5 from Part 1, together with the properties proved in Section 10. We will only use this specialization in this part.

**Theorem 13.2 (ERH).** There is a randomized algorithm Sample such that the following holds. Let $K$ be a number field, with degree $n$, discriminant $\Delta_K$, and ring of integers $\mathcal{O}_K$ of which an LLL-reduced basis is given. Let $\mathfrak{m}_0 \subseteq \mathcal{O}_K$ be an ideal modulus of which the prime ideal factorization is known, let $\mathfrak{a} \in \mathcal{I}_K$ be an ideal coprime to $\mathfrak{m}_0$, and let $y \in K_{\mathbb{R}}^{\times}$ be represented by rational numbers. Let $\mathfrak{b} \ge 2$ be an integer, let $\omega \in \mathbb{Q}_{\ge 1}$, and let $r = 48 \cdot \omega \cdot \mathfrak{b}^{2n/\mathfrak{b}} \cdot n^{7/2} \cdot |\Delta_K|^{3/2n} \cdot \mathcal{N}(\mathfrak{m}_0)^{1/n}$. Given the above data, the algorithm Sample($\mathfrak{a}, y, \mathfrak{m}_0, \mathfrak{b}, \omega$) outputs $\beta \in \mathfrak{a}$ coprime to $\mathfrak{m}_0$ such that for any set $\mathcal{S}$ of ideals in $\mathcal{O}_K$ coprime to $\mathfrak{m}_0$, we have $(\beta) \cdot \mathfrak{a}^{-1} \in \mathcal{S} \cdot \mathcal{S}_{B_{rw}}$ with probability at least

$$ \frac{\mathcal{N}(\mathfrak{m}_0) \delta_{\mathcal{S}}[r^n]}{\phi(\mathfrak{m}_0) 6}, $$

for some smoothness bound $B_{rw} = \text{poly}(\log |\Delta_K|, \log \mathcal{N}(\mathfrak{m}_0))$, and where $\phi(\mathfrak{m}_0) = |(\mathcal{O}_K/\mathfrak{m}_0)^{\times}|$. Furthermore, the algorithm Sample runs in time

$$ \text{poly}(\text{size}(\mathfrak{a}), \text{size}(y), \log(\mathcal{N}(\mathfrak{m}_0)), \mathfrak{b}^b, \log |\Delta_K|, \text{size}(\omega)). $$

Additionally, the output distribution $\mathcal{D}_{y,\mathfrak{a}}$ of Sample on input $(y, \mathfrak{a}) \in (K_{\mathbb{R}}^{\times}, \mathcal{I}_K)$ (with $\mathfrak{m}_0, \mathfrak{b}$ and $\omega$ implicit) satisfies the following properties.

(1) (Almost Lipschitz-continuous). For all $y, y' \in K_{\mathbb{R}}^{\times}$,

$$ \|\mathcal{D}_{y,\mathfrak{a}} - \mathcal{D}_{y',\mathfrak{a}}\|_1 \le \frac{n^2}{2} \|\text{Log}(y) - \text{Log}(y')\| + \frac{1}{1200 \cdot |\Delta_K| \cdot r^n}. $$

(2) (Shifting property). For all $\beta \in K$ and $\alpha \in K^{\mathfrak{m}_0, 1}$, we have the following identity of distributions:

$$ \mathcal{D}_{y,\mathfrak{a}}[-] = \mathcal{D}_{y \cdot (|\sigma(\alpha)^{-1})_{\sigma}, \mathfrak{a} \cdot (\alpha)}[\alpha \cdot -] $$

(3) (Bounded). Writing $\|\beta\| \in \text{Div}_K^0$ and $\|\cdot\|$ for the norm on $\text{Div}_K$, we have

$$ \|\|\beta\|\| \le \|d(\mathfrak{a}) + \text{Log}(y)\| + O(\log^2 |\Delta_K| + \log \mathcal{N}(\mathfrak{m}_0) + n \log(\omega)) $$

(4) (Independent of $\mathcal{N}(y)$). $\mathcal{D}_{y,\mathfrak{a}} = \mathcal{D}_{y^0,\mathfrak{a}}$, where $y^0 = y/|\mathcal{N}(y)|^{1/n}$.

**Remark 13.3.** In the case where $\mathfrak{m}_0 = \mathcal{O}_K$, we get $\mathcal{N}(\mathfrak{m}_0) = \phi(\mathfrak{m}_0) = 1$, yielding a lower bound $\delta_{\mathcal{S}}[r^n]/6$ on the success probability.

*Proof.* The algorithm Sample is Algorithm 2 from Part 1 instantiated with modulus $\mathfrak{m} := \mathfrak{m}_0$, subgroup $G := \text{Pic}_{K^{\mathfrak{m}}}^0$ (yielding $[\text{Pic}_{K^{\mathfrak{m}}}^0 : G] = 1$), ideal $\mathfrak{b} := \mathfrak{a}, y := y \in K_{\mathbb{R}}^{\times}$, block size $\mathfrak{b} := \mathfrak{b}$ and element $\tau \in (\mathcal{O}_K/\mathfrak{m}_0)^{\times}$ uniformly random$^{14}$ if $\mathfrak{m}_0 \ne \mathcal{O}_K$ and $\tau = 1$ if $\mathfrak{m}_0 = \mathcal{O}_K$ (note that $\tau K^{\mathfrak{m},1} = K^{\mathfrak{m},1} = K^*$ if $\mathfrak{m} = \mathfrak{m}_0 = \mathcal{O}_K$). We put

<footnote>$^{14}$Uniform sampling of $\tau \in (\mathcal{O}_K/\mathfrak{m}_0)^{\times}$ can be done in time $\text{poly}(\log \mathcal{N}(\mathfrak{m}_0), \log |\Delta_K|)$ by sampling uniformly in $(\mathcal{O}_K/\mathfrak{q})^{\times}$ for all prime power divisors $\mathfrak{q} \mid \mathfrak{m}_0$ and using the Chinese Remainder theorem. This uses that the factorization of $\mathfrak{m}_0$ is assumed to be known.</footnote>
the error parameter $\epsilon := \frac{1}{1200|\Delta_K|r^n} \le \frac{1}{6|\Delta_K| \cdot r^n} \le \frac{1}{6 \cdot \rho_K \cdot r^n}$ (see Equation (5)). We will use Theorem 9.5.

Note that we may assume that $\delta_S[r^n] = \min_{t \in [r^n/e^n, r^n]} \frac{|\{b \in S \mid \mathcal{N}(b) \le t\}|}{\rho_K \cdot t} > 0$, since otherwise the statement of the theorem is inherently true, as any probability is at least zero. Hence, the set $\{b \in S \mid \mathcal{N}(b) \le r^n/e^n\}$ is nonempty, and we can immediately deduce

$$ \delta_S[r^n] = \min_{t \in [r^n/e^n, r^n]} \frac{|\{b \in S \mid \mathcal{N}(b) \le t\}|}{\rho_K \cdot t} \ge \frac{1}{\rho_K \cdot r^n} \ge 6 \cdot \epsilon. \quad (102) $$

By Theorem 9.5, the success probability of Algorithm 2 with these parameters is at least

$$ \frac{\mathcal{N}(\mathbf{m}_0)}{\phi(\mathbf{m}_0)} \frac{\delta_S[r^n]}{3} - \epsilon \ge \frac{\mathcal{N}(\mathbf{m}_0)}{\phi(\mathbf{m}_0)} \frac{\delta_S[r^n]}{3} - \frac{\delta_S[r^n]}{6} \ge \frac{\mathcal{N}(\mathbf{m}_0)}{\phi(\mathbf{m}_0)} \frac{\delta_S[r^n]}{6}. $$

where the first inequality holds by Equation (102) and the second one by the fact that $\mathcal{N}(\mathbf{m}_0) \ge \phi(\mathbf{m}_0)$. This proves the lower bound on the success probability of algorithm A in the theorem.

It remains to show the bound on $B_{rw}$ and the running time. Note that $[\text{Pic}_{K^m}^0 : G] = 1$, $\text{size}(\tau) = 1$, and that

$$ \log(1/\epsilon) = O(\log(|\Delta_K|r^n)) = O(\log^2|\Delta_K| + \log\mathcal{N}(\mathbf{m}_0) + \log\omega) $$

by direct computation. Hence

$$ B_{rw} = \text{poly}(\log|\Delta_K|, \log\mathcal{N}(\mathbf{m}_0), \log\omega) $$

and we have a running time of

$$ T = \text{poly}(b^b, \text{size}(a), \text{size}(y), \log(\mathcal{N}(\mathbf{m}_0)), \log|\Delta_K|, \text{size}(\omega)), $$

with no queries to any oracle, since $G = \text{Pic}_{K^m}^0$.

The properties (1)-(3), directly follow from the almost-Lipschitz continuity (Lemma 10.6), the shifting property (Lemma 10.3) and the boundedness property (Lemma 10.5) of Algorithm 2, with the following extra remarks. For the almost-Lipschitz continuity, we use that $\|\text{Log}(y^0) - \text{Log}(z^0)\| \le \|\text{Log}(y) - \text{Log}(z)\|$ for $y^0 = \frac{y}{|\mathcal{N}(y)|^{1/n}}$ and $z^0 = \frac{z}{|\mathcal{N}(z)|^{1/n}} \in K_{\mathbb{R}}^0$. For the Lipschitz error, we just substitute $\epsilon = \frac{1}{1200|\Delta_K|r^n}$. Here, $\text{Log}(y), \text{Log}(z) \in \text{Log}(K_{\mathbb{R}}^\chi) \hookrightarrow \text{Div}_K$ inherit their ‘natural’ norm from the norm on $\text{Div}_K$ (see Section 2.8).

For the boundedness property we use that

$$ \log(B^N r^n) = O(\log^2|\Delta_K| + \log\mathcal{N}(\mathbf{m}_0) + n \log(\omega)) $$

and $s = 1/n^2$ for the parameters used in Algorithm 2. Additionally, with the instantiation $\epsilon = \frac{1}{1200|\Delta_K|r^n}$ we have

$$ s\sqrt{n \log(8n^2/\epsilon)} \le O(\log|\Delta_K| + \log(r)) \le O(\log^2|\Delta_K| + \log\mathcal{N}(\mathbf{m}_0) + \log\omega). $$

With these simplifications, Lemma 10.5 tells us that $\|\|\beta\|\| \le \|d^0(a) + \text{Log}(y)\| + O(\log^2|\Delta_K| + \log\mathcal{N}(\mathbf{m}_0) + n \log(\omega))$. In order to obtain the desired bound (i.e., with $d(a)$ instead of $d^0(a)$), we use property (4) and we replace the input $(a, y)$ by $(b, z) := (a, y \cdot \mathcal{N}(a)^{1/n})$, so that $d^0(b) + \text{Log}(z) = d(a) + \text{Log}(y)$.

For the shifting property, we use the fact that $d(a) + \text{Log}(y) + \|\alpha\| = d(a \cdot (\alpha)) + \text{Log}(y \cdot (|\sigma(\alpha)|^{-1})_\sigma) \in \text{Div}_K$. For the last property, item (4), note that Sample does not depend on $|\mathcal{N}(y)|$, as follows from Lemma 9.4. $\square$
**Remark 13.4.** In the $\mathbb{S}$-unit computation algorithm in this paper, we assume that we are given an LLL-reduced basis of the ring of integers $O_K$. In other words, we take such a basis of $O_K$ as part of the input. We refer the reader to the discussion in Section 2.6.

**Remark 13.5.** Looking into the details of Part 1, the part $b^b$ in the running time of Theorem 9.5 is caused by a $b$-BKZ reduction on an ideal lattice $\mathfrak{a}$ (see Section 9). One may wonder whether, in the context of this section, using an ideal-SVP algorithm specifically designed for ideals (e.g., [28, 62]), instead of the BKZ algorithm, might lead to better results. This is unfortunately not the case at the moment, since all current algorithms exploiting the special structure of ideal lattices are heuristic. Additionally, they all use an algorithm computing the class group and the unit group of $K$ as a building block, which would be a circular requirement here.

**Remark 13.6.** Theorem 13.2 can also be made to work for arbitrary $\tau \in K^m$ (with an additional size($\tau$) in the running time). Even a random $\tau$ is possible (which might be useful in certain use-cases), though then the factorization of $\mathfrak{m}_0$ must be known. Indeed, using this factorization, uniform sampling of $\tau \in (O_K/\mathfrak{m}_0)^\times$ can be done in time $\text{poly}(\log N(\mathfrak{m}_0), \log |\Delta_K|)$ by sampling uniformly in $(O_K/\mathfrak{q})^\times$ for all prime power divisors $\mathfrak{q} | \mathfrak{m}_0$ and using the Chinese Remainder theorem.

## 14. DENSITY OF SMOOTH IDEALS

From the early work of Hafner and McCurley [37] for imaginary quadratic fields, to the generalizations for larger degree fields [16, 10], the core of the strategy to compute class groups as been to find random relations between classes involving smooth ideals. The probability of a somewhat random ideal to be smooth thus plays a key role in the analysis of such algorithms.

For any $0 < B \le x$, let $\Psi_K(x, B)$ be the number of $B$-smooth integral ideals of $K$ of norm at most $x$. It is well known [74] that whenever $(\log \log x)^{5/3+\epsilon} \le \log B \le \log x$, we have

$$ \Psi_K(x, B) = x \cdot \rho_K \cdot \rho(u) \left( 1 + O_{\epsilon, K} \left( \frac{\log(u+1)}{\log B} \right) \right), \quad (103) $$

where $\rho$ is the Dickman function, and $u = \frac{\log x}{\log B}$. One then needs to estimate the dependence in $K$ hidden in the big $O$ error. Unfortunately, scrutinizing the proof of [74], and using the best known uniform estimates of the ideal counting function [72], one finds that the hidden constant is exponential in the degree $n$ of $K$. This means that for the estimate of Equation (103) to be non-vacuous, one needs the smoothness bound $B$ to be doubly exponential in $n$.

It is not clear at the time whether this issue is unavoidable (i.e., the estimate $\Psi_K(x, B) \sim x \cdot \rho_K \cdot \rho(u)$ is truly only valid when $B$ is large compared to the degree), or is an artifact of the techniques not being precise enough. Therefore, instead of this estimate, we rely on the following weaker but simpler combinatorial bound.

**Lemma 14.1 (ERH).** For any $\epsilon > 0$, there exists a constant $C$ such that the following holds. Let $B \ge B_{\text{sm}} := C(n + \log |\Delta_K|)^{2+\epsilon}$, and let $A \le B/(4 \log B)$. Let $S_{A,B}$ be the set of integral ideals of $O_K$ whose prime divisors have norm in $(A, B]$. Let $x \ge B \cdot e^n$, and $u = \frac{\log x}{\log B}$. Then the density at $x$ of $S_{A,B}$ satisfies

$$ \delta_{S_{A,B}}[x] \ge \frac{(4 \log B)^{1-u}}{\rho_K B} u^{-u}. $$
*Proof.* Let $y \in [x/e^n, x]$. Note that, by the assumption $x \ge B \cdot e^n$, we have $y \ge B$. Let $(\mathfrak{p}_i)_{i=1}^N$ be the list of all prime ideals in $\mathcal{O}_K$ of norm in $(A, B]$. We have

$$|S_{A,B}(y)| = \left| \left\{ \prod_{i=1}^{N} \mathfrak{p}_i^{e_i} \middle| \sum_{i=1}^{N} e_i \log(\mathcal{N}(\mathfrak{p}_i)) \le \log y \right\} \right| \ge \left| \left\{ (e_i) \in \mathbb{Z}_{\ge 0}^N \middle| \sum_{i=1}^{N} e_i \le \frac{\log y}{\log B} \right\} \right|.$$

Writing $u_y = \frac{\log y}{\log B}$ and $v = \lfloor u_y \rfloor \ge 1$ (since $y \ge B$), we deduce

$$|S_{A,B}(y)| \ge \binom{v+N-1}{v} \ge \left(\frac{v+N-1}{v}\right)^v \ge N^v v^{-v} \ge N^v u_y^{-u_y}.$$

There exists $D > 0$ depending only on $\varepsilon$ such that for any $X > D$, we have $X^{1/(2+\varepsilon/2)} < X^{1/2}/(\log X)^2$. Then, by a result of Lagarias and Odlyzko [46], there is a constant $^{15}$E (absolute) such that for any $X \ge \max(D, E(n+\log |\Delta_K|)^{2+\varepsilon/2}) =$: $F$, we have $\frac{X}{2\log X} \le \pi_K(X) \le X$. Let $A' = \max(A, F)$. Recall that $A \le B/(4\log B)$. If furthermore $F \le B/(4\log B)$, then, $A' \le B/(4\log B)$, and we get

$$N = \pi_K(B) - \pi_K(A) \ge \frac{B}{2\log B} - \pi_K(A') \ge \frac{B}{2\log B} - A' \ge \frac{B}{4\log B}.$$

We now show that we can choose the constant $C$ such that indeed $F \le B/(4\log B)$ (hence the conditions of the lemma do imply $N \ge \frac{B}{4\log B}$). There exists $G > 0$ depending only on $\varepsilon$ such that for any $X > G$, we have $X^{\frac{2+\varepsilon}{2+\varepsilon}} < X/(4\log X)$. Therefore, for any $\delta > 0$ and $B \ge \max(G, F^\delta)$, we have

$$B/(4 \log B) \ge B^{\frac{2+\varepsilon}{2+\varepsilon}} \ge F^{\delta} B^{\frac{2+\varepsilon}{2+\varepsilon}}.$$

Choosing $\delta = \frac{2+\varepsilon}{2+\varepsilon/2}$, we get that $B/(4\log B) \ge F$ (as desired). Now, we have $F^\delta = \max(D^\delta, E^\delta(n + \log |\Delta_K|)^{2+\varepsilon})$. One can therefore choose the constant $C = \max(G, D^\delta, E^\delta)$, to enforce $B/(4\log B) \le F$.

We have just proved that $N \ge \frac{B}{4\log B}$. Then, we have

$$N^v \ge N^{u_y-1} \ge (y/B)(4 \log B)^{1-u_y}.$$

We obtain $|S_{A,B}(y)| \ge (y/B)(4 \log B)^{1-u_y} u_y^{-u_y}$, hence, writing $u = u_x$, we have

$$\frac{|S_{A,B}(y)|}{\rho_K \cdot y} \ge \frac{(4 \log B)^{1-u_y}}{\rho_K B} u_y^{-u_y} \ge \frac{(4 \log B)^{1-u}}{\rho_K B} u^{-u}.$$

□

## 15. BACKGROUND ON $\mathbb{S}$-UNIT LATTICES

15.1. **$\mathbb{S}$-units.** In this section, we formally define $\mathbb{S}$-units and the Log-$\mathbb{S}$-unit lattice, and recall some of its properties.

**Definition 15.1 (S-units).** Let $\mathbb{S}$ be a set of prime ideals of $\mathcal{O}_K$. An element $\alpha \in K$ is an $\mathbb{S}$-unit if and only if $\alpha \cdot \mathcal{O}_K = \prod_{\mathfrak{p} \in \mathbb{S}} \mathfrak{p}^{v_{\mathfrak{p}}}$ for some $(v_{\mathfrak{p}})_{\mathfrak{p} \in \mathbb{S}} \in \mathbb{Z}^{\mathbb{S}}$. We write $\mathcal{O}_{K, \mathbb{S}}^\times \subset K$ for the set of $\mathbb{S}$-units.

We will use the language of divisors introduced in Section 2.8.

<footnote n="15">¹⁵The original statement [46] (putting $L = K$ and $G = \{1\}$) reads $|\pi_K(X) - \text{Li}(X)| = O(X^{1/2} \log(|\Delta_K|X^n) + \log|\Delta_K|)$, where the constants in the big-$\mathcal{O}$ are absolute, and $\text{Li}$ is the logarithmic integral.</footnote>
**Definition 15.2 (S-Divisor group).** Let $\mathbb{S}$ be a (finite) set of prime ideals of $\mathcal{O}_K$. We define the $\mathbb{S}$-divisor group $\mathrm{Div}_{K,\mathbb{S}} \subseteq \mathrm{Div}_K$

$$ \mathrm{Div}_{K,\mathbb{S}} := \bigoplus_{\mathfrak{p} \in \mathbb{S}} \mathbb{Z} \times \bigoplus_{\nu} \mathbb{R}, $$

where $\nu$ ranges over the set of all infinite places (embeddings into the complex numbers up to possible conjugation). Additionally, we define the degree-zero $\mathbb{S}$-divisor group $\mathrm{Div}^0_{K,\mathbb{S}} = \mathrm{Div}_{K,\mathbb{S}} \cap \mathrm{Div}^0_K$.

In the present part of the article, we often write elements of $\mathrm{Div}_{K,\mathbb{S}}$ as a vector $((a_p)_{p \in \mathbb{S}}, (a_\nu)_\nu)$ to emphasize that it has finite dimension and that these elements are computationally represented as lists. We have the inclusion $H \subseteq \mathrm{Log}(K_\mathbb{R}^\times) \subseteq \mathrm{Div}_{K,\mathbb{S}}$. This degree-zero $\mathbb{S}$-divisor group serves as an ambient space for the Log-$\mathbb{S}$-unit lattice, which is defined as follows.

**Definition 15.3 (Log-$\mathbb{S}$-unit lattice).** Let $\mathbb{S}$ be a set of prime ideals of $\mathcal{O}_K$. The map $\mathrm{Log}_{\mathbb{S}}$ is defined over $\mathcal{O}_{K,\mathbb{S}}^\times$ by

$$ \mathrm{Log}_{\mathbb{S}} : \mathcal{O}_{K,\mathbb{S}}^\times \to \mathrm{Div}_{K,\mathbb{S}}^0 \\ \alpha \mapsto ((-v_p)_{p \in \mathbb{S}}, \mathrm{Log}(\alpha)) = -(|\alpha|). $$

where the $v_p$ are such that $\alpha \cdot \mathcal{O}_K = \bigoplus_{p \in \mathbb{S}} p^{v_p}$, and where $\mathrm{Log}(\alpha) = (n_\nu \log |\sigma_\nu(\alpha)|)_\nu \in \bigoplus_\nu \mathbb{R}$, with $n_\nu = 2$ if $\nu$ is complex and 1 otherwise, see Section 2.7.

The Log-$\mathbb{S}$-unit lattice is defined as

$$ \mathrm{Log}_{\mathbb{S}}(\mathcal{O}_{K,\mathbb{S}}^\times) = \{\mathrm{Log}_{\mathbb{S}}(\alpha) \mid \alpha \in \mathcal{O}_{K,\mathbb{S}}^\times\} \subset \mathrm{Div}_{K,\mathbb{S}}^0. $$

**Remark 15.4.** Note that the image of $\mathrm{Log}_{\mathbb{S}}$ on $\mathcal{O}_{K,\mathbb{S}}^\times$ is indeed in $\mathrm{Div}_{K,\mathbb{S}}^0$, since this map $\mathrm{Log}_{\mathbb{S}}$ is just the negative of the 'principal divisor' map $\mathbb{S} : K \to \mathrm{Div}_K$ restricted to $\mathcal{O}_{K,\mathbb{S}}^\times$, and principal divisors have degree zero (see Section 5.1).

The Log-$\mathbb{S}$-unit lattice is a lattice in the real vector space

$$ \mathrm{Div}_{K,\mathbb{S}}^0(\mathbb{R}) := \left\{ ((x_p)_{p \in \mathbb{S}}, (x_\nu)_\nu) \in \bigoplus_{\mathfrak{p} \in \mathbb{S}} \mathbb{R} \times \bigoplus_{\nu} \mathbb{R} \mid \sum_{\mathfrak{p} \in \mathbb{S}} x_p \cdot \log \mathcal{N}(\mathfrak{p}) + \sum_\nu x_\nu = 0 \right\}. \quad (104) $$

Here the sum formula in above definition is a generalization of the degree function to real $x_p \in \mathbb{R}$. This lattice $\mathrm{Log}_{\mathbb{S}}(\mathcal{O}_{K,\mathbb{S}}^\times)$ has rank $\mathrm{r} + |\mathbb{S}|$ where $\mathrm{r} = n_\mathbb{R} + n_\mathbb{C} - 1$, i.e., it is full rank in $\mathrm{Div}^0_{K,\mathbb{S}}(\mathbb{R})$.

Note that $\mathrm{Log}_{\mathbb{S}}(\mathcal{O}_{K,\mathbb{S}}^\times) \subseteq \mathrm{Div}^0_{K,\mathbb{S}} \subseteq \mathrm{Div}_K$ inherits a Euclidean length notion via that of $\mathrm{Div}_K$ (see Section 2.8). When $\mathbb{S} = \emptyset$, the lattice $\mathrm{Log}_{\mathbb{S}}(\mathcal{O}_{K,\mathbb{S}}^\times) \subset \mathbb{R}^n$ coincides with the Log-unit lattice $\mathrm{Log}(\mathcal{O}_K^\times)$.

**Lemma 15.5.** If $\mathbb{S}$ is a set of prime ideals generating the class group, then it holds that $^{16}\mathrm{Vol}(\mathrm{Log}_{\mathbb{S}}(\mathcal{O}_{K,\mathbb{S}}^\times)) = h_K \cdot \mathrm{Vol}(\mathrm{Log}(\mathcal{O}_K^\times)) = h_K \cdot R_K \cdot \sqrt{n_\mathbb{R} + n_\mathbb{C}}$, where $h_K$ is the class number of $K$, $R_K$ is the regulator, $n_\mathbb{R}$ is the number of real embedding and $n_\mathbb{C}$ is the number of complex pairs of embeddings. In particular, $\mathrm{Vol}(\mathrm{Log}_{\mathbb{S}}(\mathcal{O}_{K,\mathbb{S}}^\times))$ does not depend on the choice of $\mathbb{S}$ (as long as it generates the class group). Moreover, we have

$$ \log(\mathrm{Vol}(\mathrm{Log}_{\mathbb{S}}(\mathcal{O}_{K,\mathbb{S}}^\times))) \leq \log |\Delta_K|. $$

<footnote>$^{16}$We understand $\mathrm{Vol}(\mathrm{Log}_{\mathbb{S}}(\mathcal{O}_{K,\mathbb{S}}^\times))$ as the volume of the quotient $\mathrm{Div}^0_{K,\mathbb{S}}(\mathbb{R})/\mathrm{Log}_{\mathbb{S}}(\mathcal{O}_{K,\mathbb{S}}^\times)$.</footnote>
**Proof.** The lemma follows from Lemma 5.1 and the observation that the group $\mathrm{Pic}_K^0$ in [14] is isomorphic to $\mathrm{Div}_{K,S}^0 / \mathrm{Log}_S(\mathcal{O}_{K,S}^\times)$, whenever $S$ generates the class group. $\square$

A lower bound on the first minimum of the lattice $\mathrm{Log}_S(\mathcal{O}_{K,S}^\times)$ can be derived from Kessler's lower bound on the first minimum of the Log-unit lattice (Lemma 2.14).

**Lemma 15.6.** For any set of prime ideals $\mathcal{S}$, it holds that $\lambda_1(\mathrm{Log}_\mathcal{S}(\mathcal{O}_{K,\mathcal{S}}^\times)) \ge \frac{1}{1000 \cdot \sqrt{n \cdot \log(n)^3}}$.

**Proof.** Let $\alpha \in \mathcal{O}_{K,\mathcal{S}}^\times$ be such that $\mathrm{Log}_\mathcal{S}(\alpha)$ reaches the first minimum of $\mathrm{Log}_\mathcal{S}(\mathcal{O}_{K,\mathcal{S}}^\times)$, i.e., $\|\mathrm{Log}_\mathcal{S}(\alpha)\| = \lambda_1(\mathrm{Log}_\mathcal{S}(\mathcal{O}_{K,\mathcal{S}}^\times))$. Let $v_p \in \mathbb{Z}$ be such that $\alpha \cdot \mathcal{O}_K = \prod_{\mathbf{p} \in \mathcal{S}} \mathbf{p}^{v_p}$ (we know that they exist since $\alpha$ is an $\mathcal{S}$-unit). Assume first that one of the $v_p$ is non-zero (say $v_{p_0}$), then $\|\mathrm{Log}_\mathcal{S}(\alpha)\| \ge |v_{p_0}| \ge 1$ since $v_{p_0}$ is an integer. This gives us $\lambda_1(\mathrm{Log}_\mathcal{S}(\mathcal{O}_{K,\mathcal{S}}^\times)) \ge 1 \ge \frac{1}{1000 \cdot \sqrt{n \cdot \log(n)^3}}$ as desired.

Suppose now that all $v_p$'s are zero. Then $\alpha \in \mathcal{O}_K^\times$ is a unit and $\|\mathrm{Log}_\mathcal{S}(\alpha)\| = \|\mathrm{Log}(\alpha)\|$, and the bound follows from Lemma 2.14. $\square$

*Representation of the log-$\mathcal{S}$-unit lattice.* In the present part of this article, we will compute a generating set of the Log-$\mathcal{S}$-unit lattice by a collection of pairs $((v_p^{(j)})_{\mathbf{p} \in \mathcal{S}}, \alpha^{(j)}) \in \mathbb{Z}^\mathcal{S} \times K$, which generate $\mathrm{Log}_\mathcal{S}(\mathcal{O}_{K,\mathcal{S}}^\times)$ as a $\mathbb{Z}$-module. How this is done is explained more precisely in Section 18. Up to and including that section, the elements $\alpha^{(j)}$ in these pairs are represented by their coordinates with respect to the basis of $\mathcal{O}_K$ (as explained in Section 2.6).

In the sections after that, Section 19 and Section 21, instead of a generating set, a *basis* of $\mathrm{Log}_\mathcal{S}(\mathcal{O}_{K,\mathcal{S}}^\times)$ is computed. This will again lead to a collection of pairs $((w_p)_{\mathbf{p} \in \mathcal{S}}, \beta) \in \mathrm{Log}_\mathcal{S}(\mathcal{O}_{K,\mathcal{S}}^\times)$ but this time the $\beta \in \mathrm{Log}_\mathcal{S}(\mathcal{O}_{K,\mathcal{S}}^\times)$ are written in a so-called *compact representation*, see Section 2.6. Indeed, the elements $\beta$ will be of the form $\beta = \prod_j (\alpha^{(j)})^{N_j}$, where $\alpha^{(j)} \in K$ come from the generating set, and $N_j \in \mathbb{Z}$. The product is *not* evaluated but rather stored as $(\alpha^{(j)}, N_j)_j$. Even in this compact representation, the bit size of the final $N_j$ can be as large as the running time of the entire algorithm. For more details, see Section 2.6 and Section 21.

## 16. THE GENERATING AND COVERING RADIUS OF THE LOG-$\mathcal{S}$-UNIT LATTICE

In this section, we give an upper bound on the generating radius $\rho(\mathrm{Log}_\mathcal{S}(\mathcal{O}_{K,\mathcal{S}}^\times))$, which is related to the covering radius of the Log-$\mathcal{S}$-unit lattice (see Definition 2.2 and Lemma 2.3). Recall that $\rho(\mathrm{Log}_\mathcal{S}(\mathcal{O}_{K,\mathcal{S}}^\times))$ is the smallest real number $r > 0$ such that $\mathrm{Log}_\mathcal{S}(\mathcal{O}_{K,\mathcal{S}}^\times)$ can be generated by vectors of Euclidean norm $\le r$. Having an upper bound on this quantity $r$ will be useful in Section 18. Indeed, we will first see in Section 17 how to compute a single vector in $\mathrm{Log}_\mathcal{S}(\mathcal{O}_{K,\mathcal{S}}^\times)$, and we will then want, in Section 18, to compute a generating set of $\mathrm{Log}_\mathcal{S}(\mathcal{O}_{K,\mathcal{S}}^\times)$. In order to do so, we will need to know how short we can expect the vectors of this generating set to be, which is exactly the generating radius $\rho(\mathrm{Log}_\mathcal{S}(\mathcal{O}_{K,\mathcal{S}}^\times))$.

The first part of this section (until and including Lemma 16.8) is devoted to computing an upper bound on the covering radius$^{17}$ $\mathrm{Log}_\mathcal{S}'(\mathcal{O}_{K,\mathcal{S}'}^\times)$ of the Log-$\mathcal{S}'$-unit lattice for a specific set $\mathcal{S}'$ (of relatively small cardinality). This upper bound

<footnote>$^{17}$This covering radius makes sense when seeing $\mathrm{Log}_\mathcal{S}'(\mathcal{O}_{K,\mathcal{S}'}^\times)$ as a lattice in the real vector space $\mathrm{Div}_{K,\mathcal{S}}(\mathbb{R})$, see Equation (104).</footnote>
is obtained due to the random walk result from [14, Theorem 3.3]. When rephrased with our formalism, and with a bit of work, the random walk theorem from [14] states that there exists a distribution $W^T$ outputting somewhat short vectors of $\text{Div}_{K, S'}^0$ (the ambient space of $\text{Log}_{S'}(\mathcal{O}_{K, S'}^\times)$) and such that $W^T \mod \text{Log}_{S'}(\mathcal{O}_{K, S'}^\times)$ is close to uniform in $\text{Div}_{K, S'}^0 \mod \text{Log}_{S'}(\mathcal{O}_{K, S'}^\times)$. The shortness bound on the output vectors of $W^T$ is proven in Lemma 16.5, and the close to uniformity modulo $\text{Log}_{S'}(\mathcal{O}_{K, S'}^\times)$ is obtained by combining Theorem 16.2 and Lemma 16.4. Intuitively, this means that any vector from $\text{Div}_{K, S'}^0 \mod \text{Log}_{S'}(\mathcal{O}_{K, S'}^\times)$ is somewhat close to a vector in the support of the distribution $W^T$, which are all somewhat short. Hence, the covering radius of $\text{Log}_{S'}(\mathcal{O}_{K, S'}^\times)$ is somewhat small (see Lemma 16.8). In order to formalize this intuition, and because our distribution $W^T$ is not perfectly uniform but only statistically close to uniform, we need to show that the volume of a small ball in $\text{Div}_{K, S'}^0 \mod \text{Log}_{S'}(\mathcal{O}_{K, S'}^\times)$ is not too small (it could happen that the ball folded modulo $\text{Log}_{S'}(\mathcal{O}_{K, S'}^\times)$ becomes much smaller than the original unfolded ball). This is what is done in Lemma 16.6.

Once we have an upper bound on $\text{cov}(\text{Log}_{S'}(\mathcal{O}_{K, S'}^\times))$, we also have an upper bound on $\varrho(\text{Log}_{S'}(\mathcal{O}_{K, S'}^\times))$ by Lemma 2.3. We then need to extend this to larger sets $\mathcal{S} \supseteq \mathcal{S}'$, which is done in Lemma 16.9. We could also extend directly the bound on $\text{cov}(\text{Log}_{\mathcal{S}}(\mathcal{O}_{K, \mathcal{S}}^\times))$ to larger sets $\mathcal{S}$, but this would grow as $\sqrt{|\mathcal{S}|}$, whereas our sharper bound on the generating radius $\varrho(\text{Log}_{\mathcal{S}}(\mathcal{O}_{K, \mathcal{S}}^\times))$ only grows as $\max_{\mathfrak{p} \in \mathcal{S}} \log \mathcal{N}(\mathfrak{p})$. Using the larger bound on $\text{cov}(\text{Log}_{\mathcal{S}}(\mathcal{O}_{K, \mathcal{S}}^\times))$ would have no impact on the asymptotic complexity of our algorithm, but we prefer to keep the intermediate results as tight as possible, to facilitate reusability in other works. Overall, our upper bound on $\varrho(\text{Log}_{\mathcal{S}}(\mathcal{O}_{K, \mathcal{S}}^\times))$, which is the main result of this section, is stated in Proposition 16.10.

We start by rephrasing the random walk theorem from [14, Theorem 3.3] (see also Definition 6.1) in $\mathcal{S}$-unit terminology. As already mentioned in the preliminaries, the quotient group $\text{Div}_{K, \mathcal{S}}^0 / \text{Log}_{\mathcal{S}}(\mathcal{O}_{K, \mathcal{S}}^\times)$ is isomorphic to the Arakelov class group $\text{Pic}_K^0$, provided that $\mathcal{S}$ generates the class group.

**Definition 16.1** (Random walk distribution, rephrased from [14, Definition 3.1]).
Let $\mathcal{S}$ be a set of prime ideals of $K$, $N \in \mathbb{Z}_{>0}$ and $s > 0$. The distribution $\mathcal{W}(\mathcal{S}, N, s)$ is a probability distribution over $\text{Div}_{K, \mathcal{S}}^0$ obtained by the following procedure.

(1) Set $y = 0 \in \text{Div}_{K, \mathcal{S}}$. The first $|\mathcal{S}|$ coordinates of $y$ are denoted by $y_{\mathfrak{p}}$ (with $\mathfrak{p} \in \mathcal{S}$) and the last $n_{\mathbb{R}} + n_{\mathbb{C}}$ coordinates of $y$ are denoted by $y_{\nu}$ (with $\nu$ the places associated with the (pairs of) embeddings $\sigma: K \to \mathbb{C}$).

(2) Sample $x \in H$ from a continuous centered Gaussian distribution with standard deviation $s$, where $H = \text{span}_{\mathbb{R}}(\text{Log}(\mathcal{O}_K^\times))$ (i.e., $H = \text{Log}(K_{\mathbb{R}}^0) = \{(x_\nu)_\nu \in \bigoplus_\nu \mathbb{R} \mid \sum_\nu x_\nu = 0\}$). Set $y_\nu = x_\nu$ for all places $\nu$.

(3) For $j$ from 1 to $N$, sample $\mathfrak{p}$ uniformly at random in $\mathcal{S}$ and update $y_{\mathfrak{p}} = y_{\mathfrak{p}}+1$ and $y_\nu = y_\nu - \frac{n_\nu \log \mathcal{N}(\mathfrak{p})}{n}$ for all places $\nu$. Here $n_\nu = 2$ if $\nu$ is complex and 1 otherwise.

(4) Return $y$

Observe that the distribution $\mathcal{W}(\mathcal{S}, N, s)$ produces vectors in $\text{Div}_{K, \mathcal{S}}^0$, (i.e., vectors $y \in \bigoplus_{\mathfrak{p} \in \mathcal{S}} \mathbb{Z} \times \bigoplus_\nu \mathbb{R}$ such that $\sum_\nu y_\nu + \sum_{\mathfrak{p} \in \mathcal{S}} y_\mathfrak{p} \cdot \log \mathcal{N}(\mathfrak{p}) = 0$).
**Theorem 16.2** ([14, Theorem 3.3], ERH). Let $\varepsilon > 0$ and $s > 0$ be positive real numbers and $k \in \mathbb{Z}_{>0}$. Let $s' = \min(\sqrt{2} \cdot s, 1/\eta_1(\mathrm{Log}(\mathcal{O}_K^\times)^\vee))$, where $\eta_1(\mathrm{Log}(\mathcal{O}_K^\times)^\vee)$ is the smoothing parameter of the dual lattice of the log-unit lattice $\mathrm{Log}(\mathcal{O}_K^\times)$. Then there exists a bound

$$B = \tilde{O}(n^{2k}[n^2(\log \log(1/\varepsilon))^2 + n^2(\log(1/s'))^2 + (\log |\Delta_K|)^2])$$

such that for any

$$N \ge \frac{\frac{n_S+n_C-1}{2} \cdot \log(1/s') + \frac{1}{2} \log(\mathrm{Vol}(\mathrm{Log}_S(\mathcal{O}_{K,S}^\times))) + \log(1/\varepsilon) + 1}{k \log n},$$

the random walk distribution $W(\mathbb{S}, N, s)$ mod $\mathrm{Log}_S(\mathcal{O}_{K,\mathbb{S}}^\times)$ is within statistical distance at most $\varepsilon/2$ from uniform in $\mathrm{Div}_{K,\mathbb{S}}^0 / \mathrm{Log}_S(\mathcal{O}_{K,\mathbb{S}}^\times)$, where $\mathbb{S} = \{\mathfrak{p} \text{ prime ideal } | \mathcal{N}(\mathfrak{p}) \le B\}$.

*Proof.* This theorem is a direct translation of [14, Theorem 3.3] (or Theorem 6.4) with this section's $\mathbb{S}$-unit terminology: recall that if $\mathbb{S}$ generates the class group, then $\mathrm{Pic}_K^0$ is isomorphic to $\mathrm{Div}_{K,\mathbb{S}}^0 / \mathrm{Log}_S(\mathcal{O}_{K,\mathbb{S}}^\times)$. By a result of Bach [4], $\mathbb{S}$ indeed generates the class group for $B \ge 12 \log^2 |\Delta_K|$, hence indeed the bound in the theorem statement suffices. $\square$

In order to prove Proposition 16.10, we will use a tail-cut random walk distribution.

**Definition 16.3** (Tail-cut random walk distribution). Let $\mathbb{S}$ be a set of prime ideals of $K$, $N \in \mathbb{Z}_{>0}$, $s > 0$ and $\varepsilon \in (0, 1]$. The distribution $W^T(\mathbb{S}, N, s, \varepsilon)$ is a probability distribution over $\mathrm{Div}_{K,\mathbb{S}}^0$ obtained as in Definition 16.1, except that the Gaussian distribution used to sample $x$ is tail-cut at $t := s \cdot \sqrt{2 \cdot n \cdot \log(\frac{4 \cdot n}{\varepsilon})}$. In other words, $x$ is sampled from $\mathcal{G}_{H,s}$ conditioned on $\|x\| \le t$.

**Lemma 16.4.** For any set of prime ideals $\mathbb{S}$, $N \in \mathbb{Z}_{>0}$, $s > 0$ and $\varepsilon \in (0, 1]$, the statistical distance between $W(\mathbb{S}, N, s)$ and $W^T(\mathbb{S}, N, s, \varepsilon)$ is upper bounded by $\varepsilon/2$.

*Proof.* By the data processing inequality (Theorem 2.16), it suffices to prove that the statistical distance between $\mathcal{G}_{H,s}$ and its tail-cut variant is bounded by $\varepsilon/2$. This directly follows from Lemma 2.19. $\square$

**Lemma 16.5.** Let $\mathbb{S}$ be a set of prime ideals, $N \in \mathbb{Z}_{>0}$, $s > 0$ and $\varepsilon \in (0, 1]$. Then the support of the distribution $W^T(\mathbb{S}, N, s, \varepsilon)$ is included in $\{x \in \mathrm{Div}_{K,\mathbb{S}}^0 | \|x\| \le R\}$, where

$$R = s \cdot \sqrt{2 \cdot n \cdot \log \left( \frac{4 \cdot n}{\varepsilon} \right)} + N \cdot \left( 1 + \max_{\mathfrak{p} \in \mathbb{S}} \log \mathcal{N}(\mathfrak{p}) \right).$$

*Proof.* Let $y$ be output by $W^T(\mathbb{S}, N, s, \varepsilon)$. By the definition of this distribution, we have $y \in \mathrm{Div}_{K,\mathbb{S}}^0$. We want to show that $\|y\| \le R$.

Let us consider the components of $y = ((y_\mathfrak{p})_{\mathfrak{p} \in \mathbb{S}}, (y_\nu)_\nu)$ in $\bigoplus_{\mathfrak{p} \in \mathbb{S}} \mathbb{Z}$ and $\bigoplus_\nu \mathbb{R}$ separately. The vector $(y_\mathfrak{p})_{\mathfrak{p} \in \mathbb{S}}$ satisfies $\|(y_\mathfrak{p})_{\mathfrak{p} \in \mathbb{S}}\| \le \|(y_\mathfrak{p})_{\mathfrak{p} \in \mathbb{S}}\|_1 \le N$, by definition. From the tail-cut definition of $W^T$, we also know that $(y_\nu)_\nu$ is the sum of a vector of norm $\le t$ (where $t$ is defined in Definition 16.3) and of $N$ vectors of norm at most $\frac{\sqrt{2n \cdot \max_{\mathfrak{p} \in \mathbb{S}} \log \mathcal{N}(\mathfrak{p})}}{n} \le \max_{\mathfrak{p} \in \mathbb{S}} \log \mathcal{N}(\mathfrak{p})$. Summing all these terms provides the desired upper bound on $\|y\|$. $\square$
We will also need the following auxiliary lemma, which lower bounds the probability that a uniform element modulo $\text{Log}_S(\mathcal{O}_{K,S}^\times)$ falls in a small ball. We denote

$$ t\mathcal{B}_\infty := \left\{ \left( (x_p)_p, (x_\nu)_\nu \right) \in \text{Div}_{K,S}^0(\mathbb{R}) \mid \left\| \left( (x_p)_p, (x_\nu)_\nu \right) \right\|_\infty \le t \right\}, $$

where $\text{Div}_{K,S}^0(\mathbb{R})$ was defined in Equation (104) (note that this is the $\mathbb{R}$-span, even for the coordinates in $\mathbb{S}$). Recall that $\mathcal{U}(\text{Div}_{K,S}^0 / \text{Log}_S(\mathcal{O}_{K,S}^\times))$ is the uniform distribution over the compact group $\text{Div}_{K,S}^0 / \text{Log}_S(\mathcal{O}_{K,S}^\times)$.

**Lemma 16.6.** Let $\mathbb{S}$ be any set of prime ideals generating the class group and let $x \in \text{Div}_{K,S}^0(\mathbb{R})$ be fixed. Then, for $t = 1 + \frac{1}{n} \cdot \sum_{\mathfrak{p} \in \mathbb{S}} \log \mathcal{N}(\mathfrak{p})$,

$$ \begin{aligned} & \operatorname{Pr}_{y \leftarrow \mathcal{U}(\text{Div}_{K,S}^0 / \text{Log}_S(\mathcal{O}_{K,S}^\times))} \left( \exists z \in t\mathcal{B}_\infty \text{ so that } y = x + z \mod \text{Log}_S(\mathcal{O}_{K,S}^\times) \right) \\ & \ge \frac{1}{(1000 \cdot n \cdot \log(n)^3)^n \cdot h_K \cdot \text{Vol}(\text{Log}(\mathcal{O}_{K,S}^\times))} \end{aligned} $$

**Remark 16.7.** Note that in this lemma, the element $y$ belongs to $\text{Div}_{K,S}^0$, hence has its first coordinates in $\bigoplus_{\mathfrak{p} \in \mathbb{S}} \mathbb{Z}$, but $x$ and $z$ are only required to live in the larger space $\text{span}_{\mathbb{R}}(\text{Log}_S(\mathcal{O}_{K,S}^\times)) = \text{Div}_{K,S}^0(\mathbb{R})$, which means that their coordinates $x_p, z_p$ might be real.

*Proof.* We will start with writing the probability in terms of volumes in the quotient $X_S = \text{Div}_{K,S}^0 / \text{Log}_S(\mathcal{O}_{K,S}^\times)$. For convenience, we will use the notation

$$ \text{Fold}_S : \text{Div}_{K,S}^0 \to X_S. $$

We have

$$ \begin{aligned} & \operatorname{Pr}_{y \leftarrow \mathcal{U}(X)} \left( \exists z \in t\mathcal{B}_\infty \text{ so that } y = x + z \mod \text{Log}_S(\mathcal{O}_{K,S}^\times) \right) \\ & = \frac{\text{Vol}(\text{Fold}_S((t\mathcal{B}_\infty + x) \cap \text{Div}_{K,S}^0))}{\text{Vol}(X_S)} \end{aligned} $$

To address the semi-continuous nature of $\text{Div}_{K,S}^0$ (as opposed to $\text{Div}_{K,S}^0(\mathbb{R}))$, we define $\bar{x} \in \text{Div}_{K,S}^0$ by the rule $\bar{x}_p := [x_p]$ and $\bar{x}_\nu = x_\nu - \frac{n_\nu}{n} \sum_{\mathfrak{p}} (\bar{x}_\mathfrak{p} - x_\mathfrak{p}) \log \mathcal{N}(\mathfrak{p})$ (for all $\mathfrak{p} \in \mathbb{S}$ and places $\nu$; here $n_\nu = 2$ if $\nu$ is complex and 1 otherwise). Then $\bar{x} \in \text{Div}_{K,S}^0$ and

$$ \|\bar{x} - x\|_{\infty} \le \frac{1}{2} + \frac{1}{n} \sum_{\mathfrak{p} \in \mathbb{S}} \log \mathcal{N}(\mathfrak{p}). \qquad (105) $$

In particular, $\frac{1}{2}\mathcal{B}_\infty + \bar{x} \subset t\mathcal{B}_\infty + x$. Since volumes in $X_S$ are invariant by translation (by elements of $\text{Div}_{K,S}^0$), we get

$$ \begin{aligned} \text{Vol}(\text{Fold}_S((t\mathcal{B}_\infty + x) \cap \text{Div}_{K,S}^0)) &\ge \text{Vol}(\text{Fold}_S((\frac{1}{2}\mathcal{B}_\infty + \bar{x}) \cap \text{Div}_{K,S}^0)) \\ &= \text{Vol}(\text{Fold}_S(\frac{1}{2}\mathcal{B}_\infty \cap \text{Div}_{K,S}^0)) \end{aligned} $$

We have $\frac{1}{2}\mathcal{B}_\infty \cap \text{Div}_{K,S}^0 = \{0\}^S \times (\frac{1}{2}\mathcal{B}_\infty^0)$, where $\mathcal{B}_\infty^0$ is the unit $\infty$-ball in the $\mathbb{R}$-vector space $\text{Div}_{K,\emptyset}^0(\mathbb{R})$. We deduce

$$ \text{Vol}(\text{Fold}_S(((\frac{1}{2}\mathcal{B}_\infty) \cap \text{Div}_{K,S}^0))) = \text{Vol}(\text{Fold}_\emptyset((\frac{1}{2}\mathcal{B}_\infty^0))) \ge \text{Vol}(\text{Fold}_\emptyset(r\mathcal{B}_\infty^0)) $$
for any $0 < r \le 1/2$. If furthermore $n^{1/2}r \le \frac{1}{2}\lambda_1(\mathrm{Log}(\mathcal{O}_K^\times))$, the restriction of $\mathrm{Fold}_0$ to $r\mathcal{B}_\infty^0 \subset n^{1/2}r\mathcal{B}_2^0$ is injective, and we get

$$ \mathrm{Vol}(\mathrm{Fold}_0(r\mathcal{B}_\infty^0)) = \mathrm{Vol}(r\mathcal{B}_\infty^0) = (2r)^{n_{\mathbb{R}}+n_{\mathbb{C}}-1} \ge (2r)^n. $$

Composing all our volume (in)equalities, for $r \le \frac{1}{2}\min(1, \lambda_1(\mathrm{Log}(\mathcal{O}_K^\times))/\sqrt{n})$ we have

$$ \mathrm{Vol}(\mathrm{Fold}_{\mathbb{S}}((t\mathcal{B}_\infty + x) \cap \mathrm{Div}_{K, \mathbb{S}}^0)) \ge (2r)^n. $$

From Lemma 2.14, we know that $\lambda_1(\mathrm{Log}(\mathcal{O}_K^\times)) \ge (1000 \cdot \sqrt{n} \cdot \log(n)^3)^{-1}$. Hence, taking $r = \frac{1}{2} \cdot \frac{1}{1000n(\log n)^3}$ satisfies the above condition. Together with the identity $\mathrm{Vol}(X_{\mathbb{S}}) = h_K \cdot \mathrm{Vol}(\mathrm{Log}(\mathcal{O}_K^\times))$ (see Lemma 15.5), we obtain the desired bound. $\square$

From this, we can prove the following upper bound on the covering radius of $\mathrm{Log}_{\mathbb{S}}(\mathcal{O}_{K, \mathbb{S}}^\times)$ when $|\mathbb{S}|$ is sufficiently large.

**Lemma 16.8 (ERH).** There exist $B_1 = \mathrm{poly}(\log|\Delta_K|)$ such that if $\mathbb{S}'$ is the set of all prime ideals of norm $\le B_1$, then $\mathbb{S}'$ generates the class group of $K$ and we have

$$ \mathrm{cov}(\mathrm{Log}_{\mathbb{S}'}(\mathcal{O}_{K, \mathbb{S}'}^\times)) \le \mathrm{poly}(\log|\Delta_K|). $$

*Proof.* Let us take $k = 1$, $\varepsilon = \frac{1}{2 \cdot (1000 \cdot n \cdot \log(n)^3)^n \cdot h_K \cdot \mathrm{Vol}(\mathrm{Log}(\mathcal{O}_K^\times))}$ and $s = 1/n$. Let $B$ and $N$ be as in Theorem 16.2, for these choices of $k$, $\varepsilon$ and $s$, with $N$ minimal.

We will prove that the lemma holds for $B_1 = B$. We have already seen that the $B$ from Theorem 16.2 is such that all prime ideals of norm $\le B$ generates the class group, which proves the first part of the lemma.

Let us now prove the second part of the lemma. Let $x \in \mathrm{span}_{\mathbb{R}}(\mathrm{Log}_{\mathbb{S}'}(\mathcal{O}_{K, \mathbb{S}'}^\times)) = \mathrm{Div}_{K, \mathbb{S}'}^0(\mathbb{R})$. We would like to show that there exists a vector $y$ in the support of the tail-cut random walk distribution $W^T(\mathbb{S}', N, s, \varepsilon)$ that is not too far away from $x \bmod \mathrm{Log}_{\mathbb{S}'}(\mathcal{O}_{K, \mathbb{S}'}^\times)$.

From Lemma 16.6 and by definition of $\varepsilon$, we know that

$$ \mathrm{Pr}_{y \leftarrow \mathcal{U}(\mathrm{Div}_{K, \mathbb{S}'}^0 / \mathrm{Log}_{\mathbb{S}'}(\mathcal{O}_{K, \mathbb{S}'}^\times))} \left( \exists z \in t\mathcal{B}_\infty \text{ such that } y = x + z \bmod \mathrm{Log}_{\mathbb{S}'}(\mathcal{O}_{K, \mathbb{S}'}^\times) \right) \ge 2\varepsilon, $$
where $\mathcal{B}_\infty := \{((x_p)_p, (x_\nu)_\nu) \in \mathrm{Div}_{K, \mathbb{S}}^0(\mathbb{R}) \mid \|(x_p)_p, (x_\nu)_\nu\|_\infty \le t\}$ and $t = 1 + \sum_{p \in \mathbb{S}'} \log \mathcal{N}(p)$.

Moreover, combining Lemma 16.4 and Theorem 16.2, we get that the statistical distance between $W^T(\mathbb{S}', N, s, \varepsilon)$ and the uniform distribution over $\mathrm{Div}_{K, \mathbb{S}}^0 / \mathrm{Log}_{\mathbb{S}'}(\mathcal{O}_{K, \mathbb{S}'}^\times)$ is at most $\varepsilon$. Hence, we obtain that

$$ \mathrm{Pr}_{y \leftarrow W^T(\mathbb{S}', N, s, \varepsilon)} \left( \exists z \in t\mathcal{B}_\infty \text{ such that } y = x + z \bmod \mathrm{Log}_{\mathbb{S}'}(\mathcal{O}_{K, \mathbb{S}'}^\times) \right) \ge 2\varepsilon - \varepsilon > 0. $$
This proves the existence of some $y$ in the support of $W^T(\mathbb{S}', N, s, \varepsilon)$ and some $z \in \mathrm{Div}_{K, \mathbb{S}}^0(\mathbb{R}) = \mathrm{span}_{\mathbb{R}}(\mathrm{Log}_{\mathbb{S}}(\mathcal{O}_{K, \mathbb{S}}^\times))$ with $\|z\|_\infty \le 1 + \sum_{p \in \mathbb{S}} \log \mathcal{N}(p)$ such that $x + z - y \in \mathrm{Log}_{\mathbb{S}'}(\mathcal{O}_{K, \mathbb{S}'}^\times)$. This means in particular that

$$ \min_{v \in \mathrm{Log}_{\mathbb{S}'}(\mathcal{O}_{K, \mathbb{S}'}^\times)} \|x - v\| \le \|z\| + \|y\|. $$

We know that the number of prime ideals of norm bounded by $B$ is at most $B \cdot n$ (since there are at most $n$ prime ideals above any prime integer in $\mathbb{Z}$). Hence, $\sum_{p \in \mathbb{S}'} \log \mathcal{N}(p) \le B \cdot n \cdot \log B$ and we have $\|z\| \le \sqrt{\pi + 1 + |\mathbb{S}'|} \cdot (1 + nB \log B) \le \mathrm{poly}(B, \log|\Delta_K|)$.
Since $y$ belongs to the support of $W^T(\mathbb{S}', N, s, \varepsilon)$, we know from Lemma 16.5 that $\|y\| \le s \cdot \sqrt{2 \cdot n \cdot \log(\frac{4n}{\varepsilon})} + N \cdot (1 + \log B)$.

Let us upper bound the terms $\log(1/\varepsilon)$, $B$ and $N$ appearing in the two upper bounds. Recall from Lemma 15.5 that $\log(h_K \cdot \mathrm{Vol}(\mathrm{Log}(\mathcal{O}_K^\times))) \le \log |\Delta_K|$. From this, we see that $\log(1/\varepsilon) = \mathrm{poly}(\log |\Delta_K|)$. It was shown in [14] (in the proof of Corollary 3.4) that $\eta_1(\mathrm{Log}(\mathcal{O}_K^\times)^\vee)) \le \mathrm{poly}(n)$. Hence, by choice of $s$, we have $1/s' = \mathrm{poly}(n)$. From this, Lemma 15.5, and the choice of $k=1$, we obtain that $B = \mathrm{poly}(\log |\Delta_K|)$ and $N = \mathrm{poly}(\log |\Delta_K|)$.

We conclude that for any $x \in \mathrm{span}_{\mathbb{R}}(\mathrm{Log}_{\mathbb{S}'}(\mathcal{O}_{K,\mathbb{S}'}^\times))$, we have

$$ \min_{v \in \mathrm{Log}_{\mathbb{S}'}(\mathcal{O}_{K,\mathbb{S}'}^\times)} \|x - v\| \le \mathrm{poly}(\log |\Delta_K|), $$

$$ \text{hence } \mathrm{cov}(\mathrm{Log}_{\mathbb{S}'}(\mathcal{O}_{K,\mathbb{S}'}^\times)) \le \mathrm{poly}(\log |\Delta_K|). \quad \square $$

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

Only one last lemma remains to be proven before being able to prove Proposition 16.10. This lemma relates the generating radii $\varrho(\mathrm{Log}_{\mathbb{S}}(\mathcal{O}_{K,\mathbb{S}}^\times))$ and $\varrho(\mathrm{Log}_{\mathbb{S}'}(\mathcal{O}_{K,\mathbb{S}'}^\times))$ when $\mathbb{S}'$ is a subset of $\mathbb{S}$.

**Lemma 16.9.** Let $\mathbb{S}$ and $\mathbb{S}'$ be finite sets of prime ideals in $\mathcal{O}_K$ satisfying $\mathbb{S}' \subseteq \mathbb{S}$. Let $\mathbb{S}'$ generate the class group. Then we have

$$ \varrho(\mathrm{Log}_{\mathbb{S}}(\mathcal{O}_{K,\mathbb{S}}^\times)) \le (n + |\mathbb{S}'|) \cdot \varrho(\mathrm{Log}_{\mathbb{S}'}(\mathcal{O}_{K,\mathbb{S}'}^\times)) + \max_{\mathfrak{p} \in \mathbb{S}} \log \mathcal{N}(\mathfrak{p}) + 1. $$

*Proof.* In order to show an upper bound on the generating radius $\varrho(\mathrm{Log}_{\mathbb{S}}(\mathcal{O}_{K,\mathbb{S}}^\times))$, we will construct short vectors that generate the lattice $\mathrm{Log}_{\mathbb{S}}(\mathcal{O}_{K,\mathbb{S}}^\times)$, using the short vectors that generate the lattice $\mathrm{Log}_{\mathbb{S}'}(\mathcal{O}_{K,\mathbb{S}'}^\times)$. In this way, we relate the generating radii of $\mathrm{Log}_{\mathbb{S}}(\mathcal{O}_{K,\mathbb{S}}^\times)$ and $\mathrm{Log}_{\mathbb{S}'}(\mathcal{O}_{K,\mathbb{S}'}^\times)$. We will first show that these vectors that we construct span a lattice of rank $n_{\mathbb{R}} + n_{\mathbb{C}} + |\mathbb{S}| - 1$ (the same as the rank of $\mathrm{Log}_{\mathbb{S}}(\mathcal{O}_{K,\mathbb{S}}^\times)$) included in $\mathrm{Log}_{\mathbb{S}}(\mathcal{O}_{K,\mathbb{S}}^\times)$. We then conclude that both lattices are equal by a volumetric argument.

Let us order the elements of $\mathbb{S} = \{\mathfrak{p}_1, \dots, \mathfrak{p}_{|\mathbb{S}|}\}$ such that $\mathbb{S}' = \{\mathfrak{p}_1, \dots, \mathfrak{p}_{|\mathbb{S}'|}\}$. By definition of $\mathrm{Log}_{\mathbb{S}}(\mathcal{O}_{K,\mathbb{S}}^\times)$ and $\mathrm{Log}_{\mathbb{S}'}(\mathcal{O}_{K,\mathbb{S}'}^\times)$, we know that every vector $v \in \mathrm{Log}_{\mathbb{S}'}(\mathcal{O}_{K,\mathbb{S}'}^\times)$ padded with $|\mathbb{S}| - |\mathbb{S}'|$ zeros (at the 'prime places') belongs to $\mathrm{Log}_{\mathbb{S}}(\mathcal{O}_{K,\mathbb{S}}^\times)$.

Let us fix some $b_1, \dots, b_r$ (for some $r > 0$) generating $\mathrm{Log}_{\mathbb{S}}(\mathcal{O}_{K,\mathbb{S}'}^\times)$ with $\|b_i\| \le \varrho(\mathrm{Log}_{\mathbb{S}'}(\mathcal{O}_{K,\mathbb{S}'}^\times))$ for all $i$'s, and let us consider the associated vectors $\bar{b}_1, \dots, \bar{b}_r \in \mathrm{Log}_{\mathbb{S}}(\mathcal{O}_{K,\mathbb{S}}^\times)$ obtained by padding them with zeros. Since padding with zeros does not change the euclidean norm, we still have $\|\bar{b}_i\| \le \varrho(\mathrm{Log}_{\mathbb{S}'}(\mathcal{O}_{K,\mathbb{S}'}^\times))$ for all $i$'s. Moreover, the vectors $\bar{b}_i$ span a lattice of rank $n_{\mathbb{R}} + n_{\mathbb{C}} + |\mathbb{S}'| - 1$, included in $\mathrm{Div}_{K,\mathbb{S}}^0$.

Let us now construct $|\mathbb{S}| - |\mathbb{S}'|$ other vectors $c_{|\mathbb{S}'+1|}, \dots, c_{|\mathbb{S}|}$ in $\mathrm{Log}_{\mathbb{S}'}(\mathcal{O}_{K,\mathbb{S}'}^\times)$. Let us fix some $i$ with $|\mathbb{S}'| < i \le |\mathbb{S}|$ and consider the prime ideal $\mathfrak{p}_i \in \mathbb{S} \setminus \mathbb{S}'$. Since $\mathbb{S}'$ generates the class group, we know that there exists $\alpha_i \in K$ and $v^{(i)} \in \mathbb{Z}^{\mathbb{S}'}$ such that $\alpha_i \cdot \mathcal{O}_K = \mathfrak{p}_i \cdot \prod_{j \le |\mathbb{S}'|} \mathfrak{p}_j^{v_j^{(i)}}$. For $j > |\mathbb{S}'|$, let us define $v_j^{(i)} = 1$ if $j = i$ and $0$ otherwise. Then, the vector $c_i := ((v_j^{(i)})_{j \le |\mathbb{S}'|}, -\mathrm{Log}(\alpha_i))$ belongs to $\mathrm{Log}_{\mathbb{S}}(\mathcal{O}_{K,\mathbb{S}}^\times)$.

By definition, we know that we can decompose $c_i = d_i + e_i$ where $d_i$ belongs to $\mathrm{span}_{\mathbb{R}}(\bar{b}_1, \dots, \bar{b}_r)$ and $e_i = ((0, \dots, 1, \dots, 0), (-\frac{n_\nu \log \mathcal{N}(\mathfrak{p}_i)}{n})_\nu) \in \mathrm{Div}_{K,\mathbb{S}}$ (with the last coefficients (associated with the infinite places) equal to $\frac{n_\nu \log \mathcal{N}(\mathfrak{p}_i)}{n}$ and
the 1 in position of the prime $\mathfrak{p}_i$). We can reduce the vector $d_i$ by using the vectors $\bar{b}_1, \dots, \bar{b}_r$ to ensure that $\|d_i\| \le (n + |\mathfrak{S}'|) \max_i \|\bar{b}_i\|$ (for example, by taking $n_{\mathbb{R}} + n_{\mathbb{C}} + |\mathfrak{S}'| - 1$ linearly independent vectors among the $\bar{b}_i$'s and performing Babai's round-off algorithm).

Hence, without loss of generality, we can assume that

$$ \|c_i\| \le (n + |\mathfrak{S}'|) \cdot \varrho(\mathrm{Log}_{\mathfrak{S}'}(\mathcal{O}_{K,\mathfrak{S}'}^{\times})) + \max_{\mathfrak{p} \in \mathfrak{S}} \log \mathcal{N}(\mathfrak{p}) + 1. $$

So if we can show that the $\bar{b}_i$'s and $c_i$'s generate $\mathrm{Log}_{\mathfrak{S}}(\mathcal{O}_{K,\mathfrak{S}}^{\times})$, we have $\varrho(\mathrm{Log}_{\mathfrak{S}}(\mathcal{O}_{K,\mathfrak{S}}^{\times})) \le (n + |\mathfrak{S}'|) \cdot \varrho(\mathrm{Log}_{\mathfrak{S}'}(\mathcal{O}_{K,\mathfrak{S}'}^{\times})) + \max_{\mathfrak{p} \in \mathfrak{S}} \log \mathcal{N}(\mathfrak{p}) + 1$.

So, it remains to show that the vectors $\bar{b}_i$'s and $c_i$'s generate $\mathrm{Log}_{\mathfrak{S}}(\mathcal{O}_{K,\mathfrak{S}}^{\times})$. Let $L$ be the lattice generated by the $\bar{b}_i$'s and the $c_i$'s. By construction, $L \subseteq \mathrm{Log}_{\mathfrak{S}}(\mathcal{O}_{K,\mathfrak{S}}^{\times})$. Moreover, from the structure of the $c_i$'s, we know that $L$ has rank $n_{\mathbb{R}} + n_{\mathbb{C}} + |\mathfrak{S}'| - 1 + (|\mathfrak{S}'| - |\mathfrak{S}'|)$, i.e., the same rank as $\mathrm{Log}_{\mathfrak{S}}(\mathcal{O}_{K,\mathfrak{S}}^{\times})$. Finally, by choice of the $c_i$'s, we know that $\mathrm{Vol}(L) = \mathrm{Vol}(\mathrm{Log}_{\mathfrak{S}'}(\mathcal{O}_{K,\mathfrak{S}'}^{\times})) = \mathrm{Vol}(\mathrm{Log}_{\mathfrak{S}}(\mathcal{O}_{K,\mathfrak{S}}^{\times}))$, where the last equality comes from Lemma 15.5. From this, we conclude that $L = \mathrm{Log}_{\mathfrak{S}}(\mathcal{O}_{K,\mathfrak{S}}^{\times})$, as desired. $\square$

Combining everything, we can now prove Proposition 16.10.

**Proposition 16.10 (ERH).** There exists some $B_1 = \mathrm{poly}(\log |\Delta_K|)$ such that for any set $\mathfrak{S}$ containing all prime ideals of $\mathcal{O}_K$ of norm $\le B_1$, it holds that

$$ \varrho(\mathrm{Log}_{\mathfrak{S}}(\mathcal{O}_{K,\mathfrak{S}}^{\times})) \le \mathrm{poly}(\log |\Delta_K|, \max_{\mathfrak{p} \in \mathfrak{S}} \log \mathcal{N}(\mathfrak{p})). $$

Moreover, $B_1$ is such that the prime ideals of norm $\le B_1$ generate the class group of $K$.

*Proof of Proposition 16.10.* We prove that the lemma holds for the same bound $B_1$ as in Lemma 16.8. We already know from Lemma 16.8 that this bound $B_1$ is such that all prime ideals of norm $\le B_1$ generates the class group.

Let us call $\mathfrak{S}'$ the set of prime ideals of norm $\le B_1$. From Lemma 16.8 and Lemma 2.3, we know that $\varrho(\mathrm{Log}_{\mathfrak{S}'}(\mathcal{O}_{K,\mathfrak{S}'}^{\times})) \le 2 \cdot \mathrm{cov}(\mathrm{Log}_{\mathfrak{S}'}(\mathcal{O}_{K,\mathfrak{S}'}^{\times})) \le \mathrm{poly}(\log |\Delta_K|)$.

From Lemma 16.9, we conclude that

$$ \begin{aligned} \varrho(\mathrm{Log}_{\mathfrak{S}}(\mathcal{O}_{K,\mathfrak{S}}^{\times})) &\le \sqrt{n + |\mathfrak{S}'|} \cdot \varrho(\mathrm{Log}_{\mathfrak{S}'}(\mathcal{O}_{K,\mathfrak{S}'}^{\times})) + \max_{\mathfrak{p} \in \mathfrak{S}} \log \mathcal{N}(\mathfrak{p}) + 1 \\ &\le \mathrm{poly} \left( \log |\Delta_K|, \max_{\mathfrak{p} \in \mathfrak{S}} \log \mathcal{N}(\mathfrak{p}) \right), \end{aligned} $$

where we used the fact that $|\mathfrak{S}'| \le nB_1 = \mathrm{poly}(B_1, \log |\Delta_K|)$ (see the proof of Lemma 16.8). $\square$

## 17. GENERATING A SINGLE $\mathfrak{S}$-UNIT

In this section, we describe an algorithm that computes in subexponential time a vector in the $\mathrm{Log-}\mathfrak{S}$-unit lattice when the set $\mathfrak{S}$ is sufficiently large. Our algorithm even does slightly more than that, namely given as input an integral ideal $\mathfrak{a}$, the algorithm computes a relation between the ideal $\mathfrak{a}$ and the ideals of $\mathfrak{S}$, that is, it outputs $\alpha \in K$ and $(v_{\mathfrak{p}})_{\mathfrak{p} \in \mathfrak{S}}$ such that $\mathfrak{a} = \alpha \cdot \mathcal{O}_K \cdot \prod_{\mathfrak{p} \in \mathfrak{S}} \mathfrak{p}^{-v_{\mathfrak{p}}}$.

Running the algorithm with $\mathfrak{a} = \mathcal{O}_K$ provides a vector in the $\mathrm{Log-}\mathfrak{S}$-unit lattice. However, in Section 18 we will use the fact that the algorithm can take as input any integral ideal $\mathfrak{a}$ and not just $\mathcal{O}_K$. Indeed, in Section 18, we want to generate many independent vectors in the $\mathrm{Log-}\mathfrak{S}$-unit lattice (so that they generate the full
lattice with good probability once we have enough of them). In order to ensure independence of the vectors, we will crucially rely on the fact that we can choose as input any ideal $\mathfrak{a}$.

Another place where we need to take as input an ideal $\mathfrak{a}$ is when we want to recover a generator of a principal ideal or compute a class group discrete logarithm (as explained in the introduction). In these cases, which correspond to the descent phase of the sieving algorithm, we need to find a relation between any input ideal $\mathfrak{a}$ and the prime ideals of $\mathcal{S}$ for which we computed the Log-$\mathcal{S}$-unit lattice.

Given as input an integral ideal $\mathfrak{a}$, Algorithm 3 uses Theorem 1.1 to sample elements $\alpha \in \mathfrak{a}$ until the relative ideal $\alpha \cdot \mathfrak{a}^{-1}$ is $\mathcal{S}$-smooth. Any such smooth relative ideal provides a relation between $\mathfrak{a}$ and the ideals of $\mathcal{S}$. By Theorem 1.1, the success probability of this procedure is related to the local density of smooth ideals, which we computed in Section 14. As will be discussed later (see Section 21.1) there are certain regimes, depending intricately on $\rho_K, n$ and $\log|\Delta_K|$ where the sampling algorithm's success probability increases when the first small primes are omitted from the computation, thus introducing a modulus $\mathfrak{m}_0$ consisting of the product of small primes. This is the main reason why Algorithm 3 starts with computing an approximation of $\rho_K$ and chooses different avenues depending on the value of $\rho_K$, leading to either a modulus $\mathfrak{m}_0$ consisting of small primes (if $\rho_K$ is large) or an empty modulus $\mathfrak{m}_0 = \mathcal{O}_K$ (if $\rho_K$ is small).

**17.1. The algorithm that generates a single $\mathcal{S}$-unit relation.** The following definition of $\omega$ will be used in Algorithm 3.

**Definition 17.1.** For a given number field $K$ of degree $n$, a modulus $\mathfrak{m}_0$, and real numbers $x, \mathfrak{b} \ge 1$, we define $\omega \in \mathbb{Z}_{>0}$ as the smallest positive integer such that $r = 48 \cdot \omega \cdot \mathfrak{b}^{2n/\mathfrak{b}} \cdot n^{7/2} \cdot |\Delta_K|^{3/2n} \cdot \mathcal{N}(\mathfrak{m}_0)^{1/n}$ satisfies $r^n \ge e^n \max(B_{\text{sm}}, B_{\text{rw}}, 10x^2)$, where $B_{\text{sm}}$ is defined in Lemma 14.1 (with $\varepsilon := 1$ loc. cit.), and $B_{\text{rw}}$ is defined in Theorem 13.2.

Note that using the fact that $B_{\text{sm}} = \text{poly}(\log|\Delta_K|)$ and $B_{\text{rw}} := \text{poly}(\log|\Delta_K|$, $\log\mathcal{N}(\mathfrak{m}_0))$, we can see that $\omega = O(1)$ is a constant (and so in particular size($\omega$) = $O(1)$ since it is an integer).

We can now describe Algorithm 3, which computes one relation.

**Notation 17.2.** Throughout the following lemmas, we will use the following notation:

* We put $B_{\text{max}} = \max(\exp(\sqrt{\log(r^n) \log \log(r^n)}), B_{\text{sm}}, B_{\text{rw}}, 10x^2)$. Note that this instantiation implies $x < \frac{10x^2}{4\log(10x^2)} < B_{\text{max}}/(4\log B_{\text{max}})$ (in the first inequality we used $x \ge 1$ and for the second one we used the fact that $y \mapsto y/(4\log(y))$ is increasing for $y > 3$).

* $u = \frac{\log(r^n)}{\log(B_{\text{max}})}$;

Note that, since $r = 48 \cdot \omega \cdot \mathfrak{b}^{2n/\mathfrak{b}} \cdot n^{7/2} \cdot |\Delta_K|^{3/2n} \cdot \mathcal{N}(\mathfrak{m}_0)^{1/n} \ge 48$, we certainly have $r^n \ge e^n \cdot \exp(\sqrt{\log(r^n) \log \log(r^n)})$ and hence $r^n \ge e^n B_{\text{max}}$.

In order to analyze the running time of Algorithm 3, we need to get a lower bound on the success probability $p_{\text{success}}$ that the repeat...until loop from lines 10-12 terminate. This is what we compute in the next four lemmas. In order to improve readability, we decomposed the computation into small lemmas, the most interesting one being the last one (Lemma 17.6).
**Algorithm 3 Computing one relation**

**Require:**

(i) An LLL-reduced basis of $O_K$,

(ii) an ideal $\mathfrak{a} \in \mathcal{I}_K$,

(iii) a set of prime ideals $\mathfrak{S}$ of $K$,

(iv) $y \in K_{\mathbb{R}}^\times$.

**Ensure:** $\alpha \in \mathfrak{a}$ and $(v_p)_{p \in \mathfrak{S}} \in \mathbb{Z}_{\ge 0}^S$ such that $\mathfrak{a} = \alpha O_K \cdot \prod_{p \in \mathfrak{S}} p^{-v_p}$

1: define $\mathfrak{b} = n^{\frac{2}{3}}$

2: compute an approximation $\tilde{\rho}_K$ of $\rho_K$ such that $\tilde{\rho}_K \le \rho_K < 2\tilde{\rho}_K$ (see Proposition 2.9)

3: define $x = \max\left(\frac{\log^{2/3} |\Delta_K|}{\log^{4/3} \log |\Delta_K|}, \frac{n^{2/3}}{\log^{2/3}(n)}\right)$

4: **if** $\tilde{\rho}_K \le \exp(x \log^2(x))$ **then**

5: define $\mathfrak{m}_0 = (1)$

6: **else**

7: define $\mathfrak{m}_0 = \prod_{\mathcal{N}(p) < x} p$

8: **end if**

9: Define $\omega$ as in Definition 17.1

10: **repeat**

11: $\alpha \leftarrow \text{Sample}(\mathfrak{a}, y, \mathfrak{m}_0, b, \omega)$ (see Theorem 13.2)

12: **until** $\alpha O_K \cdot \mathfrak{a}^{-1}$ is $\mathfrak{S}$-smooth

13: compute $(v_p)_{p \in \mathfrak{S}} \in \mathbb{Z}_{\ge 0}^S$ such that $\alpha O_K \cdot \mathfrak{a}^{-1} = \prod_{p \in \mathfrak{S}} p^{v_p}$

14: **return** $(\alpha, (v_p)_{p \in \mathfrak{S}})$.

**Lemma 17.3 (ERH).** Put $r, B_{\max}, u \in \mathbb{R}_{>0}$ as in Notation 17.2. Assume that $\mathfrak{S}$ contains all prime ideals not dividing $\mathfrak{m}_0$ of norm $\le B_{\max}$, and that $\mathfrak{a}$ is coprime with $\mathfrak{m}_0$. Then the success probability $p_{\text{success}}$ of $\alpha O_K \mathfrak{a}^{-1}$ being $\mathfrak{S}$-smooth in the repeat-loop (lines 10-12) of Algorithm 3 satisfies

$$p_{\text{success}} \ge \frac{1}{6} \frac{\mathcal{N}(\mathfrak{m}_0)}{\phi(\mathfrak{m}_0) \cdot \rho_K} \frac{(4 \log(B_{\max}))^{1-u} \cdot u^{-u}}{B_{\max}}. \quad (106)$$

*Proof.* We denote $S_{\mathfrak{S}}$ for the $\mathfrak{S}$-smooth integral ideals. Since $\mathfrak{S}$ contains all prime ideals (coprime to $\mathfrak{m}_0$) of norm $\le B_{\max}$ per assumption, and $B_{\max} \ge B_{\text{rw}}$ by definition, we have $S_{\mathfrak{S}} S_{B_{\text{rw}}} = S_{\mathfrak{S}}$ (where we considered only prime ideals coprime to $\mathfrak{m}_0$ in $S_{B_{\text{rw}}}$).

In line 11 of Algorithm 3, we use Sample from Theorem 13.2. According to that theorem,<fnref n="18" /> the probability $p_{\text{success}}$ of $\alpha O_K \cdot \mathfrak{a}^{-1}$ lying in $S_{\mathfrak{S}} \cdot S_{B_{\text{rw}}} = S_{\mathfrak{S}}$ is at least

$$p_{\text{success}} \ge \frac{\mathcal{N}(\mathfrak{m}_0)}{\phi(\mathfrak{m}_0)} \frac{\delta_{S_{\mathfrak{S}}} [r^n]}{6} \ge \frac{1}{6} \frac{\mathcal{N}(\mathfrak{m}_0)}{\phi(\mathfrak{m}_0) \cdot \rho_K} \frac{(4 \log(B_{\max}))^{1-u} \cdot u^{-u}}{B_{\max}}.$$

Here, the last inequality comes from computing the density of smooth numbers as in Lemma 14.1. We instantiate that lemma with $A := x$ if $\mathfrak{m}_0 \ne O_K$ and $A := 1$ otherwise (this is to take into account that the prime dividing $\mathfrak{m}_0$ are omitted, see lines 7 and 5), $\varepsilon := 1$, and $B := B_{\max}$. These parameters indeed satisfy the constraints of Lemma 14.1 since $B_{\max} \ge B_{\text{sm}}, r^n \ge e^n B_{\max}$, and $A \le B_{\max}/(4 \log B_{\max})$ (see Notation 17.2). □

<footnote n="18">¹⁸We can apply the theorem because $\mathfrak{a}$ is assumed to be coprime with $\mathfrak{m}_0$.</footnote>
**Lemma 17.4.** Keeping the notations from Lemma 17.3, it holds that

$$ \frac{(4 \log(B_{\max}))^{1-u} \cdot u^{-u}}{B_{\max}} \geq \frac{1}{(B_{\max})^3}. \qquad (107) $$

*Proof.* Taking negative logarithms, and writing $R = \log(r^n)$, $\beta = \log(B_{\max})$ and $u = R/\beta$, we obtain

$$ -\log\left(\frac{(4 \log(B_{\max}))^{1-u} \cdot u^{-u}}{B_{\max}}\right) = \beta + \left(\frac{R}{\beta} - 1\right) \log(4\beta) + \frac{R}{\beta} \log(R/\beta). \quad (108) $$

It suffices to show that the two right-most summands of Equation (108) are upper bounded by $\beta$. Note that, by Notation 17.2, we have that $\beta \ge \sqrt{R \log R}$. Hence, we immediately see $R/\beta \cdot \log(R/\beta) \le \sqrt{R \log R} \le \beta$. For the middle summand, note that $(R/\beta - 1) \log(4\beta) \le \beta$ is equivalent to $R \le \beta^2 / \log(4\beta) + \beta$. The latter inequality is true because $\beta \mapsto \beta^2 / \log(4\beta) + \beta$ is an increasing function for $\beta \ge 1/2$ and, for $R \ge 3$ (which is clearly satisfied since $r \ge 16$),

$$ R \le \frac{(\sqrt{R \log R})^2}{\log(4\sqrt{R \log R})} + \sqrt{R \log R} \le \beta^2 / \log(4\beta) + \beta, $$

where the first inequality follows by graphical inspection and the second by the monotonicity of the function $\beta \mapsto \beta^2 / \log(4\beta) + \beta$. $\square$

**Lemma 17.5.** Keeping the notations from Lemma 17.3, it holds that

$$ B_{\max} \in \mathbf{poly}(L_{|\Delta_K|}(\frac{1}{2}), L_{\mathcal{N}(m_0)}(\frac{1}{2}), L_{n^n}(\frac{2}{3})). $$

*Proof.* From the definition of $B_{\max}$ in Notation 17.2, we have that

$$ B_{\max} \in \mathbf{poly}(\exp(\sqrt{\log(r^n) \log \log(r^n)}), \log |\Delta_K|, \log \mathcal{N}(m_0)) \quad (109) $$

$$ = \mathbf{poly}(L_{|\Delta_K|}(\frac{1}{2}), L_{\mathcal{N}(m_0)}(\frac{1}{2}), L_{n^n}(\frac{2}{3})). \quad (110) $$

Indeed, by the definition of $r$ and the definition of $b$, and using that $\omega = O(1)$

$$ \log(r^n) \le O\left(\frac{n^2 \log b}{b} + \log |\Delta_K| + \log \mathcal{N}(m_0)\right) = O(n^{4/3} \log n, \log |\Delta_K|, \log \mathcal{N}(m_0)). $$

And hence

$$ \exp(\sqrt{\log(r^n) \log \log(r^n)}) \le \mathbf{poly}(L_{|\Delta_K|}(\frac{1}{2}), L_{\mathcal{N}(m_0)}(\frac{1}{2}), L_{n^n}(\frac{2}{3})). \quad (111) $$

$\square$

**Lemma 17.6.** Keep the notations from Lemma 17.3 and define

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

Then it holds that $B_{\max}$ and $p_{\text{success}}^{-1}$ are both in $\mathbf{poly}(L_{|\Delta_K|}(\frac{1}{2}), L_{n^n}(\frac{2}{3}), \rho_K^{\text{cut}})$.

*Proof.* Combining Lemma 17.3, Lemma 17.4 we obtain that

$$ p_{\text{success}}^{-1} \in \mathbf{poly}(\frac{\phi(m_0) \cdot \rho_K}{\mathcal{N}(m_0)}, B_{\max}). $$

Moreover, Lemma 17.5 gives us $B_{\max} \in \mathbf{poly}(L_{|\Delta_K|}(\frac{1}{2}), L_{n^n}(\frac{2}{3}), L_{\mathcal{N}(m_0)}(\frac{1}{2}))$. To prove the result, it then suffices to show that

$$ \mathbf{poly}(L_{\mathcal{N}(m_0)}(\frac{1}{2}), \frac{\phi(m_0) \cdot \rho_K}{\mathcal{N}(m_0)}) = \mathbf{poly}(\rho_K^{\text{cut}}). $$
We write $x = \max\left(\frac{\log^{2/3}|\Delta_K|}{\log^{4/3}\log|\Delta_K|}, \frac{n^{2/3}}{\log^{2/3}(n)}\right)$ as in line 3 of Algorithm 3. Note that $\rho_K^{\text{cut}} = \min(\rho_K, \exp(\Theta(x \log^2(x))))$. We distinguish two cases.

**Case 1:** $\tilde{\rho}_K \le \exp(x \log^2(x))$.

By line 4 and 5, we then have $\rho_K < 2\tilde{\rho}_K \le 2 \cdot \exp(x \log^2(x))$ (in particular, $\rho_K = \text{poly}(\rho_K^{\text{cut}})$) and $\mathfrak{m}_0 = (1)$. Hence $\mathcal{N}(\mathfrak{m}_0) = \phi(\mathfrak{m}_0) = 1$ and thus

$$ \text{poly}(L_{\mathcal{N}(\mathfrak{m}_0)}(\frac{1}{2}), \frac{\phi(\mathfrak{m}_0) \cdot \rho_K}{\mathcal{N}(\mathfrak{m}_0)}) = \text{poly}(\rho_K) = \text{poly}(\rho_K^{\text{cut}}). $$

**Case 2:** $\tilde{\rho}_K > \exp(x \log^2(x))$.

In this case, it holds that $x \log(x)^2 = O(\log \rho_K)$ and have $\mathfrak{m}_0 = \prod_{\mathcal{N}(\mathfrak{p})<x} \mathfrak{p}$ (by lines 4 and 7). On one hand, by Proposition 11.2 we have

$$ \begin{aligned} -\log\left(\frac{\mathcal{N}(\mathfrak{m}_0)}{\phi(\mathfrak{m}_0) \cdot \rho_K}\right) &\le \frac{8 \log |\Delta_K|}{\sqrt{x}} + \frac{8n \log x}{\sqrt{x}} \\ &\le O(x \log^2(x)) = O(\log \rho_K^{\text{cut}}). \end{aligned} \quad (112) $$

This follows from the fact that $\log|\Delta_K| \le O(x^{\frac{3}{2}} \cdot \log^2(x))$ and $n \le O(x^{\frac{3}{2}} \log x)$, since $x = \max\left(\left(\frac{\log|\Delta_K|}{\log^2\log|\Delta_K|}\right)^{\frac{2}{3}}, \left(\frac{n}{\log n}\right)^{\frac{2}{3}}\right)$. On the other hand, using the same bounds on $\log|\Delta_K|$ and $n$, we have, by Lemma 11.4

$$ \begin{aligned} \log \mathcal{N}(\mathfrak{m}_0) &\le O(x + \sqrt{x} \log(x) \log |\Delta_K| + \sqrt{x} \log^2(x) \cdot n) \\ &\le O(x^2 \log^3(x)). \end{aligned} \quad (113) $$

We deduce that

$$ \log L_{\mathcal{N}(\mathfrak{m}_0)}(\frac{1}{2}) \le O(\sqrt{\log \mathcal{N}(\mathfrak{m}_0) \log \log \mathcal{N}(\mathfrak{m}_0)}) \le O(x \log^2(x)) = O(\log \rho_K^{\text{cut}}). \quad (114) $$

Combining Equations (112) and (114), we thus obtain

$$ \text{poly}(L_{\mathcal{N}(\mathfrak{m}_0)}(\frac{1}{2}), \frac{\phi(\mathfrak{m}_0) \cdot \rho_K}{\mathcal{N}(\mathfrak{m}_0)}) = \text{poly}(\rho_K^{\text{cut}}). $$

□

**Theorem 17.7 (ERH).** 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(e^{\log \frac{3}{3} |\Delta_K| \cdot \log \frac{3}{3} (\log |\Delta_K|)}), e^{n^{\frac{3}{3}} \log \frac{3}{3} (n)}\right), $$

such that the following holds. Assume that $\mathcal{S}$ contains all prime ideals coprime to $\mathfrak{m}_0$ of norm $\le B_{\max}$. Then, on input an integral ideal $\mathfrak{a}$ coprime with $\mathfrak{m}_0$, the set $\mathcal{S}$ and $y \in H = \text{Log}(K_{\mathbb{R}}^0)$, Algorithm 3 outputs $(\alpha, (v_{\mathfrak{p}})_{\mathfrak{p} \in \mathcal{S}}) \in \mathfrak{a} \times \mathbb{Z}_{\ge 0}^{|\mathcal{S}|}$ such that

$$ \mathfrak{a} = \alpha \mathcal{O}_K \cdot \prod_{\mathfrak{p} \in \mathcal{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}(\mathcal{S}), \rho_K^{\text{cut}}, \text{size}(\mathfrak{a}), \text{size}(y), \log |\Delta_K|). $$

*Proof.* Thanks to the repeat...until loop from lines 10 to 12, the output of Algorithm 3 is correct whenever it terminates. The fact that $B_{\max} = \text{poly}(L_{|\Delta_K|}(1/2), L_{n^n}(2/3), \rho_K^{\text{cut}})$ follows from Lemma 17.6. Hence, the main focus of this proof is the expected running time of the algorithm.
Since lines 1 up to 10 do not significantly contribute to the running time, it suffices to concentrate on the expected running time of lines 11 up to 14.

For this time analysis we will use that $\log \mathcal{N}(\mathbf{m}_0) \le \text{poly}(\log |\Delta_K|)$, by Lemma 11.4 and the definition of $x$ on line 3. Also, we will use that $\mathbf{b}^b \le L_{n^n}(\frac{2}{3})$, from the definition of $\mathbf{b} = n^{2/3}$.

* (Line 11) The sampling algorithm Sample takes (by Theorem 13.2) time $\text{poly}(\log |\Delta_K|, \text{size}(\mathbf{a}), \log(\mathcal{N}(\mathbf{m}_0)), \text{size}(y), \mathbf{b}^b) = \text{poly}(\log |\Delta_K|, \text{size}(\mathbf{a}), \text{size}(y), L_{n^n}(\frac{2}{3}))$. Here we use that $\text{size}(\omega) = O(1)$ (see Definition 17.1).

* (Line 12 and 13) Checking for $\alpha \mathcal{O}_K \cdot \mathbf{a}^{-1}$ being $\mathbb{S}$-smooth (line 12), as well as writing down the decomposition (line 13) if the ideal indeed is smooth can be done with $\text{poly}(\text{size}(\mathbb{S}))$ division of ideals.

* (Line 14) This is the return statement.

Hence, denoting $p_{\text{success}}$ for the probability of $\alpha \mathcal{O}_K \cdot \mathbf{a}^{-1}$ being $\mathbb{S}$-smooth in line 12, we obtain an expected running time of

$$p_{\text{success}}^{-1} \cdot \text{poly}(L_{n^n}(\frac{2}{3}), \text{size}(\mathbb{S}), \text{size}(\mathbf{a}), \text{size}(y), \log |\Delta_K|). \quad (115)$$

Using Lemma 17.6 provides an upper bound on $p_{\text{success}}^{-1}$ and concludes the proof. $\square$

17.2. **Properties of the output distribution of Algorithm 3.** From now on, we assume that the input ideal $\mathbf{a}$ is $\mathbb{S}$-smooth, since this will be the case when we will call Algorithm 3 in the next section (this ensures in particular that $\mathbf{a}$ is co-prime with $\mathbf{m}_0$, which is needed to apply Theorem 17.7). We describe the input of Algorithm 3 as a divisor $\mathbf{a} = d(\mathbf{a}) + \text{Log}(y) \in \text{Div}_{K,\mathbb{S}}$ (we recover $\mathbf{a} = \text{Exp}_f(\mathbf{a}_f)$ and $y = \text{Exp}_\infty(\mathbf{a}_\infty) \in K_\mathbb{R}^\times$). The following properties of Algorithm 3 are required in the later proof that Algorithm 4 (which is essentially Algorithm 3 with a Gaussian distributed input) has an evenly distributed and concentrated output distribution (see Lemmas 18.10 and 18.11). These two properties of this last output distribution are indispensable to show that sufficiently many samples from this algorithm eventually generate the $\log\mathbb{S}$-unit lattice $\text{Log}_\mathbb{S}(\mathcal{O}_{K,\mathbb{S}}^\times)$.

We denote the output distribution of $\alpha \in K$ in Algorithm 3 with input $\mathbf{a} \in \text{Div}_{K,\mathbb{S}}$ by$^{19}$ $\bar{\mathcal{D}}_\mathbf{a}$. By abuse of notation, we denote by the same symbol $\bar{\mathcal{D}}_\mathbf{a}$ the distribution over $\text{Log}_\mathbb{S}(\mathcal{O}_{K,\mathbb{S}}^\times)$ defined by sampling $\alpha \leftarrow \bar{\mathcal{D}}_\mathbf{a}$ and taking the $\log\mathbb{S}$-unit map$^{20}$ $\text{Log}_\mathbb{S}(\alpha)$. Note that this map is well-defined, as Algorithm 3 only outputs $\alpha \in K^*$ whose prime divisors lie in $\mathbb{S}$, i.e., $\mathbb{S}$-units (by line 12 and because $\mathbf{a}$ is $\mathbb{S}$-smooth). This yields a distribution $\bar{\mathcal{D}}_\mathbf{a} \in L^1(\text{Log}_\mathbb{S}(\mathcal{O}_{K,\mathbb{S}}^\times))$ for each $\mathbf{a} \in \text{Div}_{K,\mathbb{S}}$. Note that Algorithm 3 and hence the distribution $\bar{\mathcal{D}}_\mathbf{a}$ is independent on the degree of $\mathbf{a}$ (as in Equation (10)), as Sample from Theorem 13.2 is independent on the norm.

**Lemma 17.8.** For all $\mathbf{a} \in \text{Div}_{K,\mathbb{S}}$, the output distribution $\bar{\mathcal{D}}_\mathbf{a}$ of Algorithm 3 (where we consider the divisor $\mathbf{a} = d(\mathbf{a}) + \text{Log}(y)$ as input, which is equivalent to the input $(\mathbf{a}, y)$) satisfies the following three properties.

(i) We have $\bar{\mathcal{D}}_\mathbf{a}[\text{Log}_\mathbb{S}(\mathcal{O}_{K,\mathbb{S}}^\times)] = 1$.

(ii) For all $\alpha \in K^{m_0,1}$ and all $x \in \text{Log}_\mathbb{S}(\mathcal{O}_{K,\mathbb{S}}^\times)$

$$\bar{\mathcal{D}}_\mathbf{a}[x] = \bar{\mathcal{D}}_{\mathbf{a}-\text{Log}_\mathbb{S}(\alpha)}[x + \text{Log}_\mathbb{S}(\alpha)].$$

<footnote>$^{19}$Note the difference in notation compared to $\mathcal{D}$ in Section 10; the bar signifies that the distribution is from Algorithm 3.</footnote>

<footnote>$^{20}$This sends the roots of unity to the zero-vector, but that is not troublesome, as elements $\alpha, \zeta\alpha \in K^*$ for a root of unity $\zeta$ have equal probability to be sampled.</footnote>
(iii) There exists some $R = O(\log^2|\Delta_K|) + \|\mathbf{a}\|$ such that

$$ \bar{D}_{\mathbf{a}}[\mathrm{Log}_{\mathbb{S}}(\mathcal{O}_{K,\mathbb{S}}^{\times}) \setminus (R \cdot \mathcal{B}_2)] = 0 $$

$$ \text{where } R \cdot \mathcal{B}_2 = \{\mathbf{a} \in \mathrm{Div}_{K,\mathbb{S}} \mid \|\mathbf{a}\| \le R\}. $$

(iv) For $\mathbf{a}, \mathbf{a}' \in \mathrm{Div}_{K,\mathbb{S}}$ with $\mathbf{a}' = \mathbf{a} + \sum_{\nu} b_{\nu}(\nu)$, we have

$$ \|\bar{D}_{\mathbf{a}} - \bar{D}_{\mathbf{a}'}\|_1 \le 3 \cdot |\Delta_K| \cdot r^n \cdot n^2 \cdot \|b\| + 1/200. $$

$$ \text{with } r = 48 \cdot \omega \cdot \mathbf{b}^{2n/b} \cdot n^{7/2} \cdot |\Delta_K|^{3/2n} \cdot \mathcal{N}(\mathbf{m}_0)^{1/n}. $$

*Proof.* Statement (i) follows from the fact that Algorithm 3 outputs $\alpha$ only if $\alpha \mathcal{O}_K \cdot \mathbf{a}^{-1}$ is $\mathbb{S}$-smooth. Together with the fact that $\mathbf{a}$ itself is assumed to be $\mathbb{S}$-smooth (it is made out of $\mathbf{a} \in \mathrm{Div}_{K,\mathbb{S}}$), we deduce that $\alpha$ is $\mathbb{S}$-smooth, thus an $\mathbb{S}$-unit. Therefore, $\bar{D}_{\mathbf{a}}$ only has support on $\mathrm{Log}_{\mathbb{S}}(\mathcal{O}_{K,\mathbb{S}}^{\times}) \subseteq \mathrm{Div}_{K,\mathbb{S}}^0$.

Statement (ii) follows from property (2) of Theorem 13.2. Let $\mathbf{a} = d(\mathbf{a}) + \mathrm{Log}(y)$ for $\mathbf{a} = \mathrm{Exp}_f(\mathbf{a}_f)$ and $y = \mathrm{Exp}_{\infty}(\mathbf{a}_{\infty})$. By definition of $\mathrm{Log}_{\mathbb{S}}(\alpha)$, we have that $\mathbf{a} - \mathrm{Log}_{\mathbb{S}}(\alpha) = d(\mathbf{a} \cdot (\alpha)) + \mathrm{Log}(y \cdot \alpha^{-1})$. Property (2) of Theorem 13.2 tells us that $\mathcal{D}_{y,\mathbf{a}}[-] = \mathcal{D}_{y \cdot \alpha^{-1},\mathbf{a} \cdot (\alpha)}[\alpha \cdot -]$ (note the different distribution, this is the distribution from Theorem 13.2). As the exit criterion of the repeat loop (line 12 of Algorithm 3) happens at the same occurrences, the output distribution function $\bar{D}_{\mathbf{a}}$ satisfies $\bar{D}_{\mathbf{a}}[x] = \bar{D}_{\mathbf{a}-\mathrm{Log}_{\mathbb{S}}(\alpha)}[x + \mathrm{Log}_{\mathbb{S}}(\alpha)]$ for all $x \in \mathrm{Log}_{\mathbb{S}}(\mathcal{O}_{K,\mathbb{S}}^{\times})$.

The statement (iii) follows from property (3) of Theorem 13.2, $\omega = O(1)$ (see Definition 17.1) and the fact that $\mathrm{log} \mathcal{N}(\mathbf{m}_0) = O(x \cdot \log^2(x) \cdot \mathrm{log} |\Delta_K|) = O(\log^2 |\Delta_K|)$ (see Equation (113) in the proof of Theorem 17.7, and see the definition of $x$ in line 3 of Algorithm 3). Note that here the correspondence between $(y, \mathbf{a}) \in K_{\mathbb{R}}^{\times} \times \mathcal{I}_K$ and $\mathbf{a} = d(\mathbf{a}) + \mathrm{Log}(y)$ is used.

Statement (iv) follows from Lemma 10.8 and Theorem 13.2 (property (1), Lipschitz-property), with the fact that the success probability of a single loop of Theorem 17.7 is lower bounded by $\delta_{\mathbb{S}}[r^n]/6 \ge \frac{1}{6|\Delta_K|r^n}$ (see Equation (102) in the proof of Theorem 13.2). Hence we have (applying Lemma 10.8 with $p^{-1} \le 6 \cdot |\Delta_K| \cdot r^n$)

$$ \|\bar{D}_{\mathbf{a}} - \bar{D}_{\mathbf{a}'}\|_1 \le 3 \cdot |\Delta_K| \cdot r^n \cdot n^2 \cdot \|\mathrm{Log}(y)\| + 1/200. $$

□

## 18. OBTAINING A GENERATING SET OF $\mathbb{S}$-UNITS

18.1. **Introduction.** In Section 17 a probabilistic algorithm is described that computes a single $\mathbb{S}$-unit (or a logarithmic $\mathbb{S}$-unit lattice point). But to actually obtain the entire $\mathbb{S}$-unit group $\mathcal{O}_{K,\mathbb{S}}^{\times}$, one needs a generating set of $\mathbb{S}$-units. Or, equivalently, a $\mathbb{Z}$-generating set of lattice points for the Log-$\mathbb{S}$-unit lattice $\mathrm{Log}_{\mathbb{S}}(\mathcal{O}_{K,\mathbb{S}}^{\times})$.

A 'good' output distribution. One could hope that such a generating set will eventually be formed by repeating the probabilistic algorithm (Algorithm 3) many times and joining the outputs. The chance for this approach to succeed strongly depends on the output distribution of the mentioned probabilistic algorithm. Indeed, one could imagine cases where the output distribution is, for example, only being supported on a strict sublattice of the logarithmic $\mathbb{S}$-unit lattice. In such instances one never obtains a generating set of the full logarithmic $\mathbb{S}$-unit lattice.

It turns out that, for the repeated sampling approach to succeed, it is sufficient for the output distribution to have the following two properties: 'evenly distributed', meaning not having too much weight on a strict sublattice, and 'concentrated',
meaning that most of the weight is reasonably centered around the origin. These
two properties are made more precise in Section 18.2, as well as the consequences
of these properties to the number of samples needed to generate the whole lattice.

*The output distribution of the sampling algorithm.* It remains to be shown that the output distribution of the sampling algorithm (Algorithm 3) is indeed actually ‘good’, i.e., evenly distributed and concentrated.

It turns out that the output distribution of Algorithm 3 for a fixed input (a, y) ∈ I_K × K_ℝ× is hard to analyze; and it seems very difficult to show that it satisfies these properties. Fortunately, one can feed the algorithm different inputs, causing to gain more control of the output distribution.

More specifically, in our approach we randomly sample a Gaussian distributed
point from the space $\text{Div}_{K,\mathbb{S}}$, which can be considered as an ‘ambient space’ of
the logarithmic $\mathbb{S}$-units. This randomly sampled point is then transformed into an
element $(\mathbf{a}, y) \in \mathcal{I}_K \times K_ℝ^\times$ (a from the finite places and y from the infinite places),
which is then given as an input to the $\mathbb{S}$-unit sampling algorithm (Algorithm 3).

We show that this ‘compound’ distribution, taking into account both the ran-
domness of the Gaussian over $\text{Div}_{K,\mathbb{S}}$ and the randomness of the $\mathbb{S}$-unit sampling
algorithm, indeed satisfies the ‘evenly distributed’ property (see Lemma 18.11) and
‘concentrated’ property (see Lemma 18.10). Thus, repeating the $\mathbb{S}$-unit sampling
algorithm with Gaussian distributed inputs lets us indeed obtain a generating set
of the logarithmic $\mathbb{S}$-unit lattice with high probability; this final statement is the
object of Theorem 18.14.

*Intuition.* The intuition why this approach (of letting the input be Gaussian dis-
tributed) works is already sketched in Section 12.4. Another way of looking at it is
by seeing Algorithm 3 as a specific CVP-algorithm for the logarithmic $\mathbb{S}$-unit lattice
$\text{Log}_{\mathbb{S}}(\mathcal{O}_{K,\mathbb{S}}^\times)$, given an input vector $\mathbf{a}$ in $\text{Div}_{K,\mathbb{S}}$.

As a CVP-algorithm, Algorithm 3 outputs a $\text{Log}_{\mathbb{S}}(\alpha)$ 'close' to $\mathbf{a} \in \text{Div}_{K,\mathbb{S}}$, so
one can imagine that the output only differs slightly from the input. If then the
input element $\mathbf{a} \in \text{Div}_{K,\mathbb{S}}$ is distributed according to a sufficiently wide Gaussian,
and this specific CVP output of Algorithm 3 is sufficiently close to $\mathbf{a}$, this CVP
output distribution must be close to a Gaussian as well, but instead its support
is on $\text{Log}_{\mathbb{S}}(\mathcal{O}_{K,\mathbb{S}}^\times)$. For such Gaussian distributions over lattices one can show that
sufficiently many samples thereof generate the entire lattice (see Proposition 18.2).

18.2. **Obtaining a generating set of a lattice.** Given a certain distribution $\psi$
on a lattice $\Lambda$, this section is about how many samples one has to draw from $\psi$ to
obtain a generating set of the lattice $\Lambda$. Of course, this depends on the distribution
at hand: for example, the distribution that always outputs $0 \in \Lambda$ would never yield
a generating set of the lattice $\Lambda$, no matter how many samples one takes.

For a distribution on a lattice Λ it is sufficient to consider two particular
properties to analyze the number of samples required to draw in order to obtain a
generating set of Λ. Those two properties are *evenly distributedness*, which measures
the maximum weight of the distribution $\psi$ on strict sublattices of Λ, and *concentratedness*, which measures how much weight of the distribution $\psi$ is (relatively)
close to the origin. This is formalized in the following definition and proposition.
**Definition 18.1.** Let $\Lambda \subset \mathbb{R}^n$ be a full-rank lattice, and $\psi$ be a distribution on $\Lambda$. The distribution $\psi$ is called $p$-evenly distributed if $\mathrm{Pr}_{x \leftarrow \psi}[x \in \Lambda'] \le p$ for any proper sublattice $\Lambda' \subsetneq \Lambda$. It is called $(R, q)$-concentrated if $\mathrm{Pr}_{x \leftarrow \psi}[\|v\| \ge R] \le q$.

**Proposition 18.2** ([13, Lemma 5]). Let $\Lambda \subset \mathbb{R}^n$ be a full-rank lattice, and $\psi$ be a distribution on $\Lambda$. Suppose that $\psi$ is $p$-evenly distributed and $(R, q)$-concentrated for $R \ge \mathrm{Vol}(\Lambda)^{1/n}$. Denote by $S$ the random variable defined as the number of samples drawn from $\psi$ until these samples generate $\Lambda$. Then, for any $\alpha > 0$,

$$ \mathrm{Pr} \left[ S > (2 + \alpha) \frac{t + n}{1 - p - q} \right] \le e^{-\alpha(t+n)/2}, $$

where $t = n \log_2(R) - \log_2(\mathrm{Vol}(\Lambda)) \ge 0$.

**18.3. The discrete Gaussian over a lattice is evenly distributed.** In the following two lemmas, we show that a Gaussian distribution over a lattice with an arbitrary center point is $p$-evenly distributed. This fact is used to show that the output of the sampling algorithm with a (continuous) Gaussian input is $p$-evenly distributed as well (see Lemma 18.11).

Recall that $g_\zeta(x) := e^{-\pi \|x\|^2 / \zeta^2}$ is the Gaussian function, whereas $\mathcal{G}_{X,\zeta}$ is the Gaussian distribution over $X$ (where the definition depends on whether $X$ is discrete or continuous, see Section 2.9).

**Lemma 18.3.** For any lattice $\Lambda \subseteq V$ (where $V$ is a Euclidean space) any $\zeta > 0$ and any $t, w \in V$, we have

$$ g_{\zeta}(\Lambda + t + w) + g_{\zeta}(\Lambda + t - w) \ge 2g_{\zeta}(w)g_{\zeta}(\Lambda + t). $$

*Proof.* This lemma is a simple generalization of [40, Claim 2.10], and we follow the same strategy:

$$ \begin{aligned} g_{\zeta}(\Lambda + t + w) + g_{\zeta}(\Lambda + t - w) &= \sum_{x \in \Lambda + t} \left( e^{-\pi \|x+w\|^2 / \zeta^2} + e^{-\pi \|x-w\|^2 / \zeta^2} \right) \\ &= 2e^{-\pi \|w\|^2 / \zeta^2} \sum_{x \in \Lambda + t} \left( e^{-\pi \|x\|^2 / \zeta^2} \cosh(2\pi \langle x, w \rangle / \zeta^2) \right) \\ &\ge 2g_{\zeta}(w)g_{\zeta}(\Lambda + t), \end{aligned} $$

where the last inequality follows from $\cosh(\alpha) \ge 1$ for any real $\alpha$. $\square$

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

**Lemma 18.4.** Let $\Lambda \subseteq V$ be a lattice and $V$ an Euclidean space, $t \in V$ and $\zeta \ge c \cdot \varrho(\Lambda)$ for some $c > 0$ (see Definition 2.2). Then the discrete Gaussian distribution on $\Lambda$ with parameter $\zeta$ and centered at $t$ is $p$-evenly distributed with $p = \frac{1}{1+e^{-\pi c^{-2}}}$. Concretely, for any strict sublattice $\Lambda' \subsetneq \Lambda$

$$ \frac{g_{\zeta}(\Lambda' + t)}{g_{\zeta}(\Lambda + t)} \le \frac{1}{1 + e^{-\pi c^{-2}}}. $$

*Proof.* Let $\Lambda' \subsetneq \Lambda$ be a sub-lattice of $\Lambda$ and let $w \in \Lambda \setminus \Lambda'$. Then, by Lemma 18.3,

$$ \begin{aligned} g_{\zeta}(\Lambda + t) &\ge g_{\zeta}(\Lambda' + t) + \frac{g_{\zeta}(\Lambda' + t + w) + g_{\zeta}(\Lambda' + t - w)}{2} \\ &\ge (1 + g_{\zeta}(w))g_{\zeta}(\Lambda' + t). \end{aligned} $$
Writing $\mathcal{G}_{\Lambda+t, \zeta}$ for the Gaussian distribution on $\Lambda+t$ with parameter $\zeta$, we have,

$$ \Pr_{x \leftarrow \mathcal{G}_{\Lambda+t, \zeta}} [x \in \Lambda' + t] = \frac{g_{\zeta}(\Lambda' + t)}{g_{\zeta}(\Lambda + t)} \le \frac{1}{1 + g_{\zeta}(w)}. $$

Since $\Lambda' \subsetneq \Lambda$, we know from the definition of $\varrho(\Lambda)$ that there exists $w \in \Lambda \setminus \Lambda'$ such that $\|w\| \le \varrho(\Lambda) \le \zeta/c$, hence $g_{\zeta}(w) \ge \exp(-\pi c^{-2})$, proving the lemma. $\square$

**18.4. The (semi-)discrete Gaussian over $\mathrm{Div}_{K, \mathcal{S}}$.** We introduce the following notation for the discretization of the $\mathcal{S}$-divisor group as in Definition 15.2. It is needed in Algorithm 4, as this algorithm samples a Gaussian over $\mathrm{Div}_{K, \mathcal{S}}$ and feeds it to Algorithm 3. As $\mathrm{Div}_{K, \mathcal{S}}$ is partially continuous (for which a finite computer cannot sample), we thus need this discretized $\mathrm{Div}_{K, \mathcal{S}, N}$ version of $\mathrm{Div}_{K, \mathcal{S}}$.

**Notation 18.5 (Discretized $\mathcal{S}$-divisor group).** For a set of prime ideals $\mathcal{S}$, we denote by $\mathrm{Div}_{K, \mathcal{S}, N} \subseteq \mathrm{Div}_{K, \mathcal{S}}$ the discrete subgroup of the restricted divisor group, for which $x_{\nu} \in \frac{1}{N}\mathbb{Z}$ for all places $\nu$. In other words, any element of $\mathrm{Div}_{K, \mathcal{S}, N}$ can be written as

$$ \mathbf{a} = \sum_{\mathbf{p} \in \mathcal{S}} a_{\mathbf{p}}(\|\mathbf{p}\|) + \sum_{\nu} x_{\nu}(\|\nu\|) \quad (\text{with } x_{\nu} \in \frac{1}{N}\mathbb{Z}) $$

**Remark 18.6.** In Algorithm 4, we need to compute an approximation of the discrete Gaussian over the group $\mathrm{Div}_{K, \mathcal{S}, N}$ (see Lemma 2.22). For this we need a $\mathbb{Z}$-basis of $\mathrm{Div}_{K, \mathcal{S}, N}$, which is naturally given by $\{\frac{e_{\nu}}{N} \mid \nu \text{ places of } K\} \cup \{\mathbf{e}_{\mathbf{p}} \mid \mathbf{p} \in \mathcal{S}\}$, where $\mathbf{e}_{\mathbf{p}}$ is one on the coordinate $\mathbf{x}$ and zero elsewhere (where $\mathbf{x}$ can be a place or a prime). We call this basis $\mathbf{B}(\mathrm{Div}_{K, \mathcal{S}, N})$.

In order to define a Gaussian distribution over $\mathrm{Div}_{K, \mathcal{S}}$, we recall the distance notion on this space (see Section 2.8). Since the group $\mathrm{Div}_{K, \mathcal{S}}$ is partially discrete, namely, at the finite places, the Gaussian over this group is semi-discrete as well.

**Definition 18.7 (The semi-discrete Gaussian over $\mathrm{Div}_{K, \mathcal{S}}$).** The semi-discrete Gaussian distribution $\mathcal{G}_{\mathrm{Div}_{K, \mathcal{S}}, \zeta} \in L_1(\mathrm{Div}_{K, \mathcal{S}})$ is the distribution defined by

$$ \mathcal{G}_{\mathrm{Div}_{K, \mathcal{S}, \zeta}}[\mathbf{a}] := g_{\zeta}(\mathbf{a}) \cdot \left( \int_{\mathbf{b} \in \mathrm{Div}_{K, \mathcal{S}}} g_{\zeta}(\mathbf{b}) d\mathbf{b} \right)^{-1} $$

where $g_{\zeta}(\mathbf{a}) = \exp(-\pi \|\mathbf{a}\|^2 / \zeta^2)$ (with the distance notion from Section 2.8) and where we use the shorthand notation

$$ \int_{\mathbf{b} \in \mathrm{Div}_{K, \mathcal{S}}} g_{\zeta}(\mathbf{b}) d\mathbf{b} := \sum_{(a_{\mathbf{p}}) \in \mathbb{Z}^{\mathcal{S}}} \int_{(b_{\nu})_{\nu} \in \mathrm{Log}(K_{\mathbb{R}}^{\times})} g_{\zeta} \left( \sum_{\mathbf{p} \in \mathcal{S}} a_{\mathbf{p}}(\|\mathbf{p}\|) + \sum_{\nu} b_{\nu}(\|\nu\|) \right) d\mathbf{b} $$

**Definition 18.8 (The discrete Gaussian over $\mathrm{Div}_{K, \mathcal{S}, N}$).** For $N \in \mathbb{N}_{>0}$ we define the discrete Gaussian over $\mathrm{Div}_{K, \mathcal{S}, N}$ by the rule

$$ \mathcal{G}_{\mathrm{Div}_{K, \mathcal{S}, N, \zeta}} := g_{\zeta}(\mathbf{a}) \cdot \left( \sum_{\mathbf{b} \in \mathrm{Div}_{K, \mathcal{S}, N}} g_{\zeta}(\mathbf{b}) \right)^{-1} $$

where $g_{\zeta}(\mathbf{a}) = \exp(-\pi \|\mathbf{a}\|^2 / \zeta^2)$ (with the distance notion from Section 2.8).

**18.5. Sampling a set of generators for the Log-$\mathcal{S}$-unit lattice.**
**Algorithm 4 Computing a random relation 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:** An random element of $\text{Log}_{\mathbb{S}}(O_{K,\mathbb{S}}^\times)$.

1: Let $\omega \in \mathbb{Z}_{\ge 1}$ be as in Definition 17.1 (with $\mathfrak{m}_0$, $\mathfrak{b}$, and $x$ as in Algorithm 3).

2: Let $\tilde{\varrho} = \text{poly}(\log|\Delta_K|, \max_{\mathfrak{p} \in \mathbb{S}} \log N(\mathfrak{p}))$ the bound from Proposition 16.10, such that $\varrho(\text{Log}_{\mathbb{S}}(O_{K,\mathbb{S}}^\times)) \le \tilde{\varrho}$.

3: Put $\zeta = 3 \cdot \max(\sqrt{\log(n_{\mathbb{R}} + n_{\mathbb{C}} + |\mathbb{S}|)}, \tilde{\varrho})$, and put $N := \omega^n \cdot \exp(11 + 16 \log^2 |\Delta_K| + 9n^2)$.

4: Sample, using Lemma 2.22 with $\varepsilon_G := 1/100$, and the basis $\mathbf{B}(\text{Div}_{K,\mathbb{S},N})$ described in Remark 18.6,

$$ \mathbf{a} = \sum_{\mathfrak{p} \in \mathbb{S}} a_{\mathfrak{p}} (\|\mathfrak{p}\|) + \sum_{\nu} b_{\nu} (\|\nu\|) \leftarrow \hat{\mathcal{G}}_{\mathbf{B}(\text{Div}_{K,\mathbb{S},N}), \varepsilon_G, \zeta, 0}, \quad (116) $$

put $z = \text{Exp}_{\infty}(\mathbf{a}_{\infty})$ and compute a rational $y \in K_{\mathbb{R}}^\times$ such that $\|y - z\|_{\infty} \le \min_{\nu} z_{\nu}/N$.

5: Put $\mathbf{a} = \prod_{\mathfrak{p} \in \mathbb{S}} \mathfrak{p}^{a_{\mathfrak{p}}} = \text{Exp}_{\mathfrak{f}}(\mathbf{a}_{\mathfrak{f}})$.

6: Apply Algorithm 3 with $\mathbf{a} \in \mathcal{I}_K$, $y \in K_{\mathbb{R}}^\times$, and $\mathbb{S}$, yielding $(\alpha, (v_{\mathfrak{p}})_{\mathfrak{p} \in \mathbb{S}})$.

7: return $-(v_{\mathfrak{p}} + a_{\mathfrak{p}})_{\mathfrak{p} \in \mathbb{S}}$, $\text{Log}(\alpha)$ where the $a_{\mathfrak{p}}$ are from line 4.

18.5.1. **Algorithm 4:** *Algorithm 3 with Gaussian input.* In this section, we prove that the output distribution of Algorithm 4 (which is essentially Algorithm 3 with input $\mathbf{a} \in \text{Div}_{K,\mathbb{S},N}$ following a (discrete) Gaussian distribution), is evenly distributed and concentrated on the Log-$\mathbb{S}$-unit lattice (for certain adequate parameters). Hence, by repeating Algorithm 4 sufficiently many times, one obtains a generating set of the Log-$\mathbb{S}$-unit lattice, which is made precise in the later Theorem 18.14.

**Lemma 18.9.** *Assume that $\mathbb{S}$ contains all prime ideals coprime to $\mathfrak{m}_0$ of norm $\le B_{\max}$ (where $B_{\max}$ is defined as in Theorem 17.7). Then, on input $\mathbb{S}$, Algorithm 4 runs in expected time*

$$ \text{poly}(\log |\Delta_K|, \zeta, \text{size}(\mathbb{S})) + T, $$

where $T$ is an upper bound on the expected time of Algorithm 3 on input $\mathbf{a}$ and $y$ of size $\text{size}(\mathbf{a}) \le \text{poly}(\zeta, \text{size}(\mathbb{S}), \log|\Delta_K|)$ and $\text{size}(y) \le O(\zeta n \cdot (\text{size}(\mathbb{S}) + \log|\Delta_K|))$.

*Proof.* Apart from the line 6, in which Algorithm 3 is called, Algorithm 4 only requires computation power during the sampling of the approximate discrete Gaussian and the computation of $y \in K_{\mathbb{R}}^\times$. By Lemma 2.22, and denoting $n_0 = |\mathbb{S}| + \mathbb{r} + 1 = |\mathbb{S}| + n_{\mathbb{R}} + n_{\mathbb{C}} = \text{dim}(\text{Div}_{K,\mathbb{S},N})$, the sampling of the approximate discrete Gaussian takes time (since $\varepsilon_G := 1/100$) polynomial in the size of the input, which can be given by the size of the lattice basis of $\text{Div}_{K,\mathbb{S},N}$, which is $\text{poly}(n_0)$. Note that $\max_{\mathfrak{b} \in \mathbf{B}(\text{Div}_{K,\mathbb{S},N})} \|\mathfrak{b}\| = 1$, so, by choice of $\zeta$, we have $\zeta \ge \sqrt{\frac{\log(1/\varepsilon_G)+2\log(n_0)+3}{\pi}}$. $\max_{\mathfrak{b} \in \mathbf{B}(\text{Div}_{K,\mathbb{S},N})} \|\mathfrak{b}\|$ as required to apply Lemma 2.22. The run time of the computation of $y \in K_{\mathbb{R}}^\times$ depends on the minimum of $z_\nu/N$ and the maximum of $z_\nu$. We have that $|b_\nu| \le \zeta\sqrt{n_0 \log(2n_0^2/\varepsilon_G)}$ by Lemma 2.22 (with $\varepsilon_G := 1/100$). Hence, in the worst case, we must approximate $y \approx z = \text{Exp}_{\infty}(\mathbf{a}_{\infty}) = (e^{b_\nu})_\nu$ up to precision
$\exp(-\zeta \cdot \sqrt{n_0 \cdot \log(2n_0^2/\varepsilon_G)})/N$. For the maximum of $z_\nu$, a similar reasoning tells us that $\max_\nu z_\nu \le \exp(\zeta \cdot \sqrt{n_0 \cdot \log(2n_0^2/\varepsilon_G)})$.

Since we have $\log N = O(\log |\Delta_K|)$ and $\sqrt{n_0 \log(2n_0^2/\varepsilon_G)} = O(\text{size}(\mathbb{S})+\log |\Delta_K|)$, the approximation $y \approx z$ required in line 4 can be computed within time poly($\zeta$, size($\mathbb{S}$), $\log |\Delta_K|$). This reasoning also shows that $\text{size}(y) \le O(\zeta n \cdot (\text{size}(\mathbb{S}) + \log |\Delta_K|))$. Additionally, using the same bound of Lemma 2.22, the size of $\mathfrak{a}$ must also be bounded by poly($\zeta$, size($\mathbb{S}$), $\log |\Delta_K|$). $\square$

18.5.2. The output distribution of Algorithm 4 is concentrated. In the next lemma, we prove that the output distribution of Algorithm 4 is concentrated.

**Lemma 18.10.** The output distribution $\bar{\mathcal{D}}$ of Algorithm 4 is $(R_0, 0)$-concentrated for some

$$R_0 = O(\log^2 |\Delta_K|) + 3 \cdot \zeta \cdot (|\mathbb{S}| + n_{\mathbb{R}} + n_{\mathbb{C}}).$$

*Proof.* The output distribution of Algorithm 4 depends on an approximate discrete Gaussian from line 4, which is computed using Lemma 2.22. From that lemma, denoting $n_0 = |\mathbb{S}| + n_{\mathbb{R}} + n_{\mathbb{C}} = \dim(\text{Div}_{K,\mathbb{S},N})$ follows that

$$\|\mathbf{a}\| \le \zeta \cdot \sqrt{n_0 \log(2n_0^2/\varepsilon_G)} \le 3\zeta n_0$$

with $\zeta$ from line 3 and $\varepsilon_G = 1/100$ (see line 4 of Algorithm 4). Here we use that $\sqrt{x \log(2x^2/\varepsilon_G)} \le 3x$ for $x \ge 1$ and $\varepsilon_G = 1/100$.

But since Algorithm 3 satisfies property (iii) from Lemma 17.8, we know that

$$\| \text{Log}_{\mathbb{S}}(\alpha) \| \le O(\log^2 |\Delta_K|) + \|\mathbf{a}\| \le O(\log^2 |\Delta_K|) + 3 \cdot \zeta \cdot n_0.$$

Hence, there exists a $R_0 = O(\log^2 |\Delta_K|) + 3 \cdot \zeta \cdot (|\mathbb{S}| + n_{\mathbb{R}} + n_{\mathbb{C}})$ for which no $\alpha$ with $\| \text{Log}_{\mathbb{S}}(\alpha) \| > R_0$ can be the output of Algorithm 4. $\square$

18.5.3. The output distribution of Algorithm 4 is evenly distributed. We now prove that the output distribution of Algorithm 4 is evenly distributed on the logarithmic $\mathbb{S}$-unit lattice.

The strategy to show evenly distributedness is more convoluted than was concentratedness. We start with defining the ‘continuous version of Algorithm 4’, in which in line 4 is used a semi-discrete Gaussian (as in Definition 18.7) instead of a fully discrete Gaussian (as in Definition 18.8). More precisely, the ‘continuous version of Algorithm 4’ is Algorithm 4 in which line 4 is replaced with

$$\mathbf{a} = \sum_{\mathbf{p} \in \mathbb{S}} a_{\mathbf{p}}(|\mathbf{p}|) + \sum_{\nu} b_{\nu}(|\nu|) \leftarrow \mathcal{G}_{\text{Div}_{K,\mathbb{S},\zeta}}, \text{ and put } y = \text{Exp}_{\infty}(\mathbf{a}_{\infty}).$$

We will show in Lemma 18.13 that the output distribution of the ‘continuous version’ and the ordinary version of Algorithm 4 are close in statistical distance.

In the present section, we focus on the following step: proving that the output distribution of ‘continuous version of Algorithm 4’ is evenly distributed for certain parameters. By the closeness of the ‘continuous version’ and the ordinary version of Algorithm 4, the ordinary must then also be evenly distributed.

**Lemma 18.11.** Assume that $\mathbb{S}$ generates the ray class group $Cl_K^{m_0}$ of $K$ and does not contain any prime dividing $m_0$. Then the output distribution of Algorithm 4 is 2/3-evenly distributed on $\text{Log}_{\mathbb{S}}(O_{K,\mathbb{S}}^\times)$.
Proof. We will later show, in Lemma 18.13, that Algorithm 4 is 1/50-close in statistical distance to the ‘continuous version of Algorithm 4’. We show in the current proof that this ‘continuous version’ is 6/10-evenly distributed on $\text{Log}_S(\mathcal{O}_{K,\mathcal{S}}^\times)$, and hence the ordinary version is then 2/3-evenly distributed on $\text{Log}_S(\mathcal{O}_{K,\mathcal{S}}^\times)$, since $6/10 + 1/50 < 2/3$.

The remainder of this proof is then devoted to showing that the ‘continuous version of Algorithm 4’ is 6/10-evenly distributed on $\text{Log}_S(\mathcal{O}_{K,\mathcal{S}}^\times)$.

The output distribution $\bar{D}$ of the ‘continuous version of Algorithm 4’ is supported on $\text{Log}_S(\mathcal{O}_{K,\mathcal{S}}^\times)$ and given by the rule, for $\alpha \in \mathcal{O}_{K,\mathcal{S}}^\times$,

$$ \bar{D}[\text{Log}_S(\alpha)] = \int_{\mathbf{a} \in \text{Div}_{K,\mathcal{S}}} \bar{D}_{\mathbf{a}}[\text{Log}_S(\alpha)] \cdot \mathcal{G}_{\zeta}(\mathbf{a}) d\mathbf{a}. $$

To prove that this distribution is p-evenly distributed (with $p = 6/10$), we need to show that $\bar{D}[M] = \sum_{m \in M} \bar{D}[m] \le p$ for every strict sublattice $M \subsetneq \text{Log}_S(\mathcal{O}_{K,\mathcal{S}}^\times)$.

We first prove this for the simpler case where the modulus is trivial, i.e., $\mathfrak{m}_0 = \mathcal{O}_K$; in which case we have $\mathfrak{m}_0^{\mathfrak{m}_0,1} = \mathfrak{K}^*$, and the shifting property (Property (ii) of Lemma 17.8) holds for any $\alpha \in \mathfrak{K}^*$, so in particular for $\alpha \in \mathcal{O}_{K,\mathcal{S}}^\times$.

So, pick any strict sublattice $M \subsetneq \text{Log}_S(\mathcal{O}_{K,\mathcal{S}}^\times)$. Then, by Property (ii) of Lemma 17.8, and, subsequently, by change of variables, we have

$$ \begin{aligned} \sum_{\text{Log}_S(\mu) \in M} \bar{D}[\text{Log}_S(\mu)] &= \int_{\mathbf{a} \in \text{Div}_{K,\mathcal{S}}} \sum_{\text{Log}_S(\mu) \in M} \bar{D}_{\mathbf{a}}[\text{Log}_S(\mu)] \cdot \mathcal{G}_{\zeta}(\mathbf{a}) d\mathbf{a} \\ &= \int_{\mathbf{a} \in \text{Div}_{K,\mathcal{S}}} \sum_{\text{Log}_S(\mu) \in M} \bar{D}_{\mathbf{a}+\text{Log}_S(\mu)}[0] \cdot \mathcal{G}_{\zeta}(\mathbf{a}) d\mathbf{a} \\ &= \int_{\mathbf{a} \in \text{Div}_{K,\mathcal{S}}} \sum_{\text{Log}_S(\mu) \in M} \bar{D}_{\mathbf{a}}[0] \cdot \mathcal{G}_{\zeta}(\mathbf{a} - \text{Log}_S(\mu)) d\mathbf{a} \\ &= \int_{\mathbf{a} \in \text{Div}_{K,\mathcal{S}}} \bar{D}_{\mathbf{a}}[0] \cdot \mathcal{G}_{\zeta}(\mathbf{a} + M) d\mathbf{a} \end{aligned} \quad (117) $$

Using the assumption that $\mathcal{S}$ generates the full class group, we take a fundamental domain $F$ of $\text{Log}_S(\mathcal{O}_{K,\mathcal{S}}^\times)$ in $\text{Div}_{K,\mathcal{S}}^0$, in order to decompose $\text{Div}_{K,\mathcal{S}} = \mathbb{R} \cdot \mathbf{1} + \text{Log}_S(\mathcal{O}_{K,\mathcal{S}}^\times) + F$, where $\mathbf{1} = \sum_{\nu} n_\nu \cdot (|\nu|) \in \text{Log}(K_{\mathbb{R}}^\times)$ is the vector consisting $n_\nu$, which equals 2 if $\nu$ is complex and 1 otherwise. This vector corresponds to the freedom of the norm (or rather, degree) in the space $\text{Div}_{K,\mathcal{S}}$, compared to $\text{Div}_{K,\mathcal{S}}^0$.

We can then rewrite any integral over $\text{Div}_{K,\mathcal{S}}$ with integrand $h(\mathbf{a})$ as

$$ \int_{\mathbf{a} \in \text{Div}_{K,\mathcal{S}}} h(\mathbf{a}) d\mathbf{a} = \int_{t \in \mathbb{R}} \int_{\mathbf{a} \in F} \sum_{\text{Log}_S(\beta) \in \text{Log}_S(\mathcal{O}_{K,\mathcal{S}}^\times)} h(\mathbf{a} + \text{Log}_S(\beta) + t \cdot \mathbf{1}) d\mathbf{a} dt $$

We apply this to Equation (117), we use again Lemma 17.8(ii) to write $\bar{D}_{\mathbf{a}+\text{Log}_S(\beta)}[0] = \bar{D}_{\mathbf{a}}[\text{Log}_S(\beta)]$ and we use the fact that $\bar{D}_{\mathbf{a}+t\mathbf{1}} = \bar{D}_{\mathbf{a}}$, since Algorithm 3 does not depend on the norm of the input (since Sample does not, see Theorem 13.2). Then, Equation (117) equals

$$ = \int_{t \in \mathbb{R}} \int_{\mathbf{a} \in F} \sum_{\text{Log}_S(\beta) \in \text{Log}_S(\mathcal{O}_{K,\mathcal{S}}^\times)} \bar{D}_{\mathbf{a}}[\text{Log}_S(\beta)] \cdot \mathcal{G}_{\zeta}(\mathbf{a} + t\mathbf{1} + \text{Log}_S(\beta) + M) d\mathbf{a} dt \quad (118) $$
By Hölder's inequality, the positivity of all arguments and the fact that (by Lemma 17.8(i))

$$ \sum_{\text{Log}_S(\beta) \in \text{Log}_S(\mathcal{O}_{K,S}^\times)} \bar{D}_a[\text{Log}_S(\beta)] = 1, $$

we can bound Equation (118) by

$$ \leq \int_{t \in \mathbb{R}} \int_{\mathbf{a} \in F} \max_{\text{Log}_S(\beta) \in \text{Log}_S(\mathcal{O}_{K,S}^\times)} \mathcal{G}_\zeta(\mathbf{a} + t\mathbf{1} + \text{Log}_S(\beta) + M) d\mathbf{a} dt \quad (119) $$

$$ \leq \int_{t \in \mathbb{R}} \int_{\mathbf{a} \in F} \frac{\mathcal{G}_\zeta(\mathbf{a} + t\mathbf{1} + \text{Log}_S(\mathcal{O}_{K,S}^\times))}{1 + e^{-\pi/c^2}} d\mathbf{a} dt \leq \frac{1}{1 + e^{-\pi/c^2}}. \quad (120) $$

whenever $\zeta \ge c \cdot \varrho(\text{Log}_S(\mathcal{O}_{K,S}^\times))$. Here we apply Lemma 18.4, which gives us

$$ \mathcal{G}_{\zeta}(\mathbf{a} + t\mathbf{1} + \text{Log}_{\mathbb{S}}(\beta) + M) \le \frac{\mathcal{G}_{\zeta}(\mathbf{a} + t\mathbf{1} + \text{Log}_{\mathbb{S}}(\beta) + \text{Log}_{\mathbb{S}}(\mathcal{O}_{K,\mathbb{S}}^{\times}))}{1 + e^{-\pi/c^2}} = \frac{\mathcal{G}_{\zeta}(\mathbf{a} + t\mathbf{1} + \text{Log}_{\mathbb{S}}(\mathcal{O}_{K,\mathbb{S}}^{\times}))}{1 + e^{-\pi/c^2}}. $$

By picking $c = 3$, it holds that $\zeta \ge c \cdot \varrho(\text{Log}_S(\mathcal{O}_{K,S}^\times))$ (see line 3 of Algorithm 4) and that $(1 + e^{-\pi/c^2})^{-1} \le 6/10$.

We now explain how to amend the proof for the case where $\mathfrak{m}_0 \ne \mathcal{O}_K$, i.e., a non-trivial modulus. In this case, the shifting property (Property (ii) of Lemma 17.8) holds for $\alpha \in K^{\mathfrak{m}_0,1}$ only.

Write $M_{\mathfrak{m}_0} = \text{Log}_S(K^{\mathfrak{m}_0,1}) \cap M$ and put $\{\text{Log}_S(\mu_1), \dots, \text{Log}_S(\mu_w)\} \subseteq M$ for a set of representatives of $M/M_{\mathfrak{m}_0}$ (which is finite by the fact that $K/K^{\mathfrak{m}_0,1}$ is finite). By similar computations as in Equation (117), we obtain

$$ \begin{align} \sum_{\text{Log}_S(\mu) \in M} \bar{D}[\text{Log}_S(\mu)] &= \int_{\mathbf{a} \in \text{Div}_{K,S}} \sum_{\text{Log}_S(\mu) \in M_{\mathfrak{m}_0}} \sum_{i=1}^{w} \bar{D}_{\mathbf{a}}[\text{Log}_S(\mu_i) + \text{Log}_S(\mu)] \cdot \mathcal{G}_{\zeta}(\mathbf{a}) d\mathbf{a} \nonumber \\ &= \int_{\mathbf{a} \in \text{Div}_{K,S}} \sum_{\text{Log}_S(\mu) \in M_{\mathfrak{m}_0}} \sum_{i=1}^{w} \bar{D}_{\mathbf{a}+\text{Log}_S(\mu)}[\text{Log}_S(\mu_i)] \cdot \mathcal{G}_{\zeta}(\mathbf{a}) d\mathbf{a} \nonumber \\ &= \int_{\mathbf{a} \in \text{Div}_{K,S}} \sum_{\text{Log}_S(\mu) \in M_{\mathfrak{m}_0}} \sum_{i=1}^{w} \bar{D}_{\mathbf{a}}[\text{Log}_S(\mu_i)] \cdot \mathcal{G}_{\zeta}(\mathbf{a} - \text{Log}_S(\mu)) d\mathbf{a} \nonumber \\ &= \int_{\mathbf{a} \in \text{Div}_{K,S}} \sum_{i=1}^{w} \bar{D}_{\mathbf{a}}[\text{Log}_S(\mu_i)] \cdot \mathcal{G}_{\zeta}(\mathbf{a} + M_{\mathfrak{m}_0}) d\mathbf{a} \tag{121} \end{align} $$

Now we use that $\mathbb{S}$ and $\mathfrak{m}_0$ do not share primes, and that $\mathbb{S}$ generates the ray class group $\text{Cl}_K^{\mathfrak{m}_0}$, so that we can split up the space

$$ \text{Div}_{K,\mathbb{S}} = \mathbb{R} \cdot \mathbf{1} + \text{Log}_{\mathbb{S}}(\mathcal{O}_{K,\mathbb{S}}^{\times}) \cap \text{Log}_{\mathbb{S}}(K^{\mathfrak{m}_0,1}) + F_{\mathfrak{m}_0}, \quad (122) $$

with a compact $F_{\mathfrak{m}_0}$. The set $\mathbb{S}$ and $\mathfrak{m}_0$ not sharing primes is essential for the fundamental domain $F_{\mathfrak{m}_0}$ to be compact (which is required for the current proof); indeed, if $\mathbb{S}$ and $\mathfrak{m}_0$ would share a prime, $\text{Log}_{\mathbb{S}}(\mathcal{O}_{K,\mathbb{S}}^{\times}) \cap \text{Log}_{\mathbb{S}}(K^{\mathfrak{m}_0,1})$ would be of rank strictly less than that of $\text{Div}_{K,\mathbb{S}}$, resulting in a $F_{\mathfrak{m}_0}$ in Equation (122) of infinite volume.

For $\mathbb{S}$ and $\mathfrak{m}_0$ not sharing a prime divisor, one could construct $F_{\mathfrak{m}_0}$ as follows. Pick a set of ideals $A = \{\mathbf{a}_1, \dots, \mathbf{a}_w\}$ (with all prime factors in $\mathbb{S}$) that are representatives of the ray class group $\text{Cl}_K^{\mathfrak{m}_0}$. Next, define $V$ to be the Voronoi fundamental domain of $\text{Log}(K^{\mathfrak{m}_0,1} \cap \mathcal{O}_K^\times) \subseteq H$. Then $F_{\mathfrak{m}_0} = \{\langle\langle \mathbf{a} \rangle\rangle + x \mid \mathbf{a} \in A \text{ and } x \in V\}$ is an example of a fundamental domain satisfying Equation (122).
Similar computations as in Equation (118) then show that Equation (121) equals (where $\mathrm{Log}_S(\beta)$ sums over $\mathrm{Log}_S(\mathcal{O}_{K,S}^\times \cap K^{m_0,1})$)

$$= \int_{t \in \mathbb{R}} \int_{\mathbf{a} \in F_{m_0} \mathrm{Log}_S(\beta)} \sum_{i=1}^{w} \sum_{\mathbf{b} \in \mathcal{O}_{K,S}^\times} \bar{\mathcal{D}}_{\mathbf{a}}[\mathrm{Log}_S(\beta) + \mathrm{Log}_S(\mu_i)] \cdot \mathcal{G}_\zeta(\mathbf{a} + t\mathbf{1} + \mathrm{Log}_S(\beta) + M_{m_0}) d\mathbf{a} dt \quad (123)$$

Since $\{\mathrm{Log}_S(\mu_1), \dots, \mathrm{Log}_S(\mu_w)\}$ are different representatives in $\mathrm{Log}_S(\mathcal{O}_{K,S}^\times)/\mathrm{Log}_S(\mathcal{O}_{K,S}^\times \cap K^{m_0,1})$ (indeed, if $\mathrm{Log}_S(\mu_1)-\mathrm{Log}_S(\mu_2) \in \mathrm{Log}_S(K^{m_0,1})$, we have $\mathrm{Log}_S(\mu_1)-\mathrm{Log}_S(\mu_2) \in \mathrm{Log}_S(K^{m_0,1}) \cap M$, contradiction), we can apply Hölders inequality again, yielding an upper bound of

$$\int_{t \in \mathbb{R}} \int_{\mathbf{a} \in F} \max_{\mathrm{Log}_S(\beta) \in \mathrm{Log}_S(\mathcal{O}_{K,S}^\times \cap K^{m_0,1})} \mathcal{G}_\zeta(\mathbf{a} + t\mathbf{1} + \mathrm{Log}_S(\beta) + M_{m_0}) d\mathbf{a} dt \le \frac{1}{1 + e^{\pi/c^2}}$$

whenever $\zeta \ge c \cdot \varrho(\mathrm{Log}_S(\mathcal{O}_{K,S}^\times))$, since $M_{m_0} + \mathrm{Log}_S(\mathcal{O}_{K,S}^\times \cap K^{m_0,1})$ is a lattice in $\mathrm{Log}_S(\mathcal{O}_{K,S}^\times)$. $\square$

18.5.4. About the closeness of the 'continuous version of Algorithm 4'. In this part, we show that the 'continuous version of Algorithm 4' and the ordinary one are close in statistical distance. Before we do that, we first need a lemma that shows that $N$, the discretization parameter in $\mathrm{Div}_{K,S,N}$ in Algorithm 4 satisfies some bound.

**Lemma 18.12.** Let $r = 48 \cdot \omega \cdot b^{2n/b} \cdot n^{7/2} \cdot |\Delta_K|^{3/2n} \cdot \mathcal{N}(m_0)^{1/n}$ as used in Algorithm 3. Then we have

$$40000 \cdot |\Delta_K| \cdot r^n \cdot n^{5/2} \le \omega^n \cdot \exp(11 + 16 \log^2 |\Delta_K| + 9n^2) = N,$$

where $N$ is as in line 3 in Algorithm 4.

*Proof.* Let $r = 48 \cdot \omega \cdot b^{2n/b} \cdot n^{7/2} \cdot |\Delta_K|^{3/2n} \cdot \mathcal{N}(m_0)^{1/n}$, where $m_0$ and $b$ are as chosen in Algorithm 3. The largest value $\mathcal{N}(m_0)$ can have is whenever $m_0$ is the product of the prime ideals of norm smaller than $x \le \frac{3}{2} \log |\Delta_K|$ (by line 3 of Algorithm 3 and Minkowski's theorem, which tells that $\log |\Delta_K| \ge \log(\pi/2)n \ge 0.4n$). Hence, using Lemma 11.4 with $x \le \frac{3}{2} \log |\Delta_K|$, using that $\sqrt{x}(\log(x)/(2\pi) + 2) \le 3x$ and $\sqrt{x}(\log(x)^2/(8\pi) + 2 \le 3x$ (for $x > 0.5$),

$$\log \mathcal{N}(m_0) \le x + \sqrt{x} \left( \left( \frac{\log x}{2\pi} + 2 \right) \log |\Delta_K| + \left( \frac{(\log x)^2}{8\pi} + 2 \right) n \right) \quad (124)$$

$$\le \underbrace{x}_{\le \frac{3}{2} \log |\Delta_K|} + \underbrace{3x \log |\Delta_K|}_{\le \frac{9}{2} \log^2 |\Delta_K|} + \underbrace{3xn}_{\le \frac{9}{2} \log |\Delta_K| \cdot \frac{3}{2} \log |\Delta_K|} \le 13 \log^2 |\Delta_K|. \quad (125)$$

By taking logarithms and using that $\log \mathcal{N}(m_0) \le 13 \log^2 |\Delta_K|$, that $\log(b^{2n^2/b}) \le n^2$, that $n^{7n/2} \le e^{3n^2}$, and that $48n \le e^{4n^2}$, we have that

$$r^n = (48 \cdot \omega \cdot b^{2n/b} \cdot n^{7/2} \cdot |\Delta_K|^{3/2n} \cdot \mathcal{N}(m_0)^{1/n})^n \\ \le \omega^n \cdot e^{4n^2+n^2+3n^2} \cdot e^{\frac{3}{2} \log |\Delta_K| + 13 \log^2 |\Delta_K|} \le \omega^n \cdot e^{8n^2} e^{15 \log^2 |\Delta_K|}.$$

Hence, using $40000 \le e^{11}$ and $n^{5/2} \le e^{n^2}$, we obtain

$$40000 \cdot |\Delta_K| \cdot r^n \cdot n^{5/2} \le \omega^n \cdot \exp(11 + 16 \log^2 |\Delta_K| + 9n^2) = N.$$

$\square$
Recall that the ‘continuous version of Algorithm 4’ means: Algorithm 4 in which line 4 is replaced by

$$ \mathbf{a} = \sum_{\mathbf{p} \in \mathcal{S}} a_{\mathbf{p}} (\|\mathbf{p}\|) + \sum_{\nu} b_{\nu} (\|\nu\|) \leftarrow \mathcal{G}_{\text{Div}_{K,\mathcal{S},\zeta}}, \text{ and put } y = \text{Exp}_{\infty}(\mathbf{a}_{\infty}). $$

**Lemma 18.13.** *The statistical distance of the output distributions of Algorithm 4 and the ‘continuous version of Algorithm 4’ is at most 1/50.*

*Proof.* The output distribution of the ‘continuous version of Algorithm 4’ can be written as

$$ \int_{\mathbf{a} \in \text{Div}_{K, \mathcal{S}}} \bar{\mathcal{D}}_{\mathbf{a}}[-] \mathcal{G}_{\text{Div}_{K, \mathcal{S}, \zeta}}(\mathbf{a}) d\mathbf{a} \quad (126) $$

whereas the output distribution of the ordinary one can be written as

$$ \sum_{\ddot{\mathbf{a}} \in \text{Div}_{K, \mathcal{S}, N}} \bar{\mathcal{D}}_{\ddot{\mathbf{a}}}[-] \hat{\mathcal{G}}_{\text{Div}_{K, \mathcal{S}, N}, \zeta}(\ddot{\mathbf{a}}), $$

which is $\varepsilon_G$-close (see Lemma 2.22, with $\varepsilon_G = 1/100$) to

$$ \sum_{\ddot{\mathbf{a}} \in \text{Div}_{K, \mathcal{S}, N}} \bar{\mathcal{D}}_{\ddot{\mathbf{a}}}[-] \mathcal{G}_{\text{Div}_{K, \mathcal{S}, N}, \zeta}(\ddot{\mathbf{a}}), \quad (127) $$

where the approximation $\ddot{\mathbf{a}} \approx \mathbf{a}$ is caused by the computation of $y$ in line 4. Writing $F$ for a fundamental domain of $\text{Div}_{K,\mathcal{S},N} \subseteq \text{Div}_{K,\mathcal{S}}$ (i.e., $F + \text{Div}_{K,\mathcal{S},N} = \text{Div}_{K,\mathcal{S}}$ is a tiling), and taking into account the error of $\varepsilon_G = 1/100$ caused by the Gaussian approximation (Lemma 2.22), the statistical distance between the continuous and ordinary variant of the algorithm can be estimated by (writing $|F|$ for the volume of $F$)

$$ \varepsilon_G + \frac{1}{2} \cdot \left\| \int_{\mathbf{a} \in F} \sum_{\ddot{\mathbf{a}} \in \text{Div}_{K, \mathcal{S}, N}} \bar{\mathcal{D}}_{\ddot{\mathbf{a}}+\mathbf{a}}[-] \mathcal{G}_{\text{Div}_{K, \mathcal{S}, \zeta}}(\ddot{\mathbf{a}}+\mathbf{a}) - |F|^{-1} \bar{\mathcal{D}}_{\ddot{\mathbf{a}}}[-] \mathcal{G}_{\text{Div}_{K, \mathcal{S}, N}, \zeta}}(\ddot{\mathbf{a}}) d\mathbf{a} \right\|_1 $$

By the trick $ab - a'b' = b(a - a') - a'(b' - b)$, the triangle inequality, and the fact that the $l_1$ norm of a distribution is equal to 1, the quantity above can be bounded by

$$ \varepsilon_G + \frac{1}{2} \cdot \underbrace{\int_{\mathbf{a} \in F} \sum_{\ddot{\mathbf{a}} \in \text{Div}_{K, \mathcal{S}, N}} \|\bar{\mathcal{D}}_{\ddot{\mathbf{a}}+\mathbf{a}} - \bar{\mathcal{D}}_{\ddot{\mathbf{a}}}\|_1 \cdot \mathcal{G}_{\text{Div}_{K, \mathcal{S}, \zeta}}(\ddot{\mathbf{a}}+\mathbf{a}) d\mathbf{a}}_{(A)} \quad (128) $$

$$ + \frac{1}{2} \cdot \underbrace{\int_{\mathbf{a} \in F} \sum_{\ddot{\mathbf{a}} \in \text{Div}_{K, \mathcal{S}, N}} |\mathcal{G}_{\text{Div}_{K, \mathcal{S}, \zeta}}(\ddot{\mathbf{a}}+\mathbf{a}) - |F|^{-1} \mathcal{G}_{\text{Div}_{K, \mathcal{S}, N}, \zeta}}(\ddot{\mathbf{a}})| d\mathbf{a}}_{(B)} \quad (129) $$

By property Lemma 17.8(iv), we have that $\bar{\mathcal{D}}_{\mathbf{a}}$ is almost Lipschitz-continuous in $\mathbf{a}$,

$$ \|\bar{\mathcal{D}}_{\ddot{\mathbf{a}}+\mathbf{a}} - \bar{\mathcal{D}}_{\ddot{\mathbf{a}}}\|_1 \le 3 \cdot |\Delta_K| \cdot r^n \cdot n^2 \cdot \|\ddot{\mathbf{a}}+\mathbf{a}-\ddot{\mathbf{a}}\| + \frac{1}{200}, $$

and $\|\ddot{\mathbf{a}}+\mathbf{a}-\ddot{\mathbf{a}}\| \le \|\ddot{\mathbf{a}}-\ddot{\mathbf{a}}\| + \|\mathbf{a}\| \le 2\sqrt{n}/N$ by construction$^{21}$ of $\ddot{\mathbf{a}} = \text{Log}(y/z) + \ddot{\mathbf{a}}$ on line 4 and since $\max_{\mathbf{a} \in F} \|\mathbf{a}\| = \sqrt{n}/N$ for $F = \{\sum_{\nu} x_{\nu}(\|\nu\|) \in \text{Div}_{K,\mathcal{S}} | x_{\nu} \in$

<footnote>$^{21}$We have $\|\text{Log}(y \cdot z^{-1})\| \le \sqrt{n} \max_{\nu} \text{log}(y_{\nu} z_{\nu}^{-1}) \le \sqrt{n} \max_{\nu} |y_{\nu} z_{\nu}^{-1} - 1| \le \sqrt{n}(\min_{\nu} z_{\nu})^{-1} \cdot \max_{\nu} |y_{\nu} - z_{\nu}| \le \sqrt{n}/N$, by line 4 of Algorithm 4.</footnote>
[-1/2, 1/2)}. Therefore, we can bound part (A) of Equation (128) by (using Lemma 18.12)

$$ (A) \le \underbrace{\frac{6 \cdot |\Delta_K| \cdot r^n \cdot n^{5/2}}{N}}_{\le 1/200} + 1/200 < 1/100. $$

For the bound on Equation (129), note that the sole continuity is on the $Log(K_{\mathbb{R}}^{\times})$-part of $Div_{K,\mathbb{S}}$. Hence, part (B) in Equation (129) is equal to

$$ (B) = \int_{\mathbf{a} \in F} \sum_{\mathbf{a} \in \frac{1}{N} \prod_{\nu} \mathbb{Z}} |\mathcal{G}_{\mathrm{Log}(K_{\mathbb{R}}^{\times}), \zeta}(\ddot{\mathbf{a}} + \mathbf{a}) - |F|^{-1} \mathcal{G}_{\frac{1}{N} \prod_{\nu} \mathbb{Z}, \zeta}(\ddot{\mathbf{a}})| d\mathbf{a}, \quad (130) $$

where we understand the inclusion $\frac{1}{N} \prod_{\nu} \mathbb{Z} \hookrightarrow \mathrm{Log}(K_{\mathbb{R}})$. Instantiating Lemma 9.13 with $\varepsilon = 1/700$ (loc. cit.), we can bound (B) via Equation (130) by $7\varepsilon = 1/100$. Here we use that $\zeta > 1$, that $\lambda_n(\frac{1}{N} \prod_{\nu} \mathbb{Z}) = \frac{1}{N}$, and that (by Lemma 18.12) $N \ge 40000n^2 \ge 5\pi\sqrt{n \log(4n/\varepsilon)}\varepsilon^{-1}n$, hence the assumptions of Lemma 9.13 are satisfied.

Concluding, the statistical distance between the continuous and ordinary variant of Algorithm 4, by using that $\varepsilon_{\mathcal{G}} = 1/100$, is at most $1/100 + 1/200 + 1/200 = 1/50$, since the respective summands in Equations (128) and (129) are bounded by $1/100, 1/200, 1/200$ respectively. $\square$

18.6. **Conclusion: the number of samples that generate the full $\mathbb{S}$-unit lattice.** The concluding theorem of this section quantifies how many samples of the output distribution $\bar{\mathcal{D}}$ of Algorithm 4 one needs to draw in order to get a generating set of the logarithmic unit lattice with high probability. The proof of the theorem uses the fact that this output distribution is evenly distributed and concentrated and applies Proposition 18.2 on distributions over lattices.

**Theorem 18.14.** There exists an absolute constant $C > 0$ and some $B_{\max} = \mathrm{poly}(L_{|\Delta_K|}(1/2), L_{n^n}(2/3), \rho_K^{\mathrm{cut}})$, where

$$ \rho_K^{\mathrm{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. For every number field $K$, for every $k \in \mathbb{Z}_{>0}$, and for every set of primes $\mathcal{S}$ that generates the ray class group $Cl_K^{m_0}$ of $K$, does not contain primes dividing $\mathfrak{m}_0$ and contains all primes (coprime with $\mathfrak{m}_0$) of norm $\le B_{\max}$, the probability that

$$ 6 \cdot k + 6 \cdot (|\mathcal{S}| + \mathfrak{r}) \cdot \left[ \log((|\mathcal{S}| + \mathfrak{r}) \cdot \zeta) + C \log \log |\Delta_K| \right] $$

samples from Algorithm 4 generate the entire logarithmic $\mathbb{S}$-unit lattice $\mathrm{Log}_{\mathcal{S}}(\mathcal{O}_{K,\mathbb{S}}^{\times})$ is at least $1 - e^{-k}$. Here, $|\mathcal{S}| + \mathfrak{r} = \mathrm{dim}(\mathrm{Log}_{\mathcal{S}}(\mathcal{O}_{K,\mathbb{S}}^{\times}))$ (with $\mathfrak{r} = \mathrm{dim}(\mathrm{Log}(\mathcal{O}_{K}^{\times})))$ and $\zeta$ is from line 3 of Algorithm 4.

*Proof.* By Lemma 18.11 and Lemma 18.10 the output distribution of Algorithm 4 on $\mathrm{Log}_{\mathcal{S}}(\mathcal{O}_{K,\mathbb{S}}^{\times})$ is 2/3-evenly distributed and $(R_0, 0)$-concentrated for $R_0 = O(\log^2 |\Delta_K|) + 3\zeta \cdot n_0$, where $\zeta$ is the deviation of the Gaussian distribution as in Algorithm 4, and where $n_0 = |\mathcal{S}| + n_{\mathbb{R}} + n_{\mathbb{C}} = \mathrm{dim}(\mathrm{Log}_{\mathcal{S}}(\mathcal{O}_{K,\mathbb{S}}^{\times})) + 1$.

So, one can apply Proposition 18.2 with $p = \frac{2}{3}$ and $q = 0$ (using $(1-p-q)^{-1} = 3$) to deduce that the number of samples $S$ required from the output distribution of