Cryptography Reference
In-Depth Information
2=
{
...,
−
2
,
2
,
6
,...
}
,
and
3=
{
...,
−
1
,
3
,
7
,...
}
,
since each element of
Z
is in exactly one of these sets.
In order to motivate the next notion we let
r
∈
Z
,
n
∈
N
, and consider the
set
{
r, r
+1
,...,r
+
n
−
1
}
.If
r
+
i
≡
r
+
j
(mod
n
) for 0
≤
i
≤
j
≤
n
−
1,
then
i
j
(mod
n
), so by the same argument as above
i
=
j
. This shows that
the
r
+
j
for 0
≡
≤
j
≤
n
−
1 are
n
distinct congruences classes.
Moreover, if
m
, then
m
must be in exactly one of the
n
congruence classes. In other
words,
m
∈
Z
r
+
j
(mod
n
) for some nonnegative integer
j<n
. This motivates
the following.
≡
Definition A.19
(
Complete Residue System)
Suppose that
n
∈
N
is a modulus. A set of integers
T
=
{
r
1
,r
2
,...,r
n
}
such that every integer is congruent to exactly one element of
modulo
n
is
called a
complete residue system modulo
n
. In other words, for any
a
T
∈
Z
,
there exists a unique
r
i
∈
T
such that
a
≡
r
i
(mod
n
)
. The set
{
−
}
0
,
1
,...,n
1
is a complete residue system, called the
least residue system modulo
n
.
Example A.4
The least residue system
m
odul
o
4 is
T
=
{
0
,
1
,
2
,
3
}
. Suppose
{
}
that we want to calculate the addition of
3
an
d
2
in
0
,
1
,
2
,
3
. First, we must
⊕
define what we mean by thi
s
addition. Let
a
b
=
a
+
b
where + is the ordinary
addi
ti
on of integers. Since 3 represents all integers of the form 3 + 4
k
,
k
∈
Z
,
and 2 represents all integers of the form 2 + 4
,
∈
Z
,
3+4
k
+2+4
=5+4(
k
+
) = 1 + 4(1 +
k
+
)
.
⊕
⊗
·
·
Hence, 3
2=1=3 + 2. Similarly, we may define
a
b
=
a
b
,
wh
er
e
i
s the
ordinary multiplication of
integ
ers
. The rea
de
r
ma
y v
erify t
h
at
2
⊗
3=2=
2
·
3.
Notice as well that since
a
−
b
=
a
+(
−
b
)=
a
⊕ −
b
, then 2
⊕ −
3=3=2
−
3,
for instance.
E
x
a
mple
A.4 i
llustrates the basic operations of addition and multiplication
in
{
0
,
1
,...,n
−
1
}
for any
n
∈
N
, namely,
a
⊕
b
=
a
+
b
and
a
⊗
b
=
a
·
b,
where
⊕
and
⊗
are well defined since + and
·
are well defined. Since it would be
cumbersome to use the notations of
⊕
, and
⊗
in general, we maintain the usage
of + for
, where we will understand that the the result of the given
operation is in the appropriate residue class.
⊕
and
·
for
⊗
The following result formalizes
this for us in general.
Search WWH ::
Custom Search