Calculation 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 | |
| 1.0 • 10−7 | 1.4 • 10−7 | 2.4 • 10−7 | 3.2 • 10−7 | 4.9 • 10−7 | 7.4 • 10−7 | 1.2 • 10−6 |
| 1.1 • 10−6 | 2.3 • 10−6 | 5.7 • 10−6 | 1.1 • 10−5 | 1.8 • 10−5 | 6.8 • 10−5 | 2.6 • 10−4 |
| 7.7 • 10−7 | 1.5 • 10−6 | 4.6 • 10−6 | 1.0 • 10−5 | 1.1 • 10−5 | 3.7 • 10−5 | 1.4 • 10−4 |
| 1.1 • 10−6 | 1.9 • 10−6 | 4.6 • 10−6 | 8.5 • 10−6 | 1.7 • 10−5 | 6.3 • 10−5 | 2.4 • 10−4 |
| 3.2 • 10−6 | 6.8 • 10−6 | 2.2 • 10−5 | 4.6 • 10−5 | 8.1 • 10−5 | 3.1 • 10−4 | 1.2 • 10−3 |
| 2.9 • 10−6 | 6.3 • 10−6 | 2.1 • 10−5 | 4.2 • 10−5 | 7.4 • 10−5 | 2.8 • 10−4 | 1.1 • 10−3 |
| 5.6 • 10−4 | 2.4 • 10−3 | 1.4 • 10−2 | 4.1 • 10−2 | 9.2 • 10−2 | 6.8 • 10−1 | 5.2 |
| 2.5 • 10−4 | 1.1 • 10−3 | 6.3 • 10−3 | 1.8 • 10−2 | 4.1 • 10−2 | 3.0 • 10−1 | 2.2 |
[a] For the function | |||||||
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 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 book, 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 80×86 assembler support)
Binary digits of the arguments; time in seconds | |||||||
|---|---|---|---|---|---|---|---|
128 | 256 | 512 | 768 | 1024 | 2048 | 4096 | |
| 1.5 • 10−6 | 2.2 • 10−6 | 4.6 • 10−6 | 9.1 • 10−6 | 1.4 • 10−5 | 4.9 • 10−5 | 1.9 • 10−4 |
| 1.2 • 10−6 | 1.8 • 10−6 | 3.6 • 10−6 | 5.8 • 10−6 | 9.1 • 10−6 | 2.8 • 10−5 | 9.9 • 10−5 |
| 9.8 • 10−7 | 9.7 • 10−7 | 2.3 • 10−6 | 3.1 • 10−6 | 5.7 • 10−6 | 2.0 • 10−5 | 7.3 • 10−5 |
| 2.8 • 10−6 | 4.8 • 10−6 | 1.1 • 10−5 | 2.1 • 10−5 | 3.4 • 10−5 | 1.2 • 10−4 | 4.7 • 10−4 |
| 2.3 • 10−6 | 4.2 • 10−6 | 9.5 • 10−6 | 1.9 • 10−5 | 2.9 • 10−5 | 1.0 • 10−4 | 3.8 • 10−4 |
| 4.1 • 10−4 | 1.3 • 10−3 | 6.1 • 10−3 | 1.7 • 10−2 | 3.6 • 10−2 | 2.5 • 10−1 | 1.9 |
| 2.8 • 10−4 | 1.1 • 10−3 | 5.9 • 10−3 | 1.7 • 10−2 | 3.7 • 10−2 | 2.7 • 10−1 | 2.1 |
[a] For the function | |||||||
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 | ||
| 4.3 • 10−8 | 5.4 • 10−8 | 7.8 • 10−8 | 1.0 • 10−7 | 1.4 • 10−7 | 2.2 • 10−7 | 4.1 • 10−7 |
| 1.7 • 10−7 | 5.5 • 10−7 | 1.8 • 10−6 | 3.7 • 10−6 | 8.1 • 10−6 | 1.9 • 10−5 | 5.7 • 10−5 |
| 2.1 • 10−7 | 5.1 • 10−7 | 1.2 • 10−6 | 1.8 • 10−6 | 3.9 • 10−6 | 9.4 • 10−6 | 3.1 • 10−5 |
| 5.6 • 10−5 | 4.0 • 10−4 | 2.4 • 10−3 | 6.7 • 10−3 | 2.5 • 10−2 | 1.0 • 10−1 | 6.5 • 10−1 |
[a] For the function | |||||||