I'm doing modular arithmetic in a Java program, and I want to calculate the time complexity of the individual operations.
$$ c= a · b \bmod n $$ $$ m = a^{-1} · b \bmod n $$
How do I get an approximation of the time complexity here, for example for 256-bit numbers?
I'm turning earlier discussion into a partial answer. I apologize if the whole thing can be considered off-topic (we are discussing computer science, with specialization to Java, and only potential application to cryptography).
In order to discuss time complexity, we must specify the algorithm used, and that's not done in the question. However, in Java, an easy and customary way to perform integer arithmetic on numbers of 256 bits is to use the java.math.BigInteger package. Its source code is supplied with the public JCDK, in src.zip, allowing analysis. The algorithms used by this package to compute $a⋅b$, then $a⋅b\bmod n$, are essentially the so-called classical algorithms taught in primary school with base 10, only adapted to base $2^{32}$; see e.g. multiplyToLen in BigInteger.java where the actual computation of $a⋅b$ occurs.
Assuming that implementation is used, and $a$, $b$ and $n$ are of the same order of magnitude, the asymptotic cost of computing $a⋅b\bmod n$ is going to be $O(\log(n)^2)$. More precisely, I expect the number of long multiplications to be $o(2⋅(\log_2(n)/32)^2)$, and that goal is reachable by a good Java implementation of the classical algorithms, which java.math.BigInteger seems to be.
Unless something clever is done, computing $m=a^{-1}·b\bmod n$ will be by first computing $i=a^{-1}\bmod n$ (perhaps using modInverse in BigInteger.java), then $m=i·b\bmod n$. Assuming that, the asymptotic cost is going to be at least that of the second part, which was discussed above. I suspect $i=a^{-1}\bmod n$ might cost appreciably more than $m=i·b\bmod n$, even asymptotically, but my time is missing right now for a detailed analysis; I stopped after determining that the core of the computation is by mutableModInverse in MutableBigInteger.java, and this is not quite a straightforward Extended Euclidian algorithm.
Caveat: Given that a 256-bit integer uses only eight 32-bit words/digits/limbs, asymptotic cost, be in in $O()$ or $o()$ notation, likely is a poor predictor of the actual runtime; that might be dominated by non-computational overhead, especially in Java.
Edit: As references, I suggest the HAC (esp. chapter 14), and Modern Computer Arithmetic.
n? Isnprime? Doesnhave some kind of special representation (for example it's very close to a power-of-two)? Do you need constant time inversion, or isaa non secret value allowing variable time inversion because you don't care about timing side-channels? $\endgroup$java.math.BigInteger? If yes, find the source (it is in the JCDK in src.zip), and follow what happens. The time complexity your instructor is asking about amounts to the number of elementary multiplications. $\endgroup$m = a ^-1 * b mod nthan to computei = a ^-1 mod n, thenm = i * b mod n? Is there any reason that computingm = i * b mod nwould be significantly slower or faster than computingc = a * b mod n? Then couldm = a ^-1 * b mod nbe significantly faster thanc = a * b mod n? If that's not enough: Can you find an algorithm to computei = a ^-1 mod nthat's faster than the Extended Euclidian algorithm? What's the first computational step of that? How does its cost compare tom = i * b mod n? $\endgroup$java.math.BigIntegerlast time I checked) has asymptotic cost $O((\log n)^2)$; you confused the value of $n$, and its number of bits (or words, limbs..). Further assuming reasonable use of the Extended Euclidian algorithm when computing $i=a^{-1}\bmod n$, the worst case can't be more than $O((\log n)^3)$ (but I would not bet that's quite right). And again, considering the givens 256-bit and Java, asymptotic cost in big-O notation may not accurately predict the runtime. $\endgroup$