Cryptography Reference
In-Depth Information
=
,
≥
>
n
ab
with a
b
0
and representations of n of the form:
x
2
y
2
n
=
−
,
with x
>
y
≥
0
.
Proof
The correspondence is as follows. Given a factorization
n
=
ab
we define
a
+
b
a
−
b
a
+
b
a
−
b
2
2
x
2
y
2
.
x
=
and
y
=
and then we have that
n
=
ab
=
(
)
−
(
)
=
−
2
2
2
2
x
2
y
2
, define
a
For the inverse map, given
n
=
−
=
x
+
y
and
b
=
x
−
y
and note
x
2
y
2
that then
n
=
−
=
(
x
+
y
)(
x
−
y
)
=
ab
.
x
2
y
2
, we can proceed by exhaustive
In order to represent
n
in the form
n
=
−
=
√
n
search as follows. We start with
x
0
and for
x
=
x
0
,
x
0
+
1,
x
0
+
2,
...
we compute
x
2
n
until finding a square
y
2
. It is clear that if
n
−
=
ab
then the
a
+
b
number o
f
steps increases wi
th
the size of
x
=
(clearly, the number of iterations
−
√
n
−
√
n
2
a
+
b
is
x
+
1
=
+
1) and this number also increases as the difference
2
−
=
between the factors
a
2
y
increases. If
n
is odd and composite, the difference
between the factors is the largest possible when
n
b
=
3
p
with
p
prime. In this case,
if we solve the equations
x
+
y
=
n
/
3 and
x
−
y
=
3 we find that
x
=
(
n
+
9
)/
6
and
y
6. Thus we see that in the worst case this algorit
hm
is much less
efficient even than trial division, as it will require
=
(
n
−
9
)/
−
√
n
(
n
+
9
)/
6
+
1
=
Θ(
n
)
steps. Next we discuss the complexity of the method in more detail.
6.4.3.1 The Complexity of Fermat's Method
From the preceding discussion it follows that Fermat's method is most useful when
n
has two (not necessarily prime) factors whose difference is small. Small prime factors
of a number are easily factored out either by trial division or by the rho method (and
even more so by the Elliptic Curve Method, which we shall not discuss in detail) so,
if one wants to build a composite integer
n
that it is hard to factor, the size of the
prime factors should be as large as possible relative to the size of
n
. Bearing this in
mind we see that the integers of a given size which are most difficult to factor are
those that are the product of only two primes which have approximately the same
length. But Fermat's method tells us that these primes should not be too close to each
other for, in that case, the number will be easily factored.
Suppose, for simplicity, that
n
pq
is the product of two primes and we want
to factor it (as far as Fermat's method is c
o
ncerned, the argument applies equally
=
well if the two factors are the closest to
√
n
even if they are not primes but then
n
would probably be easier to factor by other methods). In several texts it is claimed
that the number of iterations in Fermat's algorithm when trying to factor
n
=
pq
is
of the order of
and so one should make this difference greater than a fixed
bound large enough to make the computation of
|
p
−
q
|
steps infeasible. As we are
going to see, this analysis is erroneous and it is not sufficient to take
|
p
−
q
|
greater
than a fixed bound to prevent the success of Fermat's method (see [198]). In fact, the
|
p
−
q
|
