Let e=477 (decimal format)=111011101 (binary format), please finish the following computations. (i) Please draw a table (as in the example shown below) to show the process to compute m^e (mod n). You are required to use the binary method for fast modular exponentiation.

(ii) Suppose that m=3, n=5. Please compute m^e (mod n) with the help of the table generated in (1). Please show the computation process clearly. (iii) How many multiplications are required using the binary method?

Fast Modular Exponentiation - Binary Method: an example - e=58 (in decimal format )=(e5e4e0)=(111010)( in binary format ), compute C=m58(modn) signific t significi - Number of multiplications: 8 times (marked as green) - Reduce from 57 times (nave solution) to 8 times (binary method)