Cryptography Reference
In-Depth Information
(
√
p
−
√
q
2
and, as
p
and
q
get larger, this number
)
number of iterations grows like
|
−
|
may stay fixed even as
p
q
grows. Let us analyze this question.
Proposition 6.3
q primes and let t be the number of iterations
in applying Fermat's method to the factorization of n. Then
Let n
=
pq with p
>
=
(
√
p
−
√
q
(
√
p
+
√
q
2
2
2
(i) t
)
/
2
=
(
p
−
q
)
/
2
)
,
2
<
(
p
−
q
)
1
,
(iii) If p and q are large primes of approximately the same length, then len
(ii) t
+
√
n
8
(
t
)
≈
2
len
(
p
−
q
)
−
len
(
p
)
−
3
.Iflen
(
p
−
q
)
≤
(
len
(
p
)
+
3
)/
2
, then one iteration
of the algorithm suffices to factor n.
Proof
To prove (i) note that t
he
algorit
hm
proceeds to compute
x
2
−
n
for
x
=
x
0
,
, where
x
0
=
√
n
=
√
n
p
+
q
we have that
x
2
x
=
x
0
+
1,
...
+
1.When
x
=
−
n
=
2
p
+
q
2
p
−
q
2
p
+
q
2
2
2
and
n
is then factored. The numbe
r
of ste
p
s is
t
(
)
−
n
=
(
)
=
−
=
(
(
√
p
)
+
(
√
q
(
√
n
−
√
n
−
√
p
√
q
−
√
p
√
q
2
2
)
p
+
q
p
+
q
+
1
)
+
1
=
=
)
=
2
2
2
(
√
p
2
+
√
q
2
2
√
p
√
q
=
(
√
p
−
√
q
(
√
p
+
√
q
2
2
2
−
)/
2
)
)/
2
=
(
p
−
q
)
/
2
)
.
−
√
n
(
√
n
p
+
q
2
p
−
q
2
2
2
For (ii) observe that, as befor
e,
t
=
satisfies
+
t
)
−
n
=
(
)
√
n
−
(
√
n
p
−
q
which in turn gives
t
2
2
. Discarding th
e
term
t
2
(which, moreover, in the cases of interest when
t
is much smaller than
√
n
,
w
ill
be small in comparison to 2
t
2
+
2
t
=
(
)
+
n
)
2
−
(
√
n
√
n
2
2
(
p
−
q
)
n
)
), we obtain the bound
t
<
+
.
√
n
√
n
8
2
Since the latter fraction is clearly
≤
1,
w
e
obtain the required bound. Observe that
<
√
8
4
√
n
then Fermat's method is successful after
this already tells us that if
p
−
q
only one iteration.
Finally, to prove (iii) observe that, taking bina
ry
lo
ga
rithms in (i) we obtain the
approximation len
(
√
p
+
√
q
(
t
)
=
2len
(
p
−
q
)
−
(
1
+
2l
e
n
))
.Now,since
p
and
q
have
(
√
p
+
√
q
(
√
p
approximat
el
y the same length, len
)
can be approximated by len
)
+
1
(
√
p
(
√
p
and 2len
)
≈
len
(
p
)
. Thus we obtain len
(
t
)
≈
2len
(
p
−
q
)
−
(
1
+
2
(
len
)
+
1
))
=
2len
(
p
−
q
)
−
len
(
p
)
−
3. Moreover, by (ii) we have that one iteration will
8
√
n
. Taking binary logarithms we see that this happens if
2
suffice if
(
p
−
q
)
≤
2len
(
p
−
q
)<
3
+
len
(
n
)/
2 which, approximating len
(
n
)/
2bylen
(
p
)
, gives that
one iteration suffices when len
(
p
−
q
)
≤
(
len
(
p
)
+
3
)/
2.
ab
and
a
is the smallest factor of
n
greater than
√
n
, then the
bounds given in Proposition 6.3 work as well even if
a
and
b
a
re composite. The case
n
Remark 6.8
If
n
=
a
2
is not included in the proposition but then
x
0
=
√
n
=
=
a
and
n
is factored
in one iteration.
q
must increase as
p
and
q
grow, in
order to prevent Fermat factoring. For example, if
p
and
q
are 1024-bit primes, (iii)
shows that one iteration suffices to factor
n
Proposition 6.3 shows that the difference
p
−
=
pq
even if
p
−
q
is a 513-bit number, i.e.,
greater than 10
150
. Let us then estimate how the length of
p
q
should be related to the
length of
p
(and
q
) to make Fermat's method infeasible. A computation involving 2
64
operations like those performed in each iteration of Fermat's method seems feasible,
−