|
[____]
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 Bn (n=1, 2, ...) of groups, where Bn is
presented on n - 1 generators s1, ..., sn - 1 with the defining
relations
s_i s_j = s_j s_i (0 < i < j < n, j-i > 1)
s_i s_{i+1} s_i = s_{i+1} s_i s_{i+1} (0 < i < n-1) .
Bn is called braid group on n strings. In the sequel, we
refer to the above presentation as Artin presentation and to
s1, ..., sn - 1 as Artin generators of Bn.
Birman, Ko and Lee introduced an alternative way of presenting braid groups
[BKL98]. Here, Bn is presented on n(n - 1)/2 generators
ar, t (n ≥r > t ≥1) with the defining relations
a_{t,s} a_{r,q} = a_{r,q} a_{t,s} (n ≥t > s ≥1, n ≥r > q ≥1,
(t-r)(t-q)(s-r)(s-q) > 0)
a_{t,s} a_{s,r} = a_{t,r} a_{t,s} = a_{s,r} a_{t,r} (n ≥t > s > r > 0) .
We refer to this presentation as BKL presentation and to
ar, t (n ≥r > t ≥1) as BKL generators of Bn.
A possible choice for the BKL generators in terms of Artin generators is
ar, t = (sr - 1...st + 1) st (st + 1 - 1...sr - 1 - 1).
This identification is used in Magma.
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 and whose use for cryptographic purposes has been
suggested. The most important examples are variations of the conjugacy
problem.
However, both recent attacks on particular cryptosystems
[GKT+02], [HS03], [Hug02], [LL02], [LP03] and
advances in the analysis of the conjugacy problem
[GM02], [Geb03] in general
shed some doubts on the security of braid group cryptosystems. At the time
of this writing it is an open question whether braid group cryptosystems can
be made secure by an appropriate choice of parameters and keys or whether they
have to be considered as insecure. More research into these issues is
necessary.
The Magma category GrpBrd was introduced mainly with these applications
in mind. Focus was put on providing fast operations with elements and
on giving the user as much control over the details of computations as
possible.
In this section we briefly recall the basic terminology used for describing
elements of braid groups. More detailed descriptions can be found in
[ECH+92] for the Artin presentation and in
[BKL98] for the BKL presentation.
We remark that both Artin presentation and BKL presentation are special
cases of so-called Garside groups [Deh02].
In the sequel, let M be either the Artin presentation or the BKL presentation
of the braid group B on n strings, let X denote the generators of M
and let R denote the relations of M.
As the relations in R do not contain inverses of generators, we can interpret
M as monoid presentation. We denote the finitely presented monoid defined
by M by B^ +. The natural homomorphism from B^ + to B can be shown to be
injective. We identify its image with B^ + and call it the set of
positive elements of B. Finally, we denote the identity of B by 1.
We can now define two partial orderings on B. For elements u, v ∈B we
say u preceq v, if there exists a positive element a such that ua = v,
and we say v succeq u, if there exists a positive element a such that
v = au. Note that these partial orderings are different; u preceq v is
not equivalent to v succeq u.
B can be shown to be a lattice with respect to both partial
orderings, that is, for elements u, v ∈B there are elements
dl, ml, dr, mr ∈B such that
d_l \preceq u, d_l \preceq v and
d \preceq u, d \preceq v implies d \preceq d_l for all d in B
u \preceq m_l, v \preceq m_l and
u \preceq m, v \preceq m implies m_l \preceq m for all m in B
u \succeq d_r, v \succeq d_r and
u \succeq d, v \succeq d implies d_r \succeq d for all d in B
m_r \succeq u, m_r \succeq v and
m \succeq u, m \succeq v implies m \succeq m_r for all m in B
We call dl, ml, dr and mr the left-gcd, the left-lcm,
the right-gcd and the right-lcm, respectively, of u and v.
It can be shown that the left-lcm of the elements of X and the right-lcm
of the elements of X are equal; we call this element the fundamental
element of the presentation M and denote it by D. The fundamental
element is crucial for the study of braid groups. One of its most important
properties is that a certain power DN of D generates the centre of B.
(N = 2 for the Artin presentation and N = n for the BKL presentation.)
Moreover, u preceq Dk is equivalent to Dk succeq u and
Dk preceq u is equivalent to u succeq Dk for all k ∈Z, u ∈B.
In Magma, the partial ordering preceq is provided as operator
le and the partial ordering succeq is provided as
operator ge; see Section Boolean Predicates for Elements.
For a description of the functions computing lcm and gcd of elements,
see Section Lattice Operations.
The positive elements c of B satisfying c preceq D are called
simple elements; we denote the set of simple elements by C.
simple elements can be uniquely described by permutations on n points.
In Magma, a simple element c inducing a permutation π on the strings
on which B is defined, is represented by the permutation π - 1.
If M is the Artin presentation, every permutation on n points
corresponds to a simple element, that is, |C| = n!.
If M is the BKL presentation, |C| = (2n)!/(n!(n + 1)!) and only
permutations on n points which are products of
parallel, descending cycles correspond to simple elements. Here, a cycle
(i1, ..., ir) is called descending if i1> ... >ir
and two descending cycles (i1, ..., ir) and (j1, ..., js) are
called parallel if (ik - jl)(ik - jl')(ik' - jl)(ik' - jl') > 0
for all 1≤k, k'≤r and 1≤l, l'≤s. The descending cycle
(i1, ..., ir) corresponds to the element
ai1, i2ai2, i3 ... a_(ir - 1, ir) of B. It is obvious from the
defining relations that the simple elements defined by two parallel
descending cycles commute.
Every element u of B can be written in the form u = Dl c1 ... ck,
where l is a suitable integer and c1, ... ck are simple elements.
We call representations of this form simple element representations
or canonical factor products (CFP).
This section describes the ways in which elements of a braid group can be
represented internally by Magma. From the user's point of view, this
mainly affects input and printing of elements. This section is intended
to be a concise overview; for a detailed description of functions and for
examples we refer to Section Constructing and Accessing Braid Groups,
Section Creating Elements of a Braid Group and
Section Accessing Information.
Since an element of a braid group B can be represented either as word
in the generators or as product of simple elements (see Section
Lattice Operations)
with respect to either the Artin presentation or the BKL presentation of B,
there are four different ways of representing elements of B, which can
be used for entering or printing elements and for computing with elements.
Magma can work with all the above representations and conversions are
done automatically when necessary, for example, when multiplying an element
defined as word in the Artin generators with an element given as product
of simple elements for the BKL presentation. Hence, the user normally
does not have do give too much thought about how elements are represented.
It should be noted, however, that automatic conversions can affect performance
and that in time critical situations, the best results in general are
obtained if automatic conversions are avoided.
When creating a braid group B using the command BraidGroup,
the user can specify whether the Artin presentation or the BKL
presentation should be used as default presentation for B.
Unless specified otherwise by the user, this presentation is used in all
subsequent operations with B or with elements of B. In particular,
group operations and printing of elements are performed with respect to this
presentation. It is possible to change the default presentation using
the command SetPresentation. Certain commands accept a
parameter Presentation, which can be used to perform that command
with respect to a presentation other than the default presentation.
By default, group operations with elements of a braid group B are performed
using representations of the elements as products of simple elements for
the default presentation of B. Experienced users can change this
behaviour using the command SetForceCFP. If this flag is
set to false, arguments of a group operation are not automatically converted
into CFP representation if both arguments are represented as words in the
generators of the default presentation of B, but the operation is performed,
if possible, using the word representations instead.
The default printing format for an element u of a braid group B is that
both a representation of u as word in the generators of the default
presentation of B and a representation of u as product of
simple elements for the default presentation of B are printed.
Depending on the application, the user may wish to change the print format
so that only one of the above representations of u is printed. This can
be achieved using the command SetElementPrintFormat.
This section briefly describes the normal form for elements of braid groups.
For details we refer to [ECH+92] and [BKL98].
The Magma commands for computing normal forms are described in Section
Computing Normal Forms of Elements.
Let B be the braid group on n strings and fix a presentation M for B,
either the Artin presentation or the BKL presentation. A product of
simple elements
Dl c1 ... ck is said to be in left normal form with
respect to M,
if c1 ≠D, ck ≠1 and (ci - 1D) ^l ci + 1 = 1 for
i = 1, ..., k - 1, where (ci - 1D) ^l ci + 1 denotes the left-gcd
of ci - 1D and ci + 1 with respect to the presentation M.
Similarly, we define c1 ... ck Dl to be in right normal form
with respect to M, if ck ≠D, c1 ≠1 and
ci ^r (Dci + 1 - 1) = 1 for i = 1, ..., k - 1, where ^r
denotes right-gcd with respect to the presentation M.
It can be shown that the numbers of simple elements and the powers of D
in the left and right normal forms of an element are equal, that is, if
x∈B has left normal form Dl c1 ... ck and right normal form
bar(c)1 ... bar(c)kprime Dlprime then kprime=k and
lprime=l. In this situation we call l the infimum
of x, denoted by inf(x), k the canonical length of x,
denoted by len(x), and l + k the supremum of x,
denoted by sup(x). l is the maximal integer d satisfying
Ddpreceq x and l + k is the minimal integer d satisfying x preceq Dd.
To bring a product Dl c1 ... ck of simple elements into left normal
form, we proceed by induction, assuming that Dl c1 ... ck - 1 is in
left normal form. For i = k - 1, ..., 1 we now compute
d = (ci - 1D) ^l ci + 1 and, if d ≠1, replace ci by
ci d and ci + 1 by d - 1 ci + 1. Finally, we delete trailing trivial
simple elements and absorb simple elements equal to D into the leading
power of D. The result can be shown to be in
left normal form [ECH+92], [BKL98].
Both the theoretical complexity of this algorithm and its performance in
practice are determined by the gcd computations.
For the Artin presentation, the cost of computing the left-gcd of two
simple elements is O(n log n) [ECH+92], whence the complexity
of bringing a product of simple elements as above into left normal form is
O(k2 n log n).
For the Artin presentation, the cost of computing the left-gcd of two
simple elements is O(n) [BKL98], whence the complexity
of bringing a product of simple elements as above into left normal form is
O(k2 n).
Computing right normal forms is analogous.
This section outlines the algorithms used for lattice operations in a braid
group. Let u and v be elements of a braid group B and let M
be either the Artin presentation or the BKL presentation of B.
The Magma commands for computing mixed canonical forms are described in
Section Computing Normal Forms of Elements and the commands providing lattice
operations are described in Section Lattice Operations.
Evaluating partial orderings for u and v with respect to M is
straightforward. u preceq v if and only if u - 1 v is a positive
element with respect to M. The latter can be decided by computing
the left normal form Dl c1 ... ck of u - 1 v with respect
to M: u - 1 v is positive if and only if l≥0. Evaluating
the partial ordering succeq is analogous.
We call the tuple <a, b> the left-mixed canonical form of an element
x∈B, if a = a1 ... ak and b = b1 ... bs are positive elements
in left normal form (a1 = D, b1 = D is permitted), x = a - 1b and the
left-gcd of a1 and b1 is trivial.
Similarly, we call the tuple <a, b> the right-mixed canonical form
of x, if a = a1 ... ak and b = b1 ... bs are positive elements
in right normal form (ak = D, bs = D is permitted), x = ab - 1 and
the right-gcd of ak and bs is trivial.
It is not difficult to show that the left-gcd of u and v is given by
u a - 1, where <a, b> is the left-mixed canonical form of u - 1v,
and that the right-gcd of u and v is given by a - 1u, where
<a, b> is the right-mixed canonical form of u v - 1 [ECH+92].
Similarly, the left-lcm of u and v is given by
ua, where <a, b> is the right-mixed canonical form of u - 1v
and the right-lcm of u and v is given by au, where
<a, b> is the left-mixed canonical form of u v - 1
Computing the left-mixed canonical form of an element x can, after
writing x=a - 1b with two positive elements a and b, easily be
reduced to computing repeatedly the left-normal forms of a and b
and cancelling the left-gcd of the leading simple elements. Computing
the right-mixed canonical form is analogous.
Conjugacy testing, that is, deciding whether two given braids are conjugate,
and conjugacy search, that is, computing a conjugating
element for a pair of conjugate braids, are of particular
importance to public key cryptosystems based on braid groups. Known
algorithms for both conjugacy testing and conjugacy search require the
(at least partial) computation of an invariant of the conjugacy classes
of the elements in question, either the super summit set
[Gar69], [ERM94] or the ultra summit set
[Geb03].
This section recalls the definition of these invariants and sketches the
algorithms used for computing them, for conjugacy testing and for conjugacy
search. The relevant Magma commands are described in Section
Invariants of Conjugacy Classes.
For this section let B be a braid group and let M be either the
Artin presentation or the BKL presentation of B.
We define two operations, the cycling operation cyc and the
decycling operation dec, each mapping an arbitrary element x∈B
to a conjugate of x as follows.
Let x∈B be a braid with left normal form x = Dl c1 ... ck as
defined in Section Normal Form for Elements of a Braid Group. If k=0, we define
cyc(x) = x and dec(x) = x. Otherwise, we define
cyc(x) = Dl c2 ... ck (c1^(D - l)) and
dec(x) = Dl (ckDl) c1 ... ck - 1.
We now fix an element x∈B and consider the set Cx of all
conjugates of x. Proofs for the following
facts can be found in [ECH+92] or [BKL98].
- -
- The set {inf(y) : y∈Cx} is bounded above; we denote its
maximum by ss - inf(x).
- -
- The set {sup(y) : y∈Cx} is bounded below; we denote its
minimum by ss - sup(x).
- -
- The maximum of inf on Cx and the minimum of sup on
Cx can be achieved simultaneously.
We define three sets of conjugates of x as follows.
- -
- The set Px = { y∈Cx : y ∈B^ + }, containing the
positive conjugates of x.
- -
- The set Sx = { y∈Cx : inf(y) = ss - inf(x),
sup(y) = ss - sup(x) },
called the super summit set of x.
- -
- The set Ux = { y∈Sx : exists i>0 : cyci(y) = y },
called the ultra summit set of x.
Clearly, the sets Px, Sx and Ux only depend on the conjugacy class
of x. Moreover, the set Px is empty if ss - inf(x) < 0 and
it contains Sx if ss - inf(x) ≥0.
Proofs of the following properties can be found in [ECH+92] and
[BKL98] for the sets Px and Sx and in
[Geb03] for the set Ux.
- -
- The sets Px, Sx and Ux are finite.
- -
- The sets Sx and Ux are non-empty.
- -
- Representatives of Px, Sx and Ux, respectively, can be
obtained from x by a finite number of cycling and decycling
operations.
The main tools for computing the class invariants introduced in
Section Definition of the Class Invariants are the following "convexity" results
established in [ERM94] and [FGM03]
for the sets Px and Sx and in [Geb03] for the set
Ux. Let Ix ∈{ Px, Sx, Ux }.
- -
- For y, z∈Ix, there exists a finite
sequence y = y0, ..., yr=z such that for i=1, ..., r, yi∈Ix
and yi = yi - 1ci for a simple element ci.
- -
- For y∈Ix and a simple element c, there exists a
unique preceq-minimal element ιy(c) such that
c preceq ιy(c) and yιy(c) ∈Ix. Moreover,
ιy(c) is simple.
By the above results, any non-empty subset I⊆Ix with the
property that yιy(s) ∈I for all y∈I and all generators
s of the presentation M is equal to Ix. In particular,
Ix can be computed, starting from a single
representative, as closure under conjugation with minimal simple elements.
Algorithms for computing the minimal simple elements ιy(c) are given
in [FGM03] for the case Ix ∈{Px, Sx} and in
[Geb03] for the case Ix = Ux.
The Magma commands for computing the class invariants Px, Sx and
Ux as well as corresponding minimal simple elements ιy(c)
are described in Section Invariants of Conjugacy Classes.
Testing conjugacy of two braids x, y∈B can be performed using either
super summit sets or ultra summit sets. It is obvious from the results
cited in Section Definition of the Class Invariants that the following are equivalent.
- -
- x and y are conjugate in B.
- -
- Sx = Sy.
- -
- Ux = Uy.
- -
- Sx ∩Sy ≠emptyset.
- -
- Ux ∩Uy ≠emptyset.
If x and y are conjugate, a conjugating element can be obtained by
establishing an element z∈Sx ∩Sy or z∈Ux ∩Uy both
as conjugate of x and of y and keeping track of the conjugating elements
in each step.
The size of super summit sets grows rapidly with increasing values of
braid index n and canonical length. In general, computing super summit
sets is difficult or infeasible for braids on more than 5-10 strings, except
for very short canonical lengths. Ultra summit sets, on the other hand
tend to be much smaller and can frequently be computed for braids on up
to 100 strings and canonical length up to 1000, provided sufficient memory is
available [Geb03]. Conjugacy search may be successful
even in situations where the entire class invariant is too large to be
computed.
In Magma, conjugacy testing and conjugacy search based on ultra
summit sets is provided by the function IsConjugate.
[Next][Prev] [Right] [____] [Up] [Index] [Root]
|