Cryptography Reference
In-Depth Information
But what about 8 + 4? Now we try the following rule: Perform regular integer arith-
metic and divide the result by 9. We then consider
only the remainder
rather than
the original result. Since 8 + 4 = 12, and 12
/
9 has a remainder of 3, we write:
8 + 4
≡
3mod 9
We now introduce an exact definition of the modulo operation:
Definition 1.4.1
Modulo Operation
Let a
,
r
,
m
∈
Z
(where
Z
is a set of all integers) and m
>
0
. We write
≡
a
r
mod
m
if m divides a
r.
m is called the
modulus
and r is called the
remainder
.
−
There are a few implications from this definition which go beyond the casual rule
“divide by the modulus and consider the remainder.” We discuss these implications
below.
Computation of the Remainder
It is always possible to write
a
∈
Z
, such that
a
=
q
·
m
+
r
for
0
≤
r
<
m
(1.1)
−
·
−
≡
Since
a
r
=
q
m
(
m
divides
a
r
) we can now write:
a
r
mod
m
. Note that
∈{
0
,
1
,
2
,...,
m
−
}
r
1
.
Example 1.6.
Let
a
= 42 and
m
= 9. Then
42 = 4
·
9 + 6
and therefore 42
≡
6 mod 9.
The Remainder Is Not Unique
It is somewhat surprising that for every given modulus
m
and number
a
, there are
(infinitely) many valid remainders. Let's look at another example:
Example 1.7.
We want to reduce 12 modulo 9. Here are several results which are
correct according to the definition:
