| Motivated by a desire to test the security of the pubic key exchange protocol of I. Anshel, M. Anshel, and D. Goldfeld, ("An Algebraic Method for Public-Key Cryptography", Mathematical Research Letters, vol. 6, pp. 1--5, 1999), we study algorithmic approaches to the simple commutator decision and promise problems (SCDP/SCPP) for the braid groups B n. We take as our point of departure a seminal paper of O. Ore, ("Some Remarks on Commutators", Proceedings of the American Mathematical Society, Vol. 2, No. 2, pp. 307--314, 1951), which studies the SCPP for the symmetric groups.; Our results build on the work of H. Cejtin and I. Rivin, ("A Property of Alternating Groups", arXiv:math. GR/0303036). We extract, from their proof that any element of the alternating subgroup of Sn can be written as a product of two n-cycles, an explicit algorithm for solving the SCPP for Sn. We define a model of computation with respect to which the algorithm executes in time O(n2).; We then extend the algorithm to a subset of permutation braids of the braid groups Bn, to show that any element of the commutator subgroup [Bn, Bn] may be efficiently written as the product of a pure braid and a simple commutator of permutation braids. We use this result to define a probabilistic approach to the SCDP/SCPP, posing for future research the question of whether such an algorithm may be made efficient with respect to a measure of complexity such as that defined in a work of I. Kapovich, A. Myasnikov, P. Schupp, V. Shpilrain ("Average-Case Complexity and Decision Problems in Group Theory", Advances in Math. vol. 190, pp. 343--359, 2005). |
