Hostname: page-component-586b7cd67f-t7czq Total loading time: 0 Render date: 2024-11-26T13:53:11.404Z Has data issue: false hasContentIssue false
  • English
  • Français

Computing in quotients of rings of integers

Part of: Number theory Computational number theory

Published online by Cambridge University Press:  01 August 2014

Claus Fieker  and
Tommy Hofmann
Claus Fieker
Affiliation:
Fachbereich Mathematik, Technische Universität Kaiserslautern, Postfach 3049, 67653 Kaiserslautern, Germany email [email protected]
Tommy Hofmann
Affiliation:
Fachbereich Mathematik, Technische Universität Kaiserslautern, Postfach 3049, 67653 Kaiserslautern, Germany email [email protected]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We develop algorithms to turn quotients of rings of integers into effective Euclidean rings by giving polynomial algorithms for all fundamental ring operations. In addition, we study normal forms for modules over such rings and their behavior under certain quotients. We illustrate the power of our ideas in a new modular normal form algorithm for modules over rings of integers, vastly outperforming classical algorithms.

MSC classification

Secondary: 11Y40: Algebraic number theory computations 11-04: Explicit machine computation and programs (not the theory of computation or programming)
Type
Research Article
Information
LMS Journal of Computation and Mathematics , Volume 17 , Special Issue A: Algorithmic Number Theory Symposium XI , 2014 , pp. 349 - 365
Copyright
© The Author(s) 2014 

References

Ağargün, A. G. and Fletcher, C. R., ‘Euclidean rings’, Turkish J. Math. 19 (1995) no. 3, 291–299.Google Scholar
Belabas, K., ‘Topics in computational algebraic number theory’, J. Théor. Nombres Bordeaux 16 (2004) no. 1, 19–63.CrossRefGoogle Scholar
Biasse, J.-F. and Fieker, C., ‘A polynomial time algorithm for computing the HNF of a module over the integers of a number field’, Proceedings of the 37th International Symposium on Symbolic and Algebraic Computation (ISSAC ’12) (ACM, New York, NY, USA, 2012) 75–82.CrossRefGoogle Scholar
Biasse, J.-F., Fieker, C. and Hofmann, T., ‘On the computation of the HNF of a module over the ring of integers of a number field’, J. Symbolic Comput., submitted.Google Scholar
Bosma, W., Cannon, J. and Playoust, C., ‘The Magma algebra system. I. The user language’, J. Symbolic Comput. 24 (1997) no. 3–4, 235–265; Computational algebra and number theory (London, 1993).CrossRefGoogle Scholar
Bosma, W. and Pohst, M., ‘Computations with finitely generated modules over Dedekind rings’, Proceedings of the 1991 International Symposium on Symbolic and Algebraic Computation (ISSAC ’91) (ACM, New York, NY, USA, 1991) 151–156.CrossRefGoogle Scholar
Cohen, H., ‘Hermite and Smith normal form algorithms over Dedekind domains’, Math. Comp. 65 (1996) no. 216, 1681–1699.CrossRefGoogle Scholar
Cohen, H., Advanced topics in computational number theory, Graduate Texts in Mathematics 193 (Springer, New York, 2000).CrossRefGoogle Scholar
Domich, P. D., Kannan, R. and Trotter, L. E. Jr, ‘Hermite normal form computation using modulo determinant arithmetic’, Math. Oper. Res. 12 (1987) no. 1, 50–59.CrossRefGoogle Scholar
Fletcher, C. R., ‘Euclidean rings’, J. Lond. Math. Soc. (2) 4 (1971) 79–82.Google Scholar
Hafner, J. L. and McCurley, K. S., ‘Asymptotically fast triangularization of matrices over rings’, SIAM J. Comput. 20 (1991) no. 6, 1068–1083.CrossRefGoogle Scholar
Howell, J. A., ‘Spans in the module (Z m)s’, Linear Multilinear Algebra 19 (1986) no. 1, 67–77.CrossRefGoogle Scholar
Iliopoulos, C. S., ‘Worst-case complexity bounds on algorithms for computing the canonical structure of finite abelian groups and the Hermite and Smith normal forms of an integer matrix’, SIAM J. Comput. 18 (1989) no. 4, 658–669.CrossRefGoogle Scholar
Steinitz, E., ‘Rechteckige Systeme und Moduln in algebraischen Zahlköppern. I’, Math. Ann. 71 (1911) no. 3, 328–354.CrossRefGoogle Scholar
Steinitz, E., ‘Rechteckige Systeme und Moduln in algebraischen Zahlkörpern. II’, Math. Ann. 72 (1912) no. 3, 297–345.Google Scholar
Storjohann, A., ‘Algorithms for matrix canonical forms’, PhD Thesis, Department of Computer Science, Swiss Federal Institute of Technology – ETH, 2000.Google Scholar
Storjohann, A. and Mulders, T., ‘Fast algorithms for linear algebra modulo N’, Algorithms — ESA ’98 (Venice), Lecture Notes in Computer Science 1461 (Springer, Berlin, 1998) 139–150.CrossRefGoogle Scholar