Cryptography Reference
In-Depth Information
From here we obtain the final result easily as 16
≡
2 mod 7.
Note that we could perform the second method without a pocket calculator since
the numbers never become larger than 81. For the first method, on the other hand,
dividing 6561 by 7 is mentally already a bit challenging. As a general rule we should
remember that it is almost always of computational advantage to apply the modulo
reduction as soon as we can in order to keep the numbers small.
Of course, the final result of any modulo computation is always the same, no
matter how often we switch back and forth between equivalent classes.
Which Remainder Do We Choose?
By agreement, we usually choose
r
in Eq. (1.1) such that:
≤
≤
−
1
.
0
r
m
However, mathematically it does not matter which member of an equivalent class
we use.
1.4.2 Integer Rings
After studying the properties of modulo reduction we are now ready to define in
more general terms a structure that is based on modulo arithmetic. Let's look at the
mathematical construction that we obtain if we consider the set of integers from
zero to
m
−
1 together with the operations addition and multiplication:
Definition 1.4.2
Ring
The
integer ring
Z
m
consists of:
1. The set
Z
m
=
{
0
,
1
,
2
,...,
m
−
1
}
2. Two operations “
+
” and “
×
” for all a
,
b
∈
Z
m
such that:
1. a
+
b
≡
c
mod
m,
(
c
∈
Z
m
)
2. a
×
b
≡
d
mod
m,
(
d
∈
Z
m
)
Let's first look at an example for a small integer ring.
Example 1.9.
Let
m
= 9, i.e., we are dealing with the ring
Z
9
=
{
0
,
1
,
2
,
3
,
4
,
5
,
6
,
7
,
8
}
.
Let's look at a few simple arithmetic operations:
≡
6 + 8 = 14
5mod 9
×
≡
6
8 = 48
3mod 9
