The number of steps in the Euclidean algorithm over complex quadratic fields
From MaRDI portal
Let \(L(u,v)=N\) be the least possible length of the number of divisions in the Euclidean algorithm of any two integers in \({\mathbb{Q}}(\sqrt{-m})\) where \(m=1,2,3,7\) or 11. The following result is proved: Let \(x\geq | v| \geq | u| >0\). The proportion of pairs for which \(c_ 1(m) \ln x\leq L(u,v)\leq c_ 2(m) \ln x\) tends to 1 as \(x\to \infty\), where \(c_ 1(m)\) and \(c_ 2(m)\) are positive constants depending only on m.
Recommendations
- The number of steps in the Euclidean algorithm
- On the number of divisions of the Euclidean algorithm applied to Gaussian integers
- A Simple Estimate for the Number of Steps in the Euclidean Algorithm
- scientific article; zbMATH DE number 3853202
- On the average number of steps in the Euclidean algorithm
Cites work
- A Simple Estimate for the Number of Steps in the Euclidean Algorithm
- scientific article; zbMATH DE number 3657869 (Why is no real title available?)
- scientific article; zbMATH DE number 3743380 (Why is no real title available?)
- On the number of divisions of the Euclidean algorithm applied to Gaussian integers
- Shortest division chains in imaginary quadratic number fields
- The exact length of the Euclidean algorithm in [ X ]
- The number of steps in the Euclidean algorithm
Cited in
(6)- Shortest division chains in imaginary quadratic number fields
- scientific article; zbMATH DE number 3853202 (Why is no real title available?)
- scientific article; zbMATH DE number 3875409 (Why is no real title available?)
- The exact length of the Euclidean algorithm in [ X ]
- The number of steps in the Euclidean algorithm
- \((1+i)\)-ary GCD computation in \(\mathbb Z[i]\) as an analogue to the binary GCD algorithm.
This page was built for publication: The number of steps in the Euclidean algorithm over complex quadratic fields
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q807674)
