Cryptography Reference
In-Depth Information
scanned exponent bit has the value 1, a multiplication of the current result by
x
is executed following the squaring.
This seems like a simple if somewhat odd rule. For better understanding, let's
revisit the example from above. This time, let's pay close attention to the exponent
bits.
Example 7.4.
We again consider the exponentiation
x
26
. For the square-and-multiply
algorithm, the binary representation of the exponent is crucial:
x
26
=
x
11010
2
=
x
(
h
4
h
3
h
2
h
1
h
0
)
2
.
The algorithm scans the exponent bits, starting on the left with
h
4
and ending with
the rightmost bit
h
0
.
Step
#0
x
=
x
1
2
inital setting, bit processed:
h
4
= 1
#1
a
(
x
1
)
2
=
x
2
=
x
10
2
SQ, bit processed:
h
3
#1
bx
2
x
=
x
3
=
x
10
2
x
1
2
=
x
11
2
·
MUL, since
h
3
= 1
#2
a
(
x
3
)
2
=
x
6
=(
x
11
2
)
2
=
x
110
2
SQ, bit processed:
h
2
#2
b
no MUL, since
h
2
= 0
#3
a
(
x
6
)
2
=
x
12
=(
x
110
2
)
2
=
x
1100
2
SQ, bit processed:
h
1
#3
bx
12
x
=
x
13
=
x
1100
2
x
1
2
=
x
1101
2
·
MUL, since
h
1
= 1
#4
a
(
x
13
)
2
=
x
26
=(
x
1101
2
)
2
=
x
11010
2
SQ, bit processed:
h
0
#4
b
no MUL, since
h
0
= 0
To understand the algorithm it is helpful to closely observe how the binary rep-
resentation of the exponent evolves. We see that the first basic operation, squaring,
results in a left shift of the exponent, with a 0 put in the rightmost position. The other
basic operation, multiplication by
x
, results in filling a 1 into the rightmost position
of the exponent. Compare how the highlighted exponents change from iteration to
iteration.
Here is the pseudo code for the square-and-multiply algorithm:
