Consider the problem ModuloPower defined below. ModuloPower Input: Positive inte

Question

Consider the problem ModuloPower defined below. ModuloPower Input: Positive integers a, r, and p Output: a r mod p Using ideas discussed in class, write an efficient function called moduloPower, in a high level programming language of your choice, that takes arguments a, r, and p, and returns a r mod p. Then complete your solution by writing a program that reads input a, r, and p from a textfile called hw1Prob2.txt and outputs (to standard output) the answer a r mod p. Assume that the input file contains a in the first line, r in the second, and p in the third, with nothing else in the file. Finally, use your program to compute a r mod p, where a is your university ID, r is the 300-digit number obtained by concatenating the string “8901234567” thirty times and p is the 300-digit number obtained by concatenating the string “2345678901” thirty times.

Explanation / Answer

The following code is written in Python 3

def ModuloPower(a, r, p):
    res = 1
    a = a%p
    while r>0:
        if (r & 1):   # if r is odd
            res = (res*a) % p;
        r = r >> 1
        a = (a*a) % p
    return res

f = open('hw1Prob2.txt')
a = int(f.readline().strip())
r = int(f.readline().strip())
p = int(f.readline().strip())

print(ModuloPower(a, r, p))

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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