Design an algorithm that takes a positive integer N modulus

Design an algorithm that takes a positive integer N (modulus) and two non-negative integers x and y, and returns xy(mod N). (Assume that x,y N 1, and that N, x and y are in base 2 and are represented as vectors of binary digits.)

Solution

function modexp(x, y, N)

Input: Two n-bit integers x y and modulo N.

Output: x y mod N

if y = 0:

return 1

z = mod exp(x,y, N)

if y is even:

return x y mod N

else: return x · y mod N