Fast Modular Exponentiation PDF

Preview

Summary

Fast Modular Exponentiation for programming...

Description

Fast modular exponentiation Case e = 2k Suppose that we need to compute b to the power 2k modulo m using only k modular multiplications (without i using explicit exponentiation function). Denote bi := b2 mod m. • b0 = b mod m. • b1 = b0 × b0 mod m. As we wanted, b1 = b2 mod m. 1

• b2 = b1 × b1 mod m. Since b1 = b2 mod m, we have b1 × b1 = b2 × b2 = b2+2 = b4 mod m. • b3 = b2 × b2 mod m. Again, since b2 = b4 mod m, we have b3 = b4 × b4 = b8 mod m. ... • bk = bk−1 ×bk−1 mod m. Since bk−1 = b2

k−1

mod m, we have bk = b2

k−1

×b2

k−1

= b(2

k−1 +2k−1 )

k

= b2 mod m.

Our algorithm consists of k steps, on each step we perform only one modular multiplication. Note that since all numbers b1 , b2 , . . . , bk are remainders modulo m, we don’t need to multiply long numbers. Arbitrary e Let en en−1 . . . e1 e0 be the binary representation of e. By definition, e = en × 2n + en−1 × 2n−1 + . . . + e1 × 21 + e0 × 20 , thus be = b((en ×2

n )+(e

n−1 ×2

n−1 )+...+(e

1 ×2

1 )+(e

0 ×2

0 ))

n

= ben ×2 × ben−1 ×2 i

i

n−1

1

0

× . . . × be1 ×2 × be0 ×2 . i

Note that for all i, ei ∈ {0, 1}, therefore, if ei = 1 : bei ×2 = b2 , if ei = 0 : bei ×2 = 1. Hence, be is the i product of b2 for all i such that ei = 1 ⇐⇒ ei 6= 0. Therefore, the fast modular exponentiation algorithm for arbitrary e works as follows: 1. Compute en en−1 . . . e1 e0 — the binary representation of e. i

2. Compute b2 for all i = 0, 1, 2, . . . n — we have already have an efficient algorithm for that! i

3. Multiply together b2 for all i such that ei = 1. (NB: After each multiplication take modulo m to avoid long numbers!)...