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