Cryptography Reference
In-Depth Information
APPENDIX D
Calculation Times
C ALCULATION TIMES FOR SEVERAL FLINT/C functions, calculated with a Pentium 3
processor running at 2.4 GHz and 1 Gbyte main memory under Linux with gcc
3.2.2, are given in Tables D-1 and D-2. The times for n operations were measured
and then divided by n . Depending on the functions, n ranged between 100 and 5
million. An additional table (Table D-3) shows, for comparison, calculation times
that were measured for several functions in the GNU Multi Precision Arithmetic
library (GMP, version 4.1.2); cf. page 464.
Table D-1. Calculation times for several C functions (without assembler support)
Binary digits of the arguments; time in seconds
128
256
512
768
1024
2048
4096
10 7
10 7
10 7
10 7
10 7
10 7
10 6
add_l
1 . 0
·
1 . 4
·
2 . 4
·
3 . 2
·
4 . 9
·
7 . 4
·
1 . 2
·
10 6
10 6
10 6
10 5
10 5
10 5
10 4
mul_l
1 . 1
·
2 . 3
·
5 . 7
·
1 . 1
·
1 . 8
·
6 . 8
·
2 . 6
·
10 7
10 6
10 6
10 5
10 5
10 5
10 4
sqr_l
7 . 7
·
1 . 5
·
4 . 6
·
1 . 0
·
1 . 1
·
3 . 7
·
1 . 4
·
div_l
10 6
10 6
10 6
10 6
10 5
10 5
10 4
1 . 1
·
1 . 9
·
4 . 6
·
8 . 5
·
1 . 7
·
6 . 3
·
2 . 4
·
10 6
10 6
10 5
10 5
10 5
10 4
10 3
mmul_l
3 . 2
·
6 . 8
·
2 . 2
·
4 . 6
·
8 . 1
·
3 . 1
·
1 . 2
·
10 6
10 6
10 5
10 5
10 5
10 4
10 3
msqr_l
2 . 9
·
6 . 3
·
2 . 1
·
4 . 2
·
7 . 4
·
2 . 8
·
1 . 1
·
10 4
10 3
10 2
10 2
10 2
10 1
mexpk_l
5 . 6
·
2 . 4
·
1 . 4
·
4 . 1
·
9 . 2
·
6 . 8
·
5 . 2
10 4
10 3
10 3
10 2
10 2
10 1
mexpkm_l
2 . 5
·
1 . 1
·
6 . 3
·
1 . 8
·
4 . 1
·
3 . 0
·
2 . 2
*For the function div_l the number of digits refers to the dividend, while the divisor has half that number of
digits.
One can see clearly the savings that squaring achieves over multiplication.
Even the advantage realized by Montgomery exponentiation in mexpkm_l()
can been seen, which requires only a little more than half the time needed for
exponentiation using mexpk_l() . An RSA step with a 2048-bit key can thereby
be computed in half a second, and with application of the Chinese remainder
theorem (cf. page 203), in only one-fourth of a second.
Table D-2 demonstrates the difference in time that results from the use of
assembler routines. Assembler support results in a speed advantage of about 70%
for the modular functions. The gap between multiplication and squaring remains
stable at about 50%.
Since the two functions mulmon_l() and sqrmon_l() do not exist as assembler
routines, in this comparison the exponentiation function mexpk_l() can catch
up significantly to the Montgomery exponentiation mexpm_l() . Both functions
 
Search WWH ::




Custom Search