Finding the Multiplicative Inverse in GF(p)

Finding the Multiplicative Inverse in GF(p)

It is easy to find the multiplicative inverse of an element in GF(p) for small values of p. You simply construct a multiplication table, such as shown in Table 4.3b, and the desired result can be read directly. However, for large values of p, this approach is not practical.

If gcd(m, b) = 1, then b has a multiplicative inverse modulo m. That is, for positive integer b < m, there exists a b¹ < m such that bb¹ = 1 mod m. The Euclidean algorithm can be extended so that, in addition to finding gcd(m, b), if the gcd is 1, the algorithm returns the multiplicative inverse of b.

---

[Page 111]

EXTENDED EUCLID(m, b)
1. (A1, A2, A3)  (1, 0, m); (B1, B2, B3)  (0, 1, b)
2. if B3 = 0 return A3 = gcd(m, b); no inverse
3. if B3 = 1 return B3 = gcd(m, b); B2 = b1 mod m

4.

5. (T1, T2, T3)  (A1  QB1, A2  QB2, A3  QB3)
6. (A1, A2, A3)  (B1, B2, B3)
7. (B1, B2, B3)  (T1, T2, T3)
8. goto 2

Throughout the computation, the following relationships hold:

	mT1 + bT2 = T3	mA1 + bA2 = A3	mB1 + bB2 = B3

To see that this algorithm correctly returns gcd(m, b), note that if we equate A and B in the Euclidean algorithm with A3 and B3 in the extended Euclidean algorithm, then the treatment of the two variables is identical. At each iteration of the Euclidean algorithm, A is set equal to the previous value of B and B is set equal to the previous value of A mod B. Similarly, at each step of the extended Euclidean algorithm, A3 is set equal to the previous value of B3, and B3 is set equal to the previous value of A3 minus the integer quotient of A3 multiplied by B3. This latter value is simply the remainder of A3 divided by B3, which is A3 mod B3.

---

[Page 112]

Note also that if gcd(m, b) = 1, then on the final step we would have B3 = 0 and A3 = 1. Therefore, on the preceding step, B3 = 1. But if B3 = 1, then we can say the following:

mB1 + bB2 = B3

mB1 + bB2 = 1

bB2 = 1 mB1

bB2 1 (mod m)

And B2 is the multiplicative inverse of b, modulo m.

Table 4.4 is an example of the execution of the algorithm. It shows that gcd(1759, 550) = 1 and that the multiplicative inverse of 550 is 355; that is, 550 x 335 1 (mod 1759). Table 4.4. Finding the Multiplicative Inverse of 550 in GF(1759) Q A1 A2 A3 B1 B2 B3 1 0 1759 0 1 550 3 0 1 550 1 3 109 5 1 3 109 5 16 5 21 5 16 5 106 339 4 1 106 339 4 111 355 1