Cryptography Reference
In-Depth Information
exponent
e
be given by
e
=(
e
n
−
1
e
n
−
2
...e
0
)
M
,toabase
M
yet to be
determined. The following algorithm calculates the powers
a
e
mod
m
.
M
-ary algorithm for exponentiation
a
e
mod
m
1.
Calculate and store
a
2
mod
m
,
a
3
mod
m
,
...
,
a
M
−
1
mod
m
as a table.
2.
Set
p ← a
e
n
−
1
mod
m
and
i ← n −
2
.
3.
Set
p ← p
M
mod
m
.
=0
, set
p ← pa
e
i
mod
m
.
4.
If
e
i
5.
Set
i ← i −
1
;if
i ≥
0
, go to step 3.
6.
Output
p
.
The number of necessary multiplications evidently depends on the number of
digits of the exponent
e
and thus on the choice of
M
. Therefore, we would like
to determine
M
such that the exponentiation in step 3 can be computed to the
greatest extent possible by means of squaring, as in the example above for
2
16
,
and such that the number of multiplications by the precomputed powers of
a
be
minimized to a justifiable cost of storage space for the table.
The first condition suggests that we choose
M
as a power of
2
:
M
=2
k
.In
view of the second condition we consider the number of modular multiplications
as a function of
M
:
We require
log
M
e
log
2
M
=
log
2
e
(6.1)
squares in step 3 and on average
=0)=
log
2
e
k
pr (
e
i
log
M
e
pr (
e
i
=0)
(6.2)
modular multiplications in step 4, where
=0)=
1
−
1
M
pr (
e
i
is the probability that a digit
e
i
of
e
is nonzero. If we include the
M −
2
multiplications for the computation of the table, then the
M
-ary algorithm
requires on average
−
2+
log
2
e
+
log
2
e
k
1
−
2
k
1
µ
1
(
k
):=2
k
(6.3)
1+
2
k
−
1
k
2
k
=2
k
−
2+
log
2
e
(6.4)
modular squarings and multiplications.
