Parallel Algorithms for Algebraic Problems

Abstract

Fast parallel algorithms are presented for the following problems in symbolic manipulation of univariate polynomials: computing all entries of the extended Euclidean scheme of two polynomials over an arbitrary field, gcd and 1cm of many polynomials, factoring polynomials over finite fields, and the squarefree decomposition of polynomials over fields of characteristic zero and over finite fields. For the following estimates, assume that the input polynomials have degree at most n, and the finite field has $p^d $ elements. The Euclidean algorithm is deterministic and runs in parallel time $O(\log ^2 n)$. All the other algorithms are probabilistic (Las Vegas) in the general case, but when applicable to ${\bf Q}$ or ${\bf R}$, they can be implemented deterministically over these fields. The algorithms for gcd and lcm use parallel time $O(\log ^2 n)$. The factoring algorithm runs in parallel time $O(\log ^2 n\log ^2 (d + 1)\log p)$. The algorithm for squarefree decomposition runs in parallel time $O(\log ^2 n)$ for characteristic zero, and in parallel time $O(\log ^2 n+(d - 1)\log p)$ for finite fields. All Las Vegas algorithms have failure probability less than $2^{ - n} $. For all algorithms, the number of processors is polynomial in n.