Abstract
In a quadratic field Q(\(\sqrt D\)), D a squarefree integer, with class number 1 any algebraic integer can be decomposed uniquely into primes but for only 21 domains Euclidean algorithms are known. We prove that for D⩽−19 even remainder sequences with possibly non-decreasing norms cannot determine the GCD of arbitrary inputs. We then show how to compute the greatest common divisor of the algebraic integers in any fixed Q(\(\sqrt D\)) with class number 1 in O (S 2) binary steps where S is the number of bits needed to encode the inputs. We also prove that in any domain the computation of the prime factorization of an algebraic integer can be reduced in polynomial-time to factoring its norm into rational primes. Our reduction is based on a constructive version of a theorem by A. Thue. Finally we present another GCD algorithm for complex quadratic fields based on a short lattice vector construction.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Barnes, E.S., and Swinnerton-Dyer, H.P.F.: The homogeneous minima of binary quadratic forms. Acta Math. 87, 255–323 (1952).
Brauer, A., and Reynolds, R.L.: On a theorem of Aubry-Thue. Canadian J. Math. 3, 367–374 (1951).
Chatland, H., and Davenport, H.: Euclid's algorithm in real quadratic fields. Canadian J. Math. 2, 289–296 (1950).
Caviness, B.F., and Collins, G.E.: Algorithms for Gaussian integer arithmetic. Proc. 1976 ACM Symp. Symbolic Algebraic Computation, 36–45.
Hardy, G.H., and Wright, E.M.: An Introduction to the Theory of Numbers. Oxford Univ. Press 1979.
Hasse, H.: Vorlesung über die Zahlentheorie. Springer Verlag, Berlin 1950.
Kaltofen, E.: On the complexity of finding short vectors in integer lattices. Springer Lec. Notes Comp. Sci. 162, 236–244 (1983).
Kannan, R.: Improved algorithms for integer programming and related lattice problems. Proc. 15th ACM Symp. Theory Comp., 193–206 (1983).
Kannan, R., and Bachem, A.: Polynomial algorithms for computing the Smith and Hermite normal forms of an integer matrix. SIAM J. Comp. 8, 499–507 (1979).
Knuth, D.E.: The Art of Programming, Vol. 2, Seminumerical Algorithms, 2nd Ed. Reading, MA: Addison Wesley 1981.
Lenstra, A. K., Lenstra, H. W., Lovász, L.: Factoring polynomials with rational coefficients. Math. Ann. 261, 515–534 (1982).
Nagell, T.: Sur un theoreme d'Axel Thue. Arkiv för Matematik 1, 33, 489–496 (1951).
Rolletschek, H.: The Euclidean algorithm for Gaussian integers. Springer Lec. Notes Comp. Sci. 162, 12–23 (1983).
Rolletschek, H.: On the number of divisions of the Euclidean algorithm applied to Gaussian integers. Submitted to the Journal of Symbolic Computation.
Schnorr, C.P.: A remark on the construction of short lattice elements. Manuscript April 1984.
Schönhage, A.: Schnelle Berechnung von Kettenbruchentwicklungen. Acta Inf. 1, 139–144 (1971).
Schönhage, A.: Factorization of Univariate Integer Polynomials by Diophantine Approximation and by an Improved Reduction Algorithm. Proc. Internat. Conf. Automata, Lang. and Prog. 1984.
Schoof, R.: Elliptic curves over finite fields and the computation of square roots mod p. Manuscript 1983.
Shanks, D.: Solved and Unsolved Problems in Number Theory I, 2nd Ed. Chelsea Publishers, 1978.
Stark, H.: A complete determination of complex quadratic fields of class number one. Mich. Math. J. 17, 1–27 (1967).
Thue, A.: Et par antydninger til en talteoretisk methode. Vid. Selsk. Forhandlinger Christiania 7 (1902), in Norwegian.
Wang, P.: A p-adic algorithm for univariate partial fractions. Proc. 1981 ACM Symp. Symbolic and Alg. Comp., 212–217.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1985 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kaltofen, E., Rolletschek, H. (1985). Arithmetic in quadratic fields with unique factorization. In: Caviness, B.F. (eds) EUROCAL '85. EUROCAL 1985. Lecture Notes in Computer Science, vol 204. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-15984-3_278
Download citation
DOI: https://doi.org/10.1007/3-540-15984-3_278
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-15984-1
Online ISBN: 978-3-540-39685-7
eBook Packages: Springer Book Archive