Page 25 - Hardware Implementation of Finite-Field Arithmetic

8 Cha pte r O n e

1.2 Algebra

1.2.1 Groups

Definitions 1.10 A group ( G, ) consists of a set G with a binary
*
operation* on G satisfying the following three axioms:
1. x (y z) = (x y) z, ∀ x, y, z ∈ G (associativity).
*
*
*
*
2. There is an identity (or unity) element 1 in G, such that x 1 =

*
1 x = x, ∀ x ∈ G.
*
3. For each element x of G there exists an element x , called the
− 1
inverse of x, such that
x x = x x = 1.
− 1
− 1
*
*
If, furthermore,
4. x y = y x, ∀ x, y ∈ G (commutativity), the group is said to be
*
*
commutative (or abelian) .
Axioms 1 and 2 define a semigroup .
Examples 1.5
• The set of integers Z with the operation + forms a group, with
0 as identity element.
• The set Z with the operation of addition modulo n forms a
n
group, with 0 as identity element.
• The set Z with the operation of multiplication modulo n
n
is not a group, since not all elements have multiplicative
inverses.
• The set Z with the operation of multiplication modulo n
n*
forms a group, with 1 as identity element.
The following definitions generalize the Definitions 1.9:
Definitions 1.11

1. The order of an element x of a finite group G is the least
positive integer t such that
t
x = x x . . . x = 1
*
*
*
2. If the order of x is equal to the number n of elements in G,
then x is said to be a generator of G.
3. If G has a generator, then G is said to be cyclic.
Property 1.5 The order of an element x of a finite group G divides the
number of elements in G.