A parallel extended GCD algorithm (Q1018106)

This paper describes two new parallel algorithms for computing the greatest common divisor (GCD) of two integers \(u\) and \(v\). The second algorithm solves the extended GCD problem in that it also returns the Bézout coefficients, integers \(a\) and \(b\) such that \(|a| \leq v/2d\) and \(|b| \leq u/2d\) and \(au + bv = \gcd(u,v).\) The complexity of both algorithms matches the best-known result for these problems, namely time complexity \(O_\varepsilon(n / \log n)\) using \(n^{1 + \varepsilon}\) processors, where \(n\) is the bit-length of the larger of \(u\) and \(v\). The main result in both algorithms is a novel reduction algorithm that finds integers \(a\) and \(b\) such that \(|au - bv| < 2v/k\) for \(k = O(n)\) using the \(O(\log n)\) most significant bits of \(u\) and \(v\).