Problem | Binary exponentiation Recall the exponentiation algorithm given in class for evaluating aⁿ (mod m) (a Z, m,n N):

1. Compute the binary representation of n: n = b₀ 2^k + b₁ 2^k-1 + ... + b_k-1 2 + b_k , with b₀ = 1, i {0, 1} for 1 i k, and k = 2. Initialize r₀ a (mod m).

3. For 0 i k -1 compute

4. Output r_k.

(a) To warm up with a toy example, compute 17¹¹ (mod 77) using the procedure above; answers that don't use the binary exponentiation algorithm will receive no credit, even if they are correct. Show all your work, and write down all your intermediate quanti- ties b_i and r_i. Your answer should be an integer between 0 and 76.

(b) In this problem, you will formally prove that the binary exponentiation algorithm is correct.

i. Define s₀ = 1 and s_i+1 = 2s_i + b_i+1 for 0 i k -1. Use induction on i to prove that ii. (4 marks) Let r_{i ,} 0 i k, be defined as in steps 2 and 3 of the exponentiation algorithm. Use induction on i to prove that r_i a^s_i (mod m) for 0 i k.

iii. (2 marks) Prove that aⁿ r_k (mod m), so the algorithm above does indeed compute aⁿ (mod m) as claimed.

Note: Sorry for the confusion. I have updated the questions. Hopefully, you can see them clearly now. Thanks.

Transcribed image text