CODEWITHSUNDEEP
cryptographyinversemodular
skinnyas123
skinnyas123

Reputation: 382

How to get the modular inverse by using Extended Eucledian Algorithm?

Given a mod b and find its inverse, then doing the extended GCD.

ax + by = gcd(a,b)

After I get x and y, how do I get its inverse?

Upvotes: 1

Views: 2574

Answers (2)

user448810
user448810

Reputation: 17851

Do this to calculate the inverse of x to the modulus m:

function inverse(x, m)
    a, b, u := 0, m, 1
    while x > 0
        q, r := divide(b, x)
        x, a, b, u := b % x, u, x, a - q * u
    if b === 1 return a % m
    error("must be coprime")

Here := is the simultaneous assignment operator, so all calculations on the right side are done first, then all the assignments are made. The divide function returns both the quotient and remainder of b / x.

Upvotes: 1

Rasmus Faber
Rasmus Faber

Reputation: 49619

If gcd(a,b) != 1, a does not have an inverse mod b.

Otherwise ax + by = 1, which means that ax = 1 (mod b), so x is the inverse of a mod b.

Upvotes: 3

Related Questions