# Rigorous Methods for Computational Number Theory

Koen de Boer, Alice Pellet-Mary, Benjamin Wesolowski

► To cite this version:

Koen de Boer, Alice Pellet-Mary, Benjamin Wesolowski. Rigorous Methods for Computational Number Theory. 2025. hal-05365649

HAL Id: hal-05365649

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

Preprint submitted on 14 Nov 2025

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

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

<figure><img src="image_1.png" /></figure>
RIGOROUS METHODS FOR
COMPUTATIONAL NUMBER THEORY

KOEN DE BOER¹, ALICE PELLET-MARY², AND BENJAMIN WESOLOWSKI³

¹Leiden University, Mathematical Institute, Leiden, The Netherlands

²Univ. Bordeaux, CNRS, Inria, Bordeaux INP, IMB, UMR 5251, F-33400, Talence, France

³ENS de Lyon, CNRS, UMPA, UMR 5669, Lyon, France

**ABSTRACT.** We present the first algorithm for computing class groups and unit groups of arbitrary number fields that provably runs in probabilistic subexponential time, assuming the Extended Riemann Hypothesis (ERH). Previous subexponential algorithms were either restricted to imaginary quadratic fields, or relied on several heuristic assumptions that have long resisted rigorous analysis.

The heart of our method is a new general strategy to provably solve a recurring computational problem in number theory (assuming ERH): given an ideal class $[a]$ of a number field $K$, sample an ideal $b \in [a]$ belonging to a particular family of ideals (e.g., the family of smooth ideals, or near-prime ideals). More precisely, let $S$ be an arbitrary family of ideals, and $S_B$ the family of $B$-smooth ideals. We describe an efficient algorithm that samples ideals $b \in [a]$ such that $b \in S \cdot S_B$ with probability proportional to the density of $S$ within the set of all ideals.

The case where $S$ is the set of prime ideals yields the family $S \cdot S_B$ of near-prime ideals, of particular interest in that it constitutes a dense family of efficiently factorable ideals. The case of smooth ideals $S = S_B$ regularly comes up in index-calculus algorithms (notably to compute class groups and unit groups), where it has long constituted a theoretical obstacle overcome only by heuristic arguments.

CONTENTS

1. Introduction 2

2. Preliminaries 6

3. Acknowledgements 19

Part 1. Sampling ideals in a class: smooth, near-prime or otherwise 21

4. Introduction 21

5. Background on the Arakelov class group 22

6. Random walks in Arakelov ray class groups 26

7. Average densities and sampling 28

8. Uniform sampling in a box intersected with an ideal lattice 34

9. Ideal sampling 45

10. Properties of the ideal sampling algorithm 57

11. Estimation of the factor $N(m_0)/\phi(m_0)$ 65

Date: November 14, 2025.
## Part 2. Rigorous computation of class groups and unit groups 67

12. Introduction 67

13. Specialized ideal sampling algorithm 71

14. Density of smooth ideals 74

15. Background on $\mathbb{S}$-unit lattices 75

16. The generating and covering radius of the log-$\mathbb{S}$-unit lattice 77

17. Generating a single $\mathbb{S}$-unit 83

18. Obtaining a generating set of $\mathbb{S}$-units 89

19. Post-processing phase 100

20. Generating the exceptional $\mathbb{S}$-units 103

21. Full algorithm, final theorem and discussion 105

## Part 3. Provable lattice reduction techniques 114

22. Introduction 114

23. Buchmann-Kessler-Pohst algorithm 115

24. Computing the determinant of an approximate basis 121

25. Post-processing in the $\mathbb{S}$-unit computation 124

26. Lattice preliminaries 126

27. The BKZ algorithm on integer bases 130

28. The BKZ algorithm on approximate bases 134

References 142

## Part 4. Appendix 145

A.1. Proof of Theorem 6.4, the random walk theorem 145

A.2. Sampling of random prime ideals 150

A.3. Upper bound on the $n$th successive minimum of $O_K$ by Bhargava et al. 152

A.4. Upper bound on a defining polynomial of a number field 153

# 1. INTRODUCTION

Many number theoretic algorithms resort to heuristic assumptions for their analysis. This issue concerns even the most fundamental problems of the field, such as the computation of class groups in subexponential time. This persistent need for heuristic assumptions often stems from a step of this form: given an ideal class $[\mathfrak{a}]$ of a number field $K$, find a representative $\mathfrak{b} \in [\mathfrak{a}]$ belonging to a particular family $\mathcal{S}$ of ideals (for instance, the family of smooth ideals). It is relatively simple to design an algorithm for this task: sample a random representative $\mathfrak{b} \in [\mathfrak{a}]$, and hope that it belongs to the desired family $\mathcal{S}$. One then heuristically argues that the probability that $\mathfrak{b} \in \mathcal{S}$ should be proportional to the density of $\mathcal{S}$. For instance, the subexponential density of smooth ideals heuristically implies that one can find smooth representatives in subexponential time. This is the heart of state-of-the-art algorithms to compute class groups, unit groups, or generators of principal ideals in number fields [10, 16, 50], and has long constituted a theoretical obstacle overcome only by heuristic arguments (with the exception of quadratic fields [37]).

In the first part of this paper, we propose a general strategy to solve these ideal sampling tasks rigorously and efficiently, assuming only the extended Riemann
hypothesis (henceforth, ERH). In the second part, we apply this new technique to present the first algorithm for computing class groups and unit groups of arbitrary number fields that provably runs in probabilistic subexponential time. These two parts of the paper can be read essentially independently.

Part 3 consists of roughly two subjects: an slightly extended analysis and an application of a known provable variant of the BKZ algorithm for ideal lattices [38], which is used in Part 1 for lattice basis reduction; and an extended analysis of the algorithm of Buchmann, Pohst and Kessler [18, 17] which is required for the post-processing part in the class group and unit group computation in Part 2. These extra analyses are necessary to apply these known results to the specific use-cases of the present work.

**Main result of Part 1: sampling ideals.** Let $\mathcal{S}$ be an arbitrary family of ideals, and $\mathcal{S}_B$ the family of $B$-smooth ideals (i.e., products of prime ideals of norm at most $B$). In the first part of the paper, we describe an efficient algorithm that samples $\mathfrak{b} \in [\mathfrak{a}]$ such that $\mathfrak{b} \in \mathcal{S} \cdot \mathcal{S}_B$ with probability proportional to the density of $\mathcal{S}$. The set $\mathcal{S}_B$ is used to randomize the input, and $B$ can be chosen as small as $(\log |\Delta_K|)^{O(1)}$, where $\Delta_K$ is the discriminant of the field $K$. This result is formalized in Theorem 9.5, page 47, and allows to work with arbitrary ray class groups, and to restrict $\mathcal{S}_B$ to ideals whose prime factors fall in a prescribed subgroup.

For concreteness, Theorem 1.1 below is a specialization of Theorem 9.5 to the simplest case, without ray nor subgroups. Here, $\delta_{\mathcal{S}}[r^n]$ is the local density of $\mathcal{S}$ (Definition 2.11), i.e., the proportion of ideals of norm about $r^n$ that belong to $\mathcal{S}$.

**Theorem 1.1 (ERH).** Assuming ERH, there is a randomized algorithm $\mathcal{A}$ such that the following holds. Let $K$ be a number field, with degree $n$, discriminant $\Delta_K$, and let an LLL-reduced basis of the ring of integers $\mathcal{O}_K$ be given. Let $\mathfrak{a} \subseteq \mathcal{O}_K$ be an integral ideal. Let $\varepsilon \in \mathbb{R}_{>0}$, let $\mathfrak{b} \ge 2$ be an integer, and let $r \ge 48 \cdot b^{2n/b} \cdot n^{7/2} \cdot |\Delta_K|^{3/2n} \cdot \mathcal{N}(\mathfrak{a})^{1/n}$.

Given the above data, the algorithm $\mathcal{A}$ outputs $\beta \in \mathfrak{a}$ such that $(\beta) \cdot \mathfrak{a}^{-1} \in \mathcal{S} \cdot \mathcal{S}_B$ with probability at least $\delta_{\mathcal{S}}[r^n]/3 - \varepsilon$, for some smoothness bound $B = (\log |\Delta_K| + \log \log(1/\varepsilon))^O(1)$ and for any set $\mathcal{S}$ of integral ideals. Furthermore, the algorithm runs in expected polynomial time in $\log |\Delta_K|$, in $\log(\mathcal{N}(\mathfrak{a}))$, in $\log(1/\varepsilon)$, in $\mathfrak{b}^b$, and in the length of the input.

**Remark 1.2.** Note that the algorithm is described in a slightly different way than the above discussion: given $\mathfrak{a}$, we find $\beta \in \mathfrak{a}$ such that $\beta \mathfrak{a}^{-1} \in \mathcal{S} \cdot \mathcal{S}_B$. The ideal $\beta \mathfrak{a}^{-1}$ is in the inverse class of $\mathfrak{a}$, so up to an inversion, this problem is equivalent to the ideal sampling problem discussed above.

*Technique.* The folklore strategy to solve ideal sampling tasks is the following. The input ideal $\mathfrak{a}$ can be seen as a lattice, via the Minkowski embedding. One may find a reasonably short basis of $\mathfrak{a}$ (for instance, by means of LLL [51]), which then allows one to repeatedly sample reasonably short random elements $\beta \in \mathfrak{a}$, until the ideal $\mathfrak{b} = \beta \mathfrak{a}^{-1}$ belongs to the desired family $\mathcal{S}$. One then typically argues (heuristically!) that the probability of success is proportional to the density of $\mathcal{S}$.

To obtain a rigorous sampling algorithm, we proceed in two steps. First, we prove that a fairly straightforward strategy as above indeed has the desired probability of success when the input $\mathfrak{a}$ is treated as a random ideal lattice with uniformly random *Arakelov class*. More precisely, we prove in Theorem 7.1 that there is a reasonably small box $\mathcal{B}$ (in the embedding space) such that the *expected* density (over the
randomness of a) of elements $\beta \in a \cap B$ such that $\beta a^{-1} \in S$ is proportional to the density of $S$.

Second, we deal with arbitrary input a by randomizing its Arakelov class via a generalization of the random walks introduced in [14]. Concretely, the input a is multiplied by random ideals of small prime norm (the discrete part of the random walk), and is randomly distorted according to some Gaussian distribution (the continuous part of the random walk). We prove in Corollary 6.5 that the result is close to uniformly distributed in the Arakelov ray class group. The discrete part of the random walk introduces small prime factors, hence our method samples ideals in $S \cdot S_B$ instead of $S$. In all applications we are aware of, $S = S \cdot S_B$.

**Main result of Part 2: computing class groups and unit groups.** The case of smooth ideals $S = S_B$ regularly comes up in index-calculus algorithms, such as the aforementioned algorithms for computing class groups or unit groups. In these cases, this sampling task is not the only source of heuristics, so significantly more work is required to obtain a rigorous algorithm. This is the object of the second part of the article.

Let $K$ be a number field of degree $n$ and discriminant $\Delta_K$. The determination of the structure of its class group $Cl(K)$, together with a system of fundamental units, is one of the main problems of computational number theory [21, p. 217]. It has long been believed that this task can be solved in probabilistic subexponential time. Such algorithms have been described and analyzed under a variety of heuristic assumptions [16, 10]. Despite decades of investigation, only imaginary quadratic fields have been amenable to a rigorous analysis [37], assuming ERH. The history of class group computation is discussed in further detail in Section 12.2. In Part 2 of this paper, we present the first general algorithm for this problem that provably runs in probabilistic subexponential time, assuming ERH. We use the classical L-notation

$$L_x(\alpha, c) = \exp((c + o(1))(\log x)^\alpha(\log \log x)^{1-\alpha}),$$

and $L_x(\alpha) = L_x(\alpha, O(1))$. We prove the following theorem.

**Theorem 1.3 (ERH).** There is a probabilistic algorithm which, on input a number field $K$ of degree $n$ and discriminant $\Delta_K$ and an LLL-reduced basis of its ring of integers, computes its ideal class group and a compact representation of a fundamental system of units, 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$.

It has been conjectured since Buchmann's 1988 heuristic algorithm [16] that this problem can be solved in subexponential time $L_{|\Delta_K|}(1/2)$ for any family of fields of fixed degree. Theorem 1.3, together with the upper bound $\rho_K = (\log |\Delta_K|)^{O(n)}$ (see Equation (5) below), implies this conjecture, assuming ERH.

Then, it was conjectured by Biasse and Fieker's 2014 algorithm [10] that this problem can be solved in subexponential time even for varying degree. Again, Theorem 1.3 implies this conjecture, assuming ERH. However, Biasse and Fieker conjectured a complexity as in Theorem 1.3 where the quantity $\rho_K$ is replaced with $L_{n^n}(2/3)$. In our analysis, the quantity $\rho_K$ arises from the best known estimates on the density of bounded smooth ideals. It seems $\rho_K$ should appear in the same way in the heuristic complexity of [10], unless one expects a better bound on the density of smooth ideals.
**Computing $\mathcal{S}$-units.** 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 set $\mathcal{S}$ of prime ideals. It is well known that such an algorithm for $\mathcal{S}$-units can be used to compute the class group and the unit group. Combined with Theorem 17.7, which allows to decompose any integral ideal as a product of prime ideals in a sufficiently large set $\mathcal{S}$, this can also be used to solve other algorithmic problems, such as the principal ideal problem, or the class group discrete logarithm problem.

**Main results of Part 3: Detailed analyses of provable lattice techniques.**

Part 3 consists of an extended analysis of two already known results in lattice theory; namely the existence of a BKZ-algorithm variant [38] that has a provable running time, and the existence of an LLL-algorithm variant (called the Buchmann-Pohst-Kessler algorithm [18, 17]) that has a relatively well numerical stability, so that it can be used on ‘approximated’ bases. The extended analysis consists, in the case of the BKZ-algorithm, mainly of making explicit the techniques described in [38, Section 3, ‘Cost of BKZ’] and applying this BKZ-variant to ideal lattices. In the case of the Buchmann-Pohst-Kessler algorithm [18, 17], the present work required an extended analysis because in our use-case (in contrast to theirs) some lattice invariants like the rank and the determinant are unknown, thus requiring a slight extension to their algorithm.

The BKZ-variant a with provable running time is used in Part 1 for lattice basis reduction of ideal lattices, and the extended algorithm of Buchmann, Pohst and Kessler is required for the post-processing part in the class group and unit group computation in Part 2. Note that both of these algorithms being non-heuristic and having a provable running time is essential for the main results of the present work: a rigorous analysis of a common number-theoretic technique (Part 1) and a rigorous algorithm for computing the unit group and the class group that has a provable upper bound on the run time (Part 2).

**Further applications.** Sampling smooth ideals is a task that regularly arises in computational number theory. In Part 2, we focus on the problem of class group and unit group computation, but it is more generally a common component of index-calculus algorithms, like the general number field sieve for integer factorization or the computation of discrete logarithms in finite fields. We do not investigate this direction further in the present paper.

Applying the method of Part 1 to the case where $\mathcal{S}$ is the set of prime ideals allows one to sample in the family $\mathcal{S} \cdot \mathcal{S}_B$ of near-prime ideals, of particular interest in that it constitutes a dense family of efficiently factorable ideals. Therefore, our sampling method provides a rigorous way to transform any ideal $\mathfrak{a}$ into an equivalent ideal $\mathfrak{b}$ of known factorization. Obtaining such factorable ideals (or elements) is a key step in algorithms to compute power residue symbols. Specifically, it allows to perform the ‘principalization step’ in [15, §5.2] efficiently. The first author of the present article has developed this idea in his PhD dissertation [12], applying the main result of Part 1 to construct the first polynomial time algorithm to compute power residue symbols.

**Related work.** The aforementioned difficulties of ideal sampling and class group computation have already been overcome in the special case of *imaginary quadratic* number fields. Building on a result of Seysen [69], Hafner and McCurley [37] gave
a provable algorithm for computing class groups and unit groups of imaginary quadratic fields, assuming ERH. This case distinguishes itself by the finiteness of the unit group and the existence of reduced representatives of ideal classes. This algorithm exploits random walks in the class group to find B-smooth principal ideals. The idea of performing a random walk in the class group was reused in the algorithms of Buchmann [16] and Biasse and Fieker [10], in a heuristic way. Rather than random walks in class groups, our method exploits the much richer Arakelov (ray) class groups. Random walks in Arakelov class groups were first studied in [14] to prove the random self-reducibility of computational problems in ideal lattices. Their technique to study the convergence of these walks plays a key role in the present paper. We note that Schoof [68] rephrased Buchmann's algorithm in terms of Arakelov theory, and we borrow from his formalism.

## 2. PRELIMINARIES

### 2.1. Notation.
We denote by $\mathbb{N}, \mathbb{Z}, \mathbb{Q}, \mathbb{R}, \mathbb{C}$ the natural numbers, the integers, the rationals, the real numbers, and the complex numbers respectively. The notation $\log$ refers to logarithms in base $e$, whereas the notation $\log_2$ denotes logarithms in base 2. For finite sets $X$ we denote by $|X|$ the number of elements in $X$. For infinite sets $X$ with a well-defined volume, we use both notations $\text{Vol}(X) = |X|$ for the volume of $X$. The transpose of a matrix $M$ is denoted by $M^T$. For a ring $R$, we write $R^\times$ the set of invertible elements of $R$, and $R^* := R \setminus \{0\}$.

We use the classic big $O$ and $\Omega$ asymptotic notations, and all hidden constants are absolute (in particular, they never depend on the choice of a field $K$). We also use the notation $f = \text{poly}(g)$ as a synonym for $f = g^{O(1)}$. We use the notation $O_\epsilon$ to signify that the hidden constants depend on $\epsilon$. As already mentioned, to denote the running time of subexponential algorithms, we use the asymptotic $L$-notation

$$L_x(\alpha, c) = \exp\left(\left(c + o(1)\right)\left(\log x\right)^{\alpha}\left(\log \log x\right)^{1-\alpha}\right),$$

where the $o(1)$ is asymptotic in $x$ (and does not depend on other parameters). We also write $L_x(\alpha) = L_x(\alpha, O(1))$.

For a real vector space $V \subseteq \mathbb{R}^m$, we consider the Euclidean norm $\| \cdot \|$, and the infinity-norm $\| \cdot \|_\infty$. We sometimes write $\| \cdot \|_2$ for $\| \cdot \|_1$ to emphasize the type of norm. We will occasionally use the notation $\mathcal{B} = \mathcal{B}_2$ and $\mathcal{B}_\infty$ for the unit ball with respect to the Euclidean and infinity norm respectively. In particular, the Euclidean ball of radius $r$ in $V$ is typically denoted

$$r\mathcal{B} = \{\mathbf{v} \in V \mid \|\mathbf{v}\| < r\}.$$

The vector space $V$ is either clear from context or explicitly mentioned when introducing $\mathcal{B}$ or $\mathcal{B}_\infty$.

### 2.2. The Extended Riemann Hypothesis.
All statements that mention (ERH), such as Theorem 1.1, assume the Extended Riemann Hypothesis, which refers to the Riemann Hypothesis for Hecke $L$-functions (see [43, §5.7]).

### 2.3. Euclidean lattices.
A lattice $\Lambda$ is a discrete subgroup of a real vector space $V = \mathbb{R}^m$. We write $\text{span}_{\mathbb{R}}(\Lambda)$ the real vector subspace of $V$ spanned by the vectors of $\Lambda$. The rank of the lattice is the dimension of $\text{span}_{\mathbb{R}}(\Lambda)$, and we say the lattice is full-rank if $\text{span}_{\mathbb{R}}(\Lambda) = V$. A lattice (of rank $n$) can be represented by a basis $\mathbf{B} = (\mathbf{b}_1, \dots, \mathbf{b}_n)$ such that $\Lambda = \{\sum_i x_i \mathbf{b}_i, x_i \in \mathbb{Z}\}$. For a given basis $\mathbf{B} \in \mathbb{R}^{m \times n}$ we denote by $\mathcal{L}(\mathbf{B})$ the lattice spanned by the columns of this basis.
**Geometric invariants.** The covolume of $\Lambda$, denoted by $\mathrm{Vol}(\Lambda)$, is the volume of the quotient $\mathrm{span}_{\mathbb{R}}(\Lambda)/\Lambda$. If $\mathbf{B} \in \mathbb{R}^{m \times n}$ is a basis of $\Lambda$ (with column vectors), then the covolume of $\Lambda$ is equal to $\mathrm{Vol}(\Lambda) = \sqrt{\det(\mathbf{B}^{\top}\mathbf{B})}$. This quantity is also the volume of any fundamental domain of the lattice. One such domain is of special interest: the Voronoi cell.

**Definition 2.1.** Let $\Lambda \subseteq V$ be a full-rank lattice. We denote by

$$V_0(\Lambda) = \{\mathbf{x} \in V \mid \|\mathbf{x}\| \le \|\mathbf{x} - \mathbf{\ell}\| \text{ for all } \mathbf{\ell} \in \Lambda\}$$

the Voronoi cell of $\Lambda$ around zero. It is a fundamental domain for the lattice $\Lambda$ (up to a set of 'faces' of measure zero), thus has volume $\mathrm{Vol}(\Lambda)$.

The i-th successive minimum of $\Lambda$ is denoted by $\lambda_i(\Lambda)$. More precisely, each $\lambda_i(\Lambda)$ is the smallest real number such that there exist at least $i$ linearly independent vectors of euclidean norm at most $\lambda_i(\Lambda)$ in $\Lambda$. We call $\lambda_1(\Lambda)$ the first minimum, and $\lambda_n(\Lambda)$ the last minimum (where $n$ is the rank of the lattice). The covering radius $\mathrm{cov}(\Lambda)$ is the smallest $r > 0$ such that for any element $\mathbf{x} \in \mathrm{span}_{\mathbb{R}}(\Lambda)$ there exists a lattice point at distance at most $r$ from $\mathbf{x}$. The analogous notions with respect to the maximum norm $\|\cdot\|_{\infty}$ instead of the Euclidean norm are denoted by $\lambda_i^{(\infty)}(\Lambda)$ and $\mathrm{cov}_{\infty}(\Lambda)$.

The following notion, the generating radius $\varrho(\Lambda)$, is closely related to $\lambda_n(\Lambda)$ and $\mathrm{cov}(\Lambda)$, but not as standard.

**Definition 2.2 (Generating radius).** For a lattice $\Lambda$, the generating radius $\varrho(\Lambda)$ is the smallest real number such that the set of all vectors of $\Lambda$ of euclidean norm $\le \varrho(\Lambda)$ generates the lattice $\Lambda$ (as a $\mathbb{Z}$-module). In other words,

$$\varrho(\Lambda) = \min \left( r > 0 \mid \{\mathbf{x} \in \Lambda \mid \|\mathbf{x}\| \le r\} \text{ generates } \Lambda \right).$$

**Lemma 2.3.** For any lattice $\Lambda$, we have

$$\lambda_n(\Lambda) \le \varrho(\Lambda) \le 2 \cdot \mathrm{cov}(\Lambda) \le \sqrt{n} \cdot \lambda_n(\Lambda).$$

*Proof.* The left-most inequality follows from the very definitions of $\lambda_n(\Lambda)$ and $\varrho(\Lambda)$, and the right-most inequality can be found in [53, Theorem 7.9]. We prove the middle inequality by using the concept of *Voronoi-relevant vectors* of the lattice $\Lambda$. The Voronoi cell $V_0(\Lambda)$ of $L$ contains all vectors of $\mathrm{span}_{\mathbb{R}}(\Lambda)$ that are closer or equally close to 0 than to any other lattice point (see Definition 2.1). We know (e.g., [53, Proposition 8.4]) that $V_0(\Lambda)$ is compact and convex and that $\mathrm{Vol}_{\mathrm{span}_{\mathbb{R}}(\Lambda)}(V_0(\Lambda)) = \mathrm{Vol}(\Lambda)$. From the definition of the Voronoi cell and of the covering radius of $\Lambda$, we also know that all $\mathbf{x} \in V_0(\Lambda)$ satisfy $\|\mathbf{x}\| \le \mathrm{cov}(\Lambda)$ (see also [53, Proposition 8.4]).

The Voronoi-relevant vectors of $\Lambda$ are the vectors $S_{V_0} = \{\mathbf{v} \in \Lambda \mid \exists \mathbf{x} \in V_0(\Lambda), \|\mathbf{x}\| = \|\mathbf{x} - \mathbf{v}\|\}$; these are the vectors defining the facets of the Voronoi cell. From the definition of these vectors, it holds that $V_0(\Lambda) = \{\mathbf{x} \in \mathrm{span}_{\mathbb{R}}(\Lambda) \mid \forall \mathbf{v} \in S_{V_0}, \|\mathbf{x}\| \le \|\mathbf{x} - \mathbf{v}\|\}$. Moreover, since $\|\mathbf{x}\| \le \mathrm{cov}(\Lambda)$ for all $\mathbf{x} \in V_0(\Lambda)$, we have that $\|\mathbf{v}\| \le 2 \mathrm{cov}(\Lambda)$ for all Voronoi-relevant vectors $\mathbf{v}$. We will show that $S_{V_0}$ generates the lattice $\Lambda$, which will conclude the proof.

Let $\Lambda'$ be the lattice generated by the vectors in $S_{V_0}$. We know that $\Lambda' \subseteq \Lambda$ and that $\Lambda'$ has rank $n$ (since $\mathrm{span}_{\mathbb{R}}(\Lambda') = \mathrm{span}_{\mathbb{R}}(V_0(\Lambda)) = \mathrm{span}_{\mathbb{R}}(\Lambda)$). Moreover, since $S_{V_0} \subseteq \Lambda'$, we know that $V_0(\Lambda') \subseteq \{\mathbf{x} \in \mathrm{span}_{\mathbb{R}}(\Lambda) \mid \forall \mathbf{v} \in S_{V_0}, \|\mathbf{x}\| \le \|\mathbf{x} - \mathbf{v}\|\} = V_0(\Lambda)$. From this we conclude that $\mathrm{Vol}(\Lambda') \le \mathrm{Vol}(\Lambda)$ and so $\Lambda' = \Lambda$ as desired. $\square$
The next two results regarding counting lattice points in sets, Lemma 2.4 and Lemma 2.8, are folklore. We include proofs for completeness, as they play an important role in the article.

Estimation on the average number of lattice points in a measurable volume.

**Lemma 2.4.** Let $V$ be a Euclidean vector space and let $\Lambda \subseteq V$ be a full rank lattice. Let $S \subseteq V$ be a measurable set, and let $c \in V/\Lambda$ be chosen uniformly. Then

$$ \mathbb{E}_{c \leftarrow V/\Lambda} [|(\Lambda + c) \cap S|] = \text{Vol}(S)/\text{Vol}(\Lambda). $$

*Proof.* By integrating the measurable indicator set $1_S$, and choosing a fundamental domain $F$ of $V/\Lambda$ (which has volume $\text{Vol}(\Lambda)$), we obtain

$$ \mathbb{E}_{c \leftarrow V/\Lambda} [|(\Lambda+c) \cap S|] = \frac{1}{\text{Vol}(F)} \int_{c \in F} \sum_{\ell \in \Lambda} 1_S(c+\ell) d\mathbf{c} = \frac{1}{\text{Vol}(\Lambda)} \int_{\mathbf{v} \in V} 1_S(\mathbf{v}) d\mathbf{v} = \frac{\text{Vol}(S)}{\text{Vol}(\Lambda)}. \quad \square $$

Estimation on the number of lattice points in a convex measurable volume. For the ideal sampling algorithm (Algorithm 2) we need to efficiently sample in a shifted box (see Section 8). Lemma 2.8, which shares some similarities with [63, §4.2], provides means to estimate the number of lattice elements in such a box. This estimate is essential in the proof in Section 8. To prepare for the proof of this lemma, we will need some facts on Minkowski sums of sets.

**Definition 2.5.** Let $V$ be a Euclidean vector space. For two sets $X, Y \subseteq V$, we define the Minkowski sum $X \oplus Y$ as follows.

$$ X \oplus Y = \{\mathbf{x} + \mathbf{y} \mid \mathbf{x} \in X, \mathbf{y} \in Y\}. $$

For $c \in \mathbb{R}_{>0}$ we denote by $cX$ the set

$$ cX = \{c \cdot \mathbf{x} \mid \mathbf{x} \in X\}. $$

**Lemma 2.6.** Let $V$ be a Euclidean vector space and let $r, s > 0$ and let $X \subseteq V$ be a convex volume. Then

$$ (rX) \oplus (sX) = (r+s)X. $$

*Proof.* We start with inclusion to the right. Suppose $\mathbf{y} \in (rX) \oplus (sX)$, i.e., $\mathbf{y} = r\mathbf{x} + s\mathbf{x}'$ where $\mathbf{x}, \mathbf{x}' \in X$. Then $\frac{\mathbf{y}}{r+s} = \frac{r\mathbf{x}+s\mathbf{x}'}{r+s} \in X$, since it is a weighted average of two points in $X$ and $X$ is convex. So $\mathbf{y} \in (r+s)X$. Inclusion to the left holds because $\mathbf{y} \in (r+s)X$ means that $\mathbf{y} = (r+s)\mathbf{x} = r\mathbf{x} + s\mathbf{x} \in (rX) \oplus (sX)$. $\square$

**Lemma 2.7.** Let $V$ be a Euclidean vector space, let $r > 0$, let $X, Y \subseteq V$ be sets and let $S \subseteq V$ be a symmetric set, i.e., $\mathbf{x} \in S \Leftrightarrow -\mathbf{x} \in S$. Then

$$ (X \oplus S) \cap Y \subseteq [X \cap (Y \oplus S)] \oplus S. $$

*Proof.* Suppose $\mathbf{x} + \mathbf{s} = \mathbf{y} \in (X \oplus S) \cap Y$. Then $\mathbf{x} = \mathbf{y} - \mathbf{s} \in X \cap (Y \oplus S)$, so $\mathbf{y} = \mathbf{x} + \mathbf{s} \in [X \cap (Y \oplus S)] \oplus S$. $\square$

**Lemma 2.8.** Let $V$ be a $n$-dimensional Euclidean vector space, let $\Lambda \subseteq V$ be a full-rank lattice, let $X \subseteq V$ be a convex measurable volume for which $V_0 \subseteq cX$ for
some $c \in \mathbb{R}_{>0}$, where $\mathcal{V}_0$ is the Voronoi cell of $\Lambda$ (see Definition 2.1). Then, for all $\mathbf{t}, \mathbf{t}' \in V$ and all $r > 2c$,

$$ |(\Lambda + \mathbf{t}) \cap r(X + \mathbf{t}')| \in [e^{-2nc/r}, e^{2nc/r}] \cdot \frac{r^n \cdot \mathrm{Vol}(X)}{\mathrm{Vol}(\Lambda)}, $$

where $r(X + \mathbf{t}') = \{r \cdot (x + \mathbf{t}') | x \in X\}$ is the scaling of the (translated) set $X + \mathbf{t}'$ by $r \in \mathbb{R}_{>0}$.

**Proof.** As $|(\Lambda + \mathbf{t}) \cap (rX + r\mathbf{t}')| = |(\Lambda + \mathbf{t} - r\mathbf{t}') \cap rX|$, we just assume, without loss of generality, that $\mathbf{t}' = 0$. Note that $\mathcal{V}_0 \subseteq cX$, and that $X$ is convex. So, by Lemma 2.6, we have $(rX) \boxplus \mathcal{V}_0 \subseteq (rX) \boxplus (cX) = (r+c)X$. Similarly, $(r-c)X \boxplus \mathcal{V}_0 \subseteq rX$. Therefore

$$ [(\Lambda + \mathbf{t}) \cap rX] \boxplus \mathcal{V}_0 \subseteq (r+c)X. \qquad (1) $$

Note that $\mathcal{V}_0$ is symmetric and $(\Lambda + \mathbf{t}) \boxplus \mathcal{V}_0 = V$, the whole vector space. So, by Lemma 2.7 and $(r-c)X \boxplus \mathcal{V}_0 \subseteq rX$,

$$ (r-c)X = [(\Lambda + \mathbf{t}) \boxplus \mathcal{V}_0] \cap (r-c)X \qquad (2) $$

$$ \subseteq [(\Lambda + \mathbf{t}) \cap ((r-c)X \boxplus \mathcal{V}_0)] \boxplus \mathcal{V}_0 \subseteq [(\Lambda + \mathbf{t}) \cap rX] \boxplus \mathcal{V}_0 \qquad (3) $$

By Equations (1) and (3) and the fact that $\mathcal{V}_0$ is a fundamental domain of $\Lambda$ with volume $\mathrm{Vol}(\Lambda)$, we obtain

$$ (r-c)^n \mathrm{Vol}(X) \le |(\Lambda + \mathbf{t}) \cap rX| \cdot \mathrm{Vol}(\Lambda) \le (r+c)^n \mathrm{Vol}(X). $$

Dividing by $\mathrm{Vol}(\Lambda)$ and using the estimate $e^{-2nc/r} \le (1-c/r)^n \le (1+c/r)^n \le e^{2nc/r}$ (note that $r > 2c$) we arrive at the final claim. $\square$

2.4. **Number fields.** Throughout this paper, we consider a number field $K$ of rank $n$ over $\mathbb{Q}$, having ring of integers $\mathcal{O}_K$, discriminant $\Delta_K$, regulator $R_K$, class number $h_K$ and group of roots of unity $\mu_K$. Additionally, we consider a *modulus*: a formal product $\mathfrak{m} = \mathfrak{m}_0\mathfrak{m}_\infty$, where $\mathfrak{m}_0 \subseteq \mathcal{O}_K$ is an integral ideal and $\mathfrak{m}_\infty$ is a formal product of infinite places (see more details below). We know by Minkowski's theorem [55, pp. 261–264] that<fnref n="1" /> $\log|\Delta_K| \ge \log(\pi/2)n \ge 0.4n$ for $n \ge 2$.

The number field $K$ has $n$ field embeddings into $\mathbb{C}$, which are divided in $n_{\mathbb{R}}$ real embeddings and $n_{\mathbb{C}}$ conjugate pairs of complex embeddings, with $n = n_{\mathbb{R}} + 2n_{\mathbb{C}}$. These embeddings combined yield the so-called Minkowski embedding

$$ \begin{gathered} K \to K_{\mathbb{R}} \subseteq \bigoplus_{\sigma:K \hookrightarrow \mathbb{C}} \mathbb{C} \\ \alpha \mapsto (\sigma(\alpha))_{\sigma}, \end{gathered} $$

where

$$ K_{\mathbb{R}} = \left\{ x \in \bigoplus_{\sigma:K \hookrightarrow \mathbb{C}} \mathbb{C} \mid x_{\bar{\sigma}} = \bar{x}_{\sigma} \right\}. $$

Here, $\bar{\sigma}$ equals the conjugate embedding of $\sigma$ whenever $\sigma$ is a complex embedding and it is just $\sigma$ itself whenever it is a real embedding. We index the components of the vectors in $K_{\mathbb{R}}$ by the embeddings of $K$, i.e., we write $x = (x_\sigma)_\sigma \in K_{\mathbb{R}}$. Embeddings up to conjugation are called infinite places, denoted by $\nu$. With any embedding $\sigma$ we denote by $\nu_\sigma$ the associated place; and for any place we choose a fixed embedding $\sigma_\nu$. We will sometimes write $\sigma | \mathfrak{m}_\infty$ to mean that the associated

<footnote n="1">¹We have $|\Delta_K| \ge (\pi/4)^n n^{2n}/(n!)^2 \ge (\pi/2)^n$ for $n \ge 2$, since $n^{2n}/(n!)^2 \ge 2^n$ for $n \ge 2$.</footnote>
place $\nu_\sigma$ divides $\mathfrak{m}_\infty$. For any radius $r \in \mathbb{R}_{>0}$ we write $r\mathcal{B}_\infty = \{(x_\sigma)_\sigma \in K_\mathbb{R} \mid |x_\sigma| \le r$ for all $\sigma\}$, if it is clear from the context that $K_\mathbb{R}$ is the vector space at hand.

**Ideals.** The group of fractional ideals of $K$ is denoted by $\mathcal{I}_K$. Fractional ideals are denoted by $\mathfrak{a}, \mathfrak{b}, \dots$, and the symbols $\mathfrak{p}, \mathfrak{q}$ are generally reserved for integral prime ideals of $\mathcal{O}_K$. Any $\mathfrak{a} \in \mathcal{I}_K$ factors uniquely as a product of prime ideals (with possibly negative exponents), and we denote by $\mathrm{ord}_{\mathfrak{p}}(\mathfrak{a})$ the exponent of $\mathfrak{p}$ in the factorization of $\mathfrak{a}$; by extension, for any elements $\alpha \in K^*$ we define $\mathrm{ord}_{\mathfrak{p}}(\alpha) = \mathrm{ord}_{\mathfrak{p}}(\mathfrak{a})$ for $\mathfrak{a} = (\alpha)$ the principal ideal generated by $\alpha$. Two fractional ideals $\mathfrak{a}, \mathfrak{b}$ are said to be coprime if their unique decomposition into a product of prime ideals (with possibly negative coefficients) do not share any prime ideals. The algebraic norm of a fractional ideal $\mathfrak{a}$ or an element $\alpha \in K$ is denoted $\mathcal{N}(\mathfrak{a})$ and $\mathcal{N}(\alpha)$, respectively. When $\mathfrak{a} = (\alpha)$, we have $\mathcal{N}(\mathfrak{a}) = |\mathcal{N}(\alpha)|$.

**The class number formula.** Let $h_K$ be the class number of $K$, $R_K$ be its regulator and $\mu_K$ be its group of roots of unity. Let also $\zeta_K$ be the Dedekind zeta function of $K$, and $\rho_K$ be its residue at 1. The class number formula [57, VII. §5, Cor 5.11] states that

$$ \rho_K := \lim_{s \to 1} (s-1)\zeta_K(s) = \frac{2^{n_K} \cdot (2\pi)^{n_C} \cdot R_K \cdot h_K}{|\mu_K| \cdot \sqrt{|\Delta_K|}}. \quad (4) $$

The Dedekind residue $\rho_K \in \mathbb{R}_{>0}$ is bounded above$^2$ [52]: for $n = [K : \mathbb{Q}] > 1$, we have

$$ \log(\rho_K) \le (n-1) \cdot \log \left( \frac{e \log |\Delta_K|}{2(n-1)} \right) \le \log |\Delta_K|. \quad (5) $$

It can be approximated in polynomial time up to some factor [5], and so can the related quantity $R_K \cdot h_K$. More precisely, we have the following proposition.

**Proposition 2.9 (ERH).** There exists a polynomial time algorithm (in $\log |\Delta_K|$) that takes as input any number field $K$, and an LLL-reduced basis of its ring of integers $\mathcal{O}_K$, and outputs $\rho_0 \in \mathbb{Q}$ and $\eta_0 \in \mathbb{Q}$ such that

$$ \rho_0 \in [\frac{3}{4}, \frac{5}{4}] \cdot \rho_K $$

$$ \eta_0 \in [\frac{3}{4}, \frac{5}{4}] \cdot R_K \cdot h_K. $$

**Density of ideals.** In this article, we consider families of ideals, like smooth ideals or prime ideals. Given a specifically randomly generated ideal, we want to estimate the probability that it belongs to a given family. The notion of local density provides a certain approximation of this probability, for uniformly random ideals of bounded norm.

**Definition 2.10.** For any set of ideals $S$, we define $S(t) = \{\mathfrak{b} \in S \mid \mathcal{N}(\mathfrak{b}) \le t\}$.

**Definition 2.11 (Local density of an ideal set).** Let $x > 0$ a positive real number, and let $S$ be a set of integral ideals of $K$. We define the local density of $S$ at $x$ as

$$ \delta_S[x] = \min_{t \in [x/e^n, x]} \frac{|S(t)|}{\rho_K \cdot t} = \min_{t \in [x/e^n, x]} \frac{|\{\mathfrak{b} \in 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)).

<footnote>$^2$We use here that $\log(ex/2) \le x$ for all $x > 0$ and the fact that $\log(|\Delta_K|)/(n-1) > 0$ for $n \ge 2$.</footnote>
Note that the local density tends to the (asymptotic) 'natural density' of $\mathcal{S}$ as $x \to \infty$, since $|\{\mathfrak{a} \subseteq \mathcal{O}_K \mid \mathcal{N}(\mathfrak{a}) < t\}| \sim \rho_K \cdot t$ [59, §9.5]. However, this notion of natural density is not fine enough as it is simply 0 for families of interest like smooth ideals or prime ideals.

Ray. The group of fractional ideals coprime with the finite part $\mathfrak{m}_0$ of the modulus $\mathfrak{m}$ is denoted by $\mathcal{I}_K^\mathfrak{m}$. We denote by

$$K^{\mathfrak{m},1} = \langle \alpha \in \mathcal{O}_K \mid \alpha \equiv 1 \mod \mathfrak{m}_0 \text{ and } \sigma(\alpha) > 0 \text{ for all real } \sigma \mid \mathfrak{m}_\infty \rangle$$

the ray modulo $\mathfrak{m}$, a multiplicative subgroup of $K^*$. Here, the notation $\langle \cdot \rangle$ means that $K^{\mathfrak{m},1}$ is multiplicatively generated by the elements $\alpha \in \mathcal{O}_K$ satisfying $\alpha \equiv 1 \mod \mathfrak{m}_0$ and $\sigma(\alpha) > 0$ for all real $\sigma \mid \mathfrak{m}_\infty$, which also includes fractions.

The ideal ray class group $Cl_K^\mathfrak{m}$ modulo $\mathfrak{m}$ is defined as the quotient of $\mathcal{I}_K^\mathfrak{m}$ by the subgroup $\text{Princ}_K^\mathfrak{m} := \{(\alpha) \in \mathcal{I}_K^\mathfrak{m} \mid \alpha \in K^{\mathfrak{m},1}\}$. One retrieves the (ordinary) ideal class group by taking an empty modulus $\mathfrak{m} = \mathcal{O}_K$, for which $K^{\mathfrak{m},1} = K^*$. We also define $K^\mathfrak{m} = \langle \alpha \in \mathcal{O}_K \mid (\alpha) + \mathfrak{m}_0 = \mathcal{O}_K \rangle$, the multiplicative subgroup of $K^*$ generated by elements coprime to $\mathfrak{m}_0$. Note that $K^{\mathfrak{m},1} \subseteq K^\mathfrak{m}$ and that $K^\mathfrak{m} = K^*$ if $\mathfrak{m}_0 = \mathcal{O}_K$. The number of real places $\nu \mid \mathfrak{m}_\infty$ is denoted by $|\mathfrak{m}_\infty|$. We denote $\mathcal{N}(\mathfrak{m}) = \mathcal{N}(\mathfrak{m}_0) \cdot 2^{|\mathfrak{m}_\infty|}$. We will also use the generalized Euler totient $\phi(\mathfrak{m}_0) = |K^{\mathfrak{m}_0}/K^{\mathfrak{m}_0,1}|$ which equals $|\mathcal{O}_K/\mathfrak{m}_0|^\times$ for $\mathfrak{m}_0 \subsetneq \mathcal{O}_K$ and equals 1 for $\mathfrak{m}_0 = \mathcal{O}_K$.

We denote $K_{\mathbb{R}}^{\mathfrak{m}_\infty} = \{(x_\sigma)_\sigma \in K_{\mathbb{R}} \mid x_\sigma > 0 \text{ for real } \sigma \mid \mathfrak{m}_\infty\}$ for the 'positive part' of $K_{\mathbb{R}}$ with respect to the modulus $\mathfrak{m}$. For any $\tau \in K^\mathfrak{m}$, we denote $\tau K_{\mathbb{R}}^{\mathfrak{m}_\infty} = \{(x_\sigma)_\sigma \in K_{\mathbb{R}} \mid x_\sigma/\sigma(\tau) > 0 \text{ for real } \sigma \mid \mathfrak{m}_\infty\}$, which is the part of $K_{\mathbb{R}}$ that has the same sign as $\tau$ at the real embeddings $\sigma \mid \mathfrak{m}_\infty$.

### 2.5. Ideal lattices.
Ideals can be viewed as lattices in the real vector space $K_{\mathbb{R}}$, where $K_{\mathbb{R}}$ has its (Euclidean or maximum) norm inherited from the complex vector space it lives in. Explicitly, the Euclidean and maximum norm of $\alpha \in K$ are respectively defined by the rules $\|\alpha\|^2 = \sum_\sigma |\sigma(\alpha)|^2$ and $\|\alpha\|_{\infty} = \max_\sigma |\sigma(\alpha)|$, where $\sigma$ ranges over all embeddings $K \to \mathbb{C}$.

For any ideal $\mathfrak{a}$ of $K$, we define the associated lattice $\mathfrak{a} \subseteq K_{\mathbb{R}}$ to be the image of $\mathfrak{a} \subseteq K$ under the Minkowski embedding, which is clearly a discrete additive subgroup of $K_{\mathbb{R}}$. Abusing notation, we denote both the ideal and the associated lattice with the same symbol $\mathfrak{a}$. In particular, $\mathcal{O}_K$ is a lattice. Note that we have $\text{Vol}(\mathfrak{a}) = \sqrt{|\Delta_K|} \mathcal{N}(\mathfrak{a})$ for ideals $\mathfrak{a} \in \mathcal{I}_K$. The notion of ideal lattices extends to a larger family of lattices in $K_{\mathbb{R}}$ as follows.

**Definition 2.12 (Ideal lattices).** Let $K$ be a number field with ring of integers $\mathcal{O}_K$. An ideal lattice of $K$ is a lattice in $K_{\mathbb{R}}$ of the form $xa$ where $x \in K_{\mathbb{R}}^\times$ is invertible and $a$ is a fractional ideal of $K$. We denote the group of ideal lattices by $\text{IdLat}_K$.

The set of ideal lattices is a group with product $(xa)(yb) = (xy)(ab)$, inverse $x^{-1}a^{-1}$ and unit $\mathcal{O}_K$.

**Bounds on invariants of ideal lattices.** Denote $\Gamma(\Lambda) = \lambda_n(\Lambda)/\lambda_1(\Lambda)$, and define, for a fixed number field $K$:

$$\Gamma_K = \sup_{xa \in \text{IdLat}_K} \Gamma(xa) \qquad (6)$$

We have the following bounds.

**Lemma 2.13.** For any ideal lattice $xa \in \text{IdLat}_K$,
(i) $\lambda_1(x\mathfrak{a}) \ge \sqrt{n} \cdot \mathcal{N}(x\mathfrak{a})^{1/n}$.

(ii) $\lambda_n(\mathcal{O}_K)/\sqrt{n} \le \Gamma_K \le \lambda_n^\infty(\mathcal{O}_K) \le |\Delta_K|^{1/n}$.

(iii) For cyclotomic number fields $K$, $\Gamma_K = 1$.

(iv) $\lambda_n(x\mathfrak{a}) \le \sqrt{n} \cdot \Gamma_K \cdot \mathrm{Vol}(x\mathfrak{a})^{1/n}$.

(v) $\mathrm{cov}_\infty(x\mathfrak{a}) \le \mathrm{cov}(x\mathfrak{a}) \le n/2 \cdot \Gamma_K \cdot \mathrm{Vol}(x\mathfrak{a})^{1/n}$.

*Proof.* The first item follows from the fact that for any non-zero element $z \in x\mathfrak{a}$, it holds that $\mathcal{N}(x\mathfrak{a}) \le |\mathcal{N}(z)|$ and that $|\mathcal{N}(z)|^{2/n} \le \frac{1}{n} \cdot \|z\|^2$ by the inequality of arithmetic and geometric means, applied to the $(|\sigma(z)|^2)_\sigma$. Applying this to a $z$ reaching $\lambda_1(x\mathfrak{a})$ yields $\lambda_1(x\mathfrak{a}) \ge \sqrt{n}|\mathcal{N}(z)|^{1/n} \ge \sqrt{n}\mathcal{N}(x\mathfrak{a})^{1/n}$. For the second item, the inequality $\lambda_n(\mathcal{O}_K)/\sqrt{n} \le \Gamma_K$ follows from the definition of $\Gamma(\mathcal{O}_K)$ and the fact that $\lambda_1(\mathcal{O}_K) = \sqrt{n}$ (using that $\lambda_1(\mathcal{O}_K) \ge \sqrt{n}$ by the first item and that this lower bound is reached by $1 \in \mathcal{O}_K$). To obtain the bound $\Gamma_K \le \lambda_n^\infty(\mathcal{O}_K)$, pick an arbitrary ideal lattice $x\mathfrak{a} \in \mathrm{IdLat}_K$ and choose a shortest element $x\alpha \in x\mathfrak{a}$ with $\alpha \in \mathfrak{a} \in \mathcal{I}_K$. That means $\|x\alpha\| = \lambda_1(x\mathfrak{a})$. Then $x\mathfrak{a} \supset x \cdot (\alpha)$, and therefore,

$$ \lambda_n(x\mathfrak{a}) \le \lambda_n(x \cdot \alpha \mathcal{O}_K) \le \|x\alpha\| \cdot \lambda_n^\infty(\mathcal{O}_K) \le \lambda_1(x\mathfrak{a}) \cdot \lambda_n^\infty(\mathcal{O}_K). \quad (7) $$

The bound $\lambda_n^\infty(\mathcal{O}_K) \le |\Delta_K|^{1/n}$ is obtained from [8, Theorem 3.1] and is tailored to our purposes in Theorem A.3.1. Part (iii) follows from part (ii) and the fact that $\|\zeta\| = \|1\|$ for roots of unity $\zeta \in K$. Part (iv) is essentially Minkowski's bound $\lambda_1(x\mathfrak{a}) \le \sqrt{n} \mathrm{Vol}(x\mathfrak{a})^{1/n}$ combined with the definition of $\Gamma_K$. Finally, the last item follows from the fact that $\mathrm{cov}(\Lambda) \le \sqrt{n}/2 \cdot \lambda_n(\Lambda)$ [53, Theorem 7.9]. $\square$

**2.6. Representation of elements and ideals.** We assume throughout this paper that the number field $K$ is represented by a monic irreducible polynomial $f \in \mathbb{Z}[x]$ satisfying size($f$) := $\sum_i \log_2 |f_i| \le \mathrm{poly}(\log |\Delta_K|)$. This restriction is very mild, indeed we can prove that such a polynomial always exists (see Appendix A.4) and there are heuristic polynomial time algorithms computing such polynomials, e.g., [23, 34].

Additionally, we assume throughout this paper that we know an LLL-reduced basis $(\mathbf{b}_1, \dots, \mathbf{b}_n)$ of the ring of integers $\mathcal{O}_K$ of $K$. Such a basis has vectors (represented as polynomials in $\mathbb{Q}[x]/(f(x))$) whose size is polynomially bounded<fnref n="3" /> in $\log |\Delta_K|$. Note that such a basis can be computed in unconditional, probabilistic subexponential time in size($f$) (by factoring disc($f$) with [64], computing a basis of $\mathcal{O}_K$ with [19, Theorem 1.4], and reducing it with the LLL algorithm [51]).

For the main result of Part 1 such a basis is not required per se (see the discussion in Section 9.5), as any sub-order of $\mathcal{O}_K$ would suffice as well. This choice for a basis of the ring of integers is done purely because it simplifies the description and analysis of this main result.

<footnote n="3">³Let $\theta$ denote the class of $x$ in $\mathbb{Q}[x]/(f(x))$, and write $b_i = \sum_{j=1}^n q_{i,j} \theta^{j-1}$ for the elements of the LLL-reduced basis of $\mathcal{O}_K$ (with $q_{i,j} \in \mathbb{Q}$). Let $\mathbf{B} \in \mathbb{C}^{n \times n}$ be the matrix whose columns correspond to the Minkowski embedding of the $b_i$'s, and $\mathbf{T}$ be the one corresponding to the $\theta^{j-1}$'s. Then $(q_{i,j})_{i,j} = \mathbf{T}^{-1} \cdot \mathbf{B}$. By LLL reducedness of the $b_i$'s, it holds that the log of the coefficients of $\mathbf{B}$ are polynomially bounded in $\log |\Delta_K|$. The coefficients of $\mathbf{T}^{-1}$ correspond to the coefficients of the Lagrange polynomials associated to the roots of $f$, so their logarithm is also polynomially bounded in size($f$) = $\mathrm{poly}(\log |\Delta_K|)$ (using e.g., Mignotte's root separation lower bound and Cauchy's upper bound on the roots). Hence, we conclude that $|\log(q_{i,j})| \le \mathrm{poly}(\log |\Delta_K|)$.</footnote>

<footnote>It remains to prove that the denominators of the $q_i$ are bounded. As the integral basis $(1, \theta, \dots, \theta^{n-1})$ has discriminant $\Delta(f)$, any denominator of $q_i$ must divide $\Delta(f)/\Delta_K$ (since $\beta$ is integral). Since the size of $\Delta(f)$ is bounded by $\mathrm{poly}(\log |\Delta_K|)$ (per assumption), any denominator of $q_i$ must so, too.</footnote>
All elements and ideals in $K$ can then be represented by vectors and bases with rational coefficients, by using this basis of $O_K$ as a coordinate system; which we do in this paper.

The size($k$) of a number $k \in \mathbb{Z}$ is defined to be $\log_2|k|$ and is extended to rationals $\frac{a}{b}$ as size($a$) + size($b$) for reduced fractions $\frac{a}{b}$. The size of a $\mathbb{Q}$-vector is just the sum of the sizes of its entries, which allows to define the size of an element $\alpha \in K$ as the size of the rational vector representing $\alpha$ in the basis of $O_K$. The size of a matrix $M_a$ defining an ideal $\mathfrak{a}$ is defined as the sum of the sizes of the matrix entries.

Basic operations, such as addition, multiplication, inversion and approximate computation of a complex embedding of elements in $K$, are all polynomial in $\log|\Delta_K|$ and the (just defined) size of the elements involved.

Elements $x = (x_\sigma)_\sigma \in K_\mathbb{R}$ are represented with rational coefficients, that is, $x \in \bigoplus_\sigma (\mathbb{Q} + i\mathbb{Q}) \subseteq K_\mathbb{R}$, and the size of such an element is the size of the vector $(x_\sigma)_\sigma$ (which can be seen as a vector in $\mathbb{Q}^n$).

*Representation of ideals.* We assume throughout the paper that all integral ideals $\mathfrak{a} \subseteq O_K$ are represented by their Hermite Normal form (HNF) basis by default. This is possible since their matrix, using the basis of $O_K$ as coordinate system, has integral coefficients.

This requirement allows us to abuse terminology and write sentences like “the algorithm takes as input an integral ideal $\mathfrak{a}$”, without having to specify which basis of the ideal is given to the algorithm. As the HNF basis of an ideal is a canonical representation of that ideal, it cannot lead to any confusion.

Addition, multiplication and inversion of ideals given in HNF basis can be performed in time polynomial in the input size and in $\log|\Delta_K|$. Additionally, we have that the HNF basis of an integral ideal $\mathfrak{a}$ is bounded in size by $\text{poly}(n, \log N(\mathfrak{a}))$. So, by using the HNF basis of an integral ideal $\mathfrak{a}$ by default, one avoids the problem of the specific representation of $\mathfrak{a}$ bearing an influence on the running time of algorithms involving $\mathfrak{a}$. We therefore define size($\mathfrak{a}$) to be the size of its HNF basis. For a finite set $\mathbb{S}$ consisting of ideals we define size($\mathbb{S}$) = $|\mathbb{S}| \cdot \max_{\mathfrak{a} \in \mathbb{S}} \text{size}(\mathfrak{a})$. For a modulus $\mathfrak{m} = \mathfrak{m}_0\mathfrak{m}_\infty$, where $\mathfrak{m}_0 \subseteq O_K$ and $\mathfrak{m}_\infty$ is a formal product of infinite places, we define size($\mathfrak{m}$) = size($\mathfrak{m}_0$). Namely, as higher powers of infinite places do not have any influence as compared to a power of one, we will assume throughout this work that the infinite part $\mathfrak{m}_\infty$ only consists of single powers of places of $K$.

*Compact representation of elements.* In Part 2 of this article, an algorithm is discussed that computes a fundamental system of $\mathbb{S}$-units. In this algorithm, the output elements are given in a so-called *compact representation*, which we will explain presently.

Given a set of elements $\{\gamma_1, \dots, \gamma_k\}$ of $K$, we can write the element $\eta = \prod_{j=1}^k \gamma_j^{n_j}$ in compact representation by the pair of vectors

$$ (n_1, \dots, n_k) \in \mathbb{Z}^k, \quad (\gamma_1, \dots, \gamma_k) \in K^n \qquad (8) $$

In this way, $\eta$ is not explicitly computed in terms of the basis of $K$ (or $O_K$), but rather, the product is left implicit, allowing for much larger elements $\eta \in K$ to be described. Indeed, $\eta = \prod_{j=1}^k \gamma_j^{n_j}$ written in an $O_K$-basis might require $\sum_j n_j$ size($\gamma_j$) bits to write down, whereas the compact representation in Equation (8) only requires at most $\sum_j \text{size}(n_j) + \sum_j \text{size}(\gamma_j)$ bits to write down. The drawback of this
representation is that it only allows polynomial time multiplication and inversion of elements, but generally not efficient addition.

2.7. **The logarithmic embedding.** The logarithmic embedding of $K^\times$ is the map

$$ \mathrm{Log} : K^\times \to \bigoplus_\nu \mathbb{R} : \alpha \mapsto (n_\nu \log |\sigma_\nu(\alpha)|)_\nu, $$

where $n_\nu = 2$ if $\nu$ is a complex place and 1 otherwise. This map naturally extends to all invertible elements of $K_\mathbb{R}$, and this extension is surjective, i.e., $\mathrm{Log} \, K_\mathbb{R}^\times = \bigoplus_\nu \mathbb{R}$. Denoting $K_\mathbb{R}^0 = \{(x_\sigma)_\sigma \in K_\mathbb{R} \mid \prod_\sigma x_\sigma = 1\}$, we use this logarithmic map to define the vector space $H = \mathrm{Log}(K_\mathbb{R}^0)$ (called the hyperplane) and the *logarithmic unit lattice*

$$ \mathrm{Log}(\mathcal{O}_K^\times) \subseteq H, $$

a full-rank lattice in $H$. We write its dimension by $\mathfrak{r} = \dim(H) = n_\mathbb{R} + n_\mathbb{C} - 1$. Explicitly, we have

$$ H = \mathrm{Log} \, K_\mathbb{R}^0 = \{(x_\nu)_\nu \in \bigoplus_\nu \mathbb{R} \mid \sum_\nu x_\nu = 0\}. $$

The volume of the logarithmic unit lattice is given by the following formula (see, e.g., [57, I.§7 & I.§5, p. 33])

$$ \mathrm{Vol}(\mathrm{Log}(\mathcal{O}_K^\times)) = \sqrt{n_\mathbb{C} + n_\mathbb{R}} \cdot R_K. \qquad (9) $$

The first minimum of $\mathrm{Log}(\mathcal{O}_K^\times)$. By a result of Kessler [45], we have a lower bound on the first minimum of the lattice $\mathrm{Log}(\mathcal{O}_K^\times)$.

**Lemma 2.14.** We have $\lambda_1(\mathrm{Log}(\mathcal{O}_K^\times)) \ge \frac{1}{1000 \cdot \sqrt{n} \cdot \log(n)^3}$.

2.8. Divisors. We define the divisor group $\mathrm{Div}_K$ of $K$ as

$$ \mathrm{Div}_K := \bigoplus_\mathfrak{p} \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), and $\mathfrak{p}$ ranges over all prime ideals of $\mathcal{O}_K$ (also referred to as the *finite places of $K$*). We denote the canonical basis elements with the symbols $\langle \mathfrak{p} \rangle$ and $\langle \nu \rangle$ (the divisor with value 1 at $\mathfrak{p}$ or $\nu$ respectively, and 0 everywhere else). Then, an arbitrary divisor can be written as

$$ \mathbf{a} = \sum_{\mathfrak{p}} a_{\mathfrak{p}} \cdot \langle \mathfrak{p} \rangle + \sum_{\nu} a_{\nu} \cdot \langle \nu \rangle, $$

with only finitely many non-zero $a_{\mathfrak{p}}$ and with $a_{\nu} \in \mathbb{R}$. We will consistently use the symbols $\mathbf{a}, \mathbf{b}, \mathbf{e}, \dots$ for such divisors. Given such a divisor $\mathbf{a}$, we often write $\mathbf{a}_f = \sum_{\mathfrak{p}} a_{\mathfrak{p}} \cdot \langle \mathfrak{p} \rangle$ for its “finite part” and $\mathbf{a}_\infty = \sum_{\nu} a_{\nu} \cdot \langle \nu \rangle$ for its “infinite part”.

*The degree map.* The degree map is defined as

$$ \mathrm{deg} : \mathrm{Div}_K \to \mathbb{R} $$

$$ \sum_{\mathfrak{p}} a_{\mathfrak{p}} \cdot \langle \mathfrak{p} \rangle + \sum_{\nu} a_{\nu} \cdot \langle \nu \rangle \mapsto \sum_{\mathfrak{p}} a_{\mathfrak{p}} \cdot \log(\mathcal{N}(\mathfrak{p})) + \sum_{\nu} a_{\nu}. \qquad (10) $$

The kernel of this map is the subgroup $\mathrm{Div}_K^0 = \ker(\mathrm{deg})$ of degree-zero divisors.
*From field elements to divisors.* Denoting $\mathrm{ord}_{\mathfrak{p}}$ for the valuation at the prime $\mathfrak{p}$, there is a canonical homomorphism

$$ (\|\cdot\|) : K^{\times} \to \mathrm{Div}_K $$

$$ \alpha \mapsto (\|\alpha\|) = \sum_{\mathfrak{p}} \mathrm{ord}_{\mathfrak{p}}(\alpha)(\|\mathfrak{p}\|) - \underbrace{\sum_{\nu} n_{\nu} \log |\sigma_{\nu}(\alpha)| \cdot (\|\nu\|)}_{\mathrm{Log}(\alpha)} $$

with $n_{\nu} = 2$ if $\nu$ is complex and 1 otherwise. The product formula states that for any $\alpha \in K^{\times}$, we have $(\|\alpha\|) \in \mathrm{Div}_K^0$, i.e., $(\|K^{\times}\|) \subset \mathrm{Div}_K^0$.

*The exponential maps.* The finite part $\mathbf{a}_f \in \bigoplus_{\mathfrak{p}} \mathbb{Z}$ of a divisor $\mathbf{a}$ naturally corresponds to an ideal in the group $\mathcal{I}_K$ of fractional ideals via the map

$$ \mathrm{Exp}_f : \bigoplus_{\mathfrak{p}} \mathbb{Z} \to \mathcal{I}_K : \sum_{\mathfrak{p}} a_{\mathfrak{p}} \cdot (\|\mathfrak{p}\|) \mapsto \prod_{\mathfrak{p}} \mathfrak{p}^{a_{\mathfrak{p}}}. $$

This map is an isomorphism with inverse

$$ d : \mathcal{I}_K \to \bigoplus_{\mathfrak{p}} \mathbb{Z} : \mathbf{a} \mapsto \sum_{\mathfrak{p}} \mathrm{ord}_{\mathfrak{p}}(\mathbf{a}) \cdot (\|\mathfrak{p}\|). \qquad (11) $$

We will often use a normalized section defined as

$$ d^0 : \mathcal{I}_K \to \mathrm{Div}_K^0 : \mathbf{a} \mapsto \sum_{\mathfrak{p}} \mathrm{ord}_{\mathfrak{p}}(\mathbf{a}) \cdot (\|\mathfrak{p}\|) - \frac{\log(\mathcal{N}(\mathbf{a}))}{n} \sum_{\nu} n_{\nu} (\|\nu\|), \qquad (12) $$

to map into $\mathrm{Div}_K^0$ instead of $\mathrm{Div}_K$.

The infinite part $\mathbf{a}_{\infty} \in \bigoplus_{\nu} \mathbb{R}$ of $\mathbf{a}$ can be mapped into $K_{\mathbb{R}}^{\times}$ via

$$ \mathrm{Exp}_{\infty} : \bigoplus_{\nu} \mathbb{R} \to K_{\mathbb{R}}^{\times} : \sum_{\nu} a_{\nu} \cdot (\|\nu\|) \mapsto (e^{n_{\nu_{\sigma}}^{-1} \cdot a_{\nu_{\sigma}}})_{\sigma} \in K_{\mathbb{R}}^{\times}. $$

The map $\mathrm{Exp}_{\infty}$ is injective, but not surjective. Note that the logarithmic embedding $\mathrm{Log}$ introduced in Section 2.7 is a retraction of $\mathrm{Exp}_{\infty}$ (i.e., $\mathrm{Log} \circ \mathrm{Exp}_{\infty}$ is the identity). Furthermore, for any $x = (x_{\sigma})_{\sigma} \in K_{\mathbb{R}}^{\times}$, we have $\mathrm{Exp}_{\infty}(\mathrm{Log}(x)) = (|x_{\sigma}|)_{\sigma} \in K_{\mathbb{R}}^{\times}$.

The main reason for us to consider divisors is that they encode ideal lattices. This naturally follows by combining the above exponential maps into the following:

$$ \mathrm{Exp} : \mathrm{Div}_K \to \mathrm{IdLat}_K : \mathbf{a} \mapsto \mathrm{Exp}_{\infty}(\mathbf{a}_{\infty}) \cdot \mathrm{Exp}_f(\mathbf{a}_f). $$

For a divisor $\mathbf{a} = \sum_{\mathfrak{p}} a_{\mathfrak{p}} \cdot (\|\mathfrak{p}\|) + \sum_{\nu} a_{\nu} \cdot (\|\nu\|)$, the associated ideal lattice is

$$ \mathrm{Exp}(\mathbf{a}) = (e^{n_{\nu_{\sigma}}^{-1} \cdot a_{\nu_{\sigma}}})_{\sigma} \cdot \prod_{\mathfrak{p}} \mathfrak{p}^{a_{\mathfrak{p}}} = \left\{ (e^{n_{\nu_{\sigma}}^{-1} \cdot a_{\nu_{\sigma}}} \cdot \sigma(\alpha))_{\sigma} \in K_{\mathbb{R}} \mid \alpha \in \prod_{\mathfrak{p}} \mathfrak{p}^{a_{\mathfrak{p}}} \right\} \subseteq K_{\mathbb{R}}. $$

It is a group homomorphism sending the additive operation in $\mathrm{Div}_K$ to the multiplicative operation in $\mathrm{IdLat}_K$. For any divisor $\mathbf{a} \in \mathrm{Div}_K$, we have

$$ \mathrm{Vol}(\mathrm{Exp}(\mathbf{a})) = \sqrt{|\Delta_K|} \cdot \prod_{\nu} e^{a_{\nu}} \cdot \mathcal{N} \left( \prod_{\mathfrak{p}} \mathfrak{p}^{a_{\mathfrak{p}}} \right) = \sqrt{|\Delta_K|} \cdot e^{\mathrm{deg}(\mathbf{a})}. $$
Euclidean norm on $\mathrm{Div}_K$. For $\mathbf{a} \in \mathrm{Div}_K$ written as

$$ \mathbf{a} = \sum_{\mathfrak{p}} a_{\mathfrak{p}} \cdot (\|\mathfrak{p}\|) + \sum_{\nu} a_{\nu} \cdot (\|\nu\|), $$

we define the norm

$$ \|\mathbf{a}\| = \left( \sum_{\mathfrak{p}} a_{\mathfrak{p}}^2 + \sum_{\nu} a_{\nu}^2 \right)^{1/2}, $$

Note that, naturally, $H \subseteq \mathrm{Log}(K_{\mathbb{R}}^{\times}) \hookrightarrow \mathrm{Div}_K$, where the defined Euclidean norms are compatible.

Subgroups of $\mathrm{Div}_K$. Given a set $\mathcal{S}$ of prime ideals of $\mathcal{O}_K$, we define the subgroup

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

In the next two parts of this article, we will work with two important cases. In Part 1, we will consider a modulus $\mathfrak{m} = \mathfrak{m}_0\mathfrak{m}_{\infty}$, and let $\mathcal{S}$ be the set of all prime ideals that do not divide $\mathfrak{m}_0$. The resulting group $\mathrm{Div}_{K^{\mathfrak{m}}} := \bigoplus_{\mathfrak{p} \nmid \mathfrak{m}_0} \mathbb{Z} \times \bigoplus_{\nu} \mathbb{R}$ is called the Arakelov $\mathfrak{m}$-ray divisor group. In Part 2, we will consider cases where the set $\mathcal{S}$ is finite. We then call $\mathrm{Div}_{K, \mathcal{S}}$ the $\mathcal{S}$-divisor group, and it relates to the classical notion of $\mathcal{S}$-units. Further details on each specific case are discussed in the relevant sections.

**2.9. Probabilities and (Discrete) Gaussian distributions.** Given a distribution $D$ over a discrete set $X$ and $x \in X$, we denote $D(x)$ for the probability that $D$ outputs $x$ and $D(A) = \sum_{x \in A} D(x)$ for any $A \subseteq X$.

**Definition 2.15 (Statistical distance).** Let $(\Omega, \mathcal{S})$ be a measurable space with probability measures $P, Q$. The statistical distance (or total variation distance) between $P$ and $Q$ is defined by the rule

$$ SD(P, Q) = \sup_{X \in \mathcal{S}} |P(X) - Q(X)|. $$

For a discrete space $\Omega$, we have

$$ SD(P, Q) = \frac{1}{2} \sum_{x \in \Omega} |P(x) - Q(x)| := \frac{1}{2} \|P - Q\|_1. $$

For a continuous space $\Omega$ with probability densities $P, Q$, we have

$$ SD(P, Q) = \frac{1}{2} \int_{x \in \Omega} |P(x) - Q(x)| =: \frac{1}{2} \|P - Q\|_1. $$

For spaces that are partially discrete and partially continuous, some well-defined mix of an integral and a sum will define the statistical distance. Due to the equivalence of these notions (up to a constant $\frac{1}{2}$) we will often describe closeness of probability distributions in terms of the distance metric $\| \cdot \|_1$, instead of $SD(\cdot, \cdot)$.

The data processing inequality captures the idea that an algorithm (by just processing a single query) cannot increase the statistical distance between two probability distributions. A proof can be found for example in [27, §2.8].
**Theorem 2.16** (Data processing inequality). Let $(\Omega, \mathcal{S})$ be a measurable space with probability measures $P, Q$. Let $f$ be a (potentially probabilistic) function on $\Omega$. Then

$$ \|f(P) - f(Q)\|_1 \le \|P - Q\|_1. $$

In the rest of this section, we recall known results about Gaussian distributions and prove some lemmas that will be useful for the rest of the article.

*Gaussian distributions.* We denote $g_s(x) = \exp(-\pi\|x\|^2/s^2)$ the Gaussian function defined on any Euclidean vector space $V$. Since $\int_{x \in V} g_s(x)dx = s^{\dim V}$, we define the continuous Gaussian distribution on a Euclidean vector space $V$ with parameter $s$ and center $c$ by the density function

$$ \mathcal{G}_{V,s,c}(v) = s^{-\dim(V)} \cdot g_s(v-c). $$

For discrete sets $X \subseteq V$, specifically lattices, we use the same notation for the discrete Gaussian, where the subscript $X$ indicates that the Gaussian is discrete.

$$ \mathcal{G}_{X,s,c}(x) = g_s(x-c)/g_s(X-c), $$

where $g_s(X-c) = \sum_{x \in X} g_s(x-c)$. This notation $f(X) = \sum_{x \in X} f(x)$ for functions $f$ and discrete sets $X$ will be used frequently. Whenever the Gaussian is centered at the origin, i.e., $c = 0$, we will suppress the subscript $c$ from the notation, like this: $\mathcal{G}_{V,s}$.

*Tail bounds of Gaussian distributions.* The following lemma originates from Baszczyk's paper on transference theorems in lattices [6, Lemma 1.5].

**Lemma 2.17** ([6, Lemma 1.5]). For any $c > 1/\sqrt{2\pi}$ and any $n$ dimensional lattice $\Lambda$, $g_1(\Lambda \setminus c\sqrt{n}\mathcal{B}) \le C^n g_1(\Lambda)$, where $\mathcal{B}$ is the euclidean ball of radius 1 and $C = c\sqrt{2\pi e \cdot e^{-\pi c^2}} < 1$.

**Corollary 2.18.** Let $\Lambda$ be a lattice of rank $n$ and $s > 0$. For any $\varepsilon \in (0, 1]$, it holds that $\mathrm{Pr}_{x \leftarrow \mathcal{G}_{\Lambda,s}}(\|x\| \ge s \cdot \sqrt{\log(1/\varepsilon) + 2n}) \le \varepsilon$.

We also have a similar result in the case of a continuous Gaussian distribution.

**Lemma 2.19.** Let $V$ be a real vector space of dimension $n$ and $s > 0$. For any $\varepsilon \in (0, 1]$, it holds that $\mathrm{Pr}_{x \leftarrow \mathcal{G}_{V,s}}(\|x\| \ge s \cdot \sqrt{2n \cdot \log(2n/\varepsilon)}) \le \varepsilon$.

*Proof.* Let $\mathcal{B}$ be an orthonormal basis of $V$ and write $x = (x_1, \dots, x_n)$ the coordinates of $x$ in this basis. Then the random variables $x_i$ are linearly independent Gaussian distributions over $\mathbb{R}$ with standard deviation $s$. Moreover, for any $t > 0$, if $\|x\| \ge t$, there should exist some $i$ such that $|x_i| \ge t/\sqrt{n}$. Hence, we obtain

$$ \mathrm{Pr}_{x \leftarrow \mathcal{G}_{V,s}} (\|x\| \ge t) \le n \cdot \mathrm{Pr}_{x \leftarrow \mathcal{G}_{\mathbb{R},s}} (|x| \ge t/\sqrt{n}) \le 2n \cdot \exp \left( - \frac{t^2}{2n \cdot s^2} \right), $$

where the first inequality comes from the union bound and the last one comes from Chernoff's bound. Taking $t = s \cdot \sqrt{2n \cdot \log(2n/\varepsilon)}$ leads to the desired result. $\square$
Smoothing on lattices. For any $\varepsilon > 0$ and a lattice $\Lambda$ we define the smoothing parameter [54] $\eta_{\varepsilon}(\Lambda)$ to be the smallest $s \in \mathbb{R}_{>0}$ such that $g_{1/s}(\Lambda^{\vee}\setminus\{0\}) \le \varepsilon$, where $\Lambda^{\vee} = \{x \in \text{span}_{\mathbb{R}}(\Lambda) \mid \langle x, \ell \rangle \in \mathbb{Z} \text{ for all } \ell \in \Lambda\}$ is the dual lattice of $\Lambda$. This smoothing parameter satisfies the following bound [54, Lemma 3.3]

$$ \eta_{\varepsilon}(\Lambda) \le \sqrt{\frac{\log(2n(1+1/\varepsilon))}{\pi}} \cdot \lambda_n(\Lambda). \quad (13) $$

We will use the following classical results on the total Gaussian weight of a (shifted) lattice $\Lambda$.

**Lemma 2.20** (Proof of [54, Lemma 4.4]). Let $\Lambda$ be an $n$-dimensional lattice and $s \ge \eta_{\varepsilon}(\Lambda)$ for some $\varepsilon > 0$. We have

$$ g_s(\Lambda) \in [1 - \varepsilon, 1 + \varepsilon] \cdot \frac{s^n}{\text{Vol}(\Lambda)}. $$

**Lemma 2.21** ([54, Lemma 2.9]). Let $\Lambda$ be an $n$-dimensional lattice, $s > 0$ be a positive real number and $c \in \text{span}_{\mathbb{R}}(\Lambda)$ be a vector, then $g_s(\Lambda + c) \le g_s(\Lambda)$.

Approximating and computing discrete Gaussians. We will use the following lemma which says that one can sample from a distribution statistically close to a discrete Gaussian distribution. It is an adaptation of [35, Theorem 4.1] for which the Gaussian can be approximated within any error and in which only bit operations are used (as opposed to real number operations as in the original article).

**Lemma 2.22** (Adapted from [35, Theorem 4.1]). There exists a probabilistic algorithm that takes as input a basis $B = (\mathbf{b}_1, \dots, \mathbf{b}_n) \in \mathbb{Q}^{n \times n}$ of an $n$-dimensional lattice $\Lambda$, an error bound $\varepsilon_G \in (0, 1]$, a parameter $s \ge \sqrt{\frac{\log(1/\varepsilon_G)+2\log(n)+3}{\pi}} \cdot \max_i \|\mathbf{b}_i\|$ and a center $c \in \text{span}_{\mathbb{R}}(\Lambda) \cap \mathbb{Q}^n$ and outputs a sample from a distribution $\hat{G}_{\mathbf{B},\varepsilon_G,s,c}$ such that $\text{SD}(\hat{G}_{\mathbf{B},\varepsilon_G,s,c}, G_{\Lambda,s,c}) \le \varepsilon_G$. This algorithm runs in expected time (bit complexity) polynomial in the size of the input and in $\log(1/\varepsilon_G)$. Additionally, the output of $v \leftarrow \hat{G}_{\mathbf{B},\varepsilon_G,s,c}$ always satisfies $\|v - c\| \le s \cdot \sqrt{n \log(2n^2/\varepsilon_G)}$.

*Proof.* The proof can be adapted from the one of [35, Theorem 4.1], which proves the result for $\varepsilon_G = n^{-\omega(1)}$. In this proof, the statistical distance between the sampled distribution $\hat{G}_{\mathbf{B},\varepsilon_G,s,c}$ and the ideal distribution $G_{\Lambda,s,c}$ comes from two places. The first one is that the algorithm makes $n$ calls to a sub-routine algorithm Sample$_Z$, sampling from a Gaussian distribution over $\mathbb{Z}$ which is only statistically close to $G_{\mathbb{Z},s',c'}$ (for some parameters $c'$ and $s'$ depending on the input). Lemmas 4.2 and 4.3 from [35] show that the statistical distance between Sample$_Z$ and $G_{\mathbb{Z},s',c'}$ can be made as small as any arbitrary $\delta > 0$, to the cost of increasing the running time of Sample$_Z$ in a way that is polynomial in $\log(1/\delta)$. We choose $\delta = \varepsilon_G/(2n)$, which provides a running time polynomial in $\log(1/\varepsilon_G)$ and $\log n$, and ensures that the $n$ calls to Sample$_Z$ are responsible for a change of statistical distance that is at most $\varepsilon_G/2$.

The second reason why the algorithm only provides a distribution that is statistically close to $G_{\Lambda,s,c}$ comes from the fact that $g_{s'}(\mathbb{Z} + c)$ is only approximately close to $g_{s'}(\mathbb{Z})$ for an arbitrary $c \in \mathbb{R}$ (where $s' \ge s/(\max_i \|b_i\|)$). In the proof of Theorem 4.1, the authors of [35] show that, provided that $s \ge \eta_{\delta}(\mathbb{Z}) \cdot \max_i \|b_i\|$, then this statistical distance is at most $\delta'/2$, where $1 + \delta' = (1+\delta)/(1-\delta)^n$. We choose
$\delta = \varepsilon_G/(8n) \le 1/(8n)$. Using the fact that<fnref n="4" /> $(\frac{1+\delta}{1-\delta})^n \le 1 + 8n\delta$ for all $\delta \le 1/(8n)$ and $n \ge 1$, we obtain that the statistical distance between the approximate distribution and the ideal one is at most $4n\delta = \varepsilon_G/2$. Using Equation (13), we see that $\eta_\delta(\mathbb{Z}) \le \sqrt{\frac{\log(1/\varepsilon_G)+2\log(n)+3}{\pi}}$, hence $s \ge \eta_\delta(\mathbb{Z}) \cdot \max_i \|\mathbf{b}_i\|$ as desired.

For the bound on $v \leftarrow \hat{G}_{\mathbf{B},\varepsilon_G,s,c}$ observe the output $\mathbf{v}_0$ of the algorithm in [35, Section 4.2]. By [35, Lemma 4.4], the output of this algorithm satisfies $\mathbf{v}-\mathbf{c} = \sum_{i \in [n]} (\hat{z}_i - c'_i) \cdot \tilde{\mathbf{b}}_i$, where the values $\hat{z}_i$ and $c'_i$ are from the algorithm, and the $\tilde{\mathbf{b}}_i$ are the Gram-Schmidt vectors associated to the $\mathbf{b}_i$'s. Hence, by the Pythagorean theorem, $\|\mathbf{v}-\mathbf{c}\|^2 = \sum_{i \in [n]} |\hat{z}_i - c'_i|^2 \cdot \|\tilde{\mathbf{b}}_i\|^2$. In part 1(b) of the algorithm [35, Section 4.2], $D_{\mathbb{Z},s',c'}$ is implemented as in [35, Section 4.1], i.e., the algorithm SampleZ is called (see the proof of [35, Theorem 4.1]). Therefore $\hat{z}_i$ can be shown to lie in $\mathbb{Z} \cap [c'_i - t(n)s'_i, c'_i + t(n)s'_i]$, where $t(n) = \sqrt{\log(n/\delta)}$ (with $\delta = \varepsilon_G/(2n)$, as before). As a consequence,

$$ \|\mathbf{v} - \mathbf{c}\|^2 = \sum_{i \in [n]} |\hat{z}_i - c'_i|^2 \cdot \|\tilde{\mathbf{b}}_i\|^2 \le \sum_{i \in [n]} t(n)^2 (s'_i)^2 \cdot \|\tilde{\mathbf{b}}_i\|^2 = \sum_{i \in [n]} t(n)^2 s^2 = nt(n)^2 s^2, $$

by the definitions of $s'_i = s/\|\tilde{\mathbf{b}}_i\|$. Hence $\|\mathbf{v}-\mathbf{c}\| \le \sqrt{n \log(n/\delta)}s$ with $\delta = \varepsilon_G/(2n)$, as was required to prove.

We show now that the algorithm in [35] can be readily adapted into one without real number operations, but just bit operations. There are two places in the algorithm in [35, Section 3.2] where real arithmetic is used, namely in the subroutine SampleZ and in the computation of $s/\|\tilde{\mathbf{b}}_k\|$ where $\tilde{\mathbf{b}}_k$ are the Gram-Schmidt vectors. Note that the Gram-Schmidt orthogonalization itself (without normalizing) can be done with rational arithmetic in polynomial time and is thus not altered in this adapted version.

The subroutine SampleZ can be amended to avoid real operations by just approximating the sampling probabilities $\rho_s(x-c)$ with $x \in \mathbb{Z} \cap [c-s \cdot t(n), c+s \cdot t(n)]$ well enough. This can be done within polynomial bit complexity in the size of the input, and, by maybe slightly increasing $t(n)$, without loss in the approximation error $\delta$.

The value of $s/\|\tilde{\mathbf{b}}_k\|$ is only used in the subroutine SampleZ, where actually its square is used to compute $\rho_{s/\|\tilde{\mathbf{b}}_k\|}(x-c)$ and hence there is no need to compute $s/\|\tilde{\mathbf{b}}_k\|$ but rather its square $s^2/\|\tilde{\mathbf{b}}_k\|^2$ which consists of rational numbers.

Hence we can conclude that this slight adaptation of [35, Section 3] has polynomial bit-complexity in the size of its input. $\square$

### 3. ACKNOWLEDGEMENTS

First and foremost, we would like to express our gratitude to Léo Ducas, who took part in early discussions that lead to this project, and suggested key ideas for the randomisation of ideals.

We thank Aurel Page and Wessel van Woerden for insightful discussions. We thank Sameera Vemulapalli for bringing to our attention the bound on $\lambda_n(\mathcal{O}_K)$ of Bhargava et al. [8].

<footnote n="4">⁴We have $\frac{1+\delta}{1-\delta} \le 1+4\delta$ for $\delta \le 1/2$. Also, $(1+x)^n \le (e^x)^n = e^{nx} \le 1+2nx$ for $x < 1/(2n)$. Hence, for $\delta \le 1/(8n)$ and $n \in \mathbb{N}_{>0}$, $(\frac{1+\delta}{1-\delta})^n \le (1+4\delta)^n \le 1+8n\delta$.</footnote>
Alice Pellet-Mary and Benjamin Wesolowski were supported by the Agence Na-
tionale de la Recherche under grants ANR-22-PETQ-0008 (PQ-TLS) and ANR-
21-CE94-0003 (CHARM). Benjamin Wesolowski was supported by the European
Research Council under grant No. 101116169 (AGATHA CRYPTY). This work
started when the authors were visiting the Simon Institute during the lattice se-
mester in 2020.
# PART 1

## Sampling ideals in a class: smooth, near-prime or otherwise

### 4. INTRODUCTION

In this first part of the article, we propose a general strategy to provably solve a recurring computational problem in number theory (assuming the extended Riemann hypothesis, ERH): given an ideal class $[a]$ of a number field $K$, sample an ideal $c \in [a]$ belonging to a particular family of ideals (e.g., the family of smooth ideals, or near-prime ideals). While there is a simple heuristic algorithm for this task, it has proved notoriously difficult to resolve it rigorously. It has thereby been a central roadblock explaining the heuristic nature of many major algorithms in computational number theory.

The main result of this part is Theorem 9.5 (page 47). Its formulation in full generality is postponed, as it first requires the introduction of several notions. However, a simplified statement, which may already suit many needs, is available in Theorem 1.1 (page 3).

**Roadmap.** Fix an arbitrary family of ideals $\mathcal{S}$. For convenience, we consider the input to be an ideal $b \in [a]^{-1}$, and are looking for an ideal $c \in \mathcal{S}$ in the inverse class of $b$. The folklore strategy consists in considering $b$ as an *ideal lattice* via the Minkowski embedding, and sampling random elements $\beta \in b$ (within some bounds, say in a “box” $r\mathcal{B}$ of radius $r$) until $c = \beta b^{-1}$ falls in the desired family of ideals $\mathcal{S}$. Heuristically, one *expects* that for $\beta$ “sufficiently random”, the ideal $\beta b^{-1}$ falls in $\mathcal{S}$ with probability proportional to the “density” of the family (think about the set of prime ideals that have norm around $x$ having “density” $\approx 1/(\rho_K \log(x))$). This, of course, cannot be literally true for arbitrary families (e.g., principal ideals), since $\beta b^{-1}$ is confined to one ideal class. Instead, we will solve the problem for $c \in \mathcal{S} \cdot \mathcal{S}_B$, where $\mathcal{S}_B$ is the family of $B$-smooth ideals for some bound $B$. In all applications we are aware of, $\mathcal{S} = \mathcal{S} \cdot \mathcal{S}_B$ (smooth ideals, near-prime ideals).

*The Arakelov class group.* The notion of *ideal lattice* plays a key role in this sampling strategy. The space of ideal lattices up to isomorphism is naturally isomorphic to the so-called *Arakelov class groups* We open this part of the article in Section 5 with an introduction to Arakelov ray class groups. They can be thought of as a “combination” of the ray class group and the ray unit group of a number field. In Section 6, we state a useful result on these Arakelov ray class groups: certain *random walks* in them rapidly converge to the uniform distribution. This is a generalization of [14] from Arakelov class groups to Arakelov *ray class groups*.

*Average densities.* In the folklore strategy, one is hoping that for (uniformly) random $\beta \in b \cap r\mathcal{B}$ (the intersection of an ideal lattice and a “box”), the probability that
$\beta b^{-1} \in \mathcal{S}$ is proportional to the density of $\mathcal{S}$. This is generally not true. However, in Section 7, we prove that it is true on average when the ideal lattice $b$ is also random, uniformly distributed in the Arakelov ray class group. This might sound too weak for our goal: the input $b$ of the algorithm is not random. It will actually be sufficient when properly combined with a randomization step.

*Ideal sampling.* We then turn these density results into an algorithm. First, we show in Section 8 how to sample uniformly a random element in a set of the form $b \cap r\mathcal{B}$, the intersection of an ideal lattice and a “box”.

Then, Section 9 culminates with the main algorithm, Algorithm 2. It addresses the final obstacle: the density result of Section 7 only holds on average, for uniformly random ideal lattices. The input $b$ is not random, so we need to randomize it. This is where random walks in the Arakelov class group come in. Essentially, Algorithm 2 starts by multiplying $b$ with a few “small” prime ideals, resulting in a random ideal $wb$ where $w$ is smooth (i.e., $w \in S_B$ for some bound $B$).

Algorithm 2 then samples a uniformly random $\beta \in (wb) \cap r\mathcal{B}$. Then:

* From Section 6 and [14] (on the rapid equidistribution of random walks), the random ideal lattice $wb$ is close to uniformly distributed.

* From Section 7, we obtain that $\beta(wb)^{-1} \in \mathcal{S}$ with probability proportional to the density of $\mathcal{S}$.

Upon the event $\beta(wb)^{-1} \in \mathcal{S}$, we get $\beta b^{-1} = w \cdot (\beta(wb)^{-1}) \in S_B \cdot S$, as desired.

*Further properties.* Finally, in Section 10 and Section 11, we develop tools to ease the applicability of this “ideal sampling” algorithm. These tools are indispensable for the application presented in Part 2, and may be useful in other contexts. More precisely, in Section 10, three important properties of the ideal sampling algorithm are stated and proved: the *shifting property*, *boundedness* and *almost-Lipschitz-continuity*. In Section 11, we estimate quantities related to the modulus $m$, which affect the behavior of the ideal sampling algorithm.

## 5. BACKGROUND ON THE ARAKELOV CLASS GROUP

Recall that throughout this paper, we consider a number field $K$ of rank $n$ over $\mathbb{Q}$, having ring of integers $\mathcal{O}_K$, discriminant $\Delta_K$, regulator $R_K$, class number $h_K$ and group of roots of unity $\mu_K$. It has $n_{\mathbb{R}}$ real embeddings and $n_{\mathbb{C}}$ conjugate pairs of complex embeddings, with $n = n_{\mathbb{R}} + 2n_{\mathbb{C}}$.

**5.1. The Arakelov Ray Class Group.** In this section, we rely heavily on the notation introduced in Section 2.8 for the divisor group $\text{Div}_K$. The Arakelov ray divisor group with respect to a modulus $m = m_0 m_\infty$ is a subgroup $\text{Div}_K^m \subseteq \text{Div}_K$ defined as

$$ \text{Div}_K^m = \bigoplus_{p \nmid m_0} \mathbb{Z} \times \bigoplus_{\nu} \mathbb{R} $$

where $p$ ranges over the set of all prime ideals of $\mathcal{O}_K$ that do not divide the finite part $m_0$ of the modulus, and $\nu$ over the set of all infinite places (embeddings into the complex numbers up to conjugation). The case $m = \mathcal{O}_K$ yields the standard
divisor group Div$_K$. Recall that we write an arbitrary element in Div$_K^m$ as

$$
\mathbf{a} = \underbrace{\sum_{\mathfrak{p} \nmid m_0} a_{\mathfrak{p}} \cdot (\mathfrak{p})}_{\mathbf{a}_f} + \underbrace{\sum_{\nu} a_{\nu} \cdot (\nu)}_{\mathbf{a}_{\infty}}. \qquad (14)
$$

with only finitely many non-zero $a_p$ and with $a_\nu \in \mathbb{R}$. The map $\langle \cdot | \cdot \rangle : K^\times \to \mathrm{Div}_K$
naturally restricts and co-restricts to

$$
\langle \cdot | \cdot \rangle : K^m \to \mathrm{Div}_{K^m}
$$

$$
\alpha \mapsto \langle \alpha | \cdot \rangle = \sum_{\mathfrak{p} \nmid m_0} \mathrm{ord}_{\mathfrak{p}}(\alpha)(\mathfrak{p}) - \sum_{\nu} n_{\nu} \log |\sigma_{\nu}(\alpha)| \cdot \langle \nu | \cdot \rangle,
$$

where $n_\nu = 2$ whenever $\nu$ is a complex place and 1 otherwise. The divisors of the
form $\langle\alpha|\rangle$ for $\alpha \in K^{m,1}$ are called *principal m-ray divisors*.

Just as the ideal ray class group is the group of ideals coprime with $\mathfrak{m}$ quo-
tiented by the ray $K^{m,1}$, the *Picard ray group* is the group of Arakelov ray divi-
sors quotiented by the group of principal ray Arakelov divisors. In other words,
the Picard ray group $\mathrm{Pic}_K^\mathfrak{m}$ is defined by the following exact sequence, where
$\mu_{K^{\mathfrak{m},1}} = \mu_K \cap K^{\mathfrak{m},1}$ are the roots of unity in the ray:

$$
0 \to \mu_{K^{\mathfrak{m},1}} \to K^{\mathfrak{m},1} \xrightarrow{\langle \cdot | \cdot \rangle} \mathrm{Div}_{K^{\mathfrak{m}}} \to \mathrm{Pic}_{K^{\mathfrak{m}}} \to 0.
$$

For any Arakelov ray divisor **a** = $\sum_{\mathfrak{p} \nmid m_0} a_{\mathfrak{p}} \cdot (\mathfrak{p}) + \sum_{\nu} a_{\nu} \cdot (\nu)$, we denote its class
in the Picard ray group $\mathrm{Pic}_{K^{\mathfrak{m}}}$ by $[\mathbf{a}]$, in the same fashion that $[\mathbf{a}]$ denotes the ideal
class of the ideal **a** in $\mathrm{Cl}_{K}^{\mathfrak{m}}$.

Since principal ray divisors $\langle\alpha|\rangle$ for $\alpha \in K^{m,1}$ are in the kernel of the degree map, the degree factors through $\mathrm{Pic}_K^\mathfrak{m}$. We can therefore define the *degree-zero Arakelov ray divisor group* $\mathrm{Div}_{K^\mathfrak{m}}^0 = \{\mathbf{a} \in \mathrm{Div}_{K^\mathfrak{m}} | \mathrm{deg}(\mathbf{a}) = 0\}$ and the *Arakelov ray class group* $\mathrm{Pic}_{K^\mathfrak{m}}^0 = \{[\mathbf{a}] \in \mathrm{Pic}_{K^\mathfrak{m}} | \mathrm{deg}([\mathbf{a}]) = 0\}$.

The maps $\mathrm{Exp}_f$, $\mathrm{Exp}_\infty$, $d$ and $d^0$ defined in Section 2.8 naturally restrict and co-
restrict to

$$
\mathrm{Exp}_f : \bigoplus_{\mathfrak{p} \nmid m_0} \mathbb{Z} \to \mathcal{I}_K^m : \mathbf{a} \mapsto \prod_{\mathfrak{p} \nmid m_0} \mathfrak{p}^{a_{\mathfrak{p}}}, \qquad (15)
$$

$$
\mathrm{Exp}_{\infty} : \bigoplus_{\nu} \mathbb{R} \to K_{\mathbb{R}}^{\times} : \mathbf{a} \mapsto \left( e^{n_{\nu}^{-1} \cdot a_{\nu\sigma}} \right)_{\sigma}, \qquad (16)
$$

$$
d : \mathcal{I}_K^m \to \bigoplus_{\mathfrak{p} \nmid m_0} \mathbb{Z} : \mathbf{a} \mapsto \sum_{\mathfrak{p} \nmid m_0} \mathrm{ord}_{\mathfrak{p}}(\mathbf{a}) \cdot (\mathfrak{p}) , \qquad (17)
$$

$$
d^0 : \mathcal{I}_K^m \to \mathrm{Div}_{K^m}^0 : \mathbf{a} \mapsto d(\mathbf{a}) - \frac{n_\nu \log(\mathcal{N}(\mathbf{a}))}{n} \sum_\nu \langle \nu | \cdot \rangle. \quad (18)
$$

The groups and their relations treated above fit nicely in the diagram of exact
sequences given in Figure 1, where the middle row sequence splits with the section
d⁰. In this diagram we use the notation O×K,m,₁ = O×K∩Km,₁ and μK,m,₁ = μK∩Km,₁.
The group Tm = H/ Log(O×K,m,₁) is the logarithmic ray unit torus, with Log(O×K,m,₁)
the logarithmic ray unit lattice.

Relations between different ray groups. The (ray) unit groups $\mathcal{O}_K^\times$, $\mathcal{O}_{K^{m,1}}^\times$, the (ray)
class groups $\mathrm{Cl}_K$, $\mathrm{Cl}_K^m$, and the ray groups $K^{m,1}$ and $K^\mathfrak{m}$ are tightly related by an
<figure><img src="image_2.png" /><figcaption>FIGURE 1. A commutative diagram of short exact sequences involving the Arakelov ray class group.</figcaption></figure>

exact sequence (e.g., [48, Chapter VI, §1]), relating the (relative) cardinalities of these groups. Namely,

$$|\mathcal{O}_K^\times/\mathcal{O}_{K^{m,1}}^\times| \cdot |\mathrm{Cl}_K^m| = \phi(\mathfrak{m}_0) \cdot 2^{|\mathfrak{m}_\mathbb{R}|} \cdot |\mathrm{Cl}_K|, \quad (19)$$

where $\phi(\mathfrak{m}_0) = |K^{m_0}/K^{m_0,1}|$ and $|\mathfrak{m}_\mathbb{R}|$ is the number of real places dividing $\mathfrak{m}_\infty$, (note that $|K^m/K^{m,1}| = \phi(\mathfrak{m}_0) \cdot 2^{|\mathfrak{m}_\mathbb{R}|}$). Also, by observing the kernel-cokernel sequence of the inclusions $\mathcal{O}_{K^{m,1}}^\times \subseteq \mathcal{O}_K^\times \subseteq H = \log K_\mathbb{R}^0$, we obtain,

$$|\mu_{K^{m,1}}| \cdot |\mathcal{O}_K^\times/\mathcal{O}_{K^{m,1}}^\times| = |\mu_K| \cdot \mathrm{Vol}(T^m)/\mathrm{Vol}(T). \quad (20)$$

Geometric properties of the divisor group and the Arakelov class group. Recall that the norm of a divisor is defined as

$$\|\mathbf{a}\| = \left( \sum_{\mathfrak{p}} a_{\mathfrak{p}}^2 + \sum_{\nu} a_{\nu}^2 \right)^{1/2}.$$

In the following lemma, we show that the volume of the Arakelov ray class group roughly follows the square root of the absolute value of the field discriminant times $\phi(\mathfrak{m}_0) \cdot 2^{|\mathfrak{m}_\mathbb{R}|}$; with a possible additional correction factor due to the roots of unity.

**Lemma 5.1 (Volume of Pic$_K^0$).** For $n = [K : \mathbb{Q}] > 1$, we have

$$\mathrm{Vol}(\mathrm{Pic}_{K^m}^0) = |\mathrm{Cl}_K^m| \cdot \mathrm{Vol}(T^m) = \frac{|\mu_{K^{m,1}}|}{|\mu_K|} \cdot \phi(\mathfrak{m}_0) \cdot 2^{|\mathfrak{m}_\mathbb{R}|} \cdot h_K \cdot \mathrm{Vol}(T) \quad (21)$$

$$= \frac{|\mu_{K^{m,1}}|}{|\mu_K|} \cdot \phi(\mathfrak{m}_0) \cdot h_K \cdot R_K \cdot \sqrt{\mathfrak{r} + 1} \cdot 2^{|\mathfrak{m}_\mathbb{R}|}, \quad (22)$$

where $\phi(\mathfrak{m}_0) = |K^{m_0}/K^{m_0,1}|$ and $|\mathfrak{m}_\mathbb{R}|$ is the number of real places dividing $\mathfrak{m}_\infty$. Additionally,

$$\log (\mathrm{Vol}(\mathrm{Pic}_{K^m}^0)) \le \log (\mathcal{N}(\mathfrak{m}_0) \cdot 2^{|\mathfrak{m}_\mathbb{R}|}) + \log |\Delta_K|. \quad (23)$$

*Proof.* The first identity involving the volume of the Arakelov ray class group follows from the exact sequence in Figure 1. The second one can be deduced from Equations (19) and (20). The third one follows from the volume computation of $T$ in Equation (9).
The bound on the logarithm is obtained by using $\frac{|\mu_K^{m,1}|}{|\mu_K|} \le 1$, applying the class number formula [57, VII.5, Cor 5.11] and Louboutin's bound [52] on the residue $\rho_K$ of the Dedekind zeta function at $s = 1$:

$$ 
\begin{aligned}
|\mathrm{Pic}_{K^m}^0| &\le \phi(\mathfrak{m}_0) \cdot h_K \cdot R_K \cdot \sqrt{\mathfrak{r}+1} \cdot 2^{|\mathfrak{m}_\mathfrak{R}|} = \frac{\phi(\mathfrak{m}_0) \cdot \rho_K \cdot \sqrt{|\Delta_K|} \cdot |\mu_K| \cdot \sqrt{n_\mathbb{R}+n_\mathbb{C}}}{2^{n_\mathbb{R}-|\mathfrak{m}_\mathfrak{R}|} \cdot (2\pi)^{n_\mathbb{C}}} \\
&\le \phi(\mathfrak{m}_0) \cdot 2^{|\mathfrak{m}_\mathfrak{R}|} \cdot \sqrt{|\Delta_K|} \cdot \rho_K \le \phi(\mathfrak{m}_0) \cdot 2^{|\mathfrak{m}_\mathfrak{R}|} \cdot \sqrt{|\Delta_K|} \cdot \left(\frac{e \log |\Delta_K|}{2(n-1)}\right)^{n-1} \\
&\le \phi(\mathfrak{m}_0) \cdot 2^{|\mathfrak{m}_\mathfrak{R}|} \cdot |\Delta_K|.
\end{aligned}
$$

The first inequality follows from $\frac{|\mu_K|\sqrt{n_\mathbb{R}+n_\mathbb{C}}}{2^{n_\mathbb{R}}(2\pi)^{n_\mathbb{C}}} \le \frac{n^{3/2}}{2^n} \le 1$. The last inequality follows from the fact that $\frac{e \log |x|}{|x|} \le 1$ for all $x \in \mathbb{R}$. This inequality instantiated with $x = |\Delta_K|^{\frac{1}{2(n-1)}}$ then yields $\left(\frac{e \log |\Delta_K|}{2(n-1)}\right)^{n-1} \le \sqrt{|\Delta_K|}$. $\square$

**5.2. Divisors and ideal lattices.** The Exp map introduced in Section 2.8 restricts to the group homomorphism

$$ \mathrm{Exp} : \mathrm{Div}_{K^m} \to \mathrm{IdLat}_K : \mathbf{a} \mapsto \mathrm{Exp}_\infty(\mathbf{a}_\infty) \cdot \mathrm{Exp}_f(\mathbf{a}_f), $$

sending each Arakelov divisor to an ideal lattice. Recall that for any divisor $\mathbf{a} \in \mathrm{Div}_{K^m}$, we have $\mathrm{Vol}(\mathrm{Exp}(\mathbf{a})) = \sqrt{|\Delta_K|} \cdot e^{\mathrm{deg}(\mathbf{a})}.$

**5.3. τ-equivalent elements and generators of an Arakelov ray divisor.** Suppose that $\mathfrak{m}$ is a modulus, and let $\mathfrak{a}$ be any ideal coprime to $\mathfrak{m}_0$. An element $\alpha \in \mathfrak{a}$ is said to be $\tau$-equivalent (with respect to $\mathfrak{m}$) if $\alpha \equiv \tau \mod \mathfrak{m}_0$ and $\sigma_\nu(\alpha)/\sigma_\nu(\tau) \in \mathbb{R}_{>0}$ for all real $\nu | \mathfrak{m}_\infty$. If additionally, $\mathfrak{a}$ is principal, any $\tau$-equivalent element $\alpha$ such that $\mathfrak{a} = (\alpha)$ is called a $\tau$-equivalent generator of $\mathfrak{a}$.

These notions generalize to Arakelov ray divisors. As we can see Arakelov ray divisors as ideal lattices $x\mathfrak{a}$, an element of such a divisor is just an element of the shape $x\alpha$ where $\alpha \in \mathfrak{a}$ and $x \in K_\mathbb{R}$. Similarly, a generator of such divisor is an element in $K_\mathbb{R}^\times$ of the shape $x\alpha$, where $\alpha$ is a generator of $\mathfrak{a}$. The precise definitions are as follows.

**Definition 5.2** ($\tau$-equivalent elements of an Arakelov ray divisor). Let $\tau \in K^m$ and let $\mathbf{a} \in \mathrm{Div}_{K^m}$ be an Arakelov ray divisor with an infinite part $\mathbf{a}_\infty$ and a finite part $\mathbf{a}_f$ (see Equation (14)). We define the set of $\tau$-equivalent elements $\mathrm{Exp}(\mathbf{a})_\tau \subseteq K_\mathbb{R}$ of $\mathbf{a}$ by the following rule

$$ \mathrm{Exp}(\mathbf{a})_\tau := \mathrm{Exp}_\infty(\mathbf{a}_\infty) \cdot (\mathrm{Exp}_f(\mathbf{a}_f) \cap \tau K^{m,1}) $$

Equivalently, we can write

$$ \mathrm{Exp}(\mathbf{a})_\tau = \{\alpha \in \mathrm{Exp}(\mathbf{a}) \mid \mathrm{Exp}_\infty(-\mathbf{a}_\infty) \cdot \alpha \in \tau K^{m,1}\}. $$

**Definition 5.3** ($\tau$-equivalent generators of an Arakelov ray divisor). Let $\tau \in K^m$ and let $\mathbf{a} \in \mathrm{Div}_{K^m}$ be an Arakelov ray divisor with an infinite part $\mathbf{a}_\infty$ and a finite part $\mathbf{a}_f$ (see Equation (14)). We define the set of $\tau$-equivalent generators $\mathrm{Exp}(\mathbf{a})_\tau^\times \subseteq K_\mathbb{R}$ of $\mathbf{a}$ by the following rule

$$ \mathrm{Exp}(\mathbf{a})_\tau^\times := \begin{cases} \mathrm{Exp}_\infty(\mathbf{a}_\infty) \cdot (\kappa \cdot \mathcal{O}_K^\times \cap \tau K^{m,1}) \subseteq \mathrm{Exp}(\mathbf{a}) & \text{if } \mathrm{Exp}_f(\mathbf{a}_f) = (\kappa) \\ \emptyset & \text{for some } \kappa \in K^m \\ \emptyset & \text{otherwise} \end{cases} $$
Equivalently, we can write

$$ \mathrm{Exp}(\mathbf{a})_{\tau}^{\times} = \{\alpha \in \mathrm{Exp}(\mathbf{a}) \mid \mathrm{Exp}_{\infty}(-\mathbf{a}_{\infty}) \cdot \alpha \in \tau K^{\mathfrak{m},1} \text{ is a generator of } \mathrm{Exp}_{\mathfrak{f}}(\mathbf{a}_{\mathfrak{f}})\}. $$

**5.4. Uniform sampling of prime ideals in a certain Arakelov class.** In the main result of this part, we will need to sample primes $\mathfrak{p}$ that satisfy $[d^0(\mathfrak{p})] \in G$ for a certain finite-index subgroup of $\mathrm{Pic}_{K^m}^0$. The procedure explaining this and the respective running time can be found in this lemma; the proof is provided in Appendix A.2.

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

There exists a bound

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

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

## 6. RANDOM WALKS IN ARAKELOV RAY CLASS GROUPS

In this section, we present a theorem on the rapid mixing of random walks on finite-index subgroups of Arakelov ray class groups. It is a generalization of the main theorem of [14], from Arakelov class groups to finite-index subgroups $G$ of Arakelov ray class groups. Starting with a point in the hyperplane $H \hookrightarrow \mathrm{Div}_{K^m}^0$, sampled according to a Gaussian distribution, we prove that multiplying this point sufficiently often by small random prime ideals whose Arakelov classes are in $G \subseteq \mathrm{Pic}_{K^m}^0$ yields a random ray divisor that is very close to uniformly distributed in $G$, (the concerning subgroup of the Arakelov ray class group).

**Definition 6.1 (Random Walk Distribution in $\mathrm{Div}_{K^m}^0$).** For a number field $K$ and a finite-index subgroup $G \subseteq \mathrm{Pic}_{K^m}^0$, we denote by $W_G(B, N, s) \in L_1(\mathrm{Div}_{K^m}^0)$ the distribution on $\mathrm{Div}_{K^m}^0$ that is obtained by the following random walk procedure.

Sample $a = (a_\nu)_\nu \in H \subseteq \mathrm{Div}_{K^m}^0$ according to a centered Gaussian distribution with standard deviation $s > 0$ (see Section 2.9). Subsequently, sample $N$ ideals $\mathfrak{p}_j$ uniformly from the set of all prime ideals coprime with $\mathfrak{m}_0$, with norm bounded by $B$ and whose Arakelov class $[d^0(\mathfrak{p}_j)]$ lies in $G$. Finally, output $a + \sum_{j=1}^N d^0(\mathfrak{p}_j)$, where $a \in \mathrm{Div}_{K^m}^0$ is understood via the inclusion $H \subseteq \mathrm{Div}_{K^m}^0$.

**Definition 6.2.** For any distribution $\mathcal{D}$ on $\mathrm{Div}_{K^m}^0$, we define the distribution $[\mathcal{D}]$ on $\mathrm{Pic}_{K^m}^0$ by the following rule:

$$ [\mathcal{D}](\cdot) = \sum_{\kappa \in K^{\mathfrak{m},1}/\mu_{K^{\mathfrak{m},1}}} \mathcal{D}(\cdot + (\kappa)). $$

This distribution $[\mathcal{D}]$ on $\mathrm{Pic}_{K^m}^0$ arises whenever one samples $\mathbf{a} \leftarrow \mathcal{D}$ and subsequently takes the Arakelov ray class $[\mathbf{a}] \in \mathrm{Pic}_{K^m}^0$.

**Definition 6.3 (Random Walk Distribution in $\mathrm{Pic}_{K^m}^0$).** We denote by $[W_G(B, N, s)]$ the distribution on the Arakelov class group obtained by sampling $\mathbf{a}$ from $W_G(B, N, s)$ and taking the Arakelov ray class $[\mathbf{a}] \in \mathrm{Pic}_{K^m}^0$ (as in Definition 6.2).
**Theorem 6.4** (Random Walks in finite-index subgroups of the Arakelov Ray Class Group, ERH). Let $\varepsilon > 0$ and $s > 0$ be any positive real numbers and let $k \in \mathbb{R}_{>0}$ be a positive real number as well. Let $G \subseteq \text{Pic}_{K^m}^0$ be a finite-index subgroup of the Arakelov ray class group. Putting $^5\tilde{s} = \min(\sqrt{2} \cdot s, 1/\eta_1(\text{Log}(\mathcal{O}_{K^{m,1}}^{\times})^\vee))$, there exists a bound

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

such that for any integer

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

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

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

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

*Proof.* The proof is very similar to that of [14], adapted to account for the ray and the finite-index subgroup. Details can be found in Appendix A.1. □

The following instantiation of the random walk theorem gives the appropriate parameters for the main application of this paper, the sampling algorithm (see Algorithm 2 and Theorem 9.5)

**Corollary 6.5 (ERH).** Let $n = [K : \mathbb{Q}] \ge 2$, $s = 1/n^2$, let $G \subseteq \text{Pic}_{K^m}^0$ be a finite-index subgroup and let $\varepsilon > 0$ be an error parameter. There exists a bound
$$B = \tilde{O}([\text{Pic}_{K^m}^0 : G]^2 \cdot n^2 \cdot [n^2(\log \log(1/\varepsilon))^2 + (\log(|\Delta_K|\mathcal{N}(\mathfrak{m})))^2]) \text{ such that for}$$
$$N = [7n + 2 \log(1/\varepsilon) + \log|\text{Pic}_{K^m}^0| - \log[\text{Pic}_{K^m}^0 : G] + 2] \text{ the random walk distribution}$$
$$[\mathcal{W}(B, N, s)] \text{ on } \text{Pic}_{K^m}^0 \text{ is } \varepsilon\text{-close to uniform in } L_1(G), \text{ i.e.},$$

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

*Proof.* This formulation of the random walk theorem is obtained by instantiating Theorem 6.4 with $s = 1/n^2$ and $k = 1$. To obtain the bounds on $B$ and $N$, we use the inequality $1/\tilde{s} = \max(n^2/\sqrt{2}, \eta_1(\text{Log}(\mathcal{O}_{K^{m,1}}^{\times})^\vee)) \le 2800 \cdot n^2$, which we will verify at the end of this proof.

One then gets the bound on $B$ by applying Theorem 6.4 and simply moving the $n^2(\log(1/\tilde{s}))^2$ into the polylogarithmic factors. For the lower bound on $N$, note that $\frac{1}{2\log(2)} \le 1$ and $^6\mathfrak{r} \cdot \log(1/\tilde{s})/(2\log n) \le 7n$. Hence, a sufficient lower bound on $N$ is the one in Theorem 6.4 with $\frac{1}{2k \log n}$ removed and $\mathfrak{r} \cdot \log(1/\tilde{s})$ replaced by $7n$.

As promised, we finish the proof by showing $1/\tilde{s} \le 2800 \cdot n^2$. As $\text{Log}(\mathcal{O}_{K^{m,1}}^{\times}) \subseteq \text{Log}(\mathcal{O}_K^{\times})$, we have $\text{Log}(\mathcal{O}_{K^{m,1}}^{\times})^\vee \supseteq \text{Log}(\mathcal{O}_K^{\times})^\vee$. Therefore, the smoothing parameter

<footnote>$^5$Recall that for any lattice $\Lambda$, we write $\Lambda^\vee$ for its dual, and $\eta_1(\Lambda)$ for its smoothing parameter (see page 18).</footnote>

<footnote>$^6$Using the bound $1/\tilde{s} \le 2800 \cdot n^2$, we have $\frac{\mathfrak{r} \cdot \log(1/\tilde{s})}{2 \log n} \le \frac{\mathfrak{r} \cdot \log(2800 \cdot n^2)}{2 \log n} = \frac{\mathfrak{r} \cdot [\log(2800) + 2 \log n]}{2 \log n} \le \mathfrak{r} \cdot (\frac{\log(2800)}{2 \log n} + 1) \le (\frac{\log(2800)}{2 \log 2} + 1)n \le 7n$.</footnote>
of $\mathrm{Log}(\mathcal{O}_{K^{m,1}}^{\times})^{\vee}$ satisfies

$$ \eta_1(\mathrm{Log}(\mathcal{O}_{K^{m,1}}^{\times})^{\vee}) \le \eta_1(\mathrm{Log}(\mathcal{O}_K^{\times})^{\vee}) \le \frac{\sqrt{\mathfrak{r}}}{\lambda_1(\mathrm{Log}(\mathcal{O}_K^{\times}))} \le 1000 \cdot n \cdot \log(n)^3 \le 2800 \cdot n^2. $$

Here, the first inequality follows from the fact that $\eta_1(\Lambda) \le \eta_1(\Lambda')$ if $\Lambda \supseteq \Lambda'$. The second inequality holds for general lattices [54, Lemma 3.2], the third inequality holds by the fact that $1/\lambda_1(\mathrm{Log}(\mathcal{O}_K^{\times})) \le 1000 \cdot \sqrt{n} \cdot \log(n)^3$ (see Lemma 2.14) and $r \le n$, and the last inequality by $x \log(x)^3 \le 1.4 \cdot x^2$ for all $x > 0$. $\square$

## 7. AVERAGE DENSITIES AND SAMPLING

7.1. **Result.** Let $S \subseteq \mathcal{I}_K$ be a set of integral ideals, and assume that $\mathbf{a}$ is an Arakelov ray divisor whose class is uniformly distributed. In this section, we show that one can sample elements $\beta$ such that $\beta \mathbf{a}^{-1}$ corresponds to an ideal of the family $S$ with the probability one would naturally expect, i.e., proportional to the density of $S$. This is made precise in Theorem 7.1 via the notion of local density. Recall that the local density of a set of ideals $S$ is defined (Definition 2.11) as

$$ \delta_S[x] = \min_{t \in [x/e^n, x]} \frac{|S(t)|}{\rho_K \cdot t} = \min_{t \in [x/e^n, x]} \frac{|\{\mathfrak{b} \in 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)).

Recall that for $r \in \mathbb{R}_{>0}$, the box of radius $r$ in $K_{\mathbb{R}}$ is $r\mathcal{B}_{\infty} = \{(x_{\sigma})_{\sigma} \in K_{\mathbb{R}} \mid |x_{\sigma}| \le r\}$.

**Theorem 7.1.** Let $G \subseteq \mathrm{Pic}^0_{K^m}$ be a finite-index subgroup of the Arakelov ray class group, and let $[\mathfrak{b}] \in \mathrm{Pic}^0_{K^m}$ arbitrary, and let $\mathcal{D}$ be a distribution on $\mathrm{Div}^0_{K^m}$ such that $[\mathcal{D}]$ is uniform on the coset $G + [\mathfrak{b}]$. Let $r \ge 8 \cdot n^2 \cdot \Gamma_K \cdot |\Delta_K|^{1/2n} \cdot \mathcal{N}(\mathbf{m})^{1/n}$, where $\Gamma_K \le \lambda_n^{\infty}(\mathcal{O}_K) \le |\Delta_K|^{1/n}$ is defined in Equation (6), let $\tau \in K^m$ and let $S$ be a set of integral ideals coprime to $\mathbf{m}_0$ for which holds $[d^0(S)] \subseteq G + [[\tau]] - [\mathfrak{b}]$, with local density $\delta_S[r^n]$ at $r^n$. Then

$$ \mathbb{E}_{\mathbf{a} \leftarrow \mathcal{D}} \left[ \mathrm{Pr}_{\alpha \leftarrow \mathrm{Exp}(\mathbf{a}) \cap r\mathcal{B}_{\infty}} \left[ (\alpha) \cdot \mathrm{Exp}(-\mathbf{a}) \in S \mid \alpha \cdot \mathrm{Exp}_{\infty}(-\mathbf{a}_{\infty}) \in \tau K^{m,1} \right] \right] \quad (25) $$

$$ \geq \frac{\mathcal{N}(\mathbf{m}_0)}{\phi(\mathbf{m}_0)} \cdot \frac{[\mathrm{Pic}_{K^m}^0 : G]}{3} \cdot \delta_S[r^n] \quad (26) $$

$$ \geq \frac{[\mathrm{Pic}_{K^m}^0 : G]}{3} \cdot \delta_S[r^n] \quad (27) $$

where $\alpha \leftarrow \mathrm{Exp}(\mathbf{a}) \cap r\mathcal{B}_{\infty}$ is uniformly sampled from the finite set $\mathrm{Exp}(\mathbf{a}) \cap r\mathcal{B}_{\infty}$ and $\phi(\mathbf{m}_0) = |K^{m_0}/K^{m_{0,1}}| \le \mathcal{N}(\mathbf{m}_0)$.

**Remark 7.2.** The factor 1/3 in Equations (26) and (27) can be made arbitrarily close to 1 by increasing the radius $r \in \mathbb{R}$ and widening the density interval $[x/e^n, x]$ in Definition 2.11.

**Remark 7.3.** It is possible, with essentially the same proof, to rephrase this theorem in such a way that it concerns an intersection of events instead of a conditional probability. The probability then also depends on the number $\mathcal{N}(\mathbf{m}) = \mathcal{N}(\mathbf{m}_0) \cdot 2^{|m_{\mathbb{R}}|}$, where $|m_{\mathbb{R}}|$ is the number of real places dividing $m_{\infty}$. Under the same conditions as
in Theorem 7.1, one can prove that

$$ \mathrm{Pr}_{\substack{\mathbf{a} \in \mathcal{D} \\ \alpha \in \mathrm{Exp}(\mathbf{a}) \cap \mathcal{B}_{\infty}}} \left[ \begin{array}{l} (\alpha) \cdot \mathrm{Exp}(-\mathbf{a}) \in \mathcal{S}, \text{ and} \\ \alpha \cdot \mathrm{Exp}_{\infty}(-\mathbf{a}_{\infty}) \in \tau \mathbf{K}^{\mathbf{m},1} \end{array} \right] \geq \frac{\mathcal{N}(\mathbf{m}_0)}{\phi(\mathbf{m}_0)} \cdot \frac{[\mathrm{Pic}_{\mathbf{K}^{\mathbf{m}}}^0 : \mathcal{G}]}{3 \cdot \mathcal{N}(\mathbf{m})} \cdot \delta_S[r^n]. \quad (28) $$

## 7.2. Proof of Theorem 7.1.

### 7.2.1. Fixing the ideal $\mathbf{c} \in \mathcal{S}$ and the Arakelov divisor $\mathbf{a} \in \mathrm{Div}_{\mathbf{K}^m}^0$. We concentrate on the 'inner probability' of Equation (25) in Theorem 7.1 in the case where $\mathcal{S} = \{\mathbf{c}\}$ consists of a single integral ideal. We denote

$$ p_{\mathbf{a},\mathbf{c}} = \mathrm{Pr}_{\substack{\alpha \in \mathrm{Exp}(\mathbf{a}) \cap \mathcal{B}_{\infty}}} \left[ (\alpha) \cdot \mathrm{Exp}(-\mathbf{a}) = \mathbf{c} \mid \alpha \cdot \mathrm{Exp}_{\infty}(-\mathbf{a}_{\infty}) \in \tau \mathbf{K}^{\mathbf{m},1} \right], \quad (29) $$

where we leave the dependency on $r \in \mathbb{R}_{>0}$, the modulus $\mathbf{m}$ and $\tau \in \mathbf{K}^{\mathbf{m}}/\mathbf{K}^{\mathbf{m},1}$ implicit. By the law of conditional probability, we have that $p_{\mathbf{a},\mathbf{c}}$ in Equation (29) equals

$$ \mathrm{Pr}_{\substack{\alpha \in \mathrm{Exp}(\mathbf{a}) \cap \mathcal{B}_{\infty}}} \left[ \begin{array}{l} (\alpha) \cdot \mathrm{Exp}(-\mathbf{a}) = \mathbf{c} \\ \text{and} \\ \alpha \cdot \mathrm{Exp}_{\infty}(-\mathbf{a}_{\infty}) \in \tau \mathbf{K}^{\mathbf{m},1} \end{array} \right] \bigg/ \mathrm{Pr}_{\substack{\alpha \in \mathrm{Exp}(\mathbf{a}) \cap \mathcal{B}_{\infty}}} \left[ \alpha \cdot \mathrm{Exp}_{\infty}(-\mathbf{a}_{\infty}) \in \tau \mathbf{K}^{\mathbf{m},1} \right] \quad (30) $$

The following lemma addresses the probability values of the numerator and denominator in Equation (30) separately.

**Lemma 7.4.** Let $\mathbf{m} = \mathbf{m}_0\mathbf{m}_\infty$ be a modulus, let $\tau \in \mathbf{K}^\mathbf{m}/\mathbf{K}^{\mathbf{m},1}$, let $\mathbf{a} \in \mathrm{Div}_{\mathbf{K}^m}^0$ be a fixed Arakelov ray divisor, and let $\mathbf{c} \in \mathcal{I}_K^\mathbf{m}$ be an integral ideal. Then

$$ \mathrm{Pr}_{\substack{\alpha \in \mathrm{Exp}(\mathbf{a}) \cap \mathcal{B}_{\infty}}} \left[ \begin{array}{l} (\alpha) \cdot \mathrm{Exp}(-\mathbf{a}) = \mathbf{c} \\ \text{and} \\ \alpha \cdot \mathrm{Exp}_{\infty}(-\mathbf{a}_{\infty}) \in \tau \mathbf{K}^{\mathbf{m},1} \end{array} \right] = \frac{|\mathrm{Exp}(\mathbf{a} + d(\mathbf{c}))_{\tau}^{\times} \cap \mathcal{B}_{\infty}|}{|\mathrm{Exp}(\mathbf{a}) \cap \mathcal{B}_{\infty}|}, \quad (31) $$

and, there exists some $\tilde{\tau} \in K_\mathbb{R}$ such that

$$ \mathrm{Pr}_{\substack{\alpha \in \mathrm{Exp}(\mathbf{a}) \cap \mathcal{B}_{\infty}}} [\alpha \cdot \mathrm{Exp}_{\infty}(-\mathbf{a}_{\infty}) \in \tau \mathbf{K}^{\mathbf{m},1}] = \frac{|(\mathrm{Exp}(\mathbf{a})\mathbf{m}_0 + \tilde{\tau}) \cap \mathcal{B}_{\infty} \cap \tau \mathbf{K}_{\mathbb{R}}^{\mathbf{m}_{\infty}}|}{|\mathrm{Exp}(\mathbf{a}) \cap \mathcal{B}_{\infty}|}, \quad (32) $$

where the sampling $\alpha \leftarrow \mathrm{Exp}(\mathbf{a}) \cap \mathcal{B}_{\infty}$ is uniform in both expressions, and where $\tau \mathbf{K}_{\mathbb{R}}^{\mathbf{m}_{\infty}} = \{(x_\sigma)_\sigma \in K_\mathbb{R} \mid x_\sigma/\sigma(\tau) > 0 \text{ for real } \sigma \mid \mathbf{m}_{\infty}\}$.

**Proof.** By examining Definition 5.3 closely, noting that $\mathrm{Exp}_f((\mathbf{a} + d(\mathbf{c}))_f) = \mathrm{Exp}_f(\mathbf{a}_f) \cdot \mathbf{c} \in \mathcal{I}_K^\mathbf{m}$, we see that for all $\alpha \in \mathrm{Exp}(\mathbf{a})$,

$$ (\alpha) \cdot \mathrm{Exp}(-\mathbf{a}) = \mathbf{c} \text{ and } \alpha \cdot \mathrm{Exp}_{\infty}(-\mathbf{a}_{\infty}) \in \tau \mathbf{K}^{\mathbf{m},1} \iff \alpha \in \mathrm{Exp}(\mathbf{a} + d(\mathbf{c}))_{\tau}^{\times}. $$

As the number of choices for $\alpha \in \mathrm{Exp}(\mathbf{a}) \cap \mathcal{B}_{\infty}$ equals $|\mathrm{Exp}(\mathbf{a}) \cap \mathcal{B}_{\infty}|$, the number of good choices equals $|\mathrm{Exp}(\mathbf{a} + d(\mathbf{c}))_{\tau}^{\times} \cap \mathcal{B}_{\infty}|$ and since the sampling procedure is uniform, we arrive at the first probability claim. For the second probability claim, write $\mathbf{a} = \mathrm{Exp}_f(\mathbf{a}_f) \in \mathcal{I}_K^\mathbf{m}$, for conciseness. We note that for $\alpha \in \mathrm{Exp}(\mathbf{a})$, $\alpha \cdot \mathrm{Exp}_{\infty}(-\mathbf{a}_{\infty}) \in \tau \mathbf{K}^{\mathbf{m},1}$ is equivalent to

$$ \alpha \cdot \mathrm{Exp}_{\infty}(-\mathbf{a}_{\infty}) \in \mathrm{Exp}_f(\mathbf{a}_f) \cap \tau \mathbf{K}^{\mathbf{m},1} = \mathbf{a} \cap \tau \mathbf{K}^{\mathbf{m},1} = (\mathbf{a}\mathbf{m}_0 + \tau') \cap \tau \mathbf{K}_{\mathbb{R}}^{\mathbf{m}_{\infty}}, $$

where $\tau' \in \mathbf{a}$ is such that $\tau' \equiv \tau \pmod{\mathbf{m}_0}$ (note that $\mathbf{a}$ and $\mathbf{m}_0$ are coprime).

So, for $\alpha \in \mathrm{Exp}(\mathbf{a}) \cap \mathcal{B}_{\infty}$, the statement $\alpha \cdot \mathrm{Exp}_{\infty}(-\mathbf{a}_{\infty}) \in \tau \mathbf{K}^{\mathbf{m},1}$ is equivalent to

$$ \alpha \in \mathrm{Exp}_{\infty}(\mathbf{a}_{\infty})((\mathbf{a}\mathbf{m}_0 + \tau') \cap \tau \mathbf{K}_{\mathbb{R}}^{\mathbf{m}_{\infty}}) \cap \mathcal{B}_{\infty} = (\mathrm{Exp}(\mathbf{a})\mathbf{m}_0 + \tilde{\tau}) \cap \mathcal{B}_{\infty} \cap \tau \mathbf{K}_{\mathbb{R}}^{\mathbf{m}_{\infty}} $$
where we use the fact that $\mathrm{Exp}(\mathbf{a})\tau K_{\mathbb{R}}^{\mathbf{m}_{\infty}} = \tau K_{\mathbb{R}}^{\mathbf{m}_{\infty}}$ and where we put $\tilde{\tau} = \mathrm{Exp}_{\infty}(\mathbf{a}_{\infty})\tau' \in K_{\mathbb{R}}$. This proves the claim. $\square$

By combining Equations (30) to (32) and scratching redundant factors, one concludes that there exists $\tilde{\tau} \in \mathrm{Exp}(\mathbf{a})$ such that

$$p_{\mathbf{a},c} = \frac{|\mathrm{Exp}(\mathbf{a} + d(\mathbf{c}))_{\tau}^{\times} \cap r\mathcal{B}_{\infty}|}{|(\mathrm{Exp}(\mathbf{a})\mathbf{m}_0 + \tilde{\tau}) \cap r\mathcal{B}_{\infty} \cap \tau K_{\mathbb{R}}^{\mathbf{m}_{\infty}}|} \quad (33)$$

7.2.2. *Estimating* $|(\mathrm{Exp}(\mathbf{a})\mathbf{m}_0 + \tilde{\tau}) \cap r\mathcal{B}_{\infty} \cap \tau K_{\mathbb{R}}^{\mathbf{m}_{\infty}}|$. When the radius $r$ is sufficiently large compared to the lattice $\mathrm{Exp}(\mathbf{a})\mathbf{m}_0 \subseteq K_{\mathbb{R}}$, one can deduce that for $\mathbf{a} \in \mathrm{Div}_{K^{\mathbf{m}}}$ the number of points in $(\mathrm{Exp}(\mathbf{a})\mathbf{m}_0 + \tilde{\tau}) \cap r\mathcal{B}_{\infty} \cap \tau K_{\mathbb{R}}^{\mathbf{m}_{\infty}}$ is approximately $\mathrm{Vol}(r\mathcal{B}_{\infty}) \cdot 2^{-|\mathbf{m}_{\mathbb{R}}|}/\mathrm{det}(\mathbf{m}_0)$, where the $2^{-|\mathbf{m}_{\mathbb{R}}|}$ accounts for the fact that we only take the halves of the box for which $x_{\sigma}/\sigma(\tau) > 0$ at the real embeddings $\sigma | \mathbf{m}_{\infty}$. More precisely, we instantiate Lemma 2.8 with

* $\Lambda = \mathrm{Exp}(\mathbf{a} + d(\mathbf{m}_0)) \subseteq K_{\mathbb{R}}$, for which holds $\mathrm{Vol}(\Lambda) = \mathcal{N}(\mathbf{m}_0) \cdot \sqrt{|\Delta_K|}$,

* $t = \tilde{\tau} \in K_{\mathbb{R}}$,

* $(t')_{\sigma} = \mathrm{sgn}(\sigma(\tau)) \cdot 1/2$ for real $\nu | \mathbf{m}_{\infty}$, and $(t')_{\sigma} = 0$ otherwise. Here $\mathrm{sgn}(\sigma(\tau))$ is the sign of $\sigma(\tau)$.

* $X = \{(x_{\sigma})_{\sigma} \in K_{\mathbb{R}} | |x_{\sigma}| \le 1 \text{ and } |x_{\sigma}| \le \frac{1}{2} \text{ if } \sigma \text{ is real and } \sigma | \mathbf{m}_{\infty}\}$, such that $X + t' = \mathcal{B}_{\infty} \cap \tau K_{\mathbb{R}}^{\mathbf{m}_{\infty}}$. Note that $\mathrm{Vol}(X) = 2^{n_{\mathbb{R}}-|\mathbf{m}_{\mathbb{R}}|} \cdot (2\pi)^{n_{\mathbb{C}}}$, due to the hybrid complex-real nature of $K_{\mathbb{R}}^{\mathbf{m}_{\infty}}$ and taking account for the required positivity (or negativity, depending on $\tau$) at the real places $\nu | \mathbf{m}_{\infty}$.

* $c = n \cdot \mathcal{N}(\mathbf{m}_0)^{\frac{1}{n}} \cdot \Gamma_K \cdot |\Delta_K|^{\frac{1}{2n}} \ge 2 \cdot \mathrm{cov}(\mathrm{Exp}(\mathbf{a} + d(\mathbf{m}_0)))$ (see Lemma 2.13(i) and (iv)), so that the Voronoi cell $\mathcal{V}_0$ of $\mathrm{Exp}(\mathbf{a} + d(\mathbf{m}_0))$ lies in $cX$.

This yields, for $r > 8 \cdot n^2 \cdot \mathcal{N}(\mathbf{m}_0)^{\frac{1}{n}} \cdot \Gamma_K \cdot |\Delta_K|^{\frac{1}{2n}} \ge 8nc$,

$$|(\mathrm{Exp}(\mathbf{a})\mathbf{m}_0 + \tilde{\tau}) \cap r\mathcal{B}_{\infty} \cap \tau K_{\mathbb{R}}^{\mathbf{m}_{\infty}}| \in [e^{-1/4}, e^{1/4}] \cdot \frac{r^n \cdot 2^{n_{\mathbb{R}}-|\mathbf{m}_{\mathbb{R}}|} \cdot (2\pi)^{n_{\mathbb{C}}}}{\mathcal{N}(\mathbf{m}_0) \cdot \sqrt{|\Delta_K|}}. \quad (34)$$

Applying this to the denominator of Equation (33), we directly deduce that

$$p_{\mathbf{a},c} \in [e^{-1/4}, e^{1/4}] \cdot \frac{\sqrt{|\Delta_K|} \cdot \mathcal{N}(\mathbf{m}_0) \cdot 2^{|\mathbf{m}_{\mathbb{R}}|}}{r^n \cdot 2^{n_{\mathbb{R}}} \cdot (2\pi)^{n_{\mathbb{C}}}} \cdot |\mathrm{Exp}(\mathbf{a} + d(\mathbf{c}))_{\tau}^{\times} \cap r\mathcal{B}_{\infty}| \quad (35)$$

7.2.3. *Estimating the probability of sampling a fixed ideal for a random Arakelov divisor.* Still focusing on the simplified case where $S = \{\mathbf{c}\}$, the goal of this proof is to find a lower bound for $\mathbb{E}_{\mathbf{a} \leftarrow D}[p_{\mathbf{a},c}]$. By linearity of expectation, we have

$$\mathbb{E}_{\mathbf{a} \leftarrow D} [p_{\mathbf{a},c}] \in [e^{-1/4}, e^{1/4}] \cdot \frac{\sqrt{|\Delta_K|} \cdot \mathcal{N}(\mathbf{m}_0) \cdot 2^{|\mathbf{m}_{\mathbb{R}}|}}{r^n \cdot 2^{n_{\mathbb{R}}} \cdot (2\pi)^{n_{\mathbb{C}}}} \cdot \mathbb{E}_{\mathbf{a} \leftarrow D} \left[ |\mathrm{Exp}(\mathbf{a} + d(\mathbf{c}))_{\tau}^{\times} \cap r\mathcal{B}_{\infty}| \right]. \quad (36)$$

So it remains to focus on the expected value of $|\mathrm{Exp}(\mathbf{a} + d(\mathbf{c}))_{\tau}^{\times} \cap r\mathcal{B}_{\infty}|$ for $\mathbf{a} \leftarrow D$.

7.2.4. *The number* $|\mathrm{Exp}(\mathbf{a} + d(\mathbf{c}))_{\tau}^{\times} \cap r\mathcal{B}_{\infty}|$ *only depends on the Arakelov ray class* of $\mathbf{a} \in \mathrm{Div}_{K^{\mathbf{m}}}$.* A fact that plays a large role in the full proof, is that the number $|\mathrm{Exp}(\mathbf{a} + d(\mathbf{c}))_{\tau}^{\times} \cap r\mathcal{B}_{\infty}|$ of $\tau$-equivalent generators in a box depends on the Arakelov ray class $[\mathbf{a}]$ rather than the divisor $\mathbf{a}$ itself. This has as a consequence that the involved probability distribution changes from $\mathcal{D}$ to $[\mathcal{D}] = \mathcal{U}(G)$, uniform on $G \subseteq \mathrm{Pic}_{K^{\mathbf{m}}}^{0}$, which is easier to analyze. This fact, among others, is proven in the following lemma.
**Lemma 7.5.** For all ray divisors $\mathbf{a} \in \mathrm{Div}_{K^m}^0$, elements $\tau, \tau' \in K^m$, ideals $\mathbf{c} \in \mathcal{I}_K^m$ and real numbers $r > 0$ we have the following list of facts.

(i) $|\mathrm{Exp}(\mathbf{a})_{\tau}^{\times} \cap r\mathcal{B}_{\infty}| = |\mathrm{Exp}(\mathbf{a} + (\|\tau'\|))_{\tau\tau'}^{\times} \cap r\mathcal{B}_{\infty}|$, i.e., the number of $\tau$-equivalent ray generators of $\mathbf{a}$ in a fixed box of radius $r$ is equal to the number of $\tau\tau'$-equivalent ray generators of $\mathbf{a} + (\|\tau'\|)$ in the same box.

(ii) $|\mathrm{Exp}(\mathbf{a} + d(\mathbf{c}))_{\tau}^{\times} \cap r\mathcal{B}_{\infty}| = |\mathrm{Exp}(\mathbf{a} + d^0(\mathbf{c}))_{\tau}^{\times} \cap \frac{r}{\mathcal{N}(\mathbf{c})^{1/n}}\mathcal{B}_{\infty}|$, since the maps $d^0$ and $d$ only differ by some scaling $\mathcal{N}(\mathbf{c})^{1/n}$.

(iii) Writing $\mathbf{a}_{\infty} = \sum_{\nu} a_{\nu} \cdot (\|\nu\|) \in \mathrm{Div}_{K^m}^0$, we have

$$|\mathrm{Exp}(\mathbf{a}_{\infty})_1^{\times} \cap r\mathcal{B}_{\infty}| = |\mu_{K^{m,1}}| \cdot |(\mathrm{Log}(\mathcal{O}_{K^{m,1}}^{\times}) + (a_{\nu})_{\nu}) \cap S_{\mathrm{log}(r)}|, \quad (37)$$

where $S_{\mathrm{log}r} = \{(b_{\nu})_{\nu} \in \bigoplus_{\nu} \mathbb{R} \mid b_{\nu} \le n_{\nu} \log(r), \sum_{\nu} b_{\nu} = 0\} \subseteq H$ is a simplex (as in Lemma 7.6) and $\mathrm{Log}(\mathcal{O}_{K^{m,1}}^{\times}) = \mathrm{Log}(\mathcal{O}_{K}^{\times} \cap K^{m,1})$. Here, $n_{\nu} = 2$ if $\nu$ is complex and 1 otherwise.

*Proof.* For part (i), observe that multiplying by $(\frac{\sigma(\tau')}{|\sigma(\tau')|})_{\sigma} \in K_{\mathbb{R}}$ yields a bijection from $\mathrm{Exp}(\mathbf{a})$ to $\mathrm{Exp}(\mathbf{a} + (\|\tau'\|))$, preserving the maximum norm. It remains to show that this bijection sends $\mathrm{Exp}(\mathbf{a})_{\tau}^{\times}$ to $\mathrm{Exp}(\mathbf{a} + (\|\tau'\|))_{\tau'\tau}^{\times}$. Using Definition 5.3 and assuming $\mathrm{Exp}_f(\mathbf{a}_f) = \kappa\mathcal{O}_K$ (and therefore $\mathrm{Exp}_f([\mathbf{a} + (\|\tau'\|)]_f) = \tau'\kappa\mathcal{O}_K$), we have

$$ \left( \frac{\sigma(\tau')}{|\sigma(\tau')|} \right)_{\sigma} \cdot \mathrm{Exp}(\mathbf{a})_{\tau}^{\times} = \left( \frac{1}{|\sigma(\tau')|} \right)_{\sigma} \cdot (\tau') \cdot \underbrace{\mathrm{Exp}_{\infty}(\mathbf{a}_{\infty}) \cdot (\kappa \mathcal{O}_{K}^{\times} \cap \tau K^{m,1})}_{\mathrm{Exp}(\mathbf{a})_{\tau}^{\times}} \\ = \underbrace{\left( \frac{1}{|\sigma(\tau')|} \right)_{\sigma} \cdot \mathrm{Exp}_{\infty}(\mathbf{a}_{\infty}) \cdot (\tau' \kappa \mathcal{O}_{K}^{\times} \cap \tau' \tau K^{m,1})}_{\mathrm{Exp}_{\infty}((\mathbf{a} + (\|\tau'\|))_{\infty})} = \mathrm{Exp}(\mathbf{a} + (\|\tau'\|))_{\tau'\tau}^{\times} $$

For part (ii), recall that multiplying the ideal lattice $\mathrm{Exp}(d(\mathbf{c})) = \mathbf{c} \subseteq K_{\mathbb{R}}$ by the scalar $\mathcal{N}(\mathbf{c})^{-1/n}$ results in the ideal lattice $\mathrm{Exp}(d^0(\mathbf{c}))$. Applying this scalar multiplication to the set $\mathrm{Exp}(\mathbf{a} + d(\mathbf{c})) \cap r\mathcal{B}_{\infty}$ yields a bijective correspondence with $\mathrm{Exp}(\mathbf{a} + d^0(\mathbf{c})) \cap \frac{r}{\mathcal{N}(\mathbf{c})^{1/n}}\mathcal{B}_{\infty}$.

In part (iii) it is enough to show that the logarithm $\mathrm{Log} : K_{\mathbb{R}}^{\times} \to \mathrm{Log}(K_{\mathbb{R}}^{\times})$ takes $\mathrm{Exp}(\mathbf{a}_{\infty})_1^{\times}$ to the shifted lattice $\mathrm{Log}(\mathcal{O}_{K^{m,1}}^{\times}) + (a_{\nu})_{\nu} \subset H$ and takes $r\mathcal{B}_{\infty} \cap K_{\mathbb{R}}^0$ to the simplex $S_{\mathrm{log}(r)} \subset H$. This logarithmic map is $|\mu_{K^{m,1}}|$-to-one on $\mathrm{Exp}(\mathbf{a}_{\infty})_1^{\times}$, as it sends roots of unity to the all-zero vector in $\mathrm{Log}(K_{\mathbb{R}}^{\times})$ (which is the unit in that group), yielding the extra factor $|\mu_{K^{m,1}}|$ in Equation (37). Here, $\mu_{K^{m,1}} = \mu_K \cap K^{m,1}$, i.e., the roots of unity in $K^{m,1}$. $\square$

As a corollary of Lemma 7.5(i) we deduce that $|\mathrm{Exp}(\mathbf{a})_{\tau}^{\times} \cap r\mathcal{B}_{\infty}| = |\mathrm{Exp}(\mathbf{a} + (\|\kappa\|))_{\tau}^{\times} \cap r\mathcal{B}_{\infty}|$ for $\kappa \in K^{m,1}$, i.e., the number of elements $|\mathrm{Exp}(\mathbf{a})_{\tau}^{\times} \cap r\mathcal{B}_{\infty}|$ only depends on the Arakelov ray class of $\mathbf{a}$ (next to $r \in \mathbb{R}$, $\mathbf{m}$ and $\tau \in K^m$). Choose a (measurable) fundamental domain $F \subseteq \mathrm{Div}_{K^m}^0$ of the quotient group $\mathrm{Pic}_{K^m}^0$. Put $F_G = \{\mathbf{a} \in F \mid [\mathbf{a}] \in G\}$, which is a subdomain of $F$ for the subgroup $G \subseteq \mathrm{Pic}_{K^m}^0$ and likewise put $F_{T^m} = \{\mathbf{a} \in F \mid [\mathbf{a}] \in T^m\}$, a fundamental domain of $T^m$ in $\mathrm{Pic}_{K^m}^0$. Note that $F_{T^m} \subseteq F_G$. By the assumption that $[D]$ is uniform on $G + [\mathbf{b}]$,
and $[d^0(\mathbf{c})] \in [d^0(S)] \subseteq G + [\langle\tau\rangle] - [\mathbf{b}]$, we deduce, writing $\tilde{r} = r\mathcal{N}(\mathbf{c})^{-1/n}$,

$$ \mathbb{E}_{\mathbf{a} \leftarrow \mathcal{D}} \left[ |\mathrm{Exp}(\mathbf{a} + d(\mathbf{c}))_{\tau}^{\times} \cap r\mathcal{B}_{\infty}| \right] = \mathbb{E}_{\mathbf{a} \leftarrow \mathcal{D}} \left[ |\mathrm{Exp}(\mathbf{a} + d^0(\mathbf{c}))_{\tau}^{\times} \cap \tilde{r}\mathcal{B}_{\infty}| \right] \quad (38) $$

$$ = \mathbb{E}_{\mathbf{a} \leftarrow \mathcal{U}(F_G + [\mathbf{b}])} \left[ |\mathrm{Exp}(\mathbf{a} + d^0(\mathbf{c}))_{\tau}^{\times} \cap \tilde{r}\mathcal{B}_{\infty}| \right] = \mathbb{E}_{\mathbf{a} \leftarrow \mathcal{U}(F_G)} \left[ |\mathrm{Exp}(\mathbf{a} + (\langle\tau\rangle)_{\tau}^{\times} \cap \tilde{r}\mathcal{B}_{\infty}| \right] \quad (39) $$

$$ = \mathbb{E}_{\mathbf{a} \leftarrow \mathcal{U}(F_G)} \left[ |\mathrm{Exp}(\mathbf{a})_1^{\times} \cap \tilde{r}\mathcal{B}_{\infty}| \right] = \frac{1}{|G/T^m|} \mathbb{E}_{\mathbf{a} \leftarrow \mathcal{U}(F_{T^m})} \left[ |\mathrm{Exp}(\mathbf{a})_1^{\times} \cap \tilde{r}\mathcal{B}_{\infty}| \right] \quad (40) $$

where the first equality follows from scaling (Lemma 7.5(ii)) and the second one by the fact that the random variable is an Arakelov ray class invariant (Lemma 7.5(i)) and that $[\mathcal{D}]$ is uniform on $G + [\mathbf{b}]$. The third equality holds because the class $[\mathbf{a} + d^0(\mathbf{c})]$ for $\mathbf{a} \in \mathrm{Pic}_{K^m}^0$ uniformly distributed over $F_G + [\mathbf{b}]$ is distributed as $[\mathbf{a}' + (\langle\tau\rangle)]$ for $\mathbf{a}' \leftarrow \mathcal{U}(F_G)$. This follows from the assumption $d^0(\mathbf{c}) \in G + [\langle\tau\rangle] - [\mathbf{b}]$. The fourth equality follows directly from Lemma 7.5(i), and the last equality follows from Definition 5.3. Namely, an Arakelov divisor $\mathbf{a}$ can only have generators if the ideal class of $\mathrm{Exp}(\mathbf{a}_f)$ is trivial, i.e., if $[\mathbf{a}] \in T^m$. So, instead, $\mathbf{a}$ can be chosen uniformly from a fundamental domain $F_{T^m}$ of $T^m$ in $\mathrm{Div}_{K^m}^0$, with a correction factor of $\frac{1}{|G/T^m|}$ in the expected value.

### 7.2.5. Volume of the simplex in $H$
For the next step in the proof, we need to know the volume of the simplex $S_{\log r} \subseteq H$, hence the following lemma.

**Lemma 7.6.** The volume of the simplex $S_\alpha = \{(b_\nu)_\nu \in H \mid b_\nu \le n_\nu \alpha\} \subseteq H = \mathrm{Log} K_\mathbb{R}^0$ for $\alpha \in \mathbb{R}_{>0}$ is given by

$$ \mathrm{Vol}(S_\alpha) = \frac{\sqrt{r+1} \cdot (n\alpha)^r}{r!}, $$

where $r = n_\mathbb{R} + n_\mathbb{C} - 1$ and where $n_\nu = 2$ whenever $\nu$ is complex and $n_\nu = 1$ when $\nu$ is real.

*Proof.* By applying to $S_\alpha \subseteq H$ the translation $c_\nu = n_\nu \alpha - b_\nu$, one can see that $S_\alpha$ is a regular $r$-simplex $\{c \in \prod_\nu \mathbb{R} \mid \sum_\nu c_\nu = n \cdot \alpha$ and $c_\nu \ge 0\}$ with edge length $\sqrt{2} \cdot n \cdot \alpha$. Therefore, the volume of $S_\alpha$ equals $\mathrm{Vol}(S_\alpha) = \frac{(n\alpha)^r \sqrt{r+1}}{r!} [65]$. $\square$

### 7.2.6. Taking the logarithmic map into $H = \mathrm{Log} K_\mathbb{R}^0$
Applying the logarithmic map on the set $\mathrm{Exp}(\mathbf{a})_1^\times \cap r \cdot \mathcal{N}(\mathbf{c})^{-1/n}\mathcal{B}_\infty$, sends $\mathrm{Exp}(\mathbf{a})_1^\times$ to a shift of the logarithmic ray unit lattice $\mathrm{Log}(\mathcal{O}_{K^{m,1}}^\times) \subseteq H$ and $r \cdot \mathcal{N}(\mathbf{c})^{-1/n}\mathcal{B}_\infty$ to a simplex $S_{n \log r - \log \mathcal{N}(\mathbf{c})}$, where $S_x = \mathrm{Log}(x\mathcal{B}_\infty) \subseteq H = \mathrm{Log} K_\mathbb{R}^0$ as in Lemma 7.6 (see also Lemma 7.5(iii)). Note that $\mathrm{Vol}(T^m) = \mathrm{Vol}(\mathrm{Log}(\mathcal{O}_{K^{m,1}}^\times))$.

The expected value as in Equation (40) then equals the average number of points of a randomly shifted logarithmic ray unit lattice into this simplex, which equals $\mathrm{Vol}(S_{n \log r - \log \mathcal{N}(\mathbf{c})}) / \mathrm{Vol}(T^m)$ (see Lemma 2.4). Therefore,

$$ \frac{1}{|G/T^m|} \mathbb{E}_{\mathbf{a} \leftarrow \mathcal{U}(F_{T^m})} \left[ |\mathrm{Exp}(\mathbf{a})_1^\times \cap r \mathcal{N}(\mathbf{c})^{-1/n} \mathcal{B}_\infty| \right] = \frac{|\mu_{K^{m,1}}| \cdot \mathrm{Vol}(S_{n \log r - \log \mathcal{N}(\mathbf{c})})}{|G/T^m| \cdot |T^m|} \quad (41) $$

$$ = \frac{[\mathrm{Pic}_{K^m}^0 : G] \cdot |\mu_K| \cdot \mathrm{Vol}(S_{n \log r - \log \mathcal{N}(\mathbf{c})})}{\phi(\mathbf{m}_0) \cdot 2^{|\mathbf{m}_R|} \cdot h_K \cdot |T|} = \frac{[\mathrm{Pic}_{K^m}^0 : G] \cdot |\mu_K| \cdot C(r, \mathcal{N}(\mathbf{c}))}{\phi(\mathbf{m}_0) \cdot 2^{|\mathbf{m}_R|} \cdot h_K \cdot R_K} \quad (42) $$
where, for the second equation, we use that $|G/T^m| \cdot |T^m| = |G| = |\text{Pic}_{K^m}^0| / |\text{Pic}_{K^m}^0 : G|$ and Equation (21) of Lemma 5.1. For the third equation we use the fact that $\frac{\text{Vol}(S_n \log r - \log \mathcal{N}(c))}{|T|} = \frac{C(r, \mathcal{N}(c))}{R_K}$, where we define $C(r, \mathcal{N}(c)) := (n \log r - \log \mathcal{N}(c))^r / r!$ (see Lemma 7.6 and Equation (9)).

### 7.2.7. Applying the Abel summation formula to get the probability for the ideal set S.
By combining Equations (36), (40) and (42), using the class number formula (see Equation (4)) and the fact that $\frac{\mathcal{N}(m_0)}{\phi(m_0)} = \frac{|\mathcal{O}_K/m_0|}{|(\mathcal{O}_K/m_0)^\times|} \ge 1$, one obtains,

$$ \mathbb{E}_{\mathbf{a} \leftarrow D} [p_{\mathbf{a}, \mathbf{c}}] \ge e^{-1/4} \cdot \frac{\sqrt{|\Delta_K|} \cdot \mathcal{N}(\mathbf{m}_0) \cdot 2^{|\mathbf{m}_R|}}{r^n \cdot 2^{n_R} \cdot (2\pi)^{n_C}} \cdot \frac{[\text{Pic}_{K^m}^0 : G] \cdot |\mu_K| \cdot C(r, \mathcal{N}(\mathbf{c}))}{\phi(\mathbf{m}_0) \cdot 2^{|\mathbf{m}_R|} \cdot h_K \cdot R_K} \quad (43) $$

$$ = e^{-1/4} \cdot \frac{[\text{Pic}_{K^m}^0 : G] \cdot C(r, \mathcal{N}(\mathbf{c}))}{r^n \cdot \rho_K} \cdot \frac{\mathcal{N}(\mathbf{m}_0)}{\phi(\mathbf{m}_0)} \quad (44) $$

where $|\mathbf{m}_R|$ is the number of real places dividing $m_\infty$ and where $C(r, \mathcal{N}(\mathbf{c})) = (n \log r - \log \mathcal{N}(\mathbf{c}))^r / r!$. By taking the sum over all $\mathbf{c} \in S$ (note that $[d^0(S)] \subseteq G$), using linearity of the expected value operator, one can achieve the following lower bound.

$$ \mathbb{E}_{\mathbf{a} \leftarrow D} \left[ \sum_{\mathbf{c} \in S} p_{\mathbf{a}, \mathbf{c}} \right] = \sum_{\mathbf{c} \in S} \mathbb{E}_{\mathbf{a} \leftarrow D} [p_{\mathbf{a}, \mathbf{c}}] \quad (45) $$

$$ \in [e^{-1/4}, e^{1/4}] \cdot \frac{\mathcal{N}(\mathbf{m}_0)}{\phi(\mathbf{m}_0)} \cdot [\text{Pic}_{K^m}^0 : G] \cdot \sum_{\mathbf{c} \in S} \frac{C(r, \mathcal{N}(\mathbf{c}))}{\rho_K \cdot r^n} \quad (46) $$

By an application of the Abel summation formula, one can relate the sum $\sum_{\mathbf{c} \in S} C(r, \mathcal{N}(\mathbf{c}))$ to an integral involving the counting function $|S(t)| = |\{\mathbf{c} \in S \mid \mathcal{N}(\mathbf{a}) \le t\}|$ of the ideal set $S$ and the derivative of the volume function $C(r, N) = (n \log r - \log N)^r / r!$ with respect to the variable $N$. More precisely, we have

$$ \sum_{\mathbf{c} \in S} \frac{C(r, \mathcal{N}(\mathbf{c}))}{\rho_K \cdot r^n} = - \int_{t=1}^{r^n} \frac{|S(t)|}{\rho_K \cdot r^n} \cdot \left[ \frac{d}{dN} C(r, N) \right]_{N=t} dt \quad (47) $$

$$ = \frac{1}{(r-1)!} \int_{t=1}^{r^n} \frac{|S(t)|}{\rho_K \cdot t} \cdot \left[ \frac{d}{dN} \Gamma(r, n \log r - \log N) \right]_{N=t} dt, \quad (48) $$

Where the first equality is the Abel summation formula [2, Theorem 4.2] and the second equality follows from computing the derivative of the upper incomplete Gamma function $\Gamma(r, x) = \int_x^\infty u^{r-1} e^{-u} du$.

$$ -\frac{d}{dN} C(r, N) \Big|_t = \frac{(n \log r - \log t)^{r-1}}{t \cdot (r-1)!} = \frac{r^n}{t \cdot (r-1)!} \cdot \left[ \frac{d}{dN} \Gamma(r, n \log r - \log N) \right] \Big|_t. $$

Using Definition 2.11 about ideal density and the fact that the integrand is positive, Equation (48) is lower bounded by

$$ \frac{1}{(r-1)!} \int_{t=(r/e)^n}^{r^n} \frac{|S(t)|}{\rho_K \cdot t} \cdot \left[ \frac{d}{dN} \Gamma(r, n \log r - \log N) \right]_{N=t} dt \quad (49) $$

$$ \ge \frac{\delta_S[r^n]}{(r-1)!} \int_{t=(r/e)^n}^{r^n} \left[ \frac{d}{dN} \Gamma(r, n \log r - \log N) \right]_{N=t} dt \ge \frac{1}{2} \cdot \delta_S[r^n], \quad (50) $$
where the last inequality (Equation (50)) follows from the definition of the upper incomplete Gamma function,

$$ \frac{1}{(\mathbf{r}-1)!} \int_{t=(r/e)^n}^{r^n} \left( \frac{d}{dt} \Gamma(\mathbf{r}, n \log \mathbf{r} - \log N) \bigg|_{N=t} \right) dt = \frac{1}{(\mathbf{r}-1)!} \cdot (\Gamma(\mathbf{r}, 0) - \Gamma(\mathbf{r}, n)) \\ = 1 - e^{-n} \sum_{k=0}^{\mathbf{r}-1} \frac{n^k}{k!} \geq 1/2, $$

where we used the fact that $e^{-n} \sum_{k=0}^{\mathbf{r}-1} \frac{n^k}{k!}$ equals the probability that a Poisson distribution with parameter $n$ yields at most $\mathbf{r}-1 \leq n-1$ occurrences, which is bounded by a half.

By combining Equations (46), (48) and (50) and using $e^{-1/4}/2 > 1/3$, we obtain

$$ \mathbb{E}_{\mathbf{a} \leftarrow \mathcal{D}} \left[ \mathrm{Pr}_{\alpha \leftarrow \mathrm{Exp}(\mathbf{a}) \cap r \mathcal{B}_{\infty}} \left[ (\alpha) \cdot \mathrm{Exp}(-\mathbf{a}) \in \mathcal{S} \mid \alpha \cdot \mathrm{Exp}_{\infty}(-\mathbf{a}_{\infty}) \in \tau K^{\mathbf{m},1} \right] \right] \\ \geq \frac{\mathcal{N}(\mathbf{m}_0)}{\phi(\mathbf{m}_0)} \cdot [\mathrm{Pic}_{K^{\mathbf{m}}}^0 : G] \cdot \delta_{\mathcal{S}}[r^n]/3. $$

which finishes the proof. □

## 8. UNIFORM SAMPLING IN A BOX INTERSECTED WITH AN IDEAL LATTICE

### 8.1. Introduction.
In this section, we explain how one can efficiently sample in a (shifted) ideal lattice $x(\mathbf{b} + \gamma)$ intersected with a (partially positive) box, provided that the dimensions of the box are sufficiently large. More precisely, let $r > 0$ and let $r\mathcal{B}_{\infty}$ denote the box

$$ r\mathcal{B}_{\infty} := \{(x_{\sigma})_{\sigma} \in K_{\mathbb{R}} \mid |x_{\sigma}| \leq r, \forall \sigma\}. $$

Now, the box of interest is $r\mathcal{B}_{\infty} \cap \tau K_{\mathbb{R}}^{\mathbf{m}_{\infty}}$, whose coordinates at $\sigma$ have the same sign as $(\sigma(\tau))_{\sigma}$ for the real embeddings $\sigma | m_{\infty}$. Our aim of this section is to perfectly uniform sample from the intersection $r\mathcal{B}_{\infty} \cap \tau K_{\mathbb{R}}^{\mathbf{m}_{\infty}} \cap x(\mathbf{b} + \gamma)$.

The algorithm we use to sample uniformly in this box follows the framework described by Plançon and Prest in [63], and is very similar to their instantiation of that framework [63, Sec. 4.2]. The main two differences are that [63] analyzes the running time of their algorithm only heuristically, whereas here we provide a provable running time; also, [63] assumes perfect uniform samples from real intervals, whereas here we only rely on perfectly uniform bits.

**Technical idea of the algorithm.** The core idea of the algorithm applies to general lattices and relies on two observations. The first observation: for lattices $\Lambda$ satisfying $\Lambda \subseteq \frac{1}{N}\mathbb{Z}^n$ and sufficiently large, bounded convex sets $S \subseteq \mathbb{R}^n$, the task of uniformly sampling from $S \cap \Lambda$ reduces to uniformly sampling in $(1+c)S \cap \frac{1}{N}\mathbb{Z}^n$ for some constant $c > 0$, where we understand $(1+c) \cdot S := \{(1+c) \cdot s \mid s \in S\}$. Indeed, we can use a 'good' fundamental domain $F$ of $\Lambda$ to round a uniform sample of $(1+c) \cdot S \cap \frac{1}{N}\mathbb{Z}^n$ to a point in $\Lambda$. Since $(F+\ell) \cap \frac{1}{N}\mathbb{Z}^n$ contains the same number of elements for all $\ell \in \Lambda \cap S$ (since $\Lambda \subseteq \frac{1}{N}\mathbb{Z}^n$), this yields a perfect uniform distribution over $S \cap \Lambda$, if $c > 0$ is chosen adequately. This observation is formalized in Lemma 8.7.

The second observation is that each lattice $\Lambda$ given by a basis $B$ can be approximated by a lattice $\tilde{\Lambda}$ given by a basis $\tilde{B}$ that satisfies $\tilde{\Lambda} \subseteq \frac{1}{N}\mathbb{Z}^n$. Hence, by the first observation, one can perfectly uniformly sample from $\tilde{\Lambda} \cap S$ for suitable $S$. If
the approximation $\tilde{B} \approx B$ is good enough, one can transform this perfectly uniform sample from $\tilde{\Lambda} \cap S$ to a perfectly uniform sample from $\Lambda \cap S$. This observation is formalized in Proposition 8.8.

Note that in the first observation, a ‘good’ fundamental domain of the lattice is required. For such a fundamental domain, we need to know a sufficiently good basis of the ideal we want to sample from. We obtain such a basis by using one of the provable variants of the BKZ algorithm [67, 38, 32, 1]. Lemma 8.5 captures the end result of using a provable variant of the BKZ algorithm; for an in-depth proof of this lemma, we refer to Sections 26 to 28.

**Remark 8.1.** We note that this choice of basis reduction algorithm (BKZ) does not exploit the ideal structure of the lattice. There do exist algorithms that exploit the ideal structure [28, 62] and might outperform BKZ in some context. However, these algorithms are heuristic, require a quantum computer and/or some exponential pre-processing on the number field and in the case of [28] are restricted to cyclotomic number fields. Hence, we chose to use the BKZ algorithm here in order to obtain a non-heuristic algorithm. If one allows heuristics and quantum algorithms, it may be possible to diminish the block-size dependent quantity $b^b$ that appears in the running time of the basis reduction algorithm.

*Ray.* Actually, in this section, a slightly more general algorithm is described. In this more general algorithm, we sample elements from an intersection of a (shifted) ideal lattice $x(\mathfrak{b} + \gamma)$ and a box $r\mathcal{B}_\infty$, that also fall in the $\tau$-ray mod $\mathfrak{m}$, for some $\tau \in \mathcal{K}^m$.

That is, we will sample from $x((\mathfrak{b} + \gamma) \cap \tau \mathcal{K}^{m,1})$ intersected with $r\mathcal{B}_\infty$; those are the elements of the shape $x(\beta + \gamma)$ for which $\beta + \gamma \in \tau \mathcal{K}^{m,1}$ and $|x_\sigma \sigma(\beta + \gamma)| \le r$ for all embeddings $\sigma$. So, for the algorithm including the modulus $\mathfrak{m}$, the output additionally satisfies certain modular conditions depending on the modulus $\mathfrak{m}$.

One retrieves the simpler algorithm (without a modulus) that samples in $x(\mathfrak{b} + \gamma) \cap r\mathcal{B}_\infty$ by just putting $\mathfrak{m} = \mathcal{O}_K$ (so that $\tau \mathcal{K}^{m,1} = \mathcal{K}^{m,1} = \mathcal{K}^m = K^*$ for all $\tau \in \mathcal{K}^*$).

**8.2. On efficiently deciding whether an algebraic number is greater or equal to some rational number.** To be able to perfectly sample from an ideal lattice intersected with a box, one needs to be able to efficiently decide, for an algebraic number $\alpha \in \mathcal{K}$ in symbolic representation, whether $|\sigma(\alpha)| > r$ or $|\sigma(\alpha)| \le r$ (or, for real embeddings, whether $\sigma(\alpha) > r$ or $\le r$) for some rational $r \in \mathbb{Q}$ and embedding $\sigma$. Namely, the combined information over all places signifies whether the algebraic number $\alpha$ is inside some box $r\mathcal{B}_\infty$ or not.

The challenge in this question is that the algebraic number is given in some symbolic representation, like $\alpha = 408\sqrt{2} - 577(\approx -0.0008665)$. In order to decide, for example, whether $\alpha > 0$ or $\le 0$, we need to know *how well* to approximate this number (in this particular case at least up to 3 decimals).

The result of this section, in a nutshell, is that for any algebraic number $\alpha \in \mathcal{K}$ we can efficiently decide whether $|\sigma(\alpha)|$ (or $\sigma(\alpha)$ in the case of a real place) is larger than some rational $r \in \mathbb{Q}$ or not. This is proven in the following sequence of lemmas. The next lemma is coined Liouville’s lemma, since the technique comes from the tendency of algebraic numbers to avoid rationals, which was originally used to show the explicit existence of transcendental numbers (Liouville numbers).
**Lemma 8.2** (Louiville's lemma). Let $f(x) \in \mathbb{Z}[x]$ be a degree $n$ polynomial. Let $\omega \in \mathbb{R}$ be a real root of $f$. Then, if $\omega \notin \mathbb{Z}$, we have, for all $z \in \mathbb{Z}$,

$$|\omega - z| > [(n + 1)^3 \cdot 2^n \cdot (2 + \|f\|_{\infty})^n]^{-1} =: \mathfrak{A}(f).$$

*Proof.* Let $h$ $|$ $f$ be an irreducible factor of $f$ and let $\omega$ be a real root of $h(x) \in \mathbb{Z}[x]$. If $h$ is linear, $\omega = \frac{c}{d} \in \mathbb{Q}$, and by the rational root theorem, $d$ is an integer factor of the leading coefficient of $h$ (and thus of that of $f$). Hence, if $\omega \notin \mathbb{Z}$, we have $|\omega - z| \ge 1/d \ge 1/\|f\|_{\infty} > \mathfrak{A}(f)$ for every $z \in \mathbb{Z}$.

Assume now that $h$ is non-linear. By the mean value theorem, we have, for any $t \in [\omega - 1, \omega + 1]$,

$$|h(t)| = |h(t) - h(\omega)| \le \max_{t_0 \in [\omega-1, \omega+1]} |h'(t_0)| \cdot |t - \omega| \quad (51)$$

Additionally, for any integer $z \in \mathbb{Z}$, we have $|h(z)| \ge 1$, since $h(x) \in \mathbb{Z}[x]$ is irreducible and of degree $> 1$ (and hence cannot have integer roots). This immediately yields, for any integer $z \in \mathbb{Z}$,

$$|z - \omega| \ge \frac{|h(z)|}{\max_{x_0 \in [\omega-1, \omega+1]} |h'(x_0)|} \ge \left( \max_{x_0 \in [\omega-1, \omega+1]} |h'(x_0)| \right)^{-1} \quad (52)$$

$$\ge \left( \max_{h|f} \max_{\omega \text{ root of } h} \max_{x_0 \in [\omega-1, \omega+1]} |h'(x_0)| \right)^{-1} \quad (53)$$

where, in the last line, the first maximum is over all divisors of $f$ (also the possible linear ones) and the second maximum is over all real roots. We now aim to find a easy-to-compute lower bound on Equation (53), which we call $\mathfrak{A}(f)$, in terms of the coefficients of $f$ alone, using the Landau-Mignotte bound [75, Theorem 6.32] and Cauchy's bound [26, Section 3.6].

By the triangle inequality, writing $h(x) = \sum_{j=0}^{\deg(h)} h_j \cdot x^j$, $\|h\|_{\infty} = \max_j |h_j|$ and $\|f\|_{\infty} = \max_j |f_j|$, we can deduce

$$\begin{aligned}
\max_{x_0 \in [\omega-1, \omega+1]} |h'(x_0)| &\le \sum_{j=1}^{\deg(h)} j \cdot |h_j| \cdot \max_{x_0 \in [\omega-1, \omega+1]} |x_0|^{j-1} \\
&\le \deg(h)^2 \cdot \|h\|_{\infty} \cdot \max_{x_0 \in [\omega-1, \omega+1]} |x_0|^{\deg(h)-1} \\
&\le \deg(h)^2 \cdot \|h\|_{\infty} \cdot (|\omega| + 1)^{\deg(h)-1} \\
&\le n^2 \cdot (n+1) \cdot 2^n \cdot \|f\|_{\infty} \cdot (|\omega| + 1)^{n-1} \quad \text{(Landau-Mignotte bound)} \\
&\le n^2 \cdot (n+1) \cdot 2^n \cdot \|f\|_{\infty} \cdot (2 + \|f\|_{\infty})^{n-1} \quad \text{(Cauchy's bound)} \\
&< (n+1)^3 \cdot 2^n \cdot (2 + \|f\|_{\infty})^n = \mathfrak{A}(f)^{-1}.
\end{aligned}$$

where we recall that $n = \deg(f) \ge \deg(h)$. Thus, for any $z \in \mathbb{Z}$ and any real root $\omega$ of $f$ satisfying $\omega \notin \mathbb{Z}$, we have

$$|\omega - x| \ge \mathfrak{A}(f) = [(n + 1)^3 \cdot 2^n \cdot (2 + \|f\|_{\infty})^n]^{-1}. \quad (54) \quad \square$$

**Corollary 8.3.** There exists an algorithm that, given as input a degree $n$ polynomial $f(x) \in \mathbb{Z}[x]$ and some rational $r \in \mathbb{Q}$, decides whether the roots $\omega_i \in \mathbb{C}$ of $f(x)$ satisfy $|\omega_i| > r$ or $|\omega_i| \le r$ for complex roots $\omega_i$, respectively, $\omega_i > r$ or $\omega_i \le r$ for
real roots $\omega_i$. The running time of the algorithm is polynomial in the size of $f(x)$ and $r$.

*Proof.* Denote $r = \frac{a}{b} \in \mathbb{Q}$. We replace the roots $\omega_i$ by $b \cdot \omega_i$, the polynomial $f(x)$ by $b^n \cdot f(b^{-1} \cdot x)$ and the rational $r$ by $a \in \mathbb{Z}$. Hence, we may without loss of generality assume that $r \in \mathbb{Z}$, with the expense of an increase in the size of the polynomial $f$ by $n \cdot \text{size}(r)$.

We start with the case of a real root $\omega$ of $f$, and we then proceed with the case of a complex root.

**Real root case.**

According to Lemma 8.2, we have for any real but non-integral root $\omega$ of $f(x)$ and any $z \in \mathbb{Z}$, $|\omega - z| > \mathfrak{A}(f)$. This lower bound gives us means to decide whether a real root of $f$ is larger (or equal) or smaller than some integer. Namely, approximate the real roots of $f$ within precision $< \mathfrak{A}(f)/2 = [(n+1)^3 \cdot (2 + \|f\|_{\infty})^n]^{-1/2}$, which can be done in time $\text{poly}(n, \log \|f\|_{\infty}) = \text{poly}(n, \text{size}(f), \text{size}(r))$. Denote the approximations of these real roots by $\tilde{\omega}_i \approx \omega_i$. There are two cases:

* $|\tilde{\omega}_i - z| < \mathfrak{A}(f)/2$ for some integer $z \in \mathbb{Z}$. In that case, $\omega_i = z$. Indeed, if $\omega_i$ were not an integer, we must have

$$ \mathfrak{A}(f) \leq |\omega_i - z| \leq |\omega_i - \tilde{\omega}_i| + |\tilde{\omega}_i - z| < \mathfrak{A}(f), $$

which is a contradiction. Hence, $\omega_i$ is an integer and equal to $z \in \mathbb{Z}$. In such case, deciding whether $|\omega_i| > r$ or $\leq r$ is easily and efficiently done.

* $|\tilde{\omega}_i - z| \geq \mathfrak{A}(f)/2$ for all $z \in \mathbb{Z}$. Then, by the triangle inequality, we have $\omega_i \notin \mathbb{Z}$, since, for all $z \in \mathbb{Z}$,

$$ |\omega_i - z| \geq \underbrace{|\tilde{\omega}_i - z|}_{\geq \mathfrak{A}(f)/2} - \underbrace{|\omega_i - \tilde{\omega}_i|}_{< \mathfrak{A}(f)/2} > 0. $$

Hence, by Lemma 8.2, $|\omega_i - z| \geq \mathfrak{A}(f)$ for any integer $z \in \mathbb{Z}$. We claim that $\tilde{\omega}_i > r$ if and only if $\omega_i > r$. That is, by using the approximation $\tilde{\omega}_i$, we can decide whether $\omega_i > r$ or $\leq r$.

Indeed, suppose (as to achieve a contradiction) that $\omega_i \leq r$ but $\tilde{\omega}_i > r$. Then, since $|\omega_i - r| \geq \mathfrak{A}(f)$, and thus $r - \omega_i \geq \mathfrak{A}(f)$.

$$ \underbrace{r - \omega_i}_{\geq \mathfrak{A}(f)} = \underbrace{(r - \tilde{\omega}_i)}_{\leq 0} + \underbrace{\frac{(\omega_i - \tilde{\omega}_i)}{-\mathfrak{A}(f)/2, \mathfrak{A}(f)/2}}_{\in [-\mathfrak{A}(f)/2, \mathfrak{A}(f)/2]} \leq \mathfrak{A}(f)/2 $$

which is a contradiction. The other case ($\omega_i > r$ but $\tilde{\omega}_i \leq r$) can be excluded similarly.

**Complex root case.**

For the complex root case, we take the companion matrix $M_f$ of $f = \sum_{j=0}^{n} f_j x^j$. This $n \times n$ matrix $M_f$ is defined by $(M_f)_{j+1,j} = 1$ for $j \in \{1, \dots, n-1\}$ and $(M_f)_{j,n} = -f_{j-1}/f_n$ for $j \in \{1, \dots, n\}$ (this is the companion matrix of the monic polynomial $f_n^{-1} \cdot f(x)$). It is known that $M_f$ has the roots $\omega_i$ of $f$ as eigen values. Therefore, the matrix resulting from the Kronecker product $M_f \otimes M_f$ has all products $\omega_i \omega_j$ ($i, j \in \{1, \dots, n\}$) as eigen values, in particular the square absolute values $|\omega_i|^2$ for all original roots of $f$.

Computing the characteristic polynomial of $M_f \otimes M_f$, and clearing denominators of that polynomials yields the $n^2$-degree integer polynomial $g(x) \in \mathbb{Z}[x]$. Identifying the roots of $g$ that are the square absolute values of those of $f$ (by approximating
the roots of both), one can apply the same technique as in the real root case to decide whether $|\omega_i|^2 > r^2$ or not.

It remains to be shown that the polynomial $g$ is polynomially bounded in size by the size of $f$, so that all operations can be done in polynomial time in size($f$) and size($r$). The $j$-th coefficient $p_j$ of the characteristic polynomial $p(x)$ of $M_f \otimes M_f$ can be computed (up to sign) by taking the sum of all $\binom{n^2}{j}$ principal minors of $M_f \otimes M_f$ of size $j$ [41, §1.2, Equation (1.2.13)]. By Hadamard's bound, each of these principal minors has size at most $\|f\|_{\infty}^{2j}$ and can only have a denominator that is a divisor of $f_n^{2j}$. Hence, $f_n^{2n} \cdot p(x)$ must be a multiple of $g(x)$. This means that $\|g\|_{\infty} \le \|p\|_{\infty} \le (n^2)! \|f\|_{\infty}^{2n}$. Hence, $\text{size}(g) \le \text{poly}(n, \text{size}(f))$, which was to be demonstrated. $\square$

**Corollary 8.4.** There exist an algorithm that on input a degree $n$ number field $K = \mathbb{Q}(\theta)$, an ideal **b**, an element $x = (x_\sigma)_\sigma \in K_\mathbb{R}^\times$ represented by rational numbers, an element $\alpha \in \mathfrak{b}$ represented by the $\mathbb{Q}$-basis of $K$ (the power-basis formed by $\theta$), a rational $g \in \mathbb{Q}$ and an integer $k \in \mathbb{Z}_{>0}$, decides whether $x_\sigma|\sigma(\alpha)| > g^{1/k}$ or $x_\sigma|\sigma(\alpha)| \le g^{1/k}$, for every complex embedding $\sigma$; and decides whether $x_\sigma\sigma(\alpha) > g^{1/k}$ or $x_\sigma\sigma(\alpha) \le g^{1/k}$, for every real embedding $\sigma$. Moreover, this algorithm runs in time poly(size($\alpha$), size($x$), size($\mathfrak{b}$), size($g$), $n$, $\log|\Delta_K|$, $k$).

*Proof.* Throughout this paper we assume that the polynomial $f$ defining the number field $K$ satisfies $\text{size}(f) \le \text{poly}(\log|\Delta_K|)$ (see Section 2.6). As $x_\sigma|\sigma(\alpha)| > g^{1/k}$ is equivalent to $|\sigma(\alpha^k)| > g/x_\sigma^k$ (with a possible sign change), we can reduce this result to that of Corollary 8.3.

The sole challenge is to find and bound the polynomial of which $\alpha^k$ is a root. For this we start by bounding the polynomial for which $\alpha \in \mathfrak{b}$ is a root. Write down the multiplication matrix of $\alpha$ in the $\theta$-basis. That is, the matrix defined by the coefficients $q_{ij}$ occurring in the identities $\alpha\theta^j = \sum_{i=0}^{n-1} q_{ij}\theta^i$ for $j \in \{0, \dots, n-1\}$. Then the characteristic polynomial of this matrix is one of which $\alpha \in \mathfrak{b}$ must be a root.

The size of the multiplication matrix of $\alpha$ is bounded by $\text{poly}(\text{size}(\alpha), \text{size}(f)) = \text{poly}(\text{size}(\alpha), \log|\Delta_K|)$. Hence, the size of the characteristic polynomial (whose $j$-th coefficient can be shown to be the sum of all principal minors of size $j$ of the multiplication matrix, which can be bounded by Hadamard's bound) must be polynomially bounded in size($\alpha$), $\log|\Delta_K|$ and $n$ as well. By a very similar reasoning, the size of the characteristic polynomial of $\alpha^k$ must be $\text{poly}(n, \log|\Delta_K|, \text{size}(\alpha), k)$. By applying Corollary 8.3, we obtain the final result. $\square$

### 8.3. Lattice reduction.
Being able to successfully sample in an ideal lattice intersected with a box largely depends on the maximum vector length (i.e., the quality) of the basis of the ideal lattice compared to the dimensions of the box. If these dimensions of the box are somewhat larger than the basis vectors, this sampling can be done efficiently. For the applications and algorithms of the present work, we generally require the dimensions of this box to be as small as possible, since this benefits their complexity. As a consequence, we would like to obtain a basis of the ideal lattice with as small as possible maximum vector length (i.e., best basis quality), but without paying too much time.

The standard algorithm for finding lattice bases of good quality is the Block Korinek Zolotarev (BKZ) algorithm, which allows for a controllable trade-off between the output basis quality and the heuristic run time. Unfortunately, no published
versions of the BKZ-algorithm exist that have a provable run-time, which is what we require in the present work (as our end goal is an algorithm with a provable run-time). Hence, Sections 26 to 28 of this paper is devoted to showing that there exists a variant of the BKZ-algorithm with the same trade-off between output basis quality and run time as the textbook version, but in which the run time is actually proven and non-heuristic.

The proof of this result requires both careful numerical analysis (for the ideal lattice case) and precise monitoring of the sizes ('potential') of the bases occurring intermediately in the algorithm. To stay relevant with the current topic, this proof is therefore postponed to Part 3. The overall result can be summarized in the following lemma.

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

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

$$ \|x \cdot \alpha_i\| \le 2n \cdot b^{2n/b} \cdot \lambda_n(x \cdot a), $$

using time at most $T = \text{poly}(b^b, \text{size}(a), \log |\Delta_K|, \text{size}(x))$.

*Proof.* The proof can be found in Section 28.6. $\square$

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

## 8.4. Perfectly uniform sampling in a bounded convex set intersected with a lattice.

**Notation 8.6.** We denote $B_r = \{x \in \mathbb{R}^n \mid \|x\| < r\}$. For any bounded convex set $S \subset \mathbb{R}^n$ and $c \in \mathbb{R}_{>0}$, we denote $cS := \{c \cdot s \mid s \in S\}$. For a basis $\mathbf{B} = (\mathbf{b}_1, \dots, \mathbf{b}_n)$ of $\mathbb{R}^n$, we denote $\mathcal{L}(\mathbf{B}) = \mathbf{B}\mathbb{Z}^n := \{\sum_{i=1}^n \mathbf{b}_i z_i \mid z_i \in \mathbb{Z} \text{ for all } i\}$ (which is a lattice).

**Lemma 8.7.** Let $\mathbf{B} = (\mathbf{b}_1, \dots, \mathbf{b}_n)$ with $\mathbf{b}_i \in \frac{1}{N}\mathbb{Z}^n$ be a basis, let $D = \sum_i \|\mathbf{b}_i\|$, let $U, c, \varepsilon \in \mathbb{R}_{>0}$ such that $c > \varepsilon > 0$. Suppose $S$ is a convex set satisfying $B_{D/\varepsilon} \subseteq S \subseteq B_U$ for which we can perfectly uniformly sample in $(c+\varepsilon)S \cap \frac{1}{N}\mathbb{Z}^n$ within expected time $T$. Additionally, suppose we can efficiently decide membership in $cS$.

Then we can perfectly uniformly sample in $cS \cap \mathbf{B}\mathbb{Z}^n$ within time $\text{poly}(T, \text{size}(\mathbf{B}))$, $\log U, \log N)$ with success probability lower bounded by

$$ \frac{|(c - \varepsilon)S \cap \frac{1}{N}\mathbb{Z}^n|}{|(c + \varepsilon)S \cap \frac{1}{N}\mathbb{Z}^n|} \qquad (55) $$

*Proof.* (Algorithm description) Sample a perfectly uniform $u \in (c+\varepsilon)S \cap \frac{1}{N}\mathbb{Z}^n$. Compute $v = \mathbf{B}^{-1}u$ (which can be done in time $\text{poly}(T, \text{size}(\mathbf{B}), \log U)$) and put $w_i = \lfloor v_i \rfloor$, rounding to the nearest integer. Output $\mathbf{B}w$ if $\mathbf{B}w \in cS$, otherwise output 'failure'.

(Analysis) We will prove that this procedure yields a perfectly uniform sample in $\mathbf{B}\mathbb{Z}^n \cap cS$ and that the success probability of a single iteration is lower bounded by the quantity in Equation (55).

For a fixed $\mathbf{b} \in (\mathbf{B}\mathbb{Z}^n) \cap cS$, the probability that $\mathbf{b}$ is outputted is proportional to the number $|(\mathbf{b} + \mathbf{B} \cdot [-\frac{1}{2}, \frac{1}{2})^n) \cap (c + \varepsilon)S \cap \frac{1}{N}\mathbb{Z}^n|$. We have $\mathbf{b} \in cS$; and each $\mathbf{x} \in \mathbf{B} \cdot [-\frac{1}{2}, \frac{1}{2})^n$ satisfies $\|\mathbf{x}\| \le D/2 \le D$, hence $\mathbf{x} \in B_D \subseteq \varepsilon \cdot S$ (since $B_{D/\varepsilon} \subseteq S$).
So, we obtain that $\mathbf{b} + \mathbf{B} \cdot [-\frac{1}{2}, \frac{1}{2})^n \subseteq (c + \varepsilon)S$ by the convexity of $S$. Therefore

$$|(\mathbf{b} + \mathbf{B} \cdot [-\frac{1}{2}, \frac{1}{2})^n) \cap (c + \varepsilon)S \cap \frac{1}{N}\mathbb{Z}^n| = |(\mathbf{b} + \mathbf{B} \cdot [-\frac{1}{2}, \frac{1}{2})^n) \cap \frac{1}{N}\mathbb{Z}^n| \\ = N^n \det(\mathbf{B}),$$

for all $\mathbf{b} \in (\mathbf{B}\mathbb{Z}^n) \cap S$. Note that this relies critically on $\frac{1}{N}\mathbb{Z}^n \subseteq \mathbf{B}\mathbb{Z}^n$. So the sampling probability is the same for all $\mathbf{b} \in (\mathbf{B}\mathbb{Z}^n) \cap cS$, which is the property of a perfect uniform distribution. It remains to show that the probability of success (a sample in $\mathbf{B}\mathbb{Z}^n \cap cS$) is lower bounded.

If the initial uniform sample $u$ satisfies $u \in (c - \varepsilon)S \cap \frac{1}{N}\mathbb{Z}^n$, then $\mathbf{B}w = \mathbf{B}[\mathbf{B}^{-1}u] = u + y$ for some $y \in \mathbf{B}[-\frac{1}{2}, \frac{1}{2})^n \subseteq \varepsilon S$ (where we mean with $\lfloor \cdot \rfloor$ that every coordinate is rounded to the nearest integer). For such $u$ holds that $u + y$ must lie in $cS$. Therefore, the success probability is lower bounded by $\frac{|(c-\varepsilon)S \cap \frac{1}{N}\mathbb{Z}^n|}{|(c+\varepsilon)S \cap \frac{1}{N}\mathbb{Z}^n|}$. $\square$

In our context, the basis $\mathbf{B}_b$ of an ideal lattice $\mathbf{b}$ (as embedded in the Minkowski space) cannot be represented by rational numbers, but is rather symbolically represented. In the following proposition we show that this is not a real complication; namely, it is enough to be able to compute a sufficiently good rational approximation $\mathbf{C} \approx \mathbf{B}_b$ in order to be able to perfectly uniformly sample in this lattice $\mathbf{b}$ intersected with a certain convex set $S$.

As a consequence, the algorithm of the following proposition takes as an input a sufficiently good approximation $\mathbf{C}$ of $\mathbf{B}$ and uses only this rational matrix $\mathbf{C}$ to compute with. To be able to check whether an element of the lattice $\mathbf{B}\mathbb{Z}^n$ lies in the convex set $S$ or not, an auxiliary oracle is needed. In our use-case, this oracle can be implemented by using the results of Section 8.2.

**Proposition 8.8.** Let $\mathbf{B} = (\mathbf{b}_1, \dots, \mathbf{b}_n)$ with $\mathbf{b}_i \in \mathbb{R}^n$ be a basis of lattice $\Lambda$ and let $D = 2 \sum_i \|\mathbf{b}_i\|$.

(1) Let $t \in \mathbb{R}^n$ satisfying $\|t\| < U$ for some $U \in \mathbb{R}_{>0}$.

(2) Let $N \in \mathbb{Z}_{>0}$ satisfying $\frac{n}{N} \le D$ and let $\mathbf{C} \in \frac{1}{N}\mathbb{Z}^n$ be an approximation of $\mathbf{B}$ satisfying $\|\mathbf{C} - \mathbf{B}\| \le \|\mathbf{B}^{-1}\|^{-1} \cdot D/U$ and $\sum_i \|\mathbf{c}_i\| \le D$.

(3) Let $\tilde{t} \in \frac{1}{N}\mathbb{Z}^n$ an approximation of $t \in \mathbb{R}^n$ satisfying $\|t - \tilde{t}\|_{\infty} \le \frac{1}{2N}$ and $\|\tilde{t}\| < 2U$.

(4) Let $1/5 > \varepsilon > 0$ and let $S \subseteq \mathbb{R}^n$ be a convex set satisfying $B_{D/\varepsilon} \subseteq S \subseteq B_U$.

(5) Suppose we can perfectly uniformly sample in $(1 + 4\varepsilon)S \cap \frac{1}{N}\mathbb{Z}^n$ within expected time $T$.

(6) Additionally, suppose we have an oracle $O_{\mathbf{B}}$ that can decide, on input $v \in \mathbb{Z}^n$, whether $\mathbf{B}v \in S + t$ or not.

Then we can sample $v \in \mathbb{Z}^n$ such that $\mathbf{B}v$ is perfectly uniformly distributed in $(S+t) \cap \mathbf{B}\mathbb{Z}^n$, within expected time $\text{poly}(T, \text{size}(\mathbf{C}), \log U, \log N)$, using a single call to $O_{\mathbf{B}}$, and with success probability lower bounded by

$$\frac{|(1 - 5\varepsilon)S \cap \frac{1}{N}\mathbb{Z}^n|}{|(1 + 5\varepsilon)S \cap \frac{1}{N}\mathbb{Z}^n|}$$

**Proof. (Algorithm description)**

(1) We start with processing the shift $t \in \mathbb{R}^n$. We use the approximation $\tilde{t} \in \frac{1}{N}\mathbb{Z}^n$ that satisfies $\|t - \tilde{t}\|_{\infty} \le \frac{1}{2N} \le D/(2n)$ and hence $\|t - \tilde{t}\|_2 \le D/2$. We compute $w_0 = \lfloor \mathbf{C}^{-1}\tilde{t} \rfloor$ (where $\lfloor \cdot \rfloor$ means that each component is rounded to the nearest
integer).

(2) Imitate the approach in Lemma 8.7, (taking $c = 1 + 3\epsilon$) by sampling $u \in \frac{1}{N}\mathbb{Z}^n \cap (1 + 4\epsilon)S$ and computing $\mathbf{c} = \mathbf{C}[\mathbf{C}^{-1}u]$ until $\mathbf{c} \in (1 + 3\epsilon)S$. By the exact same reasoning as in Lemma 8.7, one then obtains a perfectly uniform sample $\mathbf{c} \in \mathbf{C} \cdot \mathbb{Z}^n \cap (1 + 3\epsilon)S$.

(3) We compute $v = \mathbf{C}^{-1}\mathbf{c} = [\mathbf{C}^{-1}u]$ and we output $v+w_0 \in \mathbb{Z}^n$ if $\mathbf{B}(v+w_0) \in S+t$ (using the oracle $O_B$). Otherwise output ‘failure’.

(Analysis) In this analysis we will denote $\mathbf{b} = \mathbf{B}v, \mathbf{b}_0 = \mathbf{B}w_0, \mathbf{c} = \mathbf{C}v$ and $\mathbf{c}_0 = \mathbf{C}w_0$. We will first show that the output $v+w_0 \in \mathbb{Z}^n$ has the property that $\mathbf{B}(v+w_0)$ is perfectly uniformly distributed in $\mathbf{B}\mathbb{Z}^n \cap (S+t)$. We will finish the proof with a lower bound on the success probability and a run time analysis.

By Lemma 8.7, we know that $v+w_0$ has the property that $\mathbf{C}(v+w_0) = \mathbf{c}+\mathbf{c}_0$ is perfectly uniform in $\mathbf{C}\mathbb{Z}^n \cap [(1+3\epsilon)S+\mathbf{c}_0]$. Hence $\mathbf{B}(v+w_0) = \mathbf{B}\mathbf{C}^{-1}(\mathbf{c}+\mathbf{c}_0)$ is perfectly uniform in $\mathbf{B}\mathbb{Z}^n \cap [\mathbf{B}\mathbf{C}^{-1}(1+3\epsilon)S+\mathbf{b}_0]$. So, since we reject those $v+w_0$ for which $\mathbf{B}(v+w_0) \notin S+t$, it is sufficient to show that $S+t \subset \mathbf{B}\mathbf{C}^{-1}(1+3\epsilon)S+\mathbf{b}_0$. This is equivalent to $\mathbf{C}\mathbf{B}^{-1}(S+t) \subset (1+3\epsilon)S+\mathbf{c}_0$ which is in turn equivalent to $\mathbf{C}\mathbf{B}^{-1}(S+t) - \mathbf{c}_0 \subset (1+3\epsilon)S$. To show this, take an arbitrary $s \in S$, and put

$$ \mathbf{C}\mathbf{B}^{-1}(s+t) - \mathbf{c}_0 = s + t - \mathbf{c}_0 + (\mathbf{C}\mathbf{B}^{-1} - I)s + (\mathbf{C}\mathbf{B}^{-1} - I)t. \quad (56) $$

We will now show that $\|t-\mathbf{c}_0\| \le D$, $\|(\mathbf{C}\mathbf{B}^{-1}-I)s\| \le D$ and $\|(\mathbf{C}\mathbf{B}^{-1}-I)t\| \le D$, so that the right-hand side of Equation (56) lies in $S \boxplus B_{3D} \subseteq S \boxplus (3\epsilon)S = (1+3\epsilon)S$ (where $\boxplus$ denotes the Minkowski sum). We have $\|t-\mathbf{c}_0\| \le \|t-\tilde{t}\| + \|\tilde{t}-\mathbf{c}_0\| \le D/2 + D/2$ since $\|t-\tilde{t}\| \le D/2$ by construction and $\tilde{t}-\mathbf{c}_0 = \tilde{t}-\mathbf{C}[\mathbf{C}^{-1}\tilde{t}] = \tilde{t}-\mathbf{C}(\mathbf{C}^{-1}\tilde{t}+u) = \mathbf{C}u$ with $u \in [-1/2, 1/2)^n$. Hence $\|\tilde{t}-\mathbf{c}_0\| = \|\mathbf{C}u\| \le D/2$, by assumption. Using the properties of matrix norms, we obtain $\|(\mathbf{C}\mathbf{B}^{-1}-I)\| = \|(\mathbf{C}-\mathbf{B})\mathbf{B}^{-1}\| \le \|\mathbf{C}-\mathbf{B}\|\|\mathbf{B}^{-1}\| \le D/U$. Combining this with the assumptions $\|s\| \le U$ and $\|t\| \le U$, we obtain that all the summands' norms are bounded by $D$.

(Success probability) For the success probability, note that, if $u \in \frac{1}{N}\mathbb{Z}^n$ from step (2) of the algorithm description were to be in $(1-5\epsilon)S$, a similar reasoning as above shows that, for $v = [\mathbf{C}^{-1}u]$, we surely have $\mathbf{c} = \mathbf{C}v \in (1-4\epsilon)S$.

We have, by the Neumann series of $(I-(I-\mathbf{C}^{-1}\mathbf{B}))^{-1}$, noting that $\|I-\mathbf{C}^{-1}\mathbf{B}\| \le D/U \le \epsilon < 1/5$,

$$ \|\mathbf{B}\mathbf{C}^{-1} - I\| = \|(I - (I - \mathbf{C}^{-1}\mathbf{B}))^{-1} - I\| = \left\| \sum_{j=1}^{\infty} (I - \mathbf{C}^{-1}\mathbf{B})^j \right\| \le \sum_{j=1}^{\infty} \|I - \mathbf{C}^{-1}\mathbf{B}\|^j \\ \le \frac{5}{4}D/U. $$

Hence, by similar computations as above, we can bound the norms of the following summands:

$$ \mathbf{B}(v+w_0) = \mathbf{B}\mathbf{C}^{-1}(\mathbf{c}+\mathbf{c}_0) - t \\ = \mathbf{c} + \underbrace{(\mathbf{B}\mathbf{C}^{-1}-I)\mathbf{c}}_{\le \frac{5}{4}D} + \underbrace{(\mathbf{B}\mathbf{C}^{-1}-I)t}_{\le \frac{5}{4}D} + \underbrace{(\mathbf{B}\mathbf{C}^{-1}-I)(\mathbf{c}_0-t)}_{\le \frac{5}{4}D^2/U \le D/4} + \underbrace{\mathbf{c}_0-t}_{\le D}. $$

So, since $\mathbf{c} = \mathbf{C}v \in (1-4\epsilon)S$ and all the other summands together have norm at most $4D$ and their sum thus lies in $B_{4D} \subseteq 4\epsilon S$, we see that $\mathbf{B}(v+w_0) \in (1-4\epsilon)S \boxplus 4\epsilon S \subseteq S$.
Therefore, the success probability of the entire procedure is lower bounded by
$$ \frac{|(1-5\epsilon)S \cap \frac{1}{N} \mathbb{Z}^n|}{|(1+4\epsilon)S \cap \frac{1}{N} \mathbb{Z}^n|} \ge \frac{|(1-5\epsilon)S \cap \frac{1}{N} \mathbb{Z}^n|}{|(1+5\epsilon)S \cap \frac{1}{N} \mathbb{Z}^n|}. $$

(Run time analysis) Note that the additional running time of this algorithm compared to Lemma 8.7 is caused by the (possible) extra computations on $\tilde{t} \in \frac{1}{N}\mathbb{Z}^n$ (which satisfies $\|\tilde{t}\| \le 2U$, which can be at most poly(size($C$), log $U$, log $N$)). The dependency on $n$ is hidden in size($C$). $\square$

**Notation 8.9.** We define $\phi: \prod_{\sigma} \mathbb{Z} \hookrightarrow K_{\mathbb{R}}$, $(n_{\sigma})_{\sigma} \mapsto (x_{\sigma})_{\sigma}$ by putting

$$ \left\{ \begin{array}{ll} x_{\sigma_{\nu}} = n_{\sigma_{\nu}} + i n_{\sigma_{\bar{\nu}}} & \text{if } \nu \text{ is complex} \\ x_{\sigma_{\bar{\nu}}} = n_{\sigma_{\bar{\nu}}} - i n_{\sigma_{\bar{\nu}}} & \text{if } \bar{\nu} \text{ is complex} \\ x_{\sigma_{\nu}} = n_{\sigma_{\nu}} & \text{if } \nu \text{ is real} \end{array} \right. \qquad (57) $$

Abusing notation, we will just denote $\mathbb{Z}^n$ or $\prod_{\sigma} \mathbb{Z}$ for $\phi(\prod_{\sigma} \mathbb{Z})$.

**Corollary 8.10.** Let $K$ be a degree $n$ number field, let $x \in K_{\mathbb{R}}^{\times}$ be represented by rational numbers, let $\mathfrak{b} \in \mathcal{I}_K$ be an ideal and let $\mathfrak{m} = \mathfrak{m}_0\mathfrak{m}_{\infty}$ be a modulus. 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}(x\mathfrak{b}\mathfrak{m}_0)^{1/n}$. Let $\mathbf{B}_{\mathfrak{b}\mathfrak{m}_0} = (\mathfrak{b}_1, \dots, \mathfrak{b}_n)$ with $\mathfrak{b}_j \in K_{\mathbb{R}}$ (i.e., in the Minkowski space) be a basis of $\mathfrak{b}\mathfrak{m}_0$ satisfying

$$ \|x \cdot \mathfrak{b}_i\| \le 2n \cdot \mathfrak{b}^{2n/\mathfrak{b}} \cdot \lambda_n(x \cdot \mathfrak{b} \cdot \mathfrak{m}_0) $$

Let $\tau \in K^{\mathfrak{m}}$ satisfying $\|x\tau\| \le r$. Then we can perfectly uniformly sample from

$$ x(\mathfrak{b}\mathfrak{m}_0 + \tau) \cap r\mathcal{B}_{\infty}^{\tau}. $$

within expected time poly($n, \log |\Delta_K|, \text{size}(\mathfrak{b}), \text{size}(\mathfrak{m}), \text{size}(x), \text{size}(\omega)$)

*Proof.* We apply Proposition 8.8. For this, we need to satisfy all requirements (1) - (6) in Proposition 8.8. We start with (1) and (4), then proceed with (2), (3), (5) and (6). Note that Proposition 8.8 only outputs some $v \in \mathbb{Z}^n$, but because the elements in $x(\mathfrak{b}\mathfrak{m}_0 + \tau)$ can be symbolically represented, we will see that such an output $v = (v_1, \dots, v_n) \in \mathbb{Z}^n$ can be converted into $x \sum_{j=1}^n \beta_j v_j + x\tau$ where $\beta_j \in K$ is the element in $\mathfrak{b}\mathfrak{m}_0$ associated with the basis element $\mathfrak{b}_j$.

**Requirements (1) and (4).** Since a uniform sample from $x(\mathfrak{b}\mathfrak{m}_0 + \tau) \cap r\mathcal{B}_{\infty}^{\tau}$ can be simply obtained by taking a uniform sample of $x\mathfrak{b}\mathfrak{m}_0 \cap (r\mathcal{B}_{\infty}^{\tau} - x\tau)$ and adding $x\tau$ afterwards, we concentrate on taking a uniform sample from this latter set. Recall that

$$ r\mathcal{B}_{\infty}^{\tau} = \{(x_{\sigma})_{\sigma} \in K_{\mathbb{R}} \mid |x_{\sigma}| \le r \text{ and } x_{\sigma}/\sigma(\tau) > 0 \text{ for real } \sigma \mid \mathfrak{m}\}. $$

Hence we can write $r\mathcal{B}_{\infty}^{\tau} = (r'_{\sigma})_{\sigma}\mathcal{B}_{\infty} + t' = S + t'$ with $r'_{\sigma} = r/2$ for real $\sigma \mid \mathfrak{m}_{\infty}$ and $r'_{\sigma} = r$ otherwise, and $t'_{\sigma} = r/2$ for real $\sigma \mid \mathfrak{m}_{\infty}$ and $t'_{\sigma} = 0$ otherwise; and $S = (r'_{\sigma})\mathcal{B}_{\infty}$ (which is a convex set). Then, putting $t := t' - x\tau$, we have

$$ r\mathcal{B}_{\infty}^{\tau} - x\tau = S + t' - x\tau = S + t $$

Note that $\|x \cdot \mathfrak{b}_i\| \le r/(24n^2)$ (by the definition of $r$ and Lemma 2.13(ii) and (iv); see also Equation (61)). Hence, writing $D = 2 \sum_i \|x \cdot \mathfrak{b}_i\| \le r/(12n)$, we see that $B_{6nD} \subseteq B_{r/2} \subseteq S \subseteq B_r$ and $\|t\|_{\infty} \le \|t'\| + \|x\tau\| \le 2nr$. So, taking $\epsilon := 1/(6n)$ and $U := 2nr$ satisfies the requirements (1) and (4) of Proposition 8.8.

**Requirement (2) and (3).** Let us first compute an upper bound on $U/D$. We have (see Lemma 2.13) $\lambda_1(x\mathfrak{m}_0\mathfrak{b}) \ge \sqrt{n}\mathcal{N}(x\mathfrak{m}_0\mathfrak{b})^{1/n}$ and hence $D \ge 2n^{3/2}\mathcal{N}(x\mathfrak{m}_0\mathfrak{b})^{1/n}$.
Hence, since $U = 2nr$, and $\mathbf{b}^{1/\mathbf{b}} \le e^{1/e}$,

$$ U/D \le \frac{(2 \cdot n) \cdot 48 \cdot \omega \cdot \mathbf{b}^{2n/\mathbf{b}} \cdot n^{7/2} \cdot |\Delta_K|^{\frac{3}{2n}} \cdot \mathcal{N}(x\mathbf{b}\mathbf{m}_0)^{\frac{1}{n}}}{2n^{3/2} \cdot \mathcal{N}(x\mathbf{m}_0\mathbf{b})^{1/n}} = 48 \cdot \omega \cdot e^{2n/e} \cdot n^3 \cdot |\Delta_K| \quad (58) $$

We need to (efficiently) approximate $\mathbf{C} \in \frac{1}{N}\mathbb{Z}^n$ with $\|\mathbf{C} - \mathbf{B}\| \le \|\mathbf{B}^{-1}\|^{-1} \cdot D/U$, with $\mathbf{B} = x\mathbf{B}_{\mathbf{b}\mathbf{m}_0}$. For that it is sufficient$^7$ to choose $N \ge n \cdot \|\mathbf{B}^{-1}\| \cdot U/D$. Using Lemma 24.2, noting that $\lambda_n(x \cdot \mathbf{b} \cdot \mathbf{m}_0)/\lambda_1(x \cdot \mathbf{b} \cdot \mathbf{m}_0) \le |\Delta_K|^{1/n}$ (see Lemma 2.13) and $\mathbf{b}^{1/\mathbf{b}} \le e^{1/e}$, we obtain

$$ \begin{aligned} \|\mathbf{B}^{-1}\| & \le n^{n/2+1} \lambda_1(x\mathbf{b}\mathbf{m}_0) \cdot \left( \prod_{j=1}^{n} \frac{2n \cdot \mathbf{b}^{2n/\mathbf{b}} \cdot \lambda_n(x \cdot \mathbf{b} \cdot \mathbf{m}_0)}{\lambda_j(x\mathbf{b}\mathbf{m}_0)} \right) \\ & \le n^{n/2+1} |\Delta_K| \cdot (2n)^n \cdot e^{2n^2/e}. \end{aligned} \quad (59) $$

Combining Equation (58) and Equation (59), instantiating

$$ N := \lceil n \cdot n^{n/2+1} |\Delta_K| \cdot (2n)^n \cdot e^{2n^2/e} \cdot 48 \cdot \omega \cdot e^{2n/e} \cdot n^3 \cdot |\Delta_K| \rceil \ge n \cdot \|\mathbf{B}^{-1}\|^{-1} \cdot U/D \quad (60) $$

we can certainly compute such approximation $\mathbf{C}$ within time poly($n$, $\log(N)$, $\log(r)$) for such $N$ (since $\|x\mathbf{b}_i\| < r$). Similarly, for requirement (3), we can efficiently compute $\tilde{t} \in \frac{1}{N}\mathbb{Z}^n$ satisfying $\|t - \tilde{t}\| \le 1/(2N)$. Since $1/(2N) \le D/2 \le U$ we certainly have $\|\tilde{t}\| \le 2U$.

**Requirement (5).** We can efficiently and perfectly uniformly sample in $\frac{1}{N}\mathbb{Z}^n \cap (1+c)S$ for every $c > 0$ (where we understand $\mathbb{Z}^n \hookrightarrow K_{\mathbb{R}}$ as in Notation 8.9) by simple rejection sampling (where the ‘circles’ associated to the complex places are done one-by-one). Indeed, for this $N$, the uniform random sampling in $(1+4\varepsilon)S \cap \frac{1}{N}\mathbb{Z}^n$ (with $\varepsilon = 1/(6n)$) has bit complexity $O(n \log(rN))$.

**Requirement (6).** For the implementation of the oracle $O_{x\mathbf{B}_{\mathbf{b}\mathbf{m}_0}}$, it is enough to show that we can efficiently decide for any rational number $g \in \mathbb{Q}$, integer $k \in \mathbb{Z}_{>0}$ and any embedding $\sigma$ of $K$, whether an algebraic number $x\beta$ with $\beta \in \mathbf{b}\mathbf{m}_0$ satisfies $|\sigma(x\beta)| > g^{1/k}$ or $|\sigma(x\beta)| \le g^{1/k}$. Indeed, this holds since the set $S$ is entirely defined in terms of these (absolute values of) embeddings. By putting $k = 2 \cdot \mathbf{b} \cdot n$ we can write $r = g^{1/k}$ for some rational $r$. The existence and the effectiveness of such an oracle is precisely the object of Corollary 8.4; it is clear that it runs in expected time poly($n$, $\log |\Delta_K|$, size($\mathbf{b}$), size($\mathbf{m}$), size($x$), size($\omega$)).

**Bit complexity** Since $\log(r)$, $\log(N)$ are both poly($n$, $\log |\Delta_K|$, size($\mathbf{b}$), size($\mathbf{m}$), size($x$), size($\omega$)), a single run of the algorithm takes bit complexity poly($n$, $\log |\Delta_K|$, size($\mathbf{b}$), size($\mathbf{m}$), size($x$), size($\omega$)). If the success probability of a single run is bounded from below by a constant, the entire algorithm (until success) has the same expected bit complexity. It thus remains to show that, for the box $S = (r'_{\sigma})B_{\infty}$, $\varepsilon = 1/(6n)$, and $N$ as in Equation (60), the success probability is lower bounded by a constant. We have that the success probability is lower bounded by (using Lemma 2.8 with $c = (\min_{\sigma} |r'_{\sigma}|)^{-1}$ and (the $r$ of that lemma) $r = (1 \pm 5\varepsilon) \in [\frac{1}{6}, 2]$)

$$ \frac{(1 - 5\varepsilon)S \cap \frac{1}{N}\mathbb{Z}^n}{(1 + 5\varepsilon)S \cap \frac{1}{N}\mathbb{Z}^n} \ge \frac{(1 - 5\varepsilon)^n|S|}{(1 + 5\varepsilon)^n|S|} \frac{N^n e^{-12nc}}{N^n e^{4nc}} \ge \frac{(1 - 1/n)^n e^{-16nc}}{(1 + 1/n)^n} \ge e^{-2} \cdot e^{-1} \ge e^{-3}, $$

<footnote>$^7$We have $\|A\| \le \|A\|_F = (\sum_{ij} |A_{ij}|^2)^{1/2}$ (Frobenius norm) and hence approximating $\mathbf{B}$ by $\mathbf{C} \in N^{-1}\mathbb{Z}^{n \times n}$ yields a $\mathbf{C}$ for which $|\mathbf{C}_{ij} - \mathbf{B}_{ij}| \le N^{-1}$ and hence $\|\mathbf{B} - \mathbf{C}\| \le \|\mathbf{B} - \mathbf{C}\|_F \le nN^{-1}$.</footnote>
**Algorithm 1** Uniform sampling in $x \cdot ((\mathfrak{b} + \gamma) \cap \tau K^{\mathfrak{m},1}) \cap r\mathcal{B}_{\infty}$

**Require:**

* An LLL-reduced basis of $\mathcal{O}_K$,

* A modulus $\mathfrak{m} = \mathfrak{m}_0\mathfrak{m}_{\infty}$ of the degree $n$ number field $K$.

* An ideal $\mathfrak{b} \in \mathcal{I}_K^{\mathfrak{m}}$,

* An element $\gamma \in K$,

* An element $\tau \in K^{\mathfrak{m}}$,

* A block size parameter $\mathfrak{b} \in \mathbb{Z}$, with $2 \le \mathfrak{b} \le n$.

* An element $x \in K_{\mathbb{R}}^{\times}$,

* A real number $\omega \in \mathbb{Q}_{\ge 1}$.

**Ensure:** A uniformly distributed element $\beta \in x \cdot ((\mathfrak{b} + \gamma) \cap \tau K^{\mathfrak{m},1}) \cap r\mathcal{B}_{\infty}$ with $r = 48 \cdot \omega \cdot \mathfrak{b}^{2n/\mathfrak{b}} \cdot n^{7/2} \cdot |\Delta_K|^{3/(2n)} \cdot \mathcal{N}(x\mathfrak{b}\mathfrak{m}_0)^{1/n}$.

1. **Defining the radius of the ball.**

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

2. **Obtaining a short basis of $x\mathfrak{b}\mathfrak{m}_0$.**

Apply Lemma 8.5 to obtain a b-BKZ reduced basis $B_{\mathfrak{b}\mathfrak{m}_0} = (\mathfrak{b}_1, \dots, \mathfrak{b}_n)$ of $\mathfrak{b}\mathfrak{m}_0$ that satisfies

$$ \begin{aligned} \|x \cdot \mathfrak{b}_i\| &\le 2n \cdot \mathfrak{b}^{2n/\mathfrak{b}} \cdot \lambda_n(x \cdot \mathfrak{b} \cdot \mathfrak{m}_0) \\ &\le 2n \cdot \mathfrak{b}^{2n/\mathfrak{b}} \cdot \sqrt{n} \cdot |\Delta_K|^{3/(2n)} \cdot \mathcal{N}(x\mathfrak{b}\mathfrak{m}_0)^{1/n} \le r/(24n^2), \end{aligned} \quad (61) $$

where the second inequality follows from Lemma 2.13(ii) and (iv) and the third from the definition of $r$.

3. **Computing a new shift $\gamma_m$ to take account for the modulus.**

Compute $\gamma_m \in \mathfrak{b} + \gamma$ such that $\gamma_m \equiv \tau$ modulo $\mathfrak{m}_0$, which is possible by the fact that $\mathfrak{b}$ and $\mathfrak{m}_0$ are coprime. If $\mathfrak{m}_0 = \mathcal{O}_K$, we put $\gamma_m = \gamma$.

4. **Reducing the shift $\gamma_m$ modulo the short basis of $\mathfrak{b}\mathfrak{m}_0$.**

Reduce $\gamma_m \in K$ modulo this b-BKZ-reduced basis $(\mathfrak{b}_1, \dots, \mathfrak{b}_n)$ of $\mathfrak{b}\mathfrak{m}_0$, yielding $\gamma_{\text{red}} \in \gamma_m + \mathfrak{b}\mathfrak{m}_0$. That is, write $\gamma_m = \sum_i t_i \mathfrak{b}_i$ and put $\gamma_{\text{red}} = \sum_i (t_i - [t_i])\mathfrak{b}_i$.

5. **Sampling an element in $x \cdot ((\mathfrak{b}\mathfrak{m}_0 + \gamma_{\text{red}}) \cap r\mathcal{B}_{\infty}^{\tau})$.**

Using Corollary 8.10, sample $\beta \in x \cdot ((\mathfrak{b}\mathfrak{m}_0 + \gamma_{\text{red}}) \cap r\mathcal{B}_{\infty}^{\tau})$.

6. **return $\beta$.**

$$ \text{since } c = (\min_{\sigma} |r'_{\sigma}|)^{-1} \le (r/2)^{-1} \le 1/(24n). \quad \square $$

8.5. **Algorithm for sampling in a box intersected with an ideal lattice.**

**Lemma 8.11.** Let $K$ be a number field, let $\mathfrak{m} = \mathfrak{m}_0\mathfrak{m}_{\infty}$ be a modulus of $\mathcal{O}_K$, let $\tau \in K^{\mathfrak{m}}$. Let $\mathfrak{b} \in \mathcal{I}_K^{\mathfrak{m}}$ be an ideal of $K$ coprime with $\mathfrak{m}_0$ and let $\gamma \in K$ be a shift. Let $\gamma_m \in \mathfrak{b} + \gamma$ such that $\gamma_m \equiv \tau$ modulo $\mathfrak{m}_0$.

Then

$$ (\mathfrak{b} + \gamma) \cap \tau K^{\mathfrak{m},1} = (\mathfrak{b}\mathfrak{m}_0 + \gamma_m) \cap \tau K_{\mathbb{R}}^{\mathfrak{m}_{\infty}} $$

*Proof.* By scaling up $\mathfrak{b}, \gamma, \tau$ by an integer $M \in \mathbb{N}_{>0}$ coprime with $\mathfrak{m}_0$, we can assume that they lie in $\mathcal{O}_K$. It is then enough to show that $(M\mathfrak{b} + M\gamma) \cap M\tau K^{\mathfrak{m},1} = (M\mathfrak{b}\mathfrak{m}_0 + M\gamma_m) \cap M\tau K_{\mathbb{R}}^{\mathfrak{m}_{\infty}}$.
We start with inclusion to the right. Since $M\mathfrak{b} + M\gamma \subseteq \mathcal{O}_K$, we have that $\alpha \in (M\mathfrak{b} + M\gamma) \cap M\tau K^{m,1}$ satisfies $\alpha = M\beta + M\gamma = M\tau + \mu$ with $\beta \in \mathfrak{b}$ and $\mu \in \mathfrak{m}_0 \subseteq \mathcal{O}_K$. Additionally $\sigma(\alpha)/\sigma(\tau) > 0$ for real $\sigma \mid \mathfrak{m}_\infty$ (since multiplying with $M$ does not change the sign of $\sigma(\tau)$).

By the definition of $\gamma_m \in K$, we have $\gamma_m \in \mathfrak{b} + \gamma$ and $\gamma_m \in \mathfrak{m}_0 + \tau$. Hence $\alpha - M\gamma_m \equiv 0 \pmod{M\tau}$ and both $M\mathfrak{b}$ and $\mathfrak{m}_0$. Hence $\alpha \equiv M\gamma_m \pmod{M\mathfrak{b}\mathfrak{m}_0}$, i.e., $\alpha \in M\mathfrak{b}\mathfrak{m}_0 + M\gamma_m$. Also, $\sigma(\alpha)/\sigma(\tau) > 0$ for real $\sigma \pmod{\mathfrak{m}_\infty}$, so $\alpha \in \tau K_{\mathbb{R}}^{m_\infty}$.

The inclusion to the left can be done similarly. Any $\alpha \in (M\mathfrak{b}\mathfrak{m}_0 + M\gamma_m) \subseteq \mathcal{O}_K$ satisfies $\alpha \in M\mathfrak{b} + M\gamma$. Also, since $\alpha \equiv M\gamma_m \equiv M\tau \pmod{\mathfrak{m}_0}$ and $\alpha \in \tau K_{\mathbb{R}}^{m_\infty}$, we have $\alpha \in M\tau K^{m,1}$. This concludes the proof. $\square$

**Proposition 8.12** (Correctness and efficiency of Algorithm 1). Let $K$ be a number field of degree $n$, let $\mathfrak{m} = \mathfrak{m}_0\mathfrak{m}_\infty$ be a modulus of $\mathcal{O}_K$, let $\mathfrak{b} \in \mathcal{I}_K^m$ be an ideal, let $\gamma \in K$ be a shift, let $\tau \in \mathcal{O}_K$ be coprime to $\mathfrak{m}_0$, let $\mathfrak{b} \in \{1, \dots, n\}$ be a block size parameter, let $x \in K_{\mathbb{R}}^\times$ be represented by rational numbers, let $\omega \in \mathbb{Q}_{\ge 1}$ and put $r = 48 \cdot \omega \cdot \mathfrak{b}^{2n/\mathfrak{b}} \cdot n^{7/2} \cdot |\Delta_K|^{3/2n} \cdot \mathcal{N}(x\mathfrak{b}\mathfrak{m}_0)^{1/n}$.

Then, the randomized algorithm Algorithm 1 samples from a uniform distribution over $x \cdot ((\mathfrak{b} + \gamma) \cap \tau K^{m,1}) \cap r\mathcal{B}_\infty$. Moreover, this algorithm runs in expected time $\mathcal{O}(n \log |\Delta_K|, \text{size}(\mathfrak{m}), \text{size}(\mathfrak{b}), \text{size}(\gamma), \text{size}(\tau), \text{size}(x), \text{size}(\omega))$.

*Proof.* The correctness of the algorithm follows from Corollary 8.10 and Lemma 8.11. The only thing that needs to be checked is that $\gamma_{\text{red}}$ satisfies $\|x\gamma_{\text{red}}\| \le r$. We have $\gamma_{\text{red}} = \sum_i c_i \mathfrak{b}_i$ with $c_i \in [-1/2, 1/2]$, hence $\|x\gamma_{\text{red}}\| \le \sum_i |c_i| \|x\mathfrak{b}_i\| \le r$, since the basis was BKZ-reduced (see line 2).

We conclude the proof with the estimate on the running time. In line 1, a mere instantiation of the radius $r$ is given.

In line 2, a short basis of $x\mathfrak{b}\mathfrak{m}_0$ is computed using a BKZ-like algorithm. This takes, by Lemma 8.5, time $\mathcal{O}(\mathfrak{b}^2, \text{size}(\mathfrak{b}), \text{size}(\mathfrak{m}_0), \log |\Delta_K|, \text{size}(x))$.

In line 3, a $\gamma_m \in K$ is computed satisfying $\gamma_m \in (\mathfrak{b} + \gamma) \cap (\mathfrak{m}_0 + \tau)$. For this, it suffices to compute elements $\beta \in \mathfrak{b}$ and $\mu \in \mathfrak{m}_0$ such that $\beta + \mu = 1$ (by putting $\gamma_m = \tau\beta + \gamma\mu$). Such a pair $(\beta, \mu) \in \mathfrak{b} \times \mathfrak{m}$ can be found by applying the Hermite normal form to the concatenated basis matrices of $\mathfrak{b}$ and $\mathfrak{m}$ [22, Proposition 1.3.1]. This requires $\tilde{O}(n^5 \log(M)^2)$ time [71], where $M$ is the maximum entry occurring in the basis matrices. Clearly this overall process takes time polynomial in $n$, $\text{size}(\mathfrak{m}_0)$, $\text{size}(\gamma)$ and $\text{size}(\mathfrak{b})$.

In line 4, this element $\gamma_m$ is reduced modulo $\mathfrak{b}\mathfrak{m}_0$, which takes time at most $\mathcal{O}(\text{size}(\mathfrak{b}), \text{size}(\mathfrak{m}_0), \text{size}(\gamma))$, since $\text{size}(\gamma_m) = \text{poly}(\text{size}(\mathfrak{b}), \text{size}(\mathfrak{m}_0), \text{size}(\gamma))$.

Lastly, in line 5, a uniform sample is taken, following Corollary 8.10. The expected bit complexity then follows. $\square$

## 9. IDEAL SAMPLING

9.1. **Introduction.** In this section, we prove the main result of this part, Theorem 9.5. Recall the task at hand. Fix a family of ideals $\mathcal{S}$. Given an ideal $\mathfrak{a}$, find $\beta \in \mathfrak{a}$ such that $\beta\mathfrak{a}^{-1} \in \mathcal{S} \cdot \mathcal{S}_B$ with probability proportional to the density of $\mathcal{S}$.

In Section 6 is proven that the input ideal lattice $\mathfrak{a}$ can be randomized so that its Arakelov class is uniformly distributed. For such random ideal lattices, by Section 7, the event $\beta\mathfrak{a}^{-1} \in \mathcal{S} \cdot \mathcal{S}_B$ happens with the anticipated probability (the ideal density of $\mathcal{S}$) when $\beta$ is sampled in a large enough box. Subsequently, we proved in Section 8 that one can efficiently sample from such a box. Combining these
results together leads to Algorithm 2 and Theorem 9.5, of which the latter can be
informally rephrased as follows: There is an efficient way to sample $\beta \in \mathfrak{a}$ satisfying
$\beta \mathfrak{a}^{-1} \in \mathcal{S} \cdot \mathcal{S}_B$ with a provable lower bound on the sampling probability.

In the proof of Theorem 9.5 we require three technical results, which are in the
later separate Section 9.3 and Section 9.4. The first of these three results is a
lemma that states that part of Algorithm 2 is exactly a random walk as in Theo-
rem 6.4, applied to the input ideal lattice $y \cdot \mathfrak{b}$. This allows to apply the density
result as in Theorem 7.1. The second result consists of a lemma that states that a
distribution $\mathcal{D}$ on $\text{Div}_{K^m}^0$ for which holds that the ‘folded’ distribution $[\mathcal{D}]$ is close
to uniform in $\text{Pic}_{K^m}^0$, the original distribution $\mathcal{D}$ is close to some $\mathcal{D}_U$ on $\text{Div}_{K^m}^0$
satisfying $[\mathcal{D}_U] = U(\text{Pic}_{K^m}^0)$. This allows for the statistical argument that we may
assume the ‘randomized’ ideal lattice being drawn from $\mathcal{D}_U$ rather than the original
distribution $\mathcal{D}$, for the cost of a small error coming from the statistical distance.

The last of these three results is Proposition 9.12, which shows that the output
distribution of Algorithm 2 and that of the ‘continuous variant of Algorithm 2’
(which is to be specified precisely later) are close. This result is very useful because
some algorithmic properties are much easier to prove for this ‘continuous variant’;
this closeness of the output distributions then show that these properties must also
hold for the original variant of Algorithm 2, though with a small error due to the
slight difference between the output distributions of the two variants.

## 9.2. Ideal sampling.

**Definition 9.1.** We denote by $S_B^G$ the set of $B$-smooth integral ideals coprime with $m_0$ and whose prime divisors lie in the subgroup $G \subseteq \text{Pic}_{K^m}^0$, i.e.,

$$
S_B^G = \{ \mathfrak{a} \text{ ideal of } \mathcal{O}_K \mid \mathfrak{p} \mid \mathfrak{a} \text{ implies } \mathfrak{p} \nmid m_0, \mathcal{N}(\mathfrak{p}) \le B \text{ and } [d^0(\mathfrak{p})] \in G \}.
$$

For $G = \text{Pic}_{K^m}^0$ we just get the set of smooth ideals $S_B$ coprime with $m_0$.

**Notation 9.2.** Let $\mathfrak{m} = \mathfrak{m}_0\mathfrak{m}_\infty$ be a modulus of $K$ and let $\tau \in \mathcal{O}_K$ be an element coprime with $\mathfrak{m}_0$. Then we denote

$$
\tau K_{\mathbb{R}}^{m_{\infty}} := \{(x_{\sigma})_{\sigma} \in K_{\mathbb{R}} \mid \text{sign}(x_{\sigma}) = \text{sign}(\sigma(\tau)) \text{ for all real } \sigma \mid \mathfrak{m}_{\infty}\}.
$$

Alternatively, this set consists of all $(x_\sigma)_\sigma \in K_\mathbb{R}$ for which holds $x_\sigma/\sigma(\tau) > 0$ for all real $\sigma \mid \mathfrak{m}_\infty$.

**Notation 9.3.** Let $H = \text{Log}(K_{\mathbb{R}}^0)$ be the hyper space of the number field $K$, i.e.,
$H = \{(x_\nu)_\nu \in H \mid \sum_\nu x_\nu = 0\}$. Let $(\nu_1, \dots, \nu_{r+1})$ be an ordering of the places
(with $r+1 = n_{\mathbb{R}} + n_{\mathbb{C}}$). We denote $\mathbb{Z}_H \subseteq H$ for the integral lattice with basis
$\mathbf{B}_H = (e_{\nu_1} - e_{\nu_2}, \dots, e_{\nu_i} - e_{\nu_{i+1}}, \dots, e_{\nu_r} - e_{\nu_{r+1}})$, where $e_{\nu_i}$ is the standard basis.
It satisfies $\lambda_1(\mathbb{Z}_H) = \lambda_r(\mathbb{Z}_H) = \sqrt{2}$ and hence $\text{cov}(\mathbb{Z}_H) \le n$.

We will denote $\ddot{H} = \frac{\delta}{n}\mathbb{Z}_H$ for the 'discretized' hyper space, where $\delta > 0$ is some
grid parameter. We then have $\text{cov}(\ddot{H}) \le \delta$.

**Lemma 9.4.** The output distribution of Algorithm 2 is independent of the absolute
value of the norm $|\mathcal{N}(y)|$ of $y$, and independent of the signs (and complex phase)
of the entries $y_\sigma$ of $y = (y_\sigma)_\sigma \in K_{\mathbb{R}}^\times$.

**Proof.** The variable $y$ only occurs in lines 6 and 7. The element $\tilde{\beta}$ is perfectly uniformly random over $((A_\sigma \cdot y_\sigma)_\sigma \cdot [\mathfrak{b} \cap \tau K^{\mathfrak{m},1}]) \cap r \cdot \mathcal{N}(y\tilde{\mathfrak{b}})^{1/n} \cdot \mathcal{B}_\infty$. Hence,
$\beta := (A_{\sigma}^{-1} \cdot y_{\sigma}^{-1})_{\sigma} \cdot \tilde{\beta}$ is uniformly distributed over

$$ ( [\bar{\mathfrak{b}} \cap \tau K^{\mathfrak{m},1}] ) \cap r \cdot (A_{\sigma}^{-1} \cdot y_{\sigma}^{-1})_{\sigma} \cdot |\mathcal{N}(y)|^{1/n} \cdot \mathcal{N}(\bar{\mathfrak{b}})^{1/n} \cdot \mathcal{B}_{\infty} \\ = ( [\bar{\mathfrak{b}} \cap \tau K^{\mathfrak{m},1}] ) \cap r \cdot (A_{\sigma}^{-1} \cdot (y^{0})_{\sigma}^{-1})_{\sigma} \cdot \mathcal{N}(\bar{\mathfrak{b}})^{1/n} \cdot \mathcal{B}_{\infty}, $$

where $y^0 := y/|\mathcal{N}(y)|^{1/n}$. Hence, the algorithm depends on $y^0$ and in particular not on $|\mathcal{N}(y)|$. Since the set $\mathcal{B}_{\infty}$ is symmetric around zero, the signs (and complex phases) of $y_{\sigma}^0$ (and hence of $y$) do not have any influence on the set $(A_{\sigma}^{-1} \cdot (y^0)_{\sigma}^{-1})_{\sigma} \cdot \mathcal{N}(\bar{\mathfrak{b}})^{1/n} \cdot \mathcal{B}_{\infty}$. $\square$

**Theorem 9.5 (ERH, Ideal sampling theorem).** Let $K$ be a number field of degree $n$, let $\mathfrak{m} = \mathfrak{m}_0\mathfrak{m}_{\infty}$ be a modulus, let $G \subseteq \text{Pic}_{K^{\mathfrak{m}}}^0$ a finite-index subgroup of $\text{Pic}_{K^{\mathfrak{m}}}^0$ and let $\mathbf{O}_G$ be an oracle that on input an ideal $\mathfrak{c}$ outputs whether $[d^0(\mathfrak{c})] \in G$ or not. Let $\mathfrak{b} \in \mathcal{I}_K$ be an ideal coprime with $\mathfrak{m}_0$, let $\tau \in K^{\mathfrak{m}}$ (see Section 2.4) satisfying $[|\tau|] \in G$, and let $y \in K_{\mathbb{R}}^{\times}$ be represented by rational coordinates. Let $\mathfrak{b} \in \{2, \dots, n\}$ be an integer, let $0 < \varepsilon < \min(1, \frac{20}{n})$ be an error parameter and let $\omega \in \mathbb{Q}_{\ge 1}$. Let $\mathcal{S}$ be a set of integral ideals coprime with $\mathfrak{m}_0$, satisfying $[d^0(\mathcal{S})] \subseteq G - [d^0(\mathfrak{b})]$. □

(A) **Correctness.** Algorithm 2 outputs an element $\beta \in \mathfrak{b}$ such that

* $(\beta) \cdot \mathfrak{b}^{-1} \in \mathcal{S} \cdot \mathcal{S}_B^G$,

* $\beta \in \tau K^{\mathfrak{m},1}$ (i.e., $\text{ord}_{\mathfrak{p}}(\beta - \tau) \ge \text{ord}_{\mathfrak{p}}(\mathfrak{m}_0)$ for all $\mathfrak{p} \mid \mathfrak{m}_0$ and $\sigma(\beta/\tau) > 0$ for all real $\sigma \mid \mathfrak{m}_{\infty})$,

* $|\mathcal{N}(\beta)| \le \mathcal{N}(\mathfrak{b}) \cdot B^N \cdot r^n$

with probability at least

$$ \frac{\mathcal{N}(\mathfrak{m}_0)}{\phi(\mathfrak{m}_0)} \cdot \frac{[\text{Pic}_{K^{\mathfrak{m}}}^0 : G]}{3} \cdot \delta_S[r^n] - \varepsilon \ge \frac{[\text{Pic}_{K^{\mathfrak{m}}}^0 : G]}{3} \cdot \delta_S[r^n] - \varepsilon. \quad (62) $$

Here, $B = \tilde{O}([\text{Pic}_{K^{\mathfrak{m}}}^0 : G]^2 \cdot n^2 \cdot [n^2 \cdot (\log \log(1/\varepsilon))^2 + (\log(|\Delta_K| \mathcal{N}(\mathfrak{m})))^2])$, $N = [7n+\log(\mathcal{N}(\mathfrak{m}))+\log |\text{Pic}_{K^{\mathfrak{m}}}^0| - \log[\text{Pic}_{K^{\mathfrak{m}}}^0 : G]+2\log(1/\varepsilon)+1]$ as in Corollary 6.5, $r = 48 \cdot \omega \cdot b^{2n/\mathfrak{b}} \cdot n^{7/2} \cdot |\Delta_K|^{\frac{1}{2n}} \cdot \mathcal{N}(\mathfrak{m}_0)^{\frac{1}{n}}$, and $\mathcal{N}(\mathfrak{m}) = 2^{|\mathfrak{m}_{\mathbb{R}}|} \cdot \mathcal{N}(\mathfrak{m}_0)$ with $|\mathfrak{m}_{\mathbb{R}}|$ being the number of different real embeddings dividing $\mathfrak{m}$ (see Section 2.4).

(B) **Running time.** Furthermore, Algorithm 2 has a bit complexity of $\text{poly}(b^b$, $\log |\Delta_K|$, $\text{size}(\mathfrak{b})$, $\log(1/\varepsilon)$, $\log(\mathcal{N}(\mathfrak{m}))$, $[\text{Pic}_{K^{\mathfrak{m}}}^0 : G]$, $\text{size}(y)$, $\text{size}(\tau)$, $\text{size}(\omega))$ and uses at most $\text{poly}(\log |\Delta_K|, \log \mathcal{N}(\mathfrak{m})) \cdot [\text{Pic}_{K^{\mathfrak{m}}}^0 : G]$ queries to $\mathbf{O}_G$.

**Proof of Theorem 9.5 (A) Correctness.** This proof is structured as follows. We will assume, purely for the sake of argument, that lines 4 and 5 in Algorithm 2 are replaced by the following,

$$ \text{"Sample } a = (a_{\sigma})_{\sigma} \leftarrow \mathcal{G}_{H,s} \text{ and put } (A_{\sigma})_{\sigma} = (e^{n_{\nu_{\sigma}}^{-1} a_{\sigma}})_{\sigma}. \quad (63) $$

and that $y \in K_{\mathbb{R}}^{\times}$ is replaced$^8$ by $y^0 = y/|\mathcal{N}(y)|^{1/n}$ (so that $b = \text{Log}(y) \in H$). This is indeed purely for the sake of argument, since these changes renders this algorithm unprocessable by a computer, due to the real arithmetic. We will show two things: (1) After these changes, which we will call the ‘continuous version of Algorithm 2’, both the correctness and the success probability claim as stated in Equation (62) of (A) do hold (but with $\varepsilon/2$ instead of $\varepsilon$); and (2) the output distribution of this ‘continuous version of Algorithm 2’ is $\varepsilon/2$-statistically close to the output distribution of the ordinary (or discrete) version of Algorithm 2 (that

<footnote>$^8$Note that this particular change of $y$ by $y^0$ does not impact the output distribution, by Lemma 9.4.</footnote>
is, without the changes on y and line 4 and 5). Together, we may then conclude that the correctness and success probability claim holds for the ordinary version of Algorithm 2, which is what we aimed to show.

**Part (1):** Showing the correctness and success probability for the 'continuous version of Algorithm 2'. We assume that lines 4 and 5 from Algorithm 2 are replaced by Equation (63) and that $y \in K_{\mathbb{R}}^0$. We will denote $b = \text{Log}(y) \in H$. Then, by Lemma 9.8, which we will treat later, the ideal-element pair $((\beta)\mathfrak{b}^{-1}, \beta) \in \mathcal{I}_K^m \times \mathfrak{b}$ from Algorithm 2 is distributed as

$$ ((\alpha) \cdot \text{Exp}(-\mathbf{a}), \alpha \cdot \text{Exp}_{\infty}(-\mathbf{a}_{\infty})), $$

with $\mathbf{a} \leftarrow W = W_G(N, B, s) + d^0(\mathfrak{b}) + b$ and subsequently $\alpha \leftarrow \text{Exp}(\mathbf{a})_{\tau} \cap r\mathcal{B}_{\infty}$ uniformly. Here $W = W_G(N, B, s) + d^0(\mathfrak{b}) + b$ is the random walk distribution starting on the point $d^0(\mathfrak{b}) + b \in \text{Div}_{K^m}^0$ (see Definition 6.1). Here, $\text{Exp}(\mathbf{a})_{\tau}$ is defined in Definition 5.2 and $b \in H \subseteq \text{Div}_{K^m}^0$.

For the random walk distribution $W = W_G(N, B, s) + d^0(\mathfrak{b}) + b$ on $\text{Div}_{K^m}^0$ with these parameters $(N, B, s)$ holds that $[W]$ on $\text{Pic}_{K^m}^0$ is $\varepsilon/2$-close to the uniform distribution $\mathcal{U}(G + d^0(\mathfrak{b}))$ on the coset $G + d^0(\mathfrak{b})$ in the total variation distance. So, allowing an error of $\varepsilon/2$ we may as well assume that $\mathbf{a}$ instead comes from a distribution $\mathcal{D}$ on $\text{Div}_{K^m}^0$ that satisfies $[\mathcal{D}] = \mathcal{U}(G + d^0(\mathfrak{b}))$ (see Lemma 9.9).

By applying Theorem 7.1, using that $[\|\tau\|] \in G$, one then obtains that the probability that $(\beta) \cdot \bar{\mathfrak{b}}^{-1} = (\alpha) \text{Exp}(-\mathbf{a}) \in S$ given that $\beta = \alpha \text{Exp}_{\infty}(-\mathbf{a}_{\infty}) \in \tau K^{m,1}$ (which is precisely the way how $\alpha$ is sampled) is at least $\frac{\mathcal{N}(\mathbf{m}_0)}{\phi(\mathbf{m}_0)} \frac{[\text{Pic}_{K^m}^0 : G]}{3} \cdot \delta_S[r^n] - \varepsilon/2$. From the fact that $\bar{\mathfrak{b}} = \mathfrak{b} \cdot \prod_j \mathfrak{p}_j$ with $\mathfrak{p}_j \nmid \mathbf{m}$, $[d^0(\mathfrak{p}_j)] \in G$, and $\mathcal{N}(\mathfrak{p}_j) \le B$, we have that $(\beta) \cdot \mathfrak{b}^{-1} \in S \cdot S_B^G$ in that case, and the probability claim of Equation (62) (with $\varepsilon/2$ instead of $\varepsilon$) follows.

We finish part (1) of this proof by showing that the output $\beta \in \mathfrak{b}$ of Algorithm 2 satisfies all bullet points of the theorem. By lines 6 and 7 it follows that $\beta \in \tau K^{m,1}$. By line 6 it follows that $\tilde{\beta} \in r \cdot \mathcal{N}(\bar{\mathfrak{b}})^{1/n} \cdot \mathcal{B}_{\infty}$, hence $|\mathcal{N}(\tilde{\beta})| \le r^n \cdot \mathcal{N}(\bar{\mathfrak{b}}) \le r^n \cdot B^N \cdot \mathcal{N}(\mathfrak{b})$. Since the Gaussian distortion $(A_{\sigma})_{\sigma}$ (in the 'continuous version') does not change the norm (as $a \in H$), we have $|\mathcal{N}(\tilde{\beta})| = |\mathcal{N}(\bar{\beta})|$.

**Part (2):** Showing that the output distribution of the 'continuous version of Algorithm 2' and the discrete version are $\varepsilon/2$-close. By the proposition in Section 9.4, together with the fact that the discrete Gaussian in line 4 is approximated within statistical distance $\varepsilon/4$, we conclude that with the choice of the 'grid parameter' $\delta$ of $\dot{H}$ in line 4 of Algorithm 2, the statistical difference between the 'continuous variant' and the ordinary variant of Algorithm 2 is at most $\varepsilon/4 + \varepsilon/4 = \varepsilon/2$.

Hence, the success probability of the ordinary Algorithm 2 as in the theorem statement is lower bounded by

$$ \frac{\mathcal{N}(\mathbf{m}_0)}{\phi(\mathbf{m}_0)} \frac{[\text{Pic}_{K^m}^0 : G]}{3} \cdot \delta_S[r^n] - \varepsilon/2 - \varepsilon/2 = \frac{\mathcal{N}(\mathbf{m}_0)}{\phi(\mathbf{m}_0)} \frac{[\text{Pic}_{K^m}^0 : G]}{3} \cdot \delta_S[r^n] - \varepsilon, $$

as was required to prove.

□

*Proof of Theorem 9.5 (B) Running time.* In the following complexity analysis, any complexity that is within $\text{poly}(\log |\Delta_K|, \text{size}(\mathfrak{b}), \log(1/\varepsilon), \log(\mathcal{N}(\mathfrak{m}))$, $[\text{Pic}_{K^m}^0 : G]$, $\text{size}(y), \text{size}(\tau))$ we will call 'polynomial in the size of the input'. Note that $\log B$ and $N$ are $\text{poly}(\log |\Delta_K|, \text{size}(\mathfrak{b}), \log(1/\varepsilon), \log(\mathcal{N}(\mathfrak{m}))$, $\log([\text{Pic}_{K^m}^0 : G])$, so any
complexity polynomially bounded by $\log B$ and $N$ must be polynomial in the size of the input as well. We can omit the dependency here on $|G|$ since $\log|G| \le \log|\text{Pic}_{K^m}^0| \le \log(|\Delta_K|\mathcal{N}(\mathbf{m}))$ (see Lemma 5.1).

We go through lines 1 to 7 of Algorithm 2. Line 1 just initializes $B$ and $N$ and $s$. Line 2 uses Lemma 5.4 $N$ times to obtain the random primes $\mathfrak{p}_1, \dots, \mathfrak{p}_N$. This takes complexity $O(\text{[Pic}_{K^m}^0 : G] \cdot n^3 \cdot \log^2(B) \cdot N)$ and $O(N \cdot [\text{Pic}_{K^m}^0 : G] \cdot n \log B) = \text{poly}(\log|\Delta_K|, \log\mathcal{N}(\mathbf{m})) \cdot [\text{Pic}_{K^m}^0 : G]$ queries to $\mathbf{O}_G$.

In line 3, $\mathfrak{b}$ is multiplied by the $N$ sampled prime ideals. Multiplication of two ideals can be done by LLL-reducing the $n^2 \times n$ matrix involving all products of the $\mathbb{Z}$-generators of the respective ideals, taking bit complexity $\tilde{O}(n^{11} \log(M)^3)$ [58], where $M$ is the maximum entry of the matrix involved. This multiplication is done with $N$ ideals for which $\log(M)$ is bounded by $\text{poly}(\log|\Delta_K|, \text{size}(\mathfrak{b}), \log(B))$, which means that the total bit complexity of this ideal multiplication is in polynomially bounded in the size of the input. An alternative way to see this is by using the two-element representation of ideals (e.g., [25, §4.7]).

Line 4 requires to sample $\tilde{a}$ from an approximate discrete Gaussian $\hat{G}_{\frac{\delta}{n}\mathbf{B}_H, \varepsilon/4, s, 0}$ in $\tilde{H} = \frac{\delta}{n}\mathbb{Z}_H$ as in Lemma 2.22 (with $\mathbf{B}_H$ as in Notation 9.3), which is within statistical distance $\varepsilon_G := \varepsilon/4$ of an exact discrete Gaussian. Indeed, observing that the maximum length of the basis of $\frac{\delta}{n}\mathbb{Z}_H$ (see Notation 9.3) is at most $\sqrt{2\delta}/n$ we see that certainly (see line 4)

$$s \ge \delta \sqrt{n \log(2n/(\varepsilon/40))} \ge \sqrt{\frac{\log(4/\varepsilon) + 2 \log(n) + 3}{\pi}} \cdot \frac{\sqrt{2\delta}}{n}.$$

This, according to Lemma 2.22, takes expected time polynomial in the input size and $\log(1/\varepsilon)$. Since the input size is $\text{poly}(1/\delta) = \text{poly}(n, \log|\Delta_K|, \log(1/\varepsilon), \log(\omega))$ this Gaussian sampling algorithm has a expected bit complexity of $\text{poly}(n, \log|\Delta_K|, \log(1/\varepsilon), \log(\omega))$. Note that, by Lemma 2.22, the length of $\tilde{a}$ cannot exceed $s \cdot \sqrt{n \log(2n^2/\varepsilon)}$.

In line 5 we need to approximate $(e^{n\nu_\sigma^{-1}\tilde{a}_\sigma})_\sigma$ by rational $(A_\sigma)_\sigma$ such that the relative multiplicative error is small enough. Since the length of $\tilde{a}$ does not exceed $s \cdot \sqrt{n \log(2n^2/\varepsilon)}$ (note that $s = 1/n^2$) we clearly see that $\min_\sigma \tilde{a}_\sigma$ cannot be smaller than $\varepsilon/(2n^2) < e^{-\sqrt{\log(2n^2/\varepsilon)}}$. Hence, approximating $(A_\sigma)_\sigma$ as in line 5 can be done in time $\text{poly}(n, \log(1/\delta), \log(1/\varepsilon))$ which is $\text{poly}(n, \log|\Delta_K|, \log(1/\varepsilon), \log(\omega))$. Note that the size of $(A_\sigma)_\sigma$ itself is also bounded polynomially in these latter parameters.

Line 6 requires Algorithm 1, which uses expected bit complexity at most $\text{poly}(\mathfrak{b}^b, \text{size}(\mathfrak{b}), \text{size}(\mathfrak{m}_0), \log|\Delta_K|, \text{size}(y), \text{size}((A_\sigma)_\sigma), \text{size}(\tau))$. Note that $\text{size}(\mathfrak{b}) = \text{poly}(\text{size}(\mathfrak{b}), N, \log(B))$. Proposition 8.12 can be applied here because we have $r \cdot \mathcal{N}(\mathfrak{b})^{1/n} \cdot |\mathcal{N}(y)| = 48 \cdot \omega \cdot \mathfrak{b}^{2n/\mathfrak{b}} \cdot n^{7/2} \cdot |\Delta_K|^{\frac{3}{2n}} \cdot \mathcal{N}(\mathfrak{m}_0)^{\frac{1}{n}} \cdot \mathcal{N}(\mathfrak{b})^{\frac{1}{n}} \cdot |\mathcal{N}(y)|$.

The last line, line 7, only multiplies $\tilde{\beta}$ with $(A_\sigma^{-1} \cdot y_\sigma^{-1})_\sigma$, which has bit complexity polynomial in size$((A_\sigma)_\sigma, (y_\sigma)_\sigma, \text{size}(\tilde{\beta}))$ which is polynomial in the size of the input, as size$(\tilde{\beta})$ must be $\text{poly}(r, \text{size}(\mathfrak{b}), \text{size}(y), \text{size}((A_\sigma)_\sigma))$.

Therefore, all steps require a bit complexity at most polynomial in the size of the input and $\mathfrak{b}^b$. The total number of queries to $\mathbf{O}_G$ is at most $\text{poly}(\log|\Delta_K|, \log\mathcal{N}(\mathbf{m}))$.
$[\text{Pic}_{K^m}^0 : G]$. $\square$

**Remark 9.6.** If $\mathfrak{m} = \mathcal{O}_K$, we have $\mathcal{N}(\mathfrak{m}) = \phi(\mathfrak{m}) = 1$, and $K^m = K^{m,1} = K^*$. In this case, $\tau K^{m,1} = K^*$
**Algorithm 2** Sampling of $\beta \in \mathfrak{b}$ such that $\beta \in \tau K^{\mathfrak{m},1}$

**Require:**

* An LLL-reduced basis of $\mathcal{O}_K$,

* A modulus $\mathfrak{m} = \mathfrak{m}_0\mathfrak{m}_\infty$ of the degree $n$ number field $K$.

* A finite-index subgroup $G \subseteq \text{Pic}_{K^\mathfrak{m}}^0$,

* An ideal $\mathfrak{b} \in \mathcal{I}_K$ coprime with $\mathfrak{m}_0$,

* An element $y \in K_{\mathbb{R}}^\times$,

* An element $\tau \in K^\mathfrak{m}$, satisfying $[\langle\tau\rangle] \in G$,

* An error parameter $\varepsilon > 0$.

* A block size parameter $\mathfrak{b} \in \mathbb{Z}$, with $2 \le \mathfrak{b} \le n$.

* An oracle $\mathbf{O}_G$ that on input an ideal $\mathfrak{c}$ outputs whether $[d^0(\mathfrak{c})] \in G$.

* An element $\omega \in \mathbb{Q}_{\ge 1}$.

**Ensure:** An element $\beta \in \mathfrak{b}$

1. Let $B, N$ be as in Corollary 6.5, put $s = 1/n^2$ and put $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}$.

2. Sample $N$ random prime ideals $\mathfrak{p}_1, \dots, \mathfrak{p}_N$ uniformly from the set $\{\mathfrak{p} \text{ prime ideal of } K \mid N(\mathfrak{p}) \le B, \mathfrak{p} \nmid \mathfrak{m}_0, [d^0(\mathfrak{p})] \in G\}$, using the oracle $\mathbf{O}_G$ and Lemma 5.4

3. Multiply $\mathfrak{b}$ by these $N$ random prime ideals $\mathfrak{p}_j$, obtaining $\bar{\mathfrak{b}} = \mathfrak{b} \cdot \prod_j \mathfrak{p}_j$.

4. Sample, using Lemma 2.22, an approximation of the discrete Gaussian

$$ \ddot{\alpha} = (\ddot{\alpha}_{\sigma})_{\sigma} \leftarrow \hat{\mathcal{G}}_{\frac{s}{n}\mathbf{B}_H, \varepsilon_G, s, 0} $$

with error parameter $\varepsilon_G := \varepsilon/4$, where $\frac{\delta}{n}\mathbf{B}_H$ is a basis of $\ddot{H} = \frac{\delta}{n}\mathbb{Z}_H$ (see Notation 9.3) and

$$ \delta := \frac{(\varepsilon/40)^{4n^2s+1} \cdot s}{\omega^n \cdot e^{10n^2} \cdot |\Delta_K| \cdot \sqrt{n \log(2n/(\varepsilon/40))}} $$

5. Compute a rationally represented $(A_\sigma)_\sigma \in K_{\mathbb{R}}^0$ such that

$$ \max_{\sigma} |A_{\sigma}/e^{n_{\nu_{\sigma}}^{-1}\ddot{\alpha}_{\nu_{\sigma}}} - 1| \le \delta/(2n), $$

where $n_{\nu_{\sigma}} = 2$ if $\sigma$ is complex and 1 otherwise.

6. Sample, following Algorithm 1 with input $\gamma = 0$, a uniformly random element

$$ \tilde{\beta} \in ((A_{\sigma} \cdot y_{\sigma})_{\sigma} \cdot [\bar{\mathfrak{b}} \cap \tau K^{\mathfrak{m},1}]) \cap r \cdot |\mathcal{N}(y)|^{1/n} \cdot \mathcal{N}(\bar{\mathfrak{b}})^{1/n} \cdot \mathcal{B}_{\infty} $$

7. **return** $\beta = (A_{\sigma}^{-1} \cdot y_{\sigma}^{-1})_{\sigma} \cdot \tilde{\beta} \in \mathfrak{b}$.

**Remark 9.7.** The requirement $[\langle\tau\rangle] \in G$ is not necessary. The same proof and algorithm applies for arbitrary $[\langle\tau\rangle]$; but, as $\beta \in \tau K^{\mathfrak{m},1}$, we have $[\langle\beta\rangle] = [\langle\tau\rangle]$. Hence, if we do not assume $[\langle\tau\rangle] \in G$, the property $[\langle\beta\rangle] \in G$ is generally not valid anymore.

9.3. **Two help lemmas.** The following two lemmas are used in the proof of Theorem 9.5. The first of these lemmas shows that part of Algorithm 2 consists of a random walk, whereas the second one shows that one can replace the random walk