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

Ciudad Autónoma de Buenos Aires

Congreso; Mathematical Congress of the Americas 2021; 2021

Mathematical Council of the Americas

Computing the greatest common divisor of two nonzero univariate polynomials with coefficients in a finite field F_q 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 Euclideanalgorithm, 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) in F_q[T]xF_q[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 F_q of a polynomial f in F_q[T] of degree less than q, which requires computing gcd(T^q-T,f).In this talk we shall discuss the behavior of the Euclidean algorithm applied to pairs (g,f) of elements of F_q[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.