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?
1
-
1You may have more luck on math.stackexchange.com.– cmbuckleyCommented Sep 15, 2014 at 16:27
Add a comment
|
1 Answer
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
-
Hmmm.... does make quite a lot of sense. But it's not any faster than the original idea is it? Commented Sep 15, 2014 at 17:43
-
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? Commented Sep 15, 2014 at 17:51
-
Well the Euclidean algorithm seems to be O(log b) for the worst case (consecutive Fib. numbers). Commented Sep 15, 2014 at 18:11