Aarhus University Seal / Aarhus Universitets segl

A New GCD Algorithm for Quadratic Number Rings with Unique Factorization

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

  • Department of Computer Science
  • Teoretisk naturvidenskab
We present an algorithm to compute a greatest common divisor of two integers in a quadratic number ring that is a unique factorization domain. The algorithm uses bit operations in a ring of discriminant Δ. This appears to be the first gcd algorithm of complexity o(n 2) for any fixed non-Euclidean number ring. The main idea behind the algorithm is a well known relationship between quadratic forms and ideals in quadratic rings. We also give a simpler version of the algorithm that has complexity O(n 2) in a fixed ring. It uses a new binary algorithm for reducing quadratic forms that may be of independent interest.
Original languageEnglish
Title of host publicationLATIN 2006: Theoretical Informatics, Proceedings of 7th Latin American Symposium (Valdivia, Chile, March 20-24, 2006)
EditorsJosé R. Correa, Alejandro Hevia, Marcos A. Kiwi
Number of pages13
PublisherSpringer
Publication year2006
Pages30-42
DOIs
Publication statusPublished - 2006
EventA New GCD Algorithm for Quadratic Number Rings with Unique Factorization -
Duration: 17 Dec 2010 → …

Conference

ConferenceA New GCD Algorithm for Quadratic Number Rings with Unique Factorization
Periode17/12/2010 → …
SeriesLecture Notes in Computer Science
Volume3887

See relations at Aarhus University Citationformats

ID: 3715696