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.
 
 

Transcribed Image Text:

First set some initial values: r1 = b S1 = 0 t₁ = 1 roa So = 1 to = 0 Then proceed as follows starting at i = 1: O Compute qiri-1/ ri (using integer division) o Compute 1+1 = 1-1 mod ri O Compute S+1= Si-1-qisi O Compute t+1 = ti-1-qiti 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. First set some initial values: r1 = b S1 = 0 t₁ = 1 roa So = 1 to = 0 Then proceed as follows starting at i = 1: O Compute qiri-1/ ri (using integer division) o Compute 1+1 = 1-1 mod ri O Compute S+1= Si-1-qisi O Compute t+1 = ti-1-qiti 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.

Answer rating: 100% (QA)

Answer definition of egcda b r a s 1 t 0 u b v 0 w 1 whereas u 0 q r u rs r r u u rs q u ss s s v v ss q v ts t t w w ts q w bring back r s t q egcd72 7 print egcd24 30 print Explanation The Extended ... View the full answer