Rigorous methods for computational number theory
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917280527417344 |
|---|---|
| author | de Boer, Koen Pellet-Mary, Alice Wesolowski, Benjamin |
| author_facet | de Boer, Koen Pellet-Mary, Alice Wesolowski, Benjamin |
| contents | 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 $[\mathfrak{a}]$ of a number field $K$, sample an ideal $\mathfrak b \in [\mathfrak{a}]$ belonging to a particular family of ideals (e.g., the family of smooth ideals, or near-prime ideals). More precisely, let $\mathcal{S}$ be an arbitrary family of ideals, and $\mathcal{S}_B$ the family of $B$-smooth ideals. We describe an efficient algorithm that samples ideals $\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}$ within the set of all ideals.
The case where $\mathcal{S}$ is the set of prime ideals yields 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. The case of smooth ideals $\mathcal{S} = \mathcal{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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_01588 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Rigorous methods for computational number theory de Boer, Koen Pellet-Mary, Alice Wesolowski, Benjamin Number Theory 11Y16, 11Y40, 68Q25, 11R29, 11R27 (primary), 68W40, 68W30, 11R45 (secondary) F.2.1; I.1.2; G.4 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 $[\mathfrak{a}]$ of a number field $K$, sample an ideal $\mathfrak b \in [\mathfrak{a}]$ belonging to a particular family of ideals (e.g., the family of smooth ideals, or near-prime ideals). More precisely, let $\mathcal{S}$ be an arbitrary family of ideals, and $\mathcal{S}_B$ the family of $B$-smooth ideals. We describe an efficient algorithm that samples ideals $\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}$ within the set of all ideals. The case where $\mathcal{S}$ is the set of prime ideals yields 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. The case of smooth ideals $\mathcal{S} = \mathcal{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. |
| title | Rigorous methods for computational number theory |
| topic | Number Theory 11Y16, 11Y40, 68Q25, 11R29, 11R27 (primary), 68W40, 68W30, 11R45 (secondary) F.2.1; I.1.2; G.4 |
| url | https://arxiv.org/abs/2512.01588 |