Cryptography Reference
In-Depth Information
the condition
log( X )
c log(log( X )) (log(log( X ))
1
2 log( X ) >
log(4)
+
log( c log(log( X )))) .
It is therefore natural to conclude that when c
2 there is a good chance that the Hasse
interval contains a log( p ) c smooth integer. Proving such a claim seems to be far beyond the
reach of current techniques.
15.4 The number field sieve
The most important integer factorisation algorithm for large integers is the number field
sieve (NFS). A special case of this method was invented by Pollard. 7 The algorithm requires
algebraic number theory and a complete discussion of it is beyond the scope of this topic.
Instead, we just sketch some of the basic ideas. For full details we refer to Lenstra and
Lenstra [ 334 ], Section 6.2 of Crandall and Pomerance [ 150 ], Section 10.5 of Cohen [ 127 ]
or Stevenhagen [ 525 ].
As we have seen from the quadratic sieve, reducing the size of the values being tested
for smoothness yields a better algorithm. Indeed, in the quadratic sieve the numbers were
reduced from size O ( N )to O ( N 1 / 2 + o (1) ) and, a s shown by Exercise 15.2.11 , this trick
alone lowers the complexity from O ( L N (1 / 2 , 2
o (1))). To
break the “ O ( L N (1 / 2 ,c )) barrier” one must make the numbers being tested for smoothness
dramatically smaller. A key observation is that if the numbers are of size O ( L N (2 / 3 ,c ))
then they are O ( L N (1 / 3 ,c )) smooth, for some constants c
+
o (1))) to O ( L N (1 / 2 , 1
+
and c , with probability
approximately 1 /u u
1 /L N (1 / 3 ,c/ (3 c )
=
+
o (1)). Hence, one can expect an algorithm
with running time O ( L N (1 / 3 ,c
+
o (1))) bit operations, for some constant c , by considering
smaller values for smoothness.
It seems to be impossible to directly choose values x such that x 2
(mod N )isofsize
L N (2 / 3 ,c
+
o (1)) for some constant c . Hence, the number field sieve relies on two factor
bases
B 2 ) and linear algebra one
finds an integer square u 2 and an algebraic integer square v 2 . The construction allows us to
associate an integer w modulo N to v such that u 2
B 1 and
B 2 . Using smooth elements over
B 1 (respectively,
w 2
(mod N ) and hence one can try
to split N .
We briefly outline the ideas behind the algorithm. First, choose a monic irreducible
polynomial P ( x )
∈ Z
(3 log( N ) / log(log( N ))) 1 / 3
[ x ]ofdegree d (where d grows like
)
=
N 1 /d
B 1 is primes
with a root m
modulo N (i.e., P ( m )
0(mod N )). Factor base
up to B
=
L N (1 / 3 ,c ) and factor base
B 2 is small prime ideals in the ring
Z
[ θ ]inthe
number field K
[ x ] / ( P ( x )) (i.e., θ is a generic root of P ( x )). The algorithm
exploits, in the final step, the ring homomorphism φ :
= Q
( θ )
= Q
Z
[ x ] / ( P ( x ))
→ Z
/N
Z
given by
φ ( θ )
=
m (mod N ). Suppose the ideal ( a
) is a product of prime ideals in
B 2 (one
7
The goal of Pollard's method was to factor integers of the form n 3
+ k where k is small. The algorithm in the case of numbers
of a special form is known as the special number field sieve .
 
Search WWH ::




Custom Search