Algorithmic Algebra - A Classical Introduction to Cryptography: Applications for Communications Security - page 157

A subgroup of a group G is a subset G of G such that

1. G is nonempty,
2. for all a

G ,wehave ab − 1

, b ∈ ∈ G .

Therefore it is a nonempty subset stable by multiplication and inversion. As an example,
{ and G are subgroups of G . They are the trivial subgroups. Kernels and images of

group morphisms are subgroups. Interestingly, any group G is isomorphic to a subgroup
of S G :welet f be a mapping from G to S G , defined by f ( a ) as the permutation over G
which maps x onto ax . f is a group morphism which is injective. G is thus isomorphic
to the image of this group morphism which is hence a subgroup of S G . Therefore, any
finite group of cardinality n is isomorphic to a subgroup of S n .

1 G }

6.1.4 Building New Groups

G of any
two groups G and G as the set of pairs of elements of G and G with the product
law :

We can make new groups from others. We can make the group product G ×

( a , b ) . ( c , d ) = ( ac , bd ) .

( G × G )is We notice that the notion of product of group is associative since G ×

G . We can make the product of more groups. We can also
define G n . More generally, for any set A , we can define the group G A as the set of all
functions from A to G .

G )

isomorphic to ( G × ×

We can also obtain the quotient of an Abelian group G by a subgroup H . With
additive notations, we define a congruence in G in the following way: we say that
a

, b ∈ G are congruent if a − b ∈ H . We denote a ≡ b (mod H ). The congruence

class of a ∈ G is the set of all b ∈ G which are congruent to a . We can easily check

that this is a + H , the set of all a + h terms for h ∈ H . We then define G / H as the

set of all congruence classes. We can easily define additions in G / H by saying that the

sum of the class of a and the class of b is the class of a + b which is uniquely defined:

a (mod H ) and b b (mod H ), then a a + b (mod H ).

if a ≡ ≡ + b ≡

/

n Z .As
we will see, this group is actually isomorphic to the group Z n of residues modulo n that
was defined in Section 6.1.2, and we denote a

The set n Z of all multiples of n is a subgroup of Z . We can thus define Z

≡ b (mod n ) instead of a ≡ b (mod n Z ).

6.1.5 Fundamentals on Groups

We say that an element a of a finite group G has an order n if n is the smallest positive
integer such that a n = 1. Note that the order can be infinite, but when the group has