Binary GCD like Algorithms for Some Complex Quadratic Rings

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearch

  • Department of Computer Science
On the lines of the binary gcd algorithm for rational integers, algorithms for computing the gcd are presented for the ring of integers in where . Thus a binary gcd like algorithm is presented for a unique factorization domain which is not Euclidean (case d=-19). Together with the earlier known binary gcd like algorithms for the ring of integers in and , one now has binary gcd like algorithms for all complex quadratic Euclidean domains. The running time of our algorithms is O(n 2) in each ring. While there exists an O(n 2) algorithm for computing the gcd in quadratic number rings by Erich Kaltofen and Heinrich Rolletschek, it has large constants hidden under the big-oh notation and it is not practical for medium sized inputs. On the other hand our algorithms are quite fast and very simple to implement.
Original languageEnglish
Title of host publicationAlgorithmic Number Theory : 6th International Symposium, ANTS-VI, Burlington, VT, USA, June 13-18, 2004, Proceedings
EditorsDuncan Buell
Number of pages15
Publication year2004
ISBN (print)978-3-540-22156-2
Publication statusPublished - 2004
Event6th International Symposium on Algorithmic Number Theory (ANTS-VI) - Burlington, VT, United States
Duration: 13 Jun 200418 Jun 2004
Conference number: 6


Conference6th International Symposium on Algorithmic Number Theory (ANTS-VI)
LandUnited States
ByBurlington, VT
SeriesLecture Notes in Computer Science

See relations at Aarhus University Citationformats

ID: 279858