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 Free Access
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.
- Roland Auer, Ray class fields of global function fields with many rational places, Acta Arith. 95 (2000), no. 2, 97–122. MR 1785410, DOI https://doi.org/10.4064/aa-95-2-97-122
- 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/
- W. Bosma and J.J. Cannon, Handbook of Magma functions, School of Mathematics, University of Sydney, Sydney, 1995.
- H. Cohen, F. Diaz y Diaz, and M. Olivier, Computing ray class groups, conductors and discriminants, Algorithmic number theory (Talence, 1996) Lecture Notes in Comput. Sci., vol. 1122, Springer, Berlin, 1996, pp. 49–57. MR 1446497, DOI https://doi.org/10.1007/3-540-61581-4_40
- H. Cohen, F. Diaz y Diaz, and M. Olivier, Computing ray class groups, conductors and discriminants, Math. Comp. 67 (1998), no. 222, 773–795. MR 1443117, DOI https://doi.org/10.1090/S0025-5718-98-00912-0
- Henri Cohen, A course in computational algebraic number theory, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993. MR 1228206
- Henri Cohen, Hermite and Smith normal form algorithms over Dedekind domains, Math. Comp. 65 (1996), no. 216, 1681–1699. MR 1361805, DOI https://doi.org/10.1090/S0025-5718-96-00766-1
- Henri Cohen, Advanced topics in computational number theory, Graduate Texts in Mathematics, vol. 193, Springer-Verlag, New York, 2000. MR 1728313
- M. Daberkow, C. Fieker, J. Klüners, M. Pohst, K. Roegner, M. Schörnig, and K. Wildanger, KANT V4, J. Symbolic Comput. 24 (1997), no. 3-4, 267–283. Computational algebra and number theory (London, 1993). MR 1484479, DOI https://doi.org/10.1006/jsco.1996.0126
- Claus Fieker, Computing class fields via the Artin map, Math. Comp. 70 (2001), no. 235, 1293–1303. MR 1826583, DOI https://doi.org/10.1090/S0025-5718-00-01255-2
- Helmut Hasse, Number theory, Akademie-Verlag, Berlin, 1979. Translated from the third German edition of 1969 by Horst Günter Zimmer. MR 544018
- Florian Heß, Zur Klassengruppenberechnung in algebraischen Zahlkörpern, Diplomarbeit, TU - Berlin, 1996, http://www.math.TU-Berlin.DE/~kant/publications/diplom/hess.ps.gz.
- Florian Heß, Zur Divisorenklassengruppenberechnung in globalen Funktionenkörpern, PhD thesis, TU - Berlin, 1999, http://www.math.TU-Berlin.DE/~kant/publications/diss/diss_{F}H.ps.gz.
- Serge Lang, Algebraic number theory, 2nd ed., Graduate Texts in Mathematics, vol. 110, Springer-Verlag, New York, 1994. MR 1282723
- Sebastian Pauli, Zur Berechnung von Strahlklassengruppen, Diplomarbeit, TU - Berlin, 1996, http://www.math.TU-Berlin.DE/~kant/publications/diplom/pauli.ps.gz.
- M. Pohst and H. Zassenhaus, Algorithmic algebraic number theory, Encyclopedia of Mathematics and its Applications, vol. 30, Cambridge University Press, Cambridge, 1989. MR 1033013
- Michael E. Pohst et al, The computer algebra system KASH/KANT, TU-Berlin, 2000, http://www.math.tu-berlin.de/~kant/.
- Oliver Schirokauer, Damian Weber, and Thomas Denny, Discrete logarithms: the effectiveness of the index calculus method, Algorithmic number theory (Talence, 1996) Lecture Notes in Comput. Sci., vol. 1122, Springer, Berlin, 1996, pp. 337–361. MR 1446523, DOI https://doi.org/10.1007/3-540-61581-4_66
- Charles C. Sims, Computation with finitely presented groups, Encyclopedia of Mathematics and its Applications, vol. 48, Cambridge University Press, Cambridge, 1994. MR 1267733
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
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