Appendix D: Calculation Times

Team-Fly

---

CALCULATION TIMES FOR SEVERAL FLINT/C functions, calculated with a Pentium III processor running at 500 MHz and 64 Mbyte main memory, 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 shows, for comparison, calculation times that were measured for several functions in the GNU Multi Precision Arithmetic library (GMP, version 2.0.2); cf. page 420.

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
add_l	3.8 × 10−7	5.5 × 10−7	8.8 × 10−7	1.2 × 10−6	1.5 × 10−6	2.2 × 10−6
mul_l	1.9 × 10−6	5.1 × 10−6	1.6 × 10−5	3.3 × 10−5	5.6 × 10−5	2.1 × 10−4
sqr_l	1.5 × 10−6	3.7 × 10−6	1.1 × 10−5	2.1 × 10−5	3.5 × 10−5	1.3 × 10−4
div_l[a]	2.6 × 10−6	5.8 × 10−6	7.6 × 10−5	2.7 × 10−5	5.1 × 10−5	7.8 × 10−4
mmul_l	7.5 × 10−6	2.1 × 10−5	6.6 × 10−5	1.4 × 10−4	2.3 × 10−4	8.9 × 10−4
msqr_l	7.3 × 10−6	1.9 × 10−5	6.1 × 10−5	1.2 × 10−4	2.1 × 10−4	8.1 × 10−4
mexpk_l	1.2 × 10−3	6.4 × 10−3	3.8 × 10−2	1.2 × 10−1	2.1 × 10−1	1.9
mexpkm_l	5.4 × 10−4	2.9 × 10−3	1.7 × 10−2	5.2 × 10−2	1.2 × 10−1	8.6 × 10−1
[a]For the function div_l the number of digits refers to the dividend, while the divisor has half that number of digits.

Table D.2: Calculation times for several C functions (with 80×86 assembler support)

	Binary digits of the arguments; time in seconds
	128	256	512	768	1024	2048
mul_l	4.3 × 10−6	6.9 × 10−6	1.5 × 10−5	2.9 × 10−5	4.7 × 10−5	1.6 × 10−4
sqr_l	2.5 × 10−6	4.6 × 10−6	1.0 × 10−5	1.8 × 10−5	2.9 × 10−5	9.5 × 10−5
div_l[a]	2.7 × 10−6	4.6 × 10−6	1.0 × 10−5	1.8 × 10−5	2.9 × 10−5	9.5 × 10−5
mmul_l	8.0 × 10−6	1.3 × 10−5	3.3 × 10−5	6.4 × 10−5	1.0 × 10−4	3.8 × 10−4
msqr_l	7.2 × 10−6	1.1 × 10−5	2.9 × 10−5	5.6 × 10−5	9.0 × 10−5	3.1 × 10−4
mexpk_l	1.3 × 10−3	4.3 × 10−3	1.9 × 10−2	5.3 × 10−2	1.1 × 10−1	8.7 × 10−1
mexpkm_l	7.6 × 10−4	3.3 × 10−3	1.7 × 10−2	4.9 × 10−2	1.1 × 10−1	7.8 × 10−1
[a]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 less than half the time for the exponentiation with mexpk_l(). An RSA step with a 2048-bit key can thereby, with application of the Chinese remainder theorem (cf. page 199), be computed in 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 are roughly equally fast. There exists here an interesting potential for further improvement in the performance (cf. Chapter 18) by suitable assembler extensions.

In the comparison between the FLINT/C and GMP functions (see Table D.3) one may see that the GMP multiplication and division are faster by 30% and 40% than the corresponding FLINT/C functions. However, with the routine of modular exponentiation, the functions of both libraries amount more or less to the same thing, which turns out to be the same for arguments with 4096 digits as well. Since the GMP is considered the fastest of the available libraries for large-integer arithmetic, we need not be dissatisfied with this result.

Table D.3: Calculation times for several GMP functions (with 80×86 assembler support)

	Binary digits of the arguments; time in seconds
	128	256	512	768	1024	2048
mpz_add	2.4 × 10−7	3.2 × 10−7	3.6 × 10−7	4.2 × 10−7	4.5 × 10−7	6.9 × 10−7
mpz_mul	9.8 × 10−7	3.0 × 10−6	1.1 × 10−5	2.2 × 10−5	4.1 × 10−5	4.8 × 10−5
mpz_mod[a]	5.2 × 10−7	1.8 × 10−6	5.0 × 10−6	6.4 × 10−6	1.6 × 10−5	4.0 × 10−5
mpz_powm	4.5 × 10−4	2.6 × 10−3	1.7 × 10−2	5.2 × 10−2	1.7 × 10−1	7.8 × 10−1
[a]For the function mpz_mod the number of digits refers to the dividend, while the divisor has half that number of digits.

---

Team-Fly