Cryptography Reference
In-Depth Information
To demonstrate the implementation of these principles we select an adaptive
procedure that uses the appropriate optimal value for
k
. To accomplish this we
rely again on [Cohe] and look for, as is specified there, the smallest integer value
k
that satisfies the inequality
k
(
k
+ 1)2
2
k
2
k
+1
log
2
e ≤
− k −
2
,
(6.7)
which comes from the formula
µ
2
(
k
)
given previously for the number of
necessary multiplications based on the condition
µ
2
(
k
+1)
− µ
2
(
k
)
≥
0
.
The constant number of modular squarings
log
2
e
for all algorithms for
exponentiation introduced thus far is eliminated; here only the “real” modular
multiplications, that is, those that are not squarings, are considered.
The implementation of exponentiation with variable
k
requires a large
amount of main memory for storing the precomputed powers of
a
;for
k
=8
we require about 64 Kbyte for 127
CLINT
variables (this is arrived at via
2
7
1
−
* sizeof(USHORT) * CLINTMAXSHORT)
, where two additional automatic
CLINT
fields were not counted. For applications with processors or memory models
with segmented 16-bit architecture this already has reached the limit of what is
possible (see in this regard, for example, [Dunc], Chapter 12, or [Petz], Chapter 7).
Depending on the system platform there are thus various strategies
appropriate for making memory available. While the necessary memory for the
function
mexp5_l()
is taken from the stack (as automatic
CLINT
variables), with
each call of the following function
mexpk_l()
memory is allocated from the heap.
To save the expenditure associated with this, one may imagine a variant in which
the maximum needed memory is reserved during a one-time initialization and
is released only at the end of the entire program. In each case it is possible to fit
memory management to the concrete requirements and to orient oneself to this
in the commentaries on the following code.
One further note for applications: It is recommended always to check whether
it suffices to employ the algorithm with the base
M
=2
5
. The savings in time that
comes with larger values of
k
is relatively not so large in comparison to the total
calculation time so as to justify in all cases the greater demand on memory and
the thereby requisite memory management. Typical calculation times for various
exponentiation algorithms, on the basis of which one can decide whether to use
them, are given in Appendix D.
The algorithm, implemented with
M
=2
5
, is contained in the FLINT/C
package as the function
mexp5_l()
. With the macro
EXP_L()
contained in
flint.h
one can set the exponentiation function to be used:
mexp5_l()
or the following
function
mexpk_l()
with variable
k
.
