Cryptography Reference
In-Depth Information
6.4.10 The Current Status of Factorization
6.4.10.1 The Number Field Sieve
The quadratic sieve was the most efficient factoring algorithm available until the
1990s but this is no longer the case since it has been superseded by the
number
field sieve
(NFS). The origin of NFS can be traced back to 1988, when John Pollard
suggested it as a method to factor integers that are close to a power, such as for
example Fermat numbers, but it was later extended to become a general factoring
method, also known as the
general number field sieve
(GNFS). NFS relies on the
same basic tools as QS, using factor bases, smoothness, sieving and linear algebra,
so it is not a big departure from a conceptual standpoint but, on the other hand, it
also makes use of much more sophisticated algebraic methods which are outside
the scope of this topic. The main idea is to go beyond the rings
Z
n
and to
use the ring of integers of an algebraic number field to generate the congruences
between squares modulo
n
. We refer to [60, 102, 194, 202] for details. The relevance
of NFS for cryptography lies in the fact that it is currently the fastest algorithm to
factor “difficult” numbers that are the product of two large primes which, as we will
see, are commonly used in the implementation of cryptographic schemes. Until the
arrival of NFS the fastest factoring algorithms (such as QS) had an expected running
time of
O
Z
and
1
/
2
1
/
2
and, because of the Canfield-Erdös-
Pomerance theoremwementioned, some people believed that this bound could not be
improved except perhaps for the 1
(
exp
((
1
+
o
(
1
))(
ln
n
)
(
ln ln
n
)
))
+
(
)
term. But NFS shattered this belief because,
under reasonable heuristic assumptions, it can be proved that its complexity is:
o
1
1
/
3
1
/
3
2
/
3
O
(
exp
(((
64
/
9
)
+
o
(
1
))(
ln
n
)
(
ln ln
n
)
)),
1
/
3
ie.,
O
, as defined in Definition 2.12. The complexities of
both QS and NFS are
subexponential
in the sense of Definition 2.13 and we recall that
this means that they are intermediate between polynomial and exponential. However,
as
n
gets larger, the complexity function of QS grows much faster than that of NFS.
We can use Maple to obtain a more precise idea about this. First we define these
complexities in Maple (ignoring the
o
(
L
n
[
1
/
3
,(
64
/
9
)
+
o
(
1
)
]
)
(
1
)
term) as approximate functions of the
number of bits of
n
:
> qsc := k -> evalf(exp(ln(2ˆk)ˆ(1/2)*ln(ln(2ˆk))ˆ(1/2))):
nfsc := k -> evalf(exp((64/9)ˆ(1/3)*ln(2ˆk)ˆ(1/3)*ln(ln(2ˆk))ˆ(2/3))):
Then we obtain a table (in the form of a matrix) with the values of these functions
for integers of 256
·
i
bits, with
i
ranging from 1 to 8 as follows:
> Matrix([x->x, qsc, nfsc]
∼
([seq(256*i, i=1..8)]))
