In python write a function mod_exp(x, y, n) that computes and returns the value

Question

In python write a function mod_exp(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: xy mod n

p := 1     //p holds the partial result.
s := x     //s holds the current x2jx2j.
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 := r div 2
End-while

Return(p)

Explanation / Answer

code:

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.