KTH/SU Mathematics Colloquium

08-05-15

Niels Möller, KTH

Subquadratic GCD

Subquadratic divide-and-conquer algorithms for computing the greatest common divisor have been studied for a couple of decades. The integer case has been notoriously difficult, with the need for ``backup steps'' in various forms. This talk explains why backup steps are necessary for algorithms based directly on the quotient sequence, and proposes a robustness criterion that can be used to construct a ``half-gcd'' algorithm without any backup steps.