Page 26 - Hardware Implementation of Finite-Field Arithmetic

Mathematical Backgr ound 9

Proof First observe that if H is a subgroup of G, then an equivalence
relation on G can be defined: g ≡ g if there exists an element h in H
1 2
such that g h = g . The number of elements in an equivalence class is
1 2
equal to the number |H| of elements in H. Thus the number |G| of
elements in G is equal to |H||G/H|, G/H being the set of classes and
|G/H| the number of classes. In other words the number of elements
of a subgroup divides the number of elements of the group. It remains
to observe that the set {x, x , . . . , x = 1}, where t is the order of x, is a
2
t
subgroup, so that the number t of elements of the subgroup divides
the number of elements in G.
Example 1.6 Consider the multiplicative group Z = {1, 2, 3, 4, 5, 6}.
7*
In this case, 3 and 5 are generators; the subgroup generated by 2 is
{2, 4, 1}; the corresponding classes are then {2, 4, 1} and {6, 5, 3}; the
number of elements (3) of the subgroup divides the number of
elements (6) of Z .
7*
1.2.2 Rings

Definitions 1.12 A ring (R, +, ) consists of a set R with two binary
*
operations + and , satisfying the following axioms:
*
1. (R, +) is a commutative group with additive identity element 0.
2. x (y z) = (x y) z, ∀ x, y, z ∈ R (associativity).
*
*
*
*
3. There is a multiplicative identity element 1 , with 1 ≠ 0, such that
x 1 = 1 x = x, ∀ x ∈ R.
*
*
4. x (y + z) = (x y) + (x z) and (x + y) z = (x z) + (y z),
*
*
*
*
*
*
∀ x, y, z ∈ R (distributivity).
If, furthermore,
5. x y = y x, ∀ x, y ∈ R (commutativity), the ring is said to be
*
*
commutative.
Examples 1.7
• The set of integers Z with the usual operations + and · is a
commutative ring.
• The set Z with the addition and multiplication modulo n
n
operations is a commutative ring.
Definitions 1.13
1. A subset S of a ring R is called a subring of R, provided that S is
closed under + and and forms a ring under these operations.
*
2. A subset J of a ring R is called an ideal, provided that J is a
subring of R and for all a ∈ J and b ∈ R we have that ab ∈ J and
ba ∈ J.