The function binary(b) below returns a list containing the digits of the number b in binary. Note the list is in "reverse" order from how we would usually write a binary number since the 1's place is first, then the 2's place then the 4's place etc.

def binary(b): digits=[] while b>0: if b%2==1: digits.append(1) b = b-1 else: digits.append(0) b = b/2 return digits

Problem 1: Use this command to write a function powmod(a,b,m) which (quickly) computes a^b (mod m) by Modular Exponentiation and repeated squaring. The variable a is repeatedly squared. The function is already partially written, you just need to fill in the details:

def powmod(a,b,m): bin=binary(b) #List containing the digits of b in binary length = len(bin) #Number of digits in when b is written in binary product=1 # Use this to store the current product of terms for i in range(0,length): if bin[i]==1: # Insert ONE line of code here. #Insert ONE line of code here to square a and reduce it modulo m. return product