CODEWITHSUNDEEP
algorithm
marco quezada
marco quezada

Reputation: 29

Improving inverse modulo via Euclidean algorithms

Stuck with a question for Complexity class: "You are given a,b in Z_N* and want to complete a^-1 and b^-1 mod N. By now we know how to calculate it via using the Euclidean algorithm twice, with a,N and b,N. My question is that how can one do it with a single invocation of the Euclidean Algorithm (Finding the GCD) and 3 multiplications mod N?

Upvotes: 0

Views: 53

Answers (1)

Nico Schertler
Nico Schertler

Reputation: 32667

We know the following (all congruences mod N)

a * b * (a * b)^-1 = 1

b * (a * b)^-1 = a^-1
a * (a * b)^-1 = b^-1

So if we calculate (a * b)^-1, the partial inverses a^-1 and b^-1 can be calculated with a multiplication.

Upvotes: 1

Related Questions