Cryptography Reference
In-Depth Information
⎡
⎣
⎤
⎦
256 1
.
462692684
·
10
13
1
.
115419155
·
10
14
512 6
.
686872748
·
10
19
1
.
756508010
·
10
19
768 1
.
274022968
·
10
25
1
.
077547366
·
10
23
1024 4
.
423742482
·
10
29
1
.
315844299
·
10
26
1280 5
.
053525463
·
10
33
5
.
889340171
·
10
28
1536 2
.
588065924
·
10
37
1
.
311509950
·
10
31
1792 7
.
161901227
·
10
40
1
.
736648126
·
10
33
2048 1
.
211314590
·
10
44
1
.
532970529
·
10
35
The first column gives the size of the number in bits, the second the value of the
QS running time function and the third the value of the NFS function. The following
picture gives a graphic of both functions up to 4096 bits (a logarithmic scale was
used for the
y
-axis, otherwise the curves would grow too steeply to fit in the picture):
> plots:-logplot([[x->x, qsc]
∼
([seq(256*i, i = 1..16)]),
[x->x, nfsc]
∼
([seq(256*i, i=1..16)])], linestyle=[3,1], color=[black,black],
legend=[QS,NFS], legendstyle=[location=top], title=['Running times of QS and NFS',
font=[helvetica,14]], labels=['Bit-length','Time'], labelfont=[helvetica,12])
We see that for 256-bit numbers QS is faster than NFS but the opposite is true
already for 512-bit numbers. This agrees pretty well with the results obtained in
practice, when NFS overtakes QS after 120-130 decimal digits. But notice also that,
for 2048-bit numbers (which, as we will see, is a common size for RSA moduli),
NFS is expected to be almost 10
9
times faster than QS.
There are a couple of excellent open-source implementations of NFS available,
which can be used to check the running time on integers of moderate size. They are
Msieve
[147] and GGNFS [85], both written in C, and can be downloaded from the
links given in the references.
