Cryptography Reference
In-Depth Information
CHAPTER 6
Where All Roads Meet:
Modular Exponentiation
For a long time on that spot I stood,
Where two roads converged in the wood and I thought:
“Someone going the other way
Might someday stop here for the sake
Of deciding which path to take.”
But my direction lay where it lay.
And walking on, I felt a sense
Of wonder at that difference.
—Ilya Bernstein,
Attention and Man
I
N ADDITION TO THE CALCULATIONAL
rules for addition, subtraction, and multi-
plication in residue classes we can also define an operation of exponentiation,
where the exponent specifies how many times the base is to be multiplied by
itself. Exponentiation is carried out, as us
ua
l, by means of recursive calls to
multiplication: For
a
in
m
we have
a
0
:= 1
and
a
e
+1
:=
a · a
e
.
It is easy to see that for exponentiation in
Z
Z
m
the usual rules apply (cf.
Chapter 1):
a
e
a
f
=
a
e
+
f
,
e
b
e
=(
a
b
)
e
,
(
a
e
)
f
=
a
ef
.
·
·
·
6.1 First Approaches
The simplest approach to exponentiation consists in following the recursive rule
defined above and multiplying the base
a
by itself
e
times. This requires
e −
1
modular multiplications, and for our purposes that is simply too many.
A more efficient way of proceeding is demonstrated in the following examples,
in which we consider the binary representation of the exponent:
a
15
=
a
2
3
+2
2
+2+1
=
a
2
a
2
a
16
=
a
2
4
=
a
2
2
2
2
a
2
a,
.
