Rigorous Computation of Fundamental Units in Algebraic Number Fields

2010/01/23 by Felix Fontein, Michael J. Jacobson, Fontein, Felix +1
Computer Science · Mathematics · #11R04 #11R27 #11Y40 #Algebraic Geometry and Number Theory #Coding theory and cryptography #FOS: Mathematics #Finite Group Theory Research #Number Theory (math.NT)

paper · pdf · doi:10.48550/arxiv.1001.4187

openalex publication_date 2010/01/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We present an algorithm that unconditionally computes a representation of the unit group of a number field of discriminant Δ_K, given a full-rank subgroup as input, in asymptotically fewer bit operations than the baby-step giant-step algorithm. If the input is assumed to represent the full unit group, for example, under the assumption of the Generalized Riemann Hypothesis, then our algorithm can unconditionally certify its correctness in expected time O(Δ_K^{n/(4n + 2) + ε}) = O(Δ_K^{1/4 - 1/(8n+4) + ε}) where n is the unit rank.

Related

• New techniques for computing the ideal class group and a system of fundamental units in number fields
• An L(1/3) algorithm for ideal class group and regulator computation in certain number fields
• Rigorous methods for computational number theory
• Quadratic units and cubic fields
• Codes from unit groups of division algebras over number fields