1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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