Cryptography Reference
In-Depth Information
6.4.5 Factor Bases
As we have seen, Fermat's factorization method only works well when the difference
between the factors of
n
is relatively small because in that case the number of steps
will also be small. This is related to the fact that we want to write
n
as a difference
of squares,
n
y
2
, but there is another idea, originally due to Legendre, that
relaxes this requirement in a way that allows muchmore flexibility. Legendre realized
that if we have a congruence
x
2
x
2
=
−
y
2
, then we
also obtain a nontrivial factorization of
n
. The reason is that in this case
n
divides
x
2
≡
(
mod
n
)
such that
x
≡±
y
(
mod
n
)
y
2
−
=
(
x
+
y
)
·
(
x
−
y
)
but
n
divides neither
x
+
y
nor
x
−
y
and hence both
gcd
are proper factors of
n
. This situation always arises
whenever
n
is an odd composite with at least two different prime factors:
(
x
+
y
,
n
)
and gcd
(
x
−
y
,
n
)
Proposition 6.4
Let n be an odd positive integer which is composite and is not
a prime power. Then there exist x
such that x
2
y
2
,
y
∈ Z
≡
(
mod n
)
and x
≡
±
y
(
mod n
)
.
=
,
>
Proof
Since
n
is not a prime power we can write
n
ab
with
a
b
1 and
gcd
(
a
,
b
)
=
1. Let
y
∈ Z
such that gcd
(
y
,
n
)
=
1 and
x
∈ Z
such that
x
≡
y
(
mod
a
)
and
x
≡−
y
(
mod
b
)
(such an
x
exists by the Chinese remainder
theorem). Then
a
divides
x
−
y
and
b
divides
x
+
y
and, since
a
and
b
are relatively
and so
x
2
y
2
prime, their product divides
(
x
−
y
)(
x
+
y
)
≡
(
mod
n
)
. Suppose
now that
x
≡
y
(
mod
n
)
. Then we also have that
x
≡
y
(
mod
b
)
and hence
y
≡−
y
(
mod
b
)
and 2
y
≡
0
(
mod
b
)
. Since gcd
(
y
,
b
)
=
1, this implies that
b
2, which is a contradiction because we are assuming that
n
, and hence also
b
,is
odd. The case
x
=
≡−
y
(
mod
n
)
may be discarded in a similar manner.
In the remainder of this section we will assume that
n
is an odd composite integer
which is not a perfect square; the above proposition reduces the factorization of
such an
n
to the problem of finding congruences of the form
x
2
y
2
≡
(
mod
n
)
.
The condition
x
shows that this may not be enough to factor
n
but we shall not worry much about this because, assuming some kind of statistical
independence, one expects that at least half of these congruences lead to a nontrivial
factorization of
n
. Indeed, we have seen in Corollary 2.7 that if
n
is a product of two
different odd primes, then any quadratic residue modulo
n
has exactly four square
roots and the same proof (using the Chinese remainder theorem) serves to show that
if
n
has
r
different prime factors then each square modulo
n
has 2
r
square roots. Thus
a random square root of
x
2
modulo
n
(like
y
mod
n
if
x
2
≡±
y
(
mod
n
)
y
2
≡
(
mod
n
)
) has only a
2
r
2
x
modulo
n
and so, assuming that
x
and
y
have a random behavior, there is at most a probability equal to 2
−
t
/
≤
1
/
2 chance of being equal to either
x
or
−
that a
nontrivial factor of
n
will not be found after trying
t
congruences
x
2
y
2
)
(and this probability will be even lower if the number of prime factors of
n
is greater
than 2). This is only a heuristic, non-rigorous argument but it seems to work well in
practice and so, given a reasonable number of congruences
x
2
≡
(
mod
n
y
2
≡
(
mod
n
)
,we
expect that there is a high probability that they produce a factorization of
n
.
