Cryptography Reference
In-Depth Information
(
(
))
while loop is the number of bits of
e
which is
O
len
e
. Each modular operation
ln
2
n
2
(
)
=
(
(
)
)
<
requires
O
O
len
n
bit operations (since
m
n
). Furthermore, we
will usually assume that
e
<
n
(since, by Euler's theorem, if gcd
(
m
,
n
)
=
1 then
m
e
mod
n
m
e
mod
φ(
n
)
mod
n
) and hence
O
=
(
len
(
e
))
=
O
(
len
(
n
))
, so that the
3
running time of the algorithm is
O
.
We are now going to explore a couple of variants of the binary exponentiation
algorithm. Since they are quite simple, we do not describe them in detail, and we
just give Maple implementations from which the structure of these variants is easily
deduced. We start with a recursive version of the algorithm which can be easily
implemented in Maple as follows:
(
len
(
n
)
)
> RecModExp := proc(m::nonnegint, e::nonnegint, n::posint)
ife=0then
if m <> 0 then
return 1
else
error "0ˆ0 is undefined"
end if
end if;
ifm=0then
return 0
end if
if irem(e,2)=0 then
return RecModExp(mˆ2 mod n, iquo(e,2),n)
end if;
(m*RecModExp(mˆ2 mod n, iquo(e,2),n)) mod n;
end proc:
A slightly different version of the algorithm is the 'left to right' version in which
the bits of the exponent are scanned from the most significant to the least significant
one (note that Maple uses the little-endian convention so that when using Maple's
convert/base
function the bits of the list produced by it are actually scanned
from right to left). A Maple procedure implementing this variant is given in the
next function
ExpMod
, where we assume that
n
n
.Hereweuse
Maple's powerful left-fold operator
foldl
to perform the sequence of squarings
and multiplications (see Maple's help for a description of this function) but it is easy
to replace the use of
foldl
by a '
for
loop' performing the same operations:
>
2 and
m
<
> ExpMod := proc(m::nonnegint, e::nonnegint, n::posint)
local bits, x, y;
ife=0then
if m <> 0 then
return 1
else
error "0ˆ0 is not defined"
end if
end if;
bits := op(ListTools:-Reverse(convert(e, base, 2)[1 .. -2]));
foldl((x, y) -> modp(modp(xˆ2, n)*mˆy, n), m, bits)
end proc:
Exercise 2.21
Write a version of the function
ExpMod
that, instead of using the
command
foldl
,usesa
for
loop.
Of course, Maple also has a built-in function implementing the binary exponentia-
tion algorithm, namely
Power
, the inert power function, which is also represented by
