Session S26 - Finite fields and applications

Friday, July 16, 15:00 ~ 15:20 UTC-3

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

Guillermo Matera

Universidad Nacional de General Sarmiento and CONICET, Argentina   -   This email address is being protected from spambots. You need JavaScript enabled to view it.

Computing the greatest common divisor of two nonzero univariate polynomials with coefficients in a finite field $\mathbb{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 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)\in\mathbb{F}_q[T]\times \mathbb{F}_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 $\mathbb{F}_q$ of a polynomial $f\in \mathbb{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 $\mathbb{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.

Joint work with Nardo Giménez (Universidad Nacional de General Sarmiento, Argentina), Mariana Pérez (Universidad Nacional de Hurlingham and CONICET, Argentina) and Melina Privitelli (Universidad Nacional de General Sarmiento and CONICET, Argentina).

View abstract PDF