Computing polynomial greatest common divisors using sparse interpolation

Computing polynomial greatest common divisors (GCD) plays an important role in Computer Algebra systems because the GCD operation is the bottleneck of many basic applications. For example, to simplify a rational function one divides the numerator and denominator by their GCD. In 1988 Ben-Or and Tiwari introduced the first deterministic polynomial interpolation algorithm which accounts for sparsity. The number of evaluation points needed by the Ben-Or/Tiwari algorithm is linear in the number of non-zero terms in the target polynomial, and moreover, all variables can be interpolated simultaneously hence parallelizing the algorithm is easier. In this thesis, we present modular multivariate polynomial GCD algorithms based on Ben-Or/Tiwari sparse interpolation. They compute the GCD modulo one or more primes. We apply a Kronecker substitution to reduce the number of variables and we modify the Ben-Or/Tiwari evaluation point sequence so that we can use primes of acceptable size (machine primes) as well as gain randomness on the choice of evaluation points to avoid several known issues in polynomial GCD algorithms. Based on several assumptions, we first present a simplified algorithm for GCD computation in Z[x1, . . . , xn] from which we derive some theoretical bounds and convince the reader why it works. Then we present a practical version of the algorithm where those assumptions are dropped. This leads to a more complicated algorithm but it can be shown that it always terminates and it computes the GCD efficiently. In the 1980s, subsequent research in polynomial GCD algorithm mainly focused on polynomials over number fields. In this thesis, we also present a GCD algorithm for multivariate polynomials in Q(_)[x1, . . . , xn] where _ is an algebraic number. With a prime modulus p, all operations are performed in the finite ring Zp(_) where inversions may fail due to zero divisors. We manage to get all necessary bounds to support the correctness of our algorithm.