Introduction

This chapter deals with another, quite specialised, class of finitely presented groups for which the word problem is solvable, the category of braid groups. The corresponding Magma category is called GrpBrd.

The notion of braid groups was introduced by Artin [Art47], who considered a sequence B_n (n=1, 2, ...) of groups, where B_n can be presented on n - 1 generators a_1, ..., a_(n - 1) with the defining relations

     a_t a_s = a_s a_t                         (0 < t,s < n, |t-s| > 1)
     a_t a_{t+1} a_t = a_{t+1} a_t a_{t+1}     (0 < t < n-1)  .

Recently, braid groups came under consideration as possible sources for public key cryptosystems [AAG99], [KLC+00]. The features of braid groups which make them interesting for public key cryptography are the following.

• The basic group operations in braid groups can be implemented efficiently on a computer.
• The word problem in braid groups is solvable, that is, there is a normal form for elements of a braid group and elements can be compared. Moreover, there are algorithms which are able to compute the normal form of an element efficiently.
• There are several problems in braid groups which are believed to be mathematically hard, for example the conjugacy problem, which can be used for cryptographic purposes.

In Magma, the elements of a braid group are represented as words a_(i_1)^(e_1) ... a_(i_k)^(e_k) (where 0 < i_j < n and e_(i_j) in {-1, + 1}) in the Artin generators.

Subsections

• Normal Form for Elements of a Braid Group

Normal Form for Elements of a Braid Group

This section briefly describes the normal form for elements used in the category GrpBrd. The algorithm used to compute the normal form of an element w in B_n has a complexity of O(l^2n), where l is the word length of the word in the Artin generators, representing w. For details we refer to [BKL98].

Let B_n be a braid group on n strings defined as above. For n >= t > s >= 1 define a_(t, s) := (a_(t - 1)...a_(s + 1)) a_s (a_(s + 1)^(-1)...a_(t - 1)^(-1)) and define delta := a_1...a_(n - 1).

Let pi = (i_1, ..., i_r) in Sym(n) be a cycle. If i_1> ... >i_r, we call pi descending and define a_pi := a_(i_1, i_2)a_(i_2, i_3) ... a_(i_(r - 1), i_r) in B_n.

Let pi = (i_1, ..., i_r) in Sym(n) and rho = (j_1, ..., j_s) in Sym(n) be cycles. If

(i_k - j_l)(i_k - j_(l'))(i_(k') - j_l)(i_(k') - j_(l')) > 0 (forall 1 <= k, k' <= r; 1 <= l, l' <= s),

we call pi and rho parallel and define a_(pi rho) := a_pi a_rho.

It is established in [BKL98] that any element u in B_n has a representative of the form delta^d .a_(pi_1) ... a_(pi_r) , where d in Z and pi_1, ..., pi_r are products of parallel descending cycles. The representative can be made unique by imposing an additional maximality condition on the length of the words a_(pi_1), ..., a_(pi_r), which basically means that factors corresponding to descending cycles have to be as far to the left as permitted by the above form.

Hence u can be uniquely described by the integer d and the sequence of permutations pi_1, ..., pi_r in Sym(n) as defined above.