Calculation Times - Cryptography in C and C++ - page 442

are roughly equally fast. There exists here an interesting potential for further
improvement in performance (cf. Chapter 19) by means of 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. In comparison with GMP version
2.0.2 in the first edition of this topic, the functions for modular exponentiation in
both libraries were about the same. Here GMP developers have achieved a speed
advantage of a factor of two for the GMP library.
Since the GMP library is the fastest of the available libraries for large-integer
arithmetic, we need not feel dissatisfied with this result. Rather, it can serve as
an impetus to the reader to plumb the possibilities of the FLINT/C library. What
would be required are assembler implementations of Montgomery multiplication
and squaring, a further development of the Karatsuba methods for multiplication
and squaring and their porting into assembler, and experiments for determining
the most advantageous combination of these methods.

Table D-2. Calculation times for several C functions (with 80x86 assembler support)

Binary digits of the arguments; time in seconds

128 256 512 768 1024 2048 4096

10 − 6 10 − 6 10 − 6 10 − 6 10 − 5 10 − 5 10 − 4 mul_l 1 . 5 · 2 . 2 · 4 . 6 · 9 . 1 · 1 . 4 · 4 . 9 · 1 . 9 ·

10 − 6 10 − 6 10 − 6 10 − 6 10 − 6 10 − 5 10 − 5 sqr_l 1 . 2 · 1 . 8 · 3 . 6 · 5 . 8 · 9 . 1 · 2 . 8 · 9 . 9 ·

div_l ∗ 10 − 7 10 − 7 10 − 6 10 − 6 10 − 6 10 − 5 10 − 5 9 . 8 · 9 . 7 · 2 . 3 · 3 . 1 · 5 . 7 · 2 . 0 · 7 . 3 ·

10 − 6 10 − 6 10 − 5 10 − 5 10 − 5 10 − 4 10 − 4 mmul_l 2 . 8 · 4 . 8 · 1 . 1 · 2 . 1 · 3 . 4 · 1 . 2 · 4 . 7 ·

10 − 6 10 − 6 10 − 6 10 − 5 10 − 5 10 − 4 10 − 4

msqr_l 2 . 3 · 4 . 2 · 9 . 5 · 1 . 9 · 2 . 9 · 1 . 0 · 3 . 8 ·

10 − 4 10 − 3 10 − 3 10 − 2 10 − 2 10 − 1 mexpk_l 4 . 1 · 1 . 3 · 6 . 1 · 1 . 7 · 3 . 6 · 2 . 5 · 1 . 9

10 − 4 10 − 3 10 − 3 10 − 2 10 − 2 10 − 1 mexpkm_l 2 . 8 · 1 . 1 · 5 . 9 · 1 . 7 · 3 . 7 · 2 . 7 · 2 . 1

*For the function div_l the number of digits refers to the dividend, while the divisor has half that number of digits.

Table D-3. Calculation times for several GMP functions (with 80x86 assembler support)

Binary digits of the arguments; time in seconds

128 256 512 768 1024 2048

10 − 8 10 − 8 10 − 8 10 − 7 10 − 7 10 − 7 10 − 7 mpz_add 4 . 3 · 5 . 4 · 7 . 8 · 1 . 0 · 1 . 4 · 2 . 2 · 4 . 1 ·

10 − 7 10 − 7 10 − 6 10 − 6 10 − 6 10 − 5 10 − 5

mpz_mul 1 . 7 · 5 . 5 · 1 . 8 · 3 . 7 · 8 . 1 · 1 . 9 · 5 . 7 ·

mpz_mod ∗ 10 − 7 10 − 7 10 − 6 10 − 6 10 − 6 10 − 6 10 − 5 2 . 1 · 5 . 1 · 1 . 2 · 1 . 8 · 3 . 9 · 9 . 4 · 3 . 1 ·

10 − 5 10 − 4 10 − 3 10 − 3 10 − 2 10 − 1 10 − 1

mpz_powm 5 . 6 · 4 . 0 · 2 . 4 · 6 . 7 · 2 . 5 · 1 . 0 · 6 . 5 ·

*For the function mpz_mod the number of digits refers to the dividend, while the divisor has half that number of
digits.