Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I read about the time complexity for modular arithmetic in many books. There is one thing that I don't understand. I read in some books the following:

For any $a \mod N$, $a$ has a multiplicative inverse modulo $N$ if and only if it is relatively prime to $N$. When this inverse exists, it can be found in time $O(n^3)$ (where $n$ denotes the number of bits in the binary representation of $N$) by running the extended Euclid algorithm. My question revolves around extended Euclid algorithm having $O(n^3)$ complexity.

When I write in Java or C#, a line like this:

A = B.modInverse(N) // Java syntax

Can I usually say that this line has time complexity $O(n^3)$? Or is it necessary to write the code for the extended Euclid algorithm?

Secondly, does extended Euclid algorithm depend on the compiler or the computer architecture?

share|cite|improve this question

The running time of a library function depends on the way the library function is implemented. Moreover, oftentimes it is worthwhile to code non-optimal algorithms, since for practical $n$ they might be more efficient. One good example is matrix multiplication, where the fancy algorithms are slower in practice than optimized versions of the trivial one.

In your specific case, my guess would be that they implemented the textbook solution. You can always try looking at the source code. Another possibility is timing the function for various $n$, and see if the running time scales like $n^3$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.