(In Python): Write a function modExp(x, y, n) that computes and returns the valu
ID: 3147903 • Letter: #
Question
(In Python): Write a function modExp(x, y, n) that computes and returns the value of x^y mod n. Use the fast modular exponentiation algorithm given in Figure 9.7.4 of the zyBook.
Figure 9.7.4: An iterative algorithm for fast modular exponentiation. Input: Positive integers x and y. Output: x' mod n p:= 1 /p holds the partial result. s:= X /s holds the current zº r=y /r is used to compute the binary expansion of y While (r> 0) If ( r mod 2= 1) p:= p's mod n S=S•s mod n = r div 2 End-while Return(p)Explanation / Answer
Save the below code and run, you will get the desired result
...............................................................................
def modExp(x, y, n):
p = 1
s = x
r = y
while(r>0):
if(r % 2 == 1):
p = (p*s) % n
s = (s*s)% n
r = r/2
return p
x = input("Enter x = ")
y = input("Enter y = ")
n = input("Enter n = ")
result = modExp(x, y, n)
print result
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.