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

Nardo Giménez, Guillermo Matera, Mariana Pérez +1

We analyze the behavior of the Euclidean algorithm applied to pairs (g,f) of univariate nonconstant polynomials over a finite field F_q of q elements when the highest-degree polyno…