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

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

COMBINATORICS, PROBABILITY & COMPUTING (PRINT)

CAMBRIDGE UNIV PRESS

Año: 2022 vol. 31 p. 166 - 183

0963-5483

We analyse the behaviour of the Euclidean algorithm applied to pairs (g,f) of univariate nonconstant polynomials over a finite field Fq 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.