Cryptography Reference
In-Depth Information
A.2.1. Quadratic Residues Modulo a Composite
For simplicity, we focus on odd composite numbers that are not divisible by any strict
prime power; that is, we consider numbers of the form
i
=
1
P
i
, where the
P
i
's are
distinct odd
primes and
t
>
1.
=
i
=
1
P
i
be such a composite number. A
quadratic residue modulo N
is
an integer
s
such that there exists an
r
Let
N
r
2
(mod
N
). Using the
Chinese Remainder Theorem, one can show that
s
is a quadratic residue modulo
N
if and only if it is a quadratic residue modulo each of the
P
i
's. Suppose that
s
is a
quadratic residue modulo
N
. Then the equation
x
2
∈ Z
N
satisfying
s
≡
s
(mod
N
) has 2
t
distinct (inte-
ger) solutions modulo
N
. Again, this can be proved by invoking the Chinese Remainder
Theorem: First observe that the system
≡
x
2
≡
s
(mod
P
i
)
for
i
=
1
,...,
t
(A.1)
has a solution. Next note that each single equation has two distinct solutions
±
r
i
(mod
P
i
), and finally note that each of the 2
t
different combinations yields a distinct-
solution to Eq. (A.1) modulo
N
(i.e., a distinct square root of
s
modulo
N
).
The quadratic residues modulo
N
form a subgroup of the multiplicative group mod-
ulo
N
. The subgroup contains exactly a 2
−
t
fraction of the members of the group.
Furthermore, for
N
=
i
=
1
P
i
(as before), squaring modulo
N
is a 2
t
-to-1 mapping of
the group to the subgroup. For further discussion of this mapping, in the special case
where
t
=
2 and
P
1
≡
P
2
≡
3 (mod 4), see Section A.2.4.
A.2.2. Extracting Square Roots Modulo a Composite
By the preceding discussion (and the effectiveness of the Chinese Remainder Theorem),
5
it follows that given the prime factorization of
N
, one can efficiently extract square roots
modulo
N
. On the other hand, any algorithm that extracts square roots modulo a com-
posite can be transformed into a factoring algorithm [187]: It suffices to show how
an algorithm for extraction of square roots (modulo a composite
N
) can be used to
produce non-trivial divisors of
N
. The argument is very similar to the one employed in
Section A.1.3, the difference being that there the root-extraction algorithm was assumed
to work only for extracting square roots modulo a prime (and such efficient algorithms
do exist), whereas here we assume that the algorithm works for extracting square roots
modulo composites (and such efficient algorithms are assumed not to exist).
Reduction of Factoring to Extracting Modular Square Roots.
On input a composite
number
N
, do the following:
∈{
,...,
−
}
1.
Uniformly select
r
1
N
1
.
2.
Compute
g
←
GCD
(
N
,
r
). If
g
>
1, then
output g
and halt.
6
(mod
P
i
) for
i
=
1
,...,
t
is solved by
i
=
1
c
i
·
a
i
mod
i
=
1
5
Specifically, the system
x
≡
a
i
P
i
, where
=
j
=
i
P
j
.
6
This step takes place in order to allow us to invoke the root-extraction algorithm only on relatively prime
pairs (
s
,
N
).
def
=
Q
i
·
(
Q
−
1
i
def
c
i
mod
P
i
) and
Q
i
