info:eu-repo/semantics/restrictedAccessGiménez, NardoMatera, GuillermoPérez, Mariana ValeriaPrivitelli, Melina Lorena2025-01-302025-01-302021Gimenez, Nardo Ariel; Matera, Guillermo; Pérez, Mariana; Privitelli, Melina Lorena; Average-case complexity of the Euclidean algorithm with a fixed polynomial over a finite field (2021) Combinatorics, Probability & Computing, 31 (1) pp.166-183http://dx.doi.org/10.1017/S0963548321000274https://www.cambridge.org/core/product/identifier/S0963548321000274/type/journal_articlehttps://repositorio.unahur.edu.ar/handle/123456789/521We 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.application/pdfenginfo:eu-repo/semantics/articleCiencias Exactas y NaturalesMatemáticasCiencias Básicas y Aplicadas1469-2163