## Abstract

There is a quadratic-time algorithm that determines conjugacy between finite subsets in any torsion-free hyperbolic group. Moreover, in any ?-generator, d-hyperbolic group G, if two finite subsets A and B are conjugate, then x^{-1} Ax = B for some x e G with ||x|| less than a linear function of max{||?|| : ? e A ? B}. (The coefficients of this linear function depend only on ? and d.) These results have implications for group-based cryptography and the geometry of homotopies in negatively curved spaces. In an appendix, we give examples of finitely presented groups in which the conjugacy problem for elements is soluble but the conjugacy problem for finite lists is not. © World Scientific Publishing Company.

Original language | English |
---|---|

Pages (from-to) | 725-756 |

Number of pages | 32 |

Journal | International Journal of Algebra and Computation |

Volume | 15 |

Issue number | 4 |

DOIs | |

Publication status | Published - Aug 2005 |

## Keywords

- Crytosystems
- Decision problems
- Hyperbolic groups
- Short homotopies