Cryptography Reference
In-Depth Information
r
2
mod
N
and invoke the root-extraction algorithm to obtain
r
such that
3.
Set
s
←
(
r
)
2
≡
s
(mod
N
).
r
). If
g
4.
Compute
g
←
GCD
(
N
,
r
−
>
1, then
output g
and halt.
In case the algorithm halts with some output, the output is a non-trivial divisors of
N
.
The prime factorization of
N
can be obtained by invoking the algorithm recursively on
each of the two non-trivial divisors of
N
.
Analysis.
We can assume that
r
selected in Step 1 is relatively prime to
N
, or else the
GCD of
r
and
N
yields the desired divisor. Invoking the root-extraction algorithm, we
obtain
r
such that (
r
)
2
r
2
≡
s
≡
(mod
N
). Because the root-extraction algorithm
has no information on
r
(beyond
r
2
2
t
,wehave
r
≡±
(mod
N
) with probability 2
/
r
(mod
N
). Otherwise,
r
≡ ±
r
)(
r
r
)
r
(mod
N
), and still 0
≡
(
r
−
+
(mod
N
).
r
) has a non-trivial GCD with
N
, which is found in
Step 4. Thus, with probability at least
r
(resp.,
r
Therefore,
r
−
+
1
2
, we obtain a non-trivial divisor of
N
.
A.2.3. The Legendre and Jacobi Symbols
The
Legendre symbol
of integer
r
modulo a prime
P
, denoted
LS
P
(
r
), is defined as 0
if
P
divides
r
,as
1 otherwise.
Thus, for
r
that is relatively prime to
P
, the Legendre symbol of
r
modulo
P
indicates
whether or not
r
is a quadratic residue.
The Jacobi symbol of residues modulo a composite
N
is defined based on the prime
factorization of
N
. Let
i
=
1
P
e
i
+
1 in case
r
is a quadratic residue modulo
P
, and as
−
denote the prime factorization of
N
. Then the
Jacobi
symbol
of
r
modulo
N
, denoted
JS
N
(
r
), is defined as
i
=
1
LS
P
i
(
r
)
e
i
. Although the
Jacobi symbol (of
r
modulo
N
) is defined in terms of the prime factorization of the
modulus, the Jacobi symbol can be computed efficiently
without knowledge of the
factorization of the modulus
. That is, there exists a polynomial-time algorithm that
given a pair (
r
i
N
) computes
JS
N
(
r
). The algorithm proceeds in “GCD-like” manner
7
and utilizes the following facts regarding the Jacobi symbol:
,
=
1.
JS
N
(
r
)
JS
N
(
r
mod
N
)
2.
JS
N
(
a
·
b
)
=
JS
N
(
a
)
·
JS
N
(
b
), and
JS
N
(1)
=
1
1)
(
N
2
−
1)
/
8
3.
JS
N
(2)
=
(
−
(i.e.,
JS
N
(2)
=−
1iff
N
≡
4
±
1 (mod 8))
1)
(
N
−
1)(
r
−
1)
/
4
4.
JS
N
(
r
)
=
(
−
·
JS
r
(
N
) for odd integers
N
and
r
Note that a quadratic residue modulo
N
must have Jacobi symbol 1, but not all
residues of Jacobi symbol 1 are quadratic residues modulo
N
. (In fact, for
N
=
i
=
1
P
i
,
as in Section A.2.1, half of the residues with non-zero Jacobi symbols have Jacobi
symbol 1, but only a 2
−
t
fraction of these residues are squares modulo
N
.)
8
The fact that
7
E.g.,
JS
21
(10)
=
JS
21
(2)
·
JS
21
(5)
=
(
−
1)
55
·
(
−
1)
20
·
JS
5
(21)
=−
JS
5
(1)
=−
1. In general, Fact 2 is used
only with
a
=
2 (i.e.,
JS
N
(2
·
r
)
=
JS
N
(2)
·
JS
N
(
r
)). Also, at the very beginning, one can use
JS
2
N
(
r
)
=
JS
2
(
r
)
·
JS
N
(
r
)
=
(
r
mod 2)
·
JS
N
(
r
).
8
The elements of
Z
N
having Jacobi symbol 1 form a subgroup of
Z
N
. This subgroup contains exactly half of
the members of the group.
