Cryptography Reference
In-Depth Information
Theorem A.9
(
The Binomial Theorem)
Let
x,y
∈
R
, and
n
∈
N
. Then
n
i
x
n
−
i
y
i
.
n
(
x
+
y
)
n
=
i
=0
Proof
. See [167, Theorem 1.2.3, page 19].
✷
Note that the full and null summation properties in Proposition A.1 are
just special cases of the binomial theorem (with
x
=
y
= 1 and
x
=1=
−
y
,
respectively.)
A.3 Modular Arithmetic
Definition A.17
(
Congruences)
If
n
∈
N
, then we say that
a
is
congruent
to
b
modulo
n
if
n
|
(
a
−
b
)
, denoted
by
a
≡
b
(mod
n
)
.
On the other hand, if
n
(
a
−
b
)
, then we write
≡
a
b
(mod
n
)
,
and say that
a
and
b
are
incongruent
modulo
n
, or that
a
is
not congruent
to
b
modulo
n
. The integer
n
is the
modulus
of the congruence. The set
of
all
integers that are congruent to a given integer
m
modulo
n
, denoted by
m
,is
called the
congruence class
or
residue class
of
m
modulo
n
.
A.1
We have that
a
≡
b
(mod
n
), if and only if
a
=
b
+
nk
for some
k
∈
Z
. Thus,
a
b
(mod
n
) if and only if
a
=
b
with modulus
n
. Therefore, it makes sense
to have a canonical representative.
≡
Definition A.18
(
Least Residues)
If
n
r<n
is the remainder when
a
is divided by
n
, given by Theorem A.2, the Division Algorithm, then
r
is called
the
least (nonnegative) residue of
a
modulo
n
, and the set
∈
N
,
a
∈
Z
, and
a
=
nq
+
r
where
0
≤
{
0
,
1
,
2
,...,n
−
1
}
is
called the set of
least nonnegative residues modulo
n
.
Example A.3
There are four congruence classes modulo 4, namely,
0=
{
...,
−
4
,
0
,
4
,...
}
,
1=
{
...,
−
3
,
1
,
5
,...
}
,
A.1
Note that since the notation
m
does not specify the modulus
n
, then the bar notation
will always be taken in context.
Search WWH ::
Custom Search