On the computation of the HNF of a module over the ring of integers of a number field. (May 2017)

• Record Type: Journal Article
• Authors: Biasse, Jean-François; Fieker, Claus; Hofmann, Tommy
• Is Part Of: Journal of symbolic computation. Volume 80:Part 3(2017)
• Page Start: 581
• Page End: 615
• Publication Date: 2017-05
• Subjects: Y40; Number field -- Dedekind domain -- Hermite normal form -- Relative extension of number fields; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2016.07.027
• Languages: English
• ISSNs: 0747-7171

Abstract

Abstract: We present a variation of the modular algorithm for computing the Hermite normal form of an O K -module presented by Cohen (1996), where 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 (1996) 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 .