Shortest division chains in imaginary quadratic number fields (Q1813694)

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)].