A New Approach to the Conjugacy Problem in Garside Groups

الأصل · EN

The cycling operation endows the super summit set Sₓ of any element x of a Garside group G with the structure of a directed graph Γₓ. We establish that the subset Uₓ of Sₓ consisting of the circuits of Γₓ can be used instead of Sₓ 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 are likely to have implications for the security of recently proposed cryptosystems based on the hardness of problems related to the conjugacy (search) problem in braid groups.