Cryptography Reference
In-Depth Information
Theorem 8.2.1
The set
Z
n
which consists of all integers i
= 0
,
1
,...,
n
−
1
for which
gcd(
i
,
n
)=1
forms an abelian group under multiplication modulo
n. The identity element is e
= 1
.
Let us verify the validity of the theorem by considering the following example:
Z
n
consists of the elements
{
1
,
2
,
4
,
5
,
7
,
8
}
Example 8.3.
If we choose
n
= 9,
.
Z
9
Table 8.1
Multiplication table for
×
mod 9
124578
1
124578
2
248157
4
487215
5
512784
7
751842
8
875421
Z
9
, depicted in Table 8.1, we can eas-
ily check most conditions from Definition 8.2.1. Condition 1 (closure) is satisfied
since the table only consists of integers which are elements of
By computing the
multiplication table
for
Z
9
. For this group
Conditions 3 (identity) and 4 (inverse) also hold since each row and each column
of the table is a permutation of the elements of
Z
9
. From the symmetry along the
main diagonal, i.e., the element at row
i
and column
j
equals the element at row
j
and column
i
, we can see that Condition 5 (commutativity) is satisfied. Condition
2 (associativity) cannot be directly derived from the shape of the table but follows
immediately from the associativity of the usual multiplication in
Z
n
.
Finally, the reader should remember from Section 6.3.1 that the inverse
a
−
1
of
∈
Z
n
can be computed by using the extended Euclidean algorithm.
each element
a
8.2.2 Cyclic Groups
In cryptography we are almost always concerned with
finite
structures. For instance,
for AES we needed a finite field. We provide now the straightforward definition of
a finite group:
