Cryptography Reference
In-Depth Information
As a result we have for
i
∈{
0
,...,f
}
the following expression for determining
e
i
:
e
i
=
((e_l
[
s
i
+1]
|
(e_l
[
s
i
+2]
<< BITPERDGT)) >>
d
i
)&(
2
k
−
1
);
(6.5)
Since for the sake of simplicity we set
e_l
[
s
f
+2]
←
0
, this expression holds
as well for
i
=
f
.
We have thus found an efficient method for accessing the digits of the
exponent in its
CLINT
representation, which arise from its representation
in a power-of-two base
2
k
with
k ≤
16
, whereby we are saved an explicit
transformation of the exponent. The number of necessary multiplications and
squarings for the exponentiation is now
1+
2
k
,
−
1
k ·
2
k
µ
2
(
k
):=2
k
−
1
+
log
2
e
(6.6)
where in comparison to
µ
1
(
k
)
(see page 87) the expenditure for the precomputa-
tions has been reduced by half. The table for determining the favorable values of
k
(Table 6-4) now has a somewhat different appearance.
Table 6-4. Numbers of multiplications for typical sizes of exponents and various bases
2
k
Number of Binary Digits in the Exponent
k
32
64
128
512
768
1024
2048
4096
1
47
95
191
767
1151
1535
3071
6143
2
4
88
176
704
1056
1408
2816
5632
3
4
5
168
664
994
1325
2648
5293
4
46
85
164
638
954
1270
2534
5066
5
53
91
167
626
931
1237
2459
4904
6
68
105
179
626
924
1222
2414
4798
7
99
135
209
647
939
1232
2401
4739
8
162
198
270
702
990
1278
2429
4732
Starting with 768 binary digits of the exponent, the favorable values of
k
are larger by 1 than those given in the table for the previous version of the
exponentiation algorithm, while the number of required modular multiplications
has easily been reduced. It is to be expected that this procedure is on the whole
more favorable than the variant considered previously. Nothing now stands in the
way of an implementation of the algorithm.
