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

a finite number of elements, all the orders of its elements are necessarily finite. We
also call order of a group its cardinality. We should thus avoid confusion between
the order of a group and the order of an element. We recall the famous Lagrange
Theorem.

Theorem 6.1 (Lagrange). In a finite group, the order of an element always divides
the order of its group.

How to compute orders in practice will be addressed in Chapter 7.

It is worth mentioning that we can characterize all finite Abelian groups by the
following result.

Theorem 6.2 (Reduction of finite Abelian groups). Let G be a finite Abelian group.
There exists a unique sequence n 1 ,..., n r of natural integers such that for all i , n i is

a factor of n i + 1 ,n 1 > 1 , and G is isomorphic to

Z n 1 ×···× Z n r .

6.2 The Ring Z n

6.2.1 Rings

Formally, a ring is an additively denoted Abelian group R with a second law which is
multiplicatively denoted and which fulfills the following ring properties.

1. Closure : For all a , b ∈ R , a × b is in R .

2. Associativity : is associative.

3. Neutral element : There exists a neutral element. Since it is necessarily unique,
we denote it by 1.
4. Distributivity : For any a

×

, b , c ∈ R ,wehave a × ( b + c ) = ab + ac and ( a +

b ) × c = ac + bc .

We notice that distributivity implies that a × 0 = 0 × a = 0 for any a :wehave a × 0 =

a × (0 + 0) = a × 0 + a × 0, which can be simplified by a × 0 to yield a × 0 = 0. We

thus notice that unless R is the trivial group, 0 must be different from 1: if 1 = 0, for any

= × = × =

a we have a 0, thus the group is trivial. We notice that elements

are not always invertible with respect to

a 1 a 0

× ×

a
cannot be equal to 1. We can however define the multiplicative group denoted R ∗ as
the set of all invertible ring elements. When the multiplicative group consists of R with
0 removed, we say that R is a field .

. 0 is actually not invertible since 0

In this topic we only consider commutative rings : rings for which the multiplication
is also commutative.