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

Simple item page
dc.contributor.authorGiménez, Nardo
dc.contributor.authorMatera, Guillermo
dc.contributor.authorPérez, Mariana Valeria
dc.contributor.authorPrivitelli, Melina Lorena
dc.date.accessioned2025-01-30T15:57:41Z
dc.date.available2025-01-30T15:57:41Z
dc.date.issued2021
dc.description.abstractWe 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.
dc.description.filiationFil: Gimenez, Nardo Ariel. Universidad Nacional de General Sarmiento. Instituto del Desarrollo Humano; Argentina
dc.description.filiationFil: Matera, Guillermo. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Universidad Nacional de General Sarmiento. Instituto del Desarrollo Humano; Argentina. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Matemática; Argentina
dc.description.filiationFil: Pérez, Mariana Valeria. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Universidad Nacional de Hurlingham. Instituto de de Tecnologia e Ingenieria; Argentina
dc.description.filiationFil: Privitelli, Melina Lorena. Universidad Nacional de General Sarmiento. Instituto de Ciencias; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina
dc.format.mimetypeapplication/pdf
dc.identifier.citationGimenez, 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
dc.identifier.doihttp://dx.doi.org/10.1017/S0963548321000274
dc.identifier.eissn1469-2163
dc.identifier.urihttps://www.cambridge.org/core/product/identifier/S0963548321000274/type/journal_article
dc.identifier.urihttps://repositorio.unahur.edu.ar/handle/123456789/521
dc.journal.number1
dc.journal.pagination166-183
dc.journal.titleCombinatorics Probability and Computing
dc.journal.volume31
dc.language.isoeng
dc.publisherCambridge University Press
dc.rights.licenseinfo:eu-repo/semantics/restrictedAccess
dc.subject.ocde1Ciencias Exactas y Naturales
dc.subject.ocde2Matemáticas
dc.subject.unahurCiencias Básicas y Aplicadas
dc.titleAverage-case complexity of the Euclidean algorithm with a fixed polynomial over a finite field
dc.typeinfo:eu-repo/semantics/article
dc.type.oaireinfo:eu-repo/semantics/article
dc.type.snrdinfo:ar-repo/semantics/artículo
dc.type.versioninfo:eu-repo/semantics/publishedVersion
dspace.entity.typePublication
relation.isAuthorOfPublication550d3f91-c6af-4379-a094-54e886b72955
Files
Collections
Artículos de revistas