Average-case complexity of the Euclidean algorithm with a fixed polynomial over a finite field

NARDO GIMÉNEZ; GUILLERMO MATERA; MARIANA PÉREZ; MELINA PRIVITELLI

Congreso; Mathematical Congress of Americas; 2021

Universidad de Buenos Aires

Computing the greatest common divisor of two nonzero univariate polynomials with coefficients in a finite field Fq of q elements is a critical task, which arises in connection with many problems of computational mathematics. The fundamental computational tool for this problem is the Euclidean algorithm, and many variants of it are known in the literature. In particular, its average-case complexity has been the subject of several papers by, e.g., J. von zur Gathen, B. Vallée and others. All these results consider the average, for fixed degrees e>d>0, over the set of pairs (g,f)∈Fq[T]×Fq[T] with g monic of degree e and f either of degree at most d, or of degree less than e, assuming the uniform distribution of pairs. Nevertheless, there are important tasks which rely heavily on the computation of gcd´s and lie outside the scope of these analyzes, as the standard algorithm for finding the roots in Fq of a polynomial f∈Fq[T] of degree less than q, which requires computing gcd(Tq−T,f).In this talk we shall discuss the behavior of the Euclidean algorithm applied to pairs (g,f) of elements of Fq[T] when the highest-degree polynomial g is fixed. For this purpose, considering all the elements f of fixed degree, we establish asymptotically optimal bounds in terms of q for the number of elements f which are relatively prime with g and for the average degree of gcd(g,f). We also exhibit asymptotically optimal bounds for the average-case complexity of the Euclidean algorithm applied to pairs (g,f) as above.