On computation of the greatest common divisor of several polynomials over a finite field. (Q1414018)

The author proposes a probabilistic algorithm for computing the greatest common divisor (gcd) of several polynomials over a finite field. The method is based on the work of \textit{G. Cooperman} et al. [Lect. Notes Comput. Sci. 1627, 310--317 (1999; Zbl 0977.11055)] on the gcd calculation of many integers. The idea consists in reducing the problem to determine the gcd of a pair of polynomials: Given \(m\) non-zero polynomials \(a_1,\ldots,a_m\in\mathbb{F}_q[X]\), choose \(2m\) random polynomials \(u_1,\dots,u_m\), \(v_1,\dots,v_m\in\mathbb{F}_q[X]\) of same degree and determine \[ D=\gcd\left(\sum_{j=1}^m u_ja_j,\sum_{j=1}^m v_ja_j\right). \] It is proved that with high probability \(D\) is exactly the gcd of \(a_1,\ldots,a_m\). Moreover, a detailed comparision of other reduction approaches is presented.