Python Project

The following algorithm shows how to compute a^x mod n fast with input a; x; n,

output a^x mod n. Please implement the following algorithm.

procedure FastEponentiation (a, x) -> a^x mod n; x = num(x_k.x₀)

y <-- 1

for i <-- k, k 1,, 0 do

y <-- y x y mod n

if x_i = 1 then

y <-- a x y mod n

end if

end for

end procedure

write a program using the algorithim above to compute 17²² mod 21 and output the following

		Squaring	Multiplying
i	Xi	y	y
4	1		17
3	0	172 mod 21 = 16	16
2	1	162 mod 21 = 4	17 x 4 mod 21 = 5
1	1	52 mod 21 = 4	17 x 4 mod 21 = 5
0	0	52 mod 21 = 4	4