Cryptography Reference
In-Depth Information
APPENDIX
A
Background in Computational
Number Theory
The material presented in this appendix is merely the minimum needed for the few
examples of specific constructions presented in this topic. What we cover here are a few
structural and algorithmic facts concerning prime and composite numbers. For a more
comprehensive treatment, consult any standard textbook (e.g., [10]).
A.1. Prime Numbers
A
prime
is a natural number that is not divisible by any natural number other than itself
and 1. For simplicity, say that 1 is
NOT
a prime.
For a prime
P
, the
additive group modulo P
, denoted
Z
P
, consists of the set
{
and the operation of
addition
mod
P
. All elements except the iden-
tity (i.e., 0) have order
P
(in this group). The
multiplicative group modulo P
, denoted
Z
P
, consists of the set
{
1
,...,
P
−
1
}
and the operation of
multiplication
mod
P
. This
group is cyclic too. In fact, at least 1
/
log
2
P
of the elements of the group have order
P
−
1 and are called
primitive
.
1
0
,...,
P
−
1
}
A.1.1. Quadratic Residues Modulo a Prime
∈
Z
P
A
quadratic residue modulo a prime P
is an integer
s
such that there exists an
r
satisfying
s
r
2
(mod
P
). Thus, in particular,
s
has to be relatively prime to
P
.
Clearly, if
r
is a square root of
s
modulo
P
, then so is
≡
−
r
(since (
−
r
)
2
≡
r
2
). Fur-
thermore, if
x
2
s
(mod
P
) has a solution modulo
P
, then it has exactly two such
solutions (as otherwise
r
1
≡ ±
≡
r
2
(mod
P
) are both solutions, and 0
≡
r
1
−
r
2
≡
(
r
1
−
r
2
) (mod
P
) follows, in contradiction to the primality of
P
).
The quadratic residues modulo
P
form a subgroup of the multiplicative group
modulo
P
. The former subgroup contains exactly half of the members of the group.
1
The exact number of primitive elements modulo
P
depends on the prime factorization of
P
−
1
=
i
=
1
r
2
)(
r
1
+
P
e
i
i
(see Section A.2): It equals
i
=
1
((
P
i
−
1)
·
P
e
i
−
1
).
i
