Publication: Average-case complexity of the Euclidean algorithm with a fixed polynomial over a finite field
No Thumbnail Available
Date
2021
Authors
Giménez, Nardo
Matera, Guillermo
Pérez, Mariana Valeria
Privitelli, Melina Lorena
Journal Title
Journal ISSN
Volume Title
Publisher
Cambridge University Press
Abstract
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.
Description
Keywords
Citation
Gimenez, 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-183