The function binary(b) below returns a list containing the digits of the number
ID: 3722842 • Letter: T
Question
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
Explanation / Answer
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 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: product = (product*a) % m a = (a**2) % m return product
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.