Speaker: Saurabh Agarwal
Title: A Binary GCD Like Algorithm in a non-Euclidean Unique Factorization Domain

Abstract: GCD computation is one of the most fundamental computational problems of number theory. A well known algorithm for computing the gcd is Euclid's algorithm. While Euclid's algorithm is mathematically well understood, it is the Binary gcd algorithm of Stein which is used in practice. Attempts have been made to construct binary gcd like algorithms for algebraic number rings. Until now a binary gcd like algorithm have existed only for rings which are also Euclidean domains. In this talk, we will give a binary gcd like algorithm for a ring which is not Euclidean. This establishes that the binary gcd like approach is not restricted to Euclidean domains.

This is a joint work with Gudmund Frandsen and was presented at 6th Algorithmic Number Theory Symposium (ANTS VI).

Back to the Summer School Website: [html]