Cryptography Reference
In-Depth Information
then obtain a structure that forms an abelian group with respect to mu
lt
iplication
(see Section 10.2). This structure, which in particular does not contain
0
,iscalled
a
reduced residue system
and is denoted by
Z
m
,
·
.
The significance of an algebraic structure like
Z
m
, ·
, in view of the results
we have obtained thus far, can be illustrated by looking at some other well-known
commutative rings: The set of integers
Z
Q
, the set of rational numbers
, and the
R
set of real numbers
are commutative rings with unit (in fact, the real numbers
form a field, indicating additional internal structure), with the difference that
these rings are not finite. The rules for computation that we have outlined above
for our finite ring are well known to us because we use them every day. We shall
return to these laws in Chapter 13. There they will prove to be trusty allies when
it comes to testing arithmetic functions. In this chapter we have collected some
important prerequisites.
For calculating with residue classes we rely completely on the classes'
representatives. For each residue class modulo
m
we select precisely one
representative and thereby form a
complete residue system
, in terms of which
all of our calculations modulo
m
can be carried out. The smallest nonnegative
complete residue system modulo
m
is the set
R
m
:=
{
0
,
1
,...,m−
1
}
.The
1
1
set of numbers
r
satisfying
−
2
m<r≤
2
m
will be called the
smallest absolute
complete residue system modulo
m
.
As an example we consider
26
=
0
,
1
,...,
25
. The smallest nonnegative
residue system modulo 26 is
R
26
=
{
0
,
1
,...,
25
}
Z
, and the smallest absolute
{−
12
,
−
11
,...,
0
,
1
,...,
13
}
residue system modulo 26 is the set
. The relation
between arithmetic with residue classes and modular arithmetic with residue
systems can be clarified as follows:
18 + 24 = 18 + 24 = 16
is equivalent to
18+24
≡
42
≡
16 mod 26
,
while
9
−
15 = 9+11=20
is equivalent to
9
−
15
≡
9+11
≡
20 mod 26
.
Z
26
or the set of ASCII
By identifying the alphabet with the residue class ring
Z
256
we can calculate with characters. A simple encoding system
that adds a constant from
characters with
Z
26
to each lette
r
of a text is ascribed to Julius Caesar,
whoissaidtohavepreferredtheconstant
3
. Each letter of the alphabet would
thereby be shifted one position to the right, with X moving to A, Y to B, and Z to C.
4
4
See Aulus Gellius, XII, 9 and Suetonius, Caes. LVI.
