Square and multiply

Question 1

calculate 8^13 mod 33 (?without square and multiply?)

Answer 1

instead of evaluating 8^13:
- split into 8888888888888
- each pair, multiply then mod 33
- repeat until end
- multiply pairs again then mod 33
- continue until it is reduced to one mod 33 operation

Question 2

In this method (8^13 mod something without sqr and mult), we need at most how many multiplications and mod?

Answer 2

FOr an exponent of b bits, we need at most 2b multiplications and mod

Question 3

Calculate 8^13 mod 33. square and multiply

Answer 3

Write exponent 13 as a sum of different powers of 2
13 = 8+4+1
(8^8)(8^4)8

Compute by squaring
8^2 mod 33 = 64 mod 33 = 31
8^4 mod 33 = (8^2 mod 33)^2 mod 33 = 961 mod 33 = 4
8^8 mod 33 = (8^4 mod 33)^2 mod 33 = 4^2 mod 33 = 16

8^13 mod 33 = 8416 mod 33 = 512 mod 33 = 17