Computing the multiplicative group of residue class rings
HTML articles powered by AMS MathViewer
- by Florian Heß, Sebastian Pauli and Michael E. Pohst PDF
- Math. Comp. 72 (2003), 1531-1548 Request permission
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
- Roland Auer, Ray class fields of global function fields with many rational places, Acta Arith. 95 (2000), no. 2, 97–122. MR 1785410, DOI 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 10.1007/3-540-61581-4_{4}0
- 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 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, DOI 10.1007/978-3-662-02945-9
- Henri Cohen, Hermite and Smith normal form algorithms over Dedekind domains, Math. Comp. 65 (1996), no. 216, 1681–1699. MR 1361805, DOI 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, DOI 10.1007/978-1-4419-8489-0
- 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 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 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_FH.ps.gz.
- Serge Lang, Algebraic number theory, 2nd ed., Graduate Texts in Mathematics, vol. 110, Springer-Verlag, New York, 1994. MR 1282723, DOI 10.1007/978-1-4612-0853-2
- 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, DOI 10.1017/CBO9780511661952
- 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 10.1007/3-540-61581-4_{6}6
- Charles C. Sims, Computation with finitely presented groups, Encyclopedia of Mathematics and its Applications, vol. 48, Cambridge University Press, Cambridge, 1994. MR 1267733, DOI 10.1017/CBO9780511574702
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
- © Copyright 2003 American Mathematical Society
- 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
- MathSciNet review: 1972751