Cryptography: Finding the Multiplicative Inverse in GF(p)

•If a and b are relatively prime, then b has a multiplicative inverse modulo a.

•That is, if gcd(a, b) = 1, then b has a multiplicative inverse modulo a.

•That is, for positive integer b < a, there exists a b-1 < a such that bb-1 = 1 mod a.

•If a is a prime number and b < a, then clearly a and b are relatively prime and have a greatest common divisor of 1.

•Extended Euclidean algorithm:

•ax + by = d = gcd(a, b)

•Now, if gcd(a, b) = 1, then we have ax + by = 1.

•Using the basic equalities of modular arithmetic

[(ax mod a) + (by mod a)] mod a = 1 mod a

0 + (by mod a) = 1

But if by mod a = 1, then y = b- 1

Example: 

 a = 1759, which is a prime number, and b = 550.

–The solution of the equation 1759x + 550y = d yields a value of y = 355.

–Thus, b-1 = 355. To verify, calculate 550 × 355 mod 1759 = 195250 mod 1759 = 1.

•More generally, the extended Euclidean algorithm can be used to find a multiplicative inverse in Zn for any n. If we apply the extended Euclidean algorithm to the equation nx + by = d, and the algorithm yields d = 1, then y = b-1 in Zn.