Show simple item record

dc.contributor.authorCumplido, María
dc.contributor.authorGonzález Meneses, Juan
dc.contributor.authorSilvero, Marithania
dc.identifier.citationCumplido, M., González Meneses, J., Silvero, M. (2019). The Root Extraction Problem for Generic Braids. Symmetry, 11(11), 1327. DOI:
dc.description.abstractWe show that, generically, finding the k-th root of a braid is very fast. More precisely, we provide an algorithm which, given a braid x on n strands and canonical length l, and an integer k > 1, computes a k-th root of x, if it exists, or guarantees that such a root does not exist. The generic-case complexity of this algorithm is O(l(l + n)n3 log n). The non-generic cases are treated using a previously known algorithm by Sang-Jin Lee. This algorithm uses the fact that the ultra summit set of a braid is, generically, very small and symmetric (through conjugation by the Garside element D), consisting of either a single orbit conjugated to itself by D or two orbits conjugated to each other by D.es_ES
dc.description.sponsorshipAuthors partially supported by the Spanish research project MTM2016-76453-C2-1-P and FEDER. First author was also supported by EPSRC New Investigator Award EP/S010963/1. Third author was also supported by the Basque Government grant IT974-16 and Centro de Estudios Avanzados en Física, Matemáticas y Computación de la Universidad de Huelva.
dc.relation.isversionofPublisher’s versión
dc.rightsAtribución-NoComercial-SinDerivadas 3.0 España*
dc.subject.otherBraid groupses_ES
dc.subject.otherAlgorithms in groupses_ES
dc.subject.otherGroup-based cryptographyes_ES
dc.titleThe Root Extraction Problem for Generic Braidses_ES
dc.relation.projectIDinfo:eu-repo/grantAgreement/Spanish research project [MTM2016-76453-C2-1-P]

Files in this item

This item appears in the following Collection(s)

Show simple item record

Atribución-NoComercial-SinDerivadas 3.0 España
Except where otherwise noted, this item's license is described as Atribución-NoComercial-SinDerivadas 3.0 España

Copyright © 2008-2010. ARIAS MONTANO. Repositorio Institucional de la Universidad de Huelva
Contact Us | Send Feedback |