Title: Implementing the Thull-Yap fast integer GCD algorithm
Abstract: Euclid’s algorithm is one of the oldest algorithms ever.
Its role in number theory is fundamental and its analysis has a
long and rich history too. Algorihms computing the gcd of two
intergers are quadratic in the length of the operands and are not
favoured by current processors. This led to the development of
quadratic and subquadratic binary versions that are currently
the fastest in practice.
In some cases, we need the sequence of euclidean remainders
produced by Euclid’s original approach. Fast methods exist for this
task, but they are difficult to prove and implement. The latest of
these is due to Thull and Yap and was never really implemented
efficiently. We explain how to improve this algorithm, fixing some
missing points. We detail our implementation in GMP and give
benchmarks.
We exemplify the use of the algorithm with the particular case of
Cornacchia’s algorithm that is an important piece of the Complex
Multiplication Method in primality proving with elliptic curves, which
motivated our work.
Algorithmic Number Theory, Coding and Cryptography
