Cryptography Reference
In-Depth Information
(
)
≈
(
−
)
−
(
)
−
so that if we use the approximation len
t
2len
p
q
len
p
3, given by
(
)
=
(
)
=
Proposition 6.3 for the number of iterations
t
, then if len
p
len
q
1024 and
len
(
t
)
=
64, we obtain 2len
(
p
−
q
)
−
1027
=
64. This tells us that if len
(
p
−
q
)
≤
546
then the factorization will be feasible in practice.
We see that if the difference
p
q
is close to
4
√
n
then Fermat's method is effecti
ve
to factor
n
. Thus, to obtain a security margin it seems reasonable to take
p
−
√
n
.
−
q
>
3
2
(
p
−
q
)
n
2
/
3
8
n
1
/
2
n
1
/
6
8
Then we would have, by Proposition 6.3, that
t
<
≈
=
.Ifwe
8
√
n
approximate
t
by this bound we obtain that len
3 and then the
computation would be infeasible for
n
a 1024-bit number, as this would imply a
number of iterations close to 2
167
. On the other hand, it has recently been shown in
[72] that, by combining it with an algorithm of Coppersmith, Fermat's method can
factor
n
in polynomial time whenever
(
t
)
≈
len
(
n
)/
6
−
n
1
/
3
. But one should not worry
much about this when choosing large primes
p
,
q
aiming at
n
|
p
−
q
|
<
pq
being hard
to factor. The reason is that the probability that two randomly chosen
k
-bit primes
p
,
q
, satisfy
=
1
/
3
, decreases exponentially as a function of
k
and is,
|
p
−
q
|
<(
pq
)
therefore, negligible.
6.4.4 Fermat's Factorization Method in Maple
We are going to implement Fermat's factoring method in Maple and perform some
experiments to check that the implementation behaves as predicted by the previous
estimates. For efficiency reasons, we are not going to work with
x
and
y
when trying
to find a value such that
x
2
y
2
but we are going to work instead with
k
−
n
=
=
2
x
+
1
x
2
and
r
=
−
n
. In the passage from one step of the algorithm to the next one, after
x
2
a value of
r
=
−
n
has been computed, the new value of
r
is obtained by adding
2
x
2
k
. Also, the value of
k
increases by 2 in each step (as the value of
x
is increased by 1). This is somewhat
more efficient because this way the computation of the square of
x
is replaced by an
addition. The algorithm is then the following:
=
2
x
+
1 to the old value (because
k
=
2
x
+
1
=
(
x
+
1
)
−
)
Algorithm 6.4. Fermat's factorization.
Input
:
n
, an odd composite integer.
Output
:
T
wo nontrivial factors of
n
.
x
:=
√
n
;
k
:=
2
x
+
1;
r
:=
x
2
−
n
;
while
r
is not a square
do
r
:=
r
+
k
;
k
:=
k
+
2
end do
;
x
:=
(
k
−
1
)/
2;
y
:=
√
r
;
return
x
−
y
,
x
+
y
.
