Hostname: page-component-586b7cd67f-t7fkt Total loading time: 0 Render date: 2024-11-24T13:51:08.554Z Has data issue: false hasContentIssue false
  • English
  • Français

An algorithm for the principal ideal problem in indefinite quaternion algebras

Part of: Computational number theory Algebraic number theory: global fields

Published online by Cambridge University Press:  01 August 2014

A. Page
A. Page*
Affiliation:
Université Bordeaux, IMB UMR 5251, F-33400 Talence, France email [email protected] CNRS, IMB, UMR 5251, F-33400 Talence, France INRIA, F-33400 Talence, France

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.

Deciding whether an ideal of a number field is principal and finding a generator is a fundamental problem with many applications in computational number theory. For indefinite quaternion algebras, the decision problem reduces to that in the underlying number field. Finding a generator is hard, and we present a heuristically subexponential algorithm.

MSC classification

Secondary: 11Y40: Algebraic number theory computations 11R52: Quaternion and other division algebras 11R65: Class groups and Picard groups of orders
Type
Research Article
Information
LMS Journal of Computation and Mathematics , Volume 17 , Special Issue A: Algorithmic Number Theory Symposium XI , 2014 , pp. 366 - 384
Copyright
© The Author 2014 

References

Bach, E., ‘Explicit bounds for primality testing and related problems’, Math. Comp. 55 (1990) no. 191, 355–380.Google 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’, 37th International Symposium on Symbolic and Algebraic Computation (ISSAC 2012) (ACM, New York, NY, USA, 2012).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
Buchmann, J., ‘A subexponential algorithm for the determination of class groups and regulators of algebraic number fields’, Séminaire de Théorie des Nombres, Paris 1988–1989, 27–41, Progress in Mathematics 91 (Birkhäuser, Boston, MA, 1990).Google Scholar
Dembélé, L. and Voight, J., ‘Explicit methods for Hilbert modular forms’, Elliptic curves, Hilbert modular forms and Galois deformations (Birkhäuser, Basel, 2013) 135–198.CrossRefGoogle Scholar
Fincke, U. and Pohst, M., ‘Improved methods for calculating vectors of short length in a lattice, including a complexity analysis’, Math. Comp. 44 (1985) no. 170, 463–471.Google Scholar
Granville, A., ‘Smooth numbers: computational number theory and beyond’, Algorithmic number theory: lattices, number fields, curves and cryptography, Mathematical Sciences Research Institute Publications 44 (Cambridge University Press, Cambridge, 2008) 267–323.Google Scholar
Hafner, J. L. and McCurley, K. S., ‘A rigorous subexponential algorithm for computation of class groups’, J. Amer. Math. Soc. 2 (1989) no. 4, 837–850.CrossRefGoogle Scholar
Kannan, R., ‘Improved algorithms for integer programming and related lattice problems’, Proceedings of the fifteenth annual ACM symposium on Theory of computing, STOC 83 (ACM, New York, NY, USA, 1983).Google Scholar
Kantor, W. M. and Lubotzky, A., ‘The probability of generating a finite classical group’, Geom. Dedicata 36 (1990) no. 1, 67–87.CrossRefGoogle Scholar
Katok, S., ‘Fuchsian groups’, Chicago lectures in mathematics (University of Chicago Press, Chicago, IL, 1992).Google Scholar
Kirschmer, M. and Voight, J., ‘Algorithmic enumeration of ideal classes for quaternion orders’, SIAM J. Comput. 39 (2010) no. 5, 1714–1747.Google Scholar
Klüners, J. and Pauli, S., ‘Computing residue class rings and Picard groups of orders’, J. Algebra 292 (2005) no. 1, 47–64.Google Scholar
Maclachlan, C. and Reid, A. W., The arithmetic of hyperbolic 3-manifolds, Graduate Texts in Mathematics 219 (Springer, New York, 2003).CrossRefGoogle Scholar
Sanov, I. N., ‘Euclid’s algorithm and one-sided prime factorization for matrix rings’, Sibirsk. Mat. Ž. 8 (1967) 846–852.Google Scholar
Serre, J.-P., Trees, Springer Monographs in Mathematics (Springer, Berlin, 2003) . Translated from the French original by John Stillwell. Corrected 2nd printing of the 1980 English translation.Google Scholar
Vignéras, M.-F., Arithmétique des algèbres de quaternions, Lecture Notes in Mathematics 800 (Springer, Berlin, 1980).CrossRefGoogle Scholar
Voight, J., ‘Computing fundamental domains for Fuchsian groups’, J. Théor. Nombres Bordeaux 21 (2009) no. 2, 469–491.CrossRefGoogle Scholar
Voight, J., ‘The arithmetic of quaternion algebras’, Preprint, available from http://www.math.dartmouth.edu/∼jvoight/research.html#books.Google Scholar
Vollmer, U., ‘An accelerated Buchmann algorithm for regulator computation in real quadratic fields’, Algorithmic number theory (Sydney, 2002), Lecture Notes in Computer Science 2369 (Springer, Berlin, 2002) 148–162.Google Scholar