dc.creator | Cumplido Cabello, María | es |
dc.creator | González-Meneses López, Juan | es |
dc.creator | Silvero Casanova, Marithania | es |
dc.date.accessioned | 2020-01-15T11:02:35Z | |
dc.date.available | 2020-01-15T11:02:35Z | |
dc.date.issued | 2019-10 | |
dc.identifier.citation | Cumplido Cabello, M., González-Meneses López, J. y Silvero Casanova, M. (2019). The root extraction problem for generic braids. Symmetry, 11 (11), 1-15. | |
dc.identifier.issn | 2073-8994 | es |
dc.identifier.uri | https://hdl.handle.net/11441/91652 | |
dc.description.abstract | We 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 ∆), consisting of either a single orbit conjugated to itself by ∆ or two orbits conjugated to each other by ∆. | es |
dc.description.sponsorship | Ministerio de Economia, Industria y Competitividad (MINECO). España | es |
dc.description.sponsorship | European Commission (EC). Fondo Europeo de Desarrollo Regional (FEDER) | es |
dc.description.sponsorship | Engineering and Physical Sciences Research Council (UK) | es |
dc.description.sponsorship | Gobierno Vasco | es |
dc.description.sponsorship | Centro de Estudios Avanzados en Física, Matemáticas y Computación (Universidad de Huelva) | es |
dc.format | application/pdf | es |
dc.language.iso | eng | es |
dc.publisher | MDPI | es |
dc.relation.ispartof | Symmetry, 11 (11), 1-15. | |
dc.rights | Attribution-NonCommercial-NoDerivatives 4.0 Internacional | * |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/ | * |
dc.subject | Braid groups | es |
dc.subject | Aalgorithms in groups | es |
dc.subject | Group-based cryptography | es |
dc.title | The root extraction problem for generic braids | es |
dc.type | info:eu-repo/semantics/article | es |
dcterms.identifier | https://ror.org/03yxnpp24 | |
dc.type.version | info:eu-repo/semantics/publishedVersion | es |
dc.rights.accessRights | info:eu-repo/semantics/openAccess | es |
dc.contributor.affiliation | Universidad de Sevilla. Departamento de álgebra | es |
dc.relation.projectID | MTM2016-76453-C2-1-P | es |
dc.relation.projectID | EP/S010963/1 | es |
dc.relation.projectID | IT974-16 | es |
dc.relation.publisherversion | https://www.mdpi.com/2073-8994/11/11/1327/pdf | es |
dc.identifier.doi | 10.3390/sym11111327 | es |
dc.contributor.group | Universidad de Sevilla. FQM218: Singularidades, Geometría Algebraica Aritmética, Grupos y Homotopía | es |
idus.format.extent | 15 p. | es |
dc.journaltitle | Symmetry | es |
dc.publication.volumen | 11 | es |
dc.publication.issue | 11 | es |
dc.publication.initialPage | 1 | es |
dc.publication.endPage | 15 | es |