{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T03:48:05Z","timestamp":1760240885566,"version":"build-2065373602"},"reference-count":20,"publisher":"MDPI AG","issue":"11","license":[{"start":{"date-parts":[[2019,10,23]],"date-time":"2019-10-23T00:00:00Z","timestamp":1571788800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Symmetry"],"abstract":"<jats:p>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 &gt; 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 )   n 3  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    \u0394   ), consisting of either a single orbit conjugated to itself by    \u0394    or two orbits conjugated to each other by    \u0394   .<\/jats:p>","DOI":"10.3390\/sym11111327","type":"journal-article","created":{"date-parts":[[2019,10,25]],"date-time":"2019-10-25T03:20:36Z","timestamp":1571973636000},"page":"1327","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["The Root Extraction Problem for Generic Braids"],"prefix":"10.3390","volume":"11","author":[{"given":"Mar\u00eda","family":"Cumplido","sequence":"first","affiliation":[{"name":"Institut de Math\u00e9matiques de Bourgogne, UMR 5584, CNRS, Univ. Bourgogne Franche-Comt\u00e9, 21000 Dijon, France"},{"name":"Department of Mathematics, Heriot-Watt University, Edinburgh, Scotland EH14 4AS, UK"}]},{"given":"Juan","family":"Gonz\u00e1lez-Meneses","sequence":"additional","affiliation":[{"name":"Departamento de \u00c1lgebra, Universidad de Sevilla, 41012 Sevilla, Spain"}]},{"given":"Marithania","family":"Silvero","sequence":"additional","affiliation":[{"name":"Departamento de Ciencias Integradas, Universidad de Huelva, 21007 Huelva, Spain"}]}],"member":"1968","published-online":{"date-parts":[[2019,10,23]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Dehornoy, P. (2004). Braid-based cryptography. Group Theory, Statistics, and Cryptography, American Mathematical Society. Volume 360 of Contemporary Mathematics.","DOI":"10.1090\/conm\/360\/06566"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"287","DOI":"10.4310\/MRL.1999.v6.n3.a3","article-title":"An algebraic method for public-key cryptography","volume":"6","author":"Anshel","year":"1999","journal-title":"Math. Res. Lett."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Bellare, M. (2000). New public-key cryptosystem using braid groups. Advances in Cryptology \u2014 CRYPTO 2000, Springer.","DOI":"10.1007\/3-540-44598-6"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"282","DOI":"10.1016\/j.jalgebra.2005.02.002","article-title":"A new approach to the conjugacy problem in Garside groups","volume":"292","author":"Gebhardt","year":"2005","journal-title":"J. Algebra"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"629","DOI":"10.1016\/j.jsc.2010.01.013","article-title":"Solving the conjugacy problem in Garside groups by cyclic sliding","volume":"45","author":"Gebhardt","year":"2010","journal-title":"J. Symb. Comput."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/s00209-009-0502-2","article-title":"The cyclic sliding operation in Garside groups","volume":"265","author":"Gebhardt","year":"2010","journal-title":"Math. Z."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"594","DOI":"10.1016\/j.jalgebra.2006.03.018","article-title":"Garside groups are strongly translation discrete","volume":"309","author":"Lee","year":"2007","journal-title":"J. Algebra"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"2915","DOI":"10.1081\/AGB-120003997","article-title":"Extraction of roots in Garside groups","volume":"30","author":"Sibert","year":"2002","journal-title":"Comm. Algebra"},{"key":"ref_9","unstructured":"Digne, F., Godelle, E., Krammer, D., and Michel, J. (2015). Foundations of Garside Theory, European Mathematical Society (EMS). Volume 22 of EMS Tracts in Mathematics."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"101","DOI":"10.2307\/1969218","article-title":"Theory of Braids","volume":"48","author":"Artin","year":"1947","journal-title":"Ann. Math."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"654","DOI":"10.2307\/1969050","article-title":"On the algebraical braid group","volume":"49","author":"Chow","year":"1948","journal-title":"Ann. Math."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"479","DOI":"10.1093\/qmath\/45.4.479","article-title":"Algorithms for positive braids","volume":"45","author":"Elrifai","year":"1994","journal-title":"Q. J. Math."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Epstein, D.A., Cannon, J.W., Holt, D.F., Levy, S.V., Paterson, M.S., and Thurston, W.P. (1992). Word Processing in Groups, A. K. Peters, Ltd.","DOI":"10.1201\/9781439865699"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1006\/aima.2001.2010","article-title":"The Infimum, Supremum, and Geodesic Length of a Braid Conjugacy Class","volume":"164","author":"Birman","year":"2001","journal-title":"Adv. Math."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"221","DOI":"10.4171\/ggd\/12","article-title":"Conjugacy in Garside groups. I. Cyclings, powers and rigidity","volume":"1","author":"Birman","year":"2007","journal-title":"Groups Geom. Dyn."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"13","DOI":"10.4171\/ggd\/30","article-title":"Conjugacy in Garside groups II: Structure of the ultra summit set","volume":"2","author":"Birman","year":"2008","journal-title":"Groups Geom. Dyn."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"973","DOI":"10.1515\/jgth-2018-0027","article-title":"On the centralizer of generic braids","volume":"21","author":"Valladares","year":"2018","journal-title":"J. Group Theory"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1007\/BF01444642","article-title":"Artin groups of finite type are biautomatic","volume":"292","author":"Charney","year":"1992","journal-title":"Math. Ann."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"549","DOI":"10.4171\/ggd\/407","article-title":"On the genericity of pseudo-Anosov braids II: Conjugations to rigid braids","volume":"11","author":"Caruso","year":"2017","journal-title":"Groups Geom. Dyn."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"1103","DOI":"10.2140\/agt.2003.3.1103","article-title":"The n-th root of a braid is unique up to conjugacy","volume":"3","year":"2003","journal-title":"Algebraic Geom. Topol."}],"container-title":["Symmetry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-8994\/11\/11\/1327\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T13:28:37Z","timestamp":1760189317000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-8994\/11\/11\/1327"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,10,23]]},"references-count":20,"journal-issue":{"issue":"11","published-online":{"date-parts":[[2019,11]]}},"alternative-id":["sym11111327"],"URL":"https:\/\/doi.org\/10.3390\/sym11111327","relation":{},"ISSN":["2073-8994"],"issn-type":[{"type":"electronic","value":"2073-8994"}],"subject":[],"published":{"date-parts":[[2019,10,23]]}}}