Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Computing the multiplicative group of residue class rings


Authors: Florian Heß, Sebastian Pauli and Michael E. Pohst
Journal: Math. Comp. 72 (2003), 1531-1548
MSC (2000): Primary 11R29, 11R37, 11Y16, 11Y40
DOI: https://doi.org/10.1090/S0025-5718-03-01474-1
Published electronically: January 13, 2003
MathSciNet review: 1972751
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Let $\mathbf{k}$ be a global field with maximal order $\mathfrak o_{\mathbf k}$and let ${\mathfrak{m}}_{0}$ be an ideal of $\mathfrak o_{\mathbf k}$. We present algorithms for the computation of the multiplicative group $(\mathfrak o_{\mathbf k}/{\mathfrak{m}}_{0})^*$ of the residue class ring $\mathfrak o_{\mathbf k}/{\mathfrak{m}}_{0}$ and the discrete logarithm therein based on the explicit representation of the group of principal units. We show how these algorithms can be combined with other methods in order to obtain more efficient algorithms. They are applied to the computation of the ray class group $\mathbf{Cl}_{\mathbf{k}}^{\mathfrak{m}}$ modulo $\mathfrak m={\mathfrak{m}}_{0}{\mathfrak{m}}_{\infty}$, where ${\mathfrak{m}}_{\infty}$ denotes a formal product of real infinite places, and also to the computation of conductors of ideal class groups and of discriminants and genera of class fields.


References [Enhancements On Off] (What's this?)

  • [Aue99] Roland Auer, Ray Class Fields of Global Function Fields with Many Rational Places, Carl-von-Ossietzky-Universität, Oldenburg, 1999 (see also Acta Arith. 95 (2000), 97-122). MR 2002e:11162
  • [BB +99] C. Batut, K. Belabas, D. Bernardi, H. Cohen, M. Olivier, The Computer Algebra System PARI-GP, Université Bordeaux I, 1999, ftp://megrez.math.u-bordeaux.fr/pub/pari/
  • [BC95] W. Bosma and J.J. Cannon, Handbook of Magma functions, School of Mathematics, University of Sydney, Sydney, 1995.
  • [CDO96] Henri Cohen, Francisco Diaz y Diaz, and Michel Olivier, Computing ray class groups, conductors and discriminants, ANTS II (Henri Cohen, ed.), LNCS 1122, Springer, 1996, 49-57. MR 98c:11123
  • [CDO98] Henri Cohen, Francisco Diaz y Diaz, and Michel Olivier, Computing ray class groups, conductors and discriminants, Math. Comp. 67 (1998). MR 98g:11128
  • [Coh93] Henri Cohen, A course in computational algebraic number theory, Springer Verlag, New York, 1993. MR 94i:11105
  • [Coh96] Henri Cohen, Hermite and Smith normal form algorithms over Dedekind domains, Math. Comp. 65 (1996), 1681-1699. MR 97e:11159
  • [Coh00] Henri Cohen, Advanced topics in computational number theory, Springer Verlag, New York, 2000. MR 2000k:11144
  • [DF +96] M. Daberkow, C. Fieker, J. Klüners, M. Pohst, K. Roegner, M. Schörnig, and K. Wildanger, KANT V4, J. Symb. Comp. 11 (1996), 267-283. MR 99g:11150
  • [Fie00] Claus Fieker, Computing class fields via the Artin map, Math. Comp. 70 (2001), no. 235, 1293-1303. MR 2002e:11153
  • [Has80] Helmut Hasse, Number theory, Springer Verlag, Berlin, 1980. MR 81c:12001b
  • [Hes96] Florian Heß, Zur Klassengruppenberechnung in algebraischen Zahlkörpern, Diplomarbeit, TU - Berlin, 1996, http://www.math.TU-Berlin.DE/~ kant/publications/diplom/hess.ps.gz.
  • [Hes99] Florian Heß, Zur Divisorenklassengruppenberechnung in globalen Funktionenkörpern, PhD thesis, TU - Berlin, 1999, http://www.math.TU-Berlin.DE/~ kant/publications/diss/diss_FH.ps.gz.
  • [Lan94] Serge Lang, Algebraic number theory, 2nd ed., Graduate Texts in Mathematics, vol. 110, Springer Verlag, Berlin, 1994. MR 95f:11085
  • [Pau96] Sebastian Pauli, Zur Berechnung von Strahlklassengruppen, Diplomarbeit, TU - Berlin, 1996, http://www.math.TU-Berlin.DE/~ kant/publications/diplom/pauli.ps.gz.
  • [PZ89] Michael E. Pohst and Hans Zassenhaus, Algorithmic algebraic number theory, Cambridge University Press, 1989. MR 92b:11074
  • [Po +00] Michael E. Pohst et al, The computer algebra system KASH/KANT, TU-Berlin, 2000, http://www.math.tu-berlin.de/~ kant/.
  • [SWD] Oliver Schirokauer, Damian Weber, and Thomas Denny, Discrete Logarithms: The Effectiveness of the Index Calculus Method, ANTS II (Henri Cohen, ed.), LNCS 1122, Springer, 1996, 337-361. MR 98i:11109
  • [Sim94] Charles C. Sims, Computation with finitely presented groups, Cambridge University Press, 1994. MR 95f:20053

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11R29, 11R37, 11Y16, 11Y40

Retrieve articles in all journals with MSC (2000): 11R29, 11R37, 11Y16, 11Y40


Additional Information

Florian Heß
Affiliation: Institut für Mathematik, MA 8–1, Technische Universität Berlin, Strasse des 17. Juni 136, 10623 Berlin, Germany
Address at time of publication: Department of Computer Science, University of Bristol, BS8 1UB, England
Email: florian@cs.bris.ac.uk

Sebastian Pauli
Affiliation: Institut für Mathematik, MA 8–1, Technische Universität Berlin, Strasse des 17. Juni 136, 10623 Berlin, Germany
Email: pauli@math.tu-berlin.de

Michael E. Pohst
Affiliation: Institut für Mathematik, MA 8–1, Technische Universität Berlin, Strasse des 17. Juni 136, 10623 Berlin, Germany
Email: pohst@math.tu-berlin.de

DOI: https://doi.org/10.1090/S0025-5718-03-01474-1
Received by editor(s): February 2, 1999
Received by editor(s) in revised form: November 8, 2001
Published electronically: January 13, 2003
Article copyright: © Copyright 2003 American Mathematical Society

American Mathematical Society