(In Pyhton): Write a function modInv(a, b) that returns the multiplicative inver

Question

(In Pyhton): Write a function modInv(a, b) that returns the multiplicative inverse of a, mod b (i.e., it should return an integer x {1, 2, 3, … , b – 1} such that (ax) mod b = 1). You can assume that the inverse exists, i.e., gcd(a, b) = 1 (in other words, a and b are relatively prime).

You can use the extended Euclidean algorithm to find the inverse. In addition to computing the gcd of two numbers a and b, the extended algorithm returns the Bézout coefficients s and t. These are two integers that express the gcd as a linear combination of a and b: gcd(a, b) = sa + tb.

When a and b are relatively prime, gcd(a, b) = 1, so we can write

sa + tb = 1

sa – 1 = -tb

Recall one of the results we proved earlier: x mod n = y mod n iff n | (x – y). From the second equation above, it’s clear that b | (sa – 1). Therefore, (sa) mod b = 1 mod b = 1. To ensure that s is in the allowable set of values {1, 2, 3, … , b – 1}, we simply have the algorithm return s mod b to find the inverse.

To run the extended Euclidean algorithm on two numbers a and b (assuming a > b), we keep track of four quantities that are repeatedly calculated: the remainder ri, the quotient qi, and the coefficients si and ti.

We stop as soon as we reach a remainder of 0 at r6. Then the gcd is the remainder from the previous round, r5 (which is 1, indicating 1073 and 462 are relatively prime). The two Bézout coefficients are the s5 and t5 from the previous round: s = -31 and t = 72. We can easily verify that sa + tb = -31(1073) + 72(462) = 1, which matches the gcd of 1073 and 462.
Since a (1073) and b (462) are relatively prime, s mod b is the multiplicative inverse of a, mod b. (-31) mod 462 = 431. Verify: (as) mod b = (1073*431) mod 462 = 462463 mod 462 = 1.

Python tip: Use // for integer division; a single forward slash results in floating-point division.

First set some initial values ro a ri b Then proceed as follows, starting at i 1: o Compute q ri-1 ri (using integer division o Compute ri 1 r-1 mod ri o Compute si 1 s 1 qisi o Compute t+1 ti-1 qil Repeat this set of calculations until the remainder becomes 0. The gcd is then the remainder from the previous round, and the Bézout coefficients are the s and t from the previous round

Explanation / Answer

def modInv(a, b):
   rprev = a
   rcurr = b
   sprev = 1
   scurr = 0
   tprev = 0
   tcurr = 1
   while rcurr != 0:
       quot = rprev // rcurr
       rnext = rprev % rcurr
       snext = sprev - (quot * scurr)
       tnext = tprev - (quot * tcurr)
       rprev = rcurr
       rcurr = rnext
       tprev = tcurr
       tcurr = tnext
       sprev = scurr
       scurr = snext

   gcd = rprev
   return sprev % b

print modInv(1073, 462)

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

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