Cryptography Reference
In-Depth Information
Here raising the base to the fifteenth power requires only six multiplications,
as opposed to fourteen in the first method. Half of these are squarings, which, as
we know, require only about half as much CPU time as regular multiplications.
Exponentiation to the sixteenth power is accomplished with only four squarings.
Algorithms for exponentiation of
a
e
modulo
m
that calculate with the binary
representation of the exponent are in general much more favorable than the first
approach, as we are about to see. But first we must observe that the intermediate
results of many integer multiplications one after the other quickly occupy more
storage space than can be supplied by all the computer memory in the world,
for from
p
=
a
b
follows
log
p
=
b
log
a
, and thus the number of digits of the
exponentiated
a
b
is the product of the exponent and the number of digits of the
base. However, if we carry out the calculation of
a
e
Z
m
,
that is, by means of
modular
multiplication, then we avoid this problem. In fact,
most applications require exponentiation modulo
m
, so we may as well focus our
attention on this case.
Let
e
=(
e
n
−
1
e
n
−
2
...e
0
)
2
with
e
n
−
1
>
0
be the binary representation
of the exponent
e
. Then the following
binary algorithm
requires
in a residue class ring
log
2
e
=
n
modular squarings and
δ
(
e
)
−
1
modular multiplications, where
n
−
1
δ
(
e
):=
e
i
i
=0
is the number of ones in the binary representation of
e
. If we assume that each
digit takes on the value
0
or
1
with equal probability, then we may conclude
that
δ
(
e
)
has the expected value
δ
(
e
)=
n/
2
, and altogether we have
2
log
2
e
multiplications for the algorithm.
Binary algorithm for exponentiation of
a
e
modulo
m
1.
Set
p ← a
e
n
−
1
and
i ← n −
2
.
2.
Set
p ← p
2
mod
m
.
3.
If
e
i
=1
, set
p
←
p
·
a
mod
m
.
4.
Set
i
←
i
−
1
;if
i
≥
0
, go to step 2.
5.
Output
p
.
The following implementation of this algorithm gives good results already for
small exponents, those that can be represented by the
USHORT
type.
