Cryptography Reference
In-Depth Information
Implementing Modular Exponentiation. Notice that many cryptosystems require us to
raise integers to large powers modulo
. It is easy to write an algorithm that does a
poor job of this. Consider the relatively easy problem of raising 2 to the 340th power
modulo 341; that is, compute the lnr
n
x
of
2
340
x
(mod 341).
Do we compute 2
340
, then compute the least nonnegative residue? Of course not; if the
numbers involved were only moderately larger, the storage space of computers would
be quickly maxed out trying to contain such a large number.
Our second alternative may be to write a loop which executes 339 times, begins with
a value of the base 2, then multiplying the product times 2 each time and taking the lnr
modulo 341 on each iteration. This is better, but only moderately larger exponents could
make this far too slow. For example, an exponent larger than a trillion would cause the
loop to execute more than a trillion times, and even supercomputers would take a while
to crank through such a loop.
A much better alternative is to do repeated squarings and multiplications, taking
the lnr after each operation. To see this, we rewrite 2
340
as
2
340
= 2
170
2
= (2
170
)
2
= ((2
85
)
2
)
2
= (((2
42
2
1
)
2
)
2
)
2
= (((2(2
42
)
2
)
2
)
2
)
2
= (((2(2
21
2
)
2
)
2
)
2
)
2
= (((2((2
21
)
2
)
2
)
2
)
2
)
2
= (((2((2
10
2
1
)
2
)
2
)
2
)
2
)
2
= (((2((2(2
10
)
2
)
2
)
2
)
2
)
2
)
2
= (((2((2(2
5
2
)
2
)
2
)
2
)
2
)
2
)
2
= (((2((2((2
5
)
2
)
2
)
2
)
2
)
2
)
2
)
2
= (((2((2((2
2
2
1
)
2
)
2
)
2
)
2
)
2
)
2
)
2
= (((2((2((2(2
2
)
2
)
2
)
2
)
2
)
2
)
2
)
2
)
2
.
Computing 2
340
modulo 341 then becomes a matter of calculating
(((2((2((2(2
2
)
2
)
2
)
2
)
2
)
2
)
2
)
2
)
2
(((2((2((2(4)
2
)
2
)
2
)
2
)
2
)
2
)
2
)
2
(((2((2((32)
2
)
2
)
2
)
2
)
2
)
2
)
2
Search WWH ::
Custom Search