Cryptography Reference
In-Depth Information
CHAPTER 5
Modular Arithmetic:
Calculating with
Residue Classes
Every fine story must leave in the mind of the sensitive reader an intangible
residuum of pleasure
...
—Willa Cather,
Not Under Forty
, “Miss Jewett”
W
E BEGIN THIS CHAPTER WITH
a discussion of the principle of division with
remainder. In relation to this we shall explain the significance of these remainders,
their possible applications, and how one calculates with them. In order for the
functions to be introduced later to be understandable, we begin with a bit of
algebra.
We have seen that in division with remainder of an integer
a ∈
Z
byanatural
number
0
<m
∈
N
one has the unique representation
a
=
qm
+
r,
0
≤ r<m.
Here
r
is called the
remainder after division of
a
by
m
or the
residue of
a
modulo
m
, and it holds that
m
divides
a − r
without remainder, or in mathematical
notation,
m |
(
a − r
)
.
This statement about divisibility was given a new notation by Gauss, in
analogy to the equal sign:
1
a ≡ r
mod
m
(say “
a
is
congruent
to
r
modulo
m
”).
Congruence modulo a natural number
m
is an
equivalence relation
on the
set of natural numbers. This means that the set
R
:=
{
(
a, b
)
|
a
≡
b
mod
m
}
1
Carl Friedrich Gauss, 1777-1855, is to be counted among the greatest mathematicians of all
time. He made many significant discoveries in mathematics as well as in the natural sciences,
and in particular, at the age of 24 he published his famous
Disquisitiones Arithmeticae
, which
is the foundation upon which modern number theory has been built.
