Cryptography Reference
In-Depth Information
Example 2.14
Let us try to do a modular exponentiation by means of the naive
algorithm consisting in multiplying the basis by itself
e
−
1 times (where
e
is the
exponent):
> 21293ˆ4589764534197876275671393839 mod 298483279246566637216195857103;
Error, numeric exception: overflow
Here, Maple was trying to compute 21293
4589764534197876275671393839
before
reducing it modulo
n
298483279246566637216195857103. But this power is
an enormous number because, as can be seen by taking the logarithm, the size of a
power grows proportionally to the exponent, or, in other words, exponentially. Thus
this number does not fit in the computer's memory producing the overflow error. This
problem is easily corrected because all operations can be carried out modulo
n
, i.e.,
after each multiplication, the remainder of the result divided by
n
can be computed
and the multiplication result can be replaced by this remainder, so that no numbers
greater than
n
=
−
1 are ever multiplied. Let us try this in Maple:
>z:=1:
for i to 4589764534197876275671393839 do
z := 21293*z mod 298483279246566637216195857103
end do:
z;
Warning, computation interrupted
Nowmemorywas not a problembut we had to stop the computation becauseMaple
would be unable to complete it in our lifetime. Actually, we were asking Maple to
carry out 4589764534197876275671393838 multiplications and the same number
of divisions by 298483279246566637216195857103. Even assuming a computer
powerful enough for Maple to carry out one billion of these multiplication/division
pairs per second, this computation would take:
> 4589764534197876275671393838./(365*24*3600*10ˆ9);
1.455404786*10ˆ11
years. Taking into account that the age of the universe is variously estimated at
between 12 and 14 billion years (i.e., less than 14
10
9
years), we see that the entire
life of the universe would not be enough for this computation. Moreover, it should
be taken into account that the involved numbers in the example are relatively small
and, at any rate, much smaller than the numbers used in cryptographic applications.
The naive exponentiation algorithm requires a number of multiplications (and divi-
sions) that is just one less than the exponent. Thus the total number of operations is
proportional to the exponent (and not to its size!) and hence the algorithm runs in
exponential time.
·
Fortunately, we do not have to use the algorithm in the preceding example since
there is amuchmore efficient algorithmwhich runs in polynomial time, with the num-
ber of operations bounded by amultiple of the number of binary digits in the exponent.
This algorithm is variously known as
fast exponentiation
,
modular exponentiation
,
binary exponentiation
,
square and multiply algorithm
… and the basic idea is the
following. Suppose that we want to compute
m
e
mod
n
and that the binary expan-
sion of the exponent is
e
=
i
=
0
e
i
2
i
where
e
i
=
(
e
k
e
k
−
1
...
e
1
e
0
)
2
∈ Z
2
. Then
