For a general description of homomorphisms, we refer to Chapter MAPPINGS. This section describes some special aspects of homomorphisms whose domain is in the category GrpBrd.
An important special case of homomorphisms with domain in the category GrpBrd is the following. A homomorphism f:B -> G, where both B and G are in the category GrpBrd and the images of the Artin generators of B are words of length at most 1 in the Artin generators of G. This situation can for example occur for embeddings of certain subgroups; a setting which is of particular interest for cryptographic applications.
The Magma implementation uses special optimisation techniques, if a homomorphism with domain in the category GrpBrd has the additional properties listed above. Compared to the general case, this results in faster evaluation of such homomorphisms.
Computing preimages under homomorphisms with domain in the category GrpBrd currently is only supported for the special case described above.
Check: BoolElt Default: true
Returns the homomorphism from the braid group B to the group G defined by the assignment S. S can be the one of the following:Note, that it is currently not possible to define a homomorphism by assigning images to the elements of an arbitrary generating set of B.
- A list, sequence or indexed set containing the images of the k Artin generators B.1, ..., B.k of B. Here, the i-th element of S is interpreted as the image of B.i, that is, the order of the elements in S is important.
- A list, sequence, enumerated set or indexed set, containing k tuples <x_i, y_i> or arrow pairs x_i - > y_i, where x_i is a generator of B and y_i in G (i=1, ..., k) and the set {x_1, ..., x_k} is the full set of Artin generators of B. In this case, y_i is assigned as the image of x_i, hence the order of the elements in S is not important.
If the category of the codomain supports element arithmetic and element comparison, by default the constructed homomorphism is checked by verifying that the would-be images of the Artin generators satisfy the braid relations of B. In this case, it is assured that the returned map is a well-defined homomorphism. The most important situation in which it is not possible to perform checking is the case in which the domain is a finitely presented group (FPGroup; cf. Chapter FINITELY PRESENTED GROUPS) which is not free. Checking may be disabled by setting the parameter Check to false.
Given a homomorphism whose domain is a braid group B and an element e of B, return the image of e under f as element of the codomain of f.
Given a homomorphism whose domain is a braid group B, return the image of B under f as a subgroup of the codomain of f.
This function is not supported for all codomain categories.
Given a homomorphism whose domain is a braid group B and an element g of the image of f, return the preimage of g under f as an element of B.
This function currently is only supported, if the codomain G of f is in the category GrpBrd and the images of all Artin generators of B are words of length at most 1 in the Artin generators of G.
The domain of the homomorphism f.
The codomain of the homomorphism f.
The image or range of the homomorphism f as a subgroup of the codomain of f.
This function is not supported for all codomain categories.
> Bn := BraidGroup(10); > Sn := Sym(10); > f := hom< Bn->Sn | [ Sn!(i,i+1) : i in [1..Ngens(Bn)] ] >;Of course, the image of f is the full symmetric group.
> Image(f) eq Sn; trueNow we compute the image of a pseudo-random element of Bn under f.
> f(Random(Bn)); (1, 5, 8)(2, 4, 9, 7, 6, 3)
We set up these groups for l = 6 and r = 7.
> l := 6; > r := 7; > B := BraidGroup(l+r); > L := BraidGroup(l); > R := BraidGroup(r);We now construct the embeddings f : L -> B and g : R -> B.
> f := hom< L-> B | [ L.i -> B.i : i in [1..Ngens(L)] ] >; > g := hom< R-> B | [ R.i -> B.(l+i) : i in [1..Ngens(R)] ] >;To complete the preparatory steps, we choose a random element of B which is not too short.
> x := Random(B, 15, 25);The data constructed so far is assumed to be publicly available. Each time two users A and B require a shared key, the following steps are performed.
> a := Random(L, 15, 25); > y1 := NormalFormWord(x^f(a));We assess how well the secret element a is disguised in the normal form y_1 by comparing the word length of a to the lengths of the longest common prefix of y_1 and f(a^(-1)) and the longest common suffix of y_1 and f(a). We write two auxiliary functions to compute the latter.
> function LengthOfCommonPrefix(s1, s2) > i := 0; > while (i lt #s1 and i lt #s2 and s1[i+1] eq s2[i+1]) do > i +:= 1; > end while; > return i; > end function; > > LengthOfCommonSuffix := > func<s1,s2 | LengthOfCommonPrefix(Reverse(s1),Reverse(s2))>; > > #a; 19 > LengthOfCommonPrefix(Eltseq(f(a^-1)), Eltseq(y1)); 0 > LengthOfCommonSuffix(Eltseq(f(a)), Eltseq(y1)); 1We see that the normal form y_1 reveals almost no information about the conjugating element. Now for step (b):
> b := Random(R, 15, 25); > y2 := NormalFormWord(x^g(b)); > LengthOfCommonPrefix(Eltseq(g(b^-1)), Eltseq(y2)); 0 > LengthOfCommonSuffix(Eltseq(g(b)), Eltseq(y2)); 0 > #b; 21Again, the conjugating element is very well disguised in the normal form y_2. We now verify that A and B arrive at the same information in steps (c) and (d).
> K_A := NormalFormWord(y2^f(a)); > K_B := NormalFormWord(y1^g(b)); > AreIdentical(K_A, K_B); trueWe see that the information computed by A and B in steps (c) and (d) is indeed identical and hence can be used (in suitable form) as a common secret. [Next][Prev] [Right] [Left] [Up] [Index] [Root]