On the computation of the HNF of a module over the ring of integers of a number field

DOI10.1016/J.JSC.2016.07.027MaRDI QIDQ1711990zbMATH OpenOpenAlexWikidataFDO

Authors Jean-François Biasse, Claus Fieker, Tommy Hofmann

Publication date 21 January 2019

Published in Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1612.09428

zbMATH Keywords

Dedekind domainHermite normal formnumber fieldrelative extension of number fields

Mathematics Subject Classification ID

Algebraic number theory computations (11Y40) Symbolic computation and algebraic computation (68W30)

Abstract: We present a variation of the modular algorithm for computing the Hermite normal form of an $mathcal{O}_K$-module presented by Cohen, where $mathcal{O}_K$ is the ring of integers of a number field $K$. An approach presented in (Cohen 1996) based on reductions modulo ideals was conjectured to run in polynomial time by Cohen, but so far, no such proof was available in the literature. In this paper, we present a modification of the approach of Cohen to prevent the coefficient swell and we rigorously assess its complexity with respect to the size of the input and the invariants of the field $K$.

Recommendations

• A polynomial time algorithm for computing the HNF of a module over the integers of a number field
• On the module structure of rings of integers in p-adic number fields over associated orders
• The multiplicative structure of division rings over number fields and the Hasse norm principle
• Sur le noyau hilbertien d'un corps de nombres
• Computing the torsion of the p-ramified module of a number field
• On the computation of Hilbert class fields
• scientific article; zbMATH DE number 1254235
• scientific article; zbMATH DE number 1273653
• On the Ring of Integers in an Algebraic Number Field as a representation Module of Galois Group
• On the Computation of the Class Number of an Algebraic Number Field

Cites work

• A polynomial time algorithm for computing the HNF of a module over the integers of a number field
• Advanced Topics in Computional Number Theory
• An LLL algorithm with quadratic complexity
• An LLL-reduction algorithm with quasi-linear time complexity, extended abstract
• Approximate formulas for some functions of prime numbers
• Asymptotically Fast Triangularization of Matrices over Rings
• Computing the sign or the value of the determinant of an integer matrix, a complexity survey.
• Exact solution of linear equations using p-adic expansions
• Fast multiplication and its applications
• Fast multiplication of large numbers
• Hermite and Smith normal form algorithms over Dedekind domains
• scientific article; zbMATH DE number 435565 (Why is no real title available?)
• scientific article; zbMATH DE number 1254301 (Why is no real title available?)
• scientific article; zbMATH DE number 1273653 (Why is no real title available?)
• scientific article; zbMATH DE number 1305088 (Why is no real title available?)
• scientific article; zbMATH DE number 1936673 (Why is no real title available?)
• On the deterministic complexity of factoring polynomials over finite fields
• On the Galois cohomology of Dedekind rings
• On the Theorem on the Primitive Element
• Perturbation analysis of the QR factor R in the context of LLL lattice basis reduction
• Short bases of lattices over number fields
• Spans in the module (Z_m)^s
• Topics in computational algebraic number theory

Cited in

(11)

• Computing in quotients of rings of integers
• scientific article; zbMATH DE number 1273653 (Why is no real title available?)
• Computation of lattice isomorphisms and the integral matrix similarity problem
• Constructing totally p-adic numbers of small height
• Computing isomorphisms between lattices
• A polynomial time algorithm for computing the HNF of a module over the integers of a number field
• Algebraic number fields and the LLL algorithm
• On module unique-SVP and NTRU
• On the construction of class fields
• An algorithm for solving the principal ideal problem with subfields
• Algebraic algorithms for vector bundles over curves

This page was built for publication: On the computation of the HNF of a module over the ring of integers of a number field

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1711990)