Cryptography Reference
In-Depth Information
6.4.10.2 A Factorization Record
Since NFS is the fastest factoring algorithm known so far, its running time plays a
crucial role in the choice of cryptographic parameters for schemes whose security
relies on the hardness of the integer factorization problem. We will examine this ques-
tion when discussing the security of these schemes but, for now, we will mention the
current factorization record (for an integer with two prime factors of approximately
the same size) which corresponds to the following 768-bit, 232-digit number:
> RSA768 :=
12301866845301177551304949583849627207728535695953347921973224521517264005072636\
57518745202199786469389956474942774063845925192557326303453731548268507917026122\
142913461670429214311602221240479274737794080665351419597459856902143413:
This number belonged to the now discontinued “RSA Factoring Challenge” [170]
and is the product of the primes:
> p := 334780716989568987860441698482126908177047949837137685689124313889828837938\
78002287614711652531743087737814467999489:
q := 367460436667995904282446337996279526322791581643430876426760322838157396665\
11279233373417143396810270092798736308917:
The bit length of
n
,
p
, and
q
is, respectively:
> ilog2
∼
([RSA768, p, q])+
∼
1;
[768, 384, 384]
and the verification that
p
and
q
are indeed the factors is easy:
> evalb(RSA768 = p*q);
true
The factorization of RSA768 was obtained by a team of researchers from several
countries led by T. Kleinjung and the method used was NFS. The factorization effort
is described in detail in [113] where it is estimated that the computation requiredmore
than 10
20
operations, the equivalent of almost 2000years of computing on a single
core 2.2GHz AMD Opteron. To give an idea of the size of the computation involved
we will only mention that the number of relations obtained was 64334489730 which,
after filtering and discarding some of them, produced a matrix of size 192796550
×
10
9
nonzero entries. The sieving step took a little
less than two years of computing time and the matrix step about four months, and
both were distributed on a variety of machines. The computation began in 2005
and was finished in December, 2009, but discarding some time spent on additional
computations and other work, total calendar timemay be estimated at about 2
192796550 with more than 27
·
5years.
Taking this as a reference, we can use the expected running time of GNFS to obtain
an estimate of the time it would require to factor, say, a 2048-bit integer (having only
two prime factors of approximately the same length) with the same computational
resources. The number of years would be:
.
> 2.5*nfsc(2048)/nfsc(768);
3.556619822*10ˆ12
or, taking into account the more recent estimates,
more than 250 times the age of the
universe!
