Python Project The following algorithm shows how to compute a x mod n fast with
ID: 3825817 • Letter: P
Question
Python Project
The following algorithm shows how to compute ax mod n fast with input a; x; n,
output ax mod n. Please implement the following algorithm.
procedure FastEponentiation (a, x) -> ax mod n; x = num(xk…….x0)
y <-- 1
for i <-- k, k – 1,…, 0 do
y <-- y x y mod n
if xi = 1 then
y <-- a x y mod n
end if
end for
end procedure
write a program using the algorithim above to compute 1722 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
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
Explanation / Answer
def FastEponentiation(a, x, n):
y = 1
s = "{0:b}".format(x)
k = len(s)
for i in range(0, k):
y = (y*y) % n
if s[i] == '1':
y = (a*y)%n
return y
print(FastEponentiation(17,22, 21))
# pastebin link: https://pastebin.com/5qtp3jGv
# Please rate positively
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.