A fast Euclidean algorithm for Gaussian integers

DOI10.1006/JSCO.2001.0518MaRDI QIDQ1600038zbMATH OpenOpenAlexFDO

Authors George E. Collins

Publication date 11 June 2002

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

Full work available at URL https://semanticscholar.org/paper/ed559d3b642cb5d0746f26c5c39eb63385579af7

zbMATH Keywords

Euclid's algorithmGaussian integers

Mathematics Subject Classification ID

Multiplicative structure; Euclidean algorithm; greatest common divisors (11A05) Number-theoretic algorithms; complexity (11Y16) Approximation algorithms (68W25)

Review text

Euclid's algorithm with Gaussian integers is carried out using approximate division (leading parts only). Often the quotient has small components, and then addition and shifting can be used instead of multiplication, thereby speeding up the process. Experiments with randomly chosen numbers are reported, with tables showing the improvement obtained.

Recommendations

• scientific article; zbMATH DE number 3853202
• Performance of a GCD algorithm for Gaussian integers
• \((1+i)\)-ary GCD computation in \(\mathbb Z[i]\) as an analogue to the binary GCD algorithm.
• On the number of divisions of the Euclidean algorithm applied to Gaussian integers
• scientific article; zbMATH DE number 1643956

Cites work

• \((1+i)\)-ary GCD computation in \(\mathbb Z[i]\) as an analogue to the binary GCD algorithm.
• scientific article; zbMATH DE number 1643956 (Why is no real title available?)
• scientific article; zbMATH DE number 3728392 (Why is no real title available?)
• scientific article; zbMATH DE number 1178976 (Why is no real title available?)
• On the number of divisions of the Euclidean algorithm applied to Gaussian integers
• The Computing Time of the Euclidean Algorithm

Cited in

(12)

• On the number of divisions of the Euclidean algorithm applied to Gaussian integers
• Fast computation of the biquadratic residue symbol.
• New fast Euclidean algorithms
• Efficient algorithms for the gcd and cubic residuosity in the ring of Eisenstein integers
• scientific article; zbMATH DE number 1643956 (Why is no real title available?)
• The Euclid algorithm is ``totally Gaussian
• scientific article; zbMATH DE number 3853202 (Why is no real title available?)
• Two efficient algorithms for the computation of ideal sums in quadratic orders
• Another note on “Euclidean algorithms are Gaussian” by V. Baladi and B. Vallée
• Performance of a GCD algorithm for Gaussian integers
• A Paper-and-Pencil gcd Algorithm for Gaussian Integers
• Testing elementary function identities using CAD

This page was built for publication: A fast Euclidean algorithm for Gaussian integers

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