Cryptography Reference
In-Depth Information
R
n
(
a
):=
{
x
∈
Z
|
a
≡
x
(mod
n
)
}
are sometimes also used to refer to
R
n
(
a
).
Furthermore, one frequently uses the term residue to actually refer to a residue class.
For example, the residue (class) of 0 modulo 2 is the set of even integers, whereas
the residue (class) of 1 modulo 2 is the set of odd integers. Similarly, the residue
classes modulo 4 are defined as follows:
In the literature,
a
or
a
+
n
Z
0=0+4
Z
=
R
4
(0) =
{
0
,
0
±
4
,
0
±
2
·
4
,...
}
=
{
0
,
−
4
,
4
,
−
8
,
8
,...
}
1=1+4
Z
=
R
4
(1) =
{
1
,
1
±
4
,
1
±
2
·
4
,...
}
=
{
1
,
−
3
,
5
,
−
7
,
9
,...
}
2=2+4
Z
=
R
4
(2) =
{
2
,
2
±
4
,
2
±
2
·
4
,...
}
=
{
2
,
−
2
,
6
,
−
6
,
10
,...
}
3=3+4
Z
=
R
4
(3) =
{
3
,
3
±
4
,
3
±
2
·
4
,...
}
=
{
3
,
−
1
,
7
,
−
5
,
11
,...
}
As already mentioned in Section 3.1.2.3,
Z
n
is used to represent
Z
/n
Z
,
and
. It consists
of all residue classes modulo
n
(there are
n
such classes, because all residues
0
,
1
,...,n
Z
/n
Z
is used to represent the quotient group of
Z
modulo
n
Z
}
is called a
complete residue system modulo
n
. Note that other elements could also
be used to get a complete residue system modulo
n
, but that the ones mentioned
earlier simplify things considerably.
The modulo
n
operator defines a mapping
f
:
−
1 can occur in the division with
n
). In fact, the set
{
0
,...,n
−
1
Z
→
Z
n
, and this mapping
represents a homomorphism from
Z
n
. This means that we can add and multi-
ply residues (or residue classes, respectively) similar to integers. The corresponding
rules are as follows:
Z
onto
R
n
(
a
+
b
)=
R
n
(
R
n
(
a
)+
R
n
(
b
))
R
n
(
a
·
b
)=
R
n
(
R
n
(
a
)
·
R
n
(
b
))
Consequently, intermediate results of a modular computation can be reduced
(i.e., computed modulo
m
) at any time without changing the result. The following
examples are to make this point more clear.
R
7
(12 + 18)
=
R
7
(
R
7
(12) +
R
7
(18))
