Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9493177 | Journal of Algebra | 2005 | 21 Pages |
Abstract
The cycling operation endows the super summit set Sx of any element x of a Garside group G with the structure of a directed graph Îx. We establish that the subset Ux of Sx consisting of the circuits of Îx can be used instead of Sx for deciding conjugacy to x in G, yielding a faster and more practical solution to the conjugacy problem for Garside groups. Moreover, we present a probabilistic approach to the conjugacy search problem in Garside groups. The results have implications for the security of recently proposed cryptosystems based on the hardness of problems related to the conjugacy (search) problem in braid groups.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Algebra and Number Theory
Authors
Volker Gebhardt,