Artículo
Average-case complexity of the Euclidean algorithm with a fixed polynomial over a finite field
Fecha de publicación:
06/07/2021
Editorial:
Cambridge University Press
Revista:
Combinatorics, Probability & Computing (print)
ISSN:
0963-5483
e-ISSN:
1469-2163
Idioma:
Inglés
Tipo de recurso:
Artículo publicado
Clasificación temática:
Resumen
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.
Palabras clave:
FINITE FIELDS
,
RATIONAL POINTS
,
EUCLIDEAN ALGORITHMS
,
SYMMETRIC FUNCTIONS
Archivos asociados
Licencia
Identificadores
Colecciones
Articulos(SEDE CENTRAL)
Articulos de SEDE CENTRAL
Articulos de SEDE CENTRAL
Citación
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; Cambridge University Press; Combinatorics, Probability & Computing (print); 31; 1; 6-7-2021; 166-183
Compartir
Altmétricas