Cryptography Reference
In-Depth Information
Z
it gives a decomposition of
as a disjoint union of nonempty equivalence classes
which, in this case, are called
congruence classes
. The congruence class or
residue
class
of
a
modulo
n
is the set
a
¯
={
b
∈ Z|
a
≡
b
(
mod
n
)
}={
a
+
nq
|
q
∈
is the ideal
6
of
Z}=
consisting of all multiples of
n
.Fromthe
definition of congruence, it readily follows that, for
a
a
+
n
Z
, where
n
Z
Z
,
b
∈ Z
,
a
≡
b
(
mod
n
)
if and
only if
a
and
b
give the same remainder (in the set
{
0
,
1
,...,
n
−
1
}
) when divided
by
n
, i.e., if and only if
a
mod
n
b
mod
n
.
It is clear then that the set of all con
gruen
ce classes modulo
n
has exactly
n
members and is the set
=
Z ={
0
. In this set, two binary operations
called
addition and
mul
tiplication are defined in a natural way by setting
Z
/
n
,...,
n
−
1
}
+
b
a
¯
=
·
b
a
. It is easily checked that these definitions are
correct (for the resulting class does not depend on the
representatives a
and
b
chosen
to represent the classes
+
b
and
a
¯
=
a
·
b
for
a
,
b
∈ Z
a
and
b
). Moreover, these operations give the set
the
structure of a
commutative ring with identity
, where the required ring properties are
derived from those of the addition and the multiplication in
¯
Z
/
n
Z
is a
quotient ring
(called the
residue class ring
modulo
n
). This is just the quotient group
Z
/
Z
, of which
Z
/
n
Z
.
There is an alternativeway of looking at this ringwhich is perhapsmore convenient
for our purposes. Let us consider the set
n
Z
which, since
n
Z
is an ideal of the ring, inherits the ring structure of
Z
(its elements are
called the
least non
-
negative residues
modulo
n
). The remainder of division of
a
by
n
is equal to the unique representative of the congruence class of
a
modulo
n
in
Z
n
={
0
,
1
,...,
n
−
1
}
Z
n
,
namely
a
mod
n
. Then it is easily checked that the map
Z
/
n
Z −→
Z
n
a
¯
−→
a
mod
n
,
from
a
the least non-negative
residue of
a
modulo
n
, is a bijection. Moreover, if one defines operations in
Z
/
n
Z
to
Z
n
, which assigns to each residue class
¯
Z
n
by
a
ab
mod
n
(we commit an obvious abuse of
notation here), so that now addition and multiplication are just the ordinary addition
and multiplication of integers followed by reduction modulo
n
, then the above map
preserves these operations and hencewe see that
+
b
=
(
a
+
b
)
mod
n
and
ab
=
Z
n
becomes a ring (commutative and
with 1) which is, actually, isomorphic to the ring
. This canonical isomorphism
allows us to identify these two rings and to work with whichever of them is more
convenient in a given setting. We shall usually work with
Z
/
n
Z
Z
n
and we remark that any
nontrivial alphabet, i.e., any finite set with more than one element, can be identified
with one of these sets and hence can be given the corresponding ring structure.
Remark 2.3
We will often use generic notation for the elements and operations of
the ring
Z
n
. For example, if
a
,
b
∈ Z
n
, we may write
a
+
b
for their sum in this ring
and we only write
Z
n
proceeds by adding the elements as integers and then taking the least non-negative
residuemodulo
n
. Asimilar remark applies to the product and other standard notation,
(
a
+
b
)
mod
n
if we want to emphasize that the addition in
6
An ideal of a (commutative) ring is an additive subgroup which is closed under multiplication by
elements of the ring.
