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 · Combinatorics Probability Computing · 2021
Abstract We analyse the behaviour of the Euclidean algorithm applied to pairs (g,f) of univariate nonconstant polynomials over a finite field $\mathbb{F}_{q}$ of q elements when the highest degree polynomial g is fixed. Considering all the elements f of fixed degree, we establish asymptotically optimal bounds in terms of q for the number of elements f that 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.