Shortest division chains in imaginary quadratic number fields

DOI10.1016/S0747-7171(08)80016-8MaRDI QIDQ1813694zbMATH OpenFDO

Authors Heinrich Rolletschek

Publication date 25 June 1992

Published in Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0747-7171(08)80016-8

zbMATH Keywords

Euclidean algorithmimaginary quadratic fieldshortest division chain

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16) Algebraic number theory computations (11Y40) Symbolic computation and algebraic computation (68W30)

Review text

The author shows that generally in an imaginary quadratic field, with or without Euclidean algorithm, the shortest division chain in an integral order is accomplished by the closest quotient in the Euclidean norm, i.e., for \(\rho_{i-1}\) and \(\rho_ i\) we choose \(\gamma_ i\) so that \(\rho_{i+1}=\rho_{i-1}-\gamma_ i\rho_ i\) is minimized. Special considerations are needed when the choice of \(\gamma_ i\) is not uniquely defined. Only in the ring for \(\sqrt{-11}\) is a counterexample possible. For \(\rho_ 0=6\), \(\rho_ 1=-2\sqrt{-11}\) the closest \(\gamma_ 1=0\) leads to a chain one member longer than \(\gamma_ 1=(1+\sqrt{-11})/2\). In practice, it may be more efficient to use the closest quotient than the shortest chain when a gcd is to be found [see \textit{E. Kaltofen} and the author, Math. Comput. 53, 697-720 (1989; Zbl 0687.12001)].

Recommendations

• On the number of divisions of the Euclidean algorithm applied to Gaussian integers
• scientific article; zbMATH DE number 3959562
• On the minimal algorithm in rings of imaginary quadratic integers
• Shortest division chains in unique factorization domains
• The number of steps in the Euclidean algorithm over complex quadratic fields

Cites work

• A complete determination of the complex quadratic fields of class-number one
• A weakening of the euclidean property for integral domains and applications to algebraic number theory. I.
• About Euclidean rings
• scientific article; zbMATH DE number 3959562 (Why is no real title available?)
• scientific article; zbMATH DE number 3728392 (Why is no real title available?)
• scientific article; zbMATH DE number 3531521 (Why is no real title available?)
• scientific article; zbMATH DE number 3198951 (Why is no real title available?)
• On the number of divisions of the Euclidean algorithm applied to Gaussian integers

Cited in

(6)

• On the minimal algorithm in rings of imaginary quadratic integers
• The Kronecker-Vahlen theorem fails in real quadratic norm-Euclidean fields
• Shortest division chains in unique factorization domains
• \((1+i)\)-ary GCD computation in \(\mathbb Z[i]\) as an analogue to the binary GCD algorithm.
• The number of steps in the Euclidean algorithm over complex quadratic fields
• On the asymptotic analysis of the Euclidean algorithm

This page was built for publication: Shortest division chains in imaginary quadratic number fields

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1813694)