Improving inverse modulo via Euclidean algorithms

Question

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?

You may have more luck on math.stackexchange.com.

cmbuckley
– cmbuckley

2014-09-15 16:27:45 +00:00
Commented Sep 15, 2014 at 16:27 — cmbuckley
– cmbuckley, Commented Sep 15, 2014 at 16:27

Nico Schertler · Accepted Answer · 2014-09-15 16:36:23Z

1

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.

answered Sep 15, 2014 at 16:36

Nico Schertler

32.7k4 gold badges45 silver badges76 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

marco quezada Over a year ago

Hmmm.... does make quite a lot of sense. But it's not any faster than the original idea is it?

Nico Schertler Over a year ago

Not sure. But I guess that executing the Euclidean algorithm is much slower than multiplication. Of course, this depends on the size of the numbers and if the multiplication can be performed with a few hardware instructions. Doesn't the extended Euclidean algorithm include multiplications as well?

marco quezada Over a year ago

Well the Euclidean algorithm seems to be O(log b) for the worst case (consecutive Fib. numbers).

Collectives™ on Stack Overflow

Improving inverse modulo via Euclidean algorithms

1 Answer 1

3 Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Related