Raid Braid: Fast Conjugacy Disassembly in Braid and Other Groups

The conjugacy problem in finitely presented groups is an impor- tant old problem that has gained prominence recently via group theoretical encryption methods. The theory of rewriting systems is extended to allow conjugacy problems in certain groups to be solved using rewriting methods. We construct explicit rewrite systems to solve the word and conjugacy prob- lems in the braid groups. We show that the complexity of both algorithms is polynomial-time. This resolves an old problem in low-dimensional topology and shows that the braid group is not a suitable platform group for cryptog- raphy, against expectations in the literature.