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,
 
 
Search WWH ::




Custom Search