Cryptography Reference
In-Depth Information
A detailed analysis of the time behavior of Montgomery reduction with the
various optimizations taken into account can be found in [Boss]. There we are
promised a ten to twenty percent saving in time over modular exponentiation by
using Montgomery multiplication. As can be seen in the overviews in Appendix D
of typical calculation times for FLINT/C functions, our implementations bear
out this claim fully. To be sure, we have the restriction that the exponentiation
functions that use Montgomery reduction can be used only for odd moduli.
Nonetheless, for many applications, for example for encryption and decryption,
as well as for computing digital signatures according to the RSA procedure (see
Chapter 17), the functions
mexp5m_l()
and
mexpkm_l()
are the functions of choice.
Altogether, we have at our disposal a number of capable functions for
modular exponentiation. To obtain an overview, in Table 6-5 we collect these
functions together with their particular properties and domains of application.
Table 6-5. Exponentiation functions in FLINT/C
Function
Domain of Application
General
2
5
-ary exponentiation, without memory allocation, greater
stack requirements.
mexp5_l()
General
2
k
-ary exponentiation with optimal
k
for
CLINT
numbers,
with memory allocation, lower stack requirements.
mexpk_l()
2
5
-ary Montgomery exponentiation for odd moduli, without
memory allocation, greater stack requirements.
mexp5m_l()
2
k
-ary Montgomery exponentiation for odd moduli, with optimal
k
for
CLINT
numbers up to 4096 binary digits, with memory allocation,
lower stack requirements.
mexpkm_l()
umexp_l()
Mixed binary exponentiation of a
CLINT
base with
USHORT
exponent,
lower stack requirements.
umexpm_l()
Mixed binary exponentiation of a
CLINT
base with
USHORT
exponent
and Montgomery reduction, thus only for odd moduli, lower stack
requirements.
wmexp_l()
Mixed binary exponentiation of a
USHORT
base with
CLINT
exponent,lower stack requirements.
wmexpm_l()
Mixed binary exponentiation with Montgomery squaring of a
USHORT
base with
CLINT
exponent, odd moduli, lower stack requirements.
mexp2_l()
Mixed exponentiation with a power-of-2 exponent, lower stack
requirements.
