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?

  • 1
    $\begingroup$ Do you know the factorization on n? Is n prime? Does n have some kind of special representation (for example it's very close to a power-of-two)? Do you need constant time inversion, or is a a non secret value allowing variable time inversion because you don't care about timing side-channels? $\endgroup$ – CodesInChaos Jan 20 '13 at 10:19
  • 1
    $\begingroup$ Time complexity in Java is an imprecise notion, and with 256-bit operands is not a very relevant notion. However, if you can't change the problem, live with it. Will you be using 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$ – fgrieu Jan 20 '13 at 13:32
  • $\begingroup$ Thank you for response. I know variable a and b should be between 1 to n-1 ok. I want compare two lines . Is it this operand c= a * b mod n speedup from operand m = a ^-1 * b mod n or Vice versa. $\endgroup$ – almodawan Jan 20 '13 at 15:46
  • 2
    $\begingroup$ Hints: Can you see a better way to compute m = a ^-1 * b mod n than to compute i = a ^-1 mod n, then m = i * b mod n? Is there any reason that computing m = i * b mod n would be significantly slower or faster than computing c = a * b mod n? Then could m = a ^-1 * b mod n be significantly faster than c = a * b mod n? If that's not enough: Can you find an algorithm to compute i = a ^-1 mod n that's faster than the Extended Euclidian algorithm? What's the first computational step of that? How does its cost compare to m = i * b mod n? $\endgroup$ – fgrieu Jan 20 '13 at 16:09
  • 1
    $\begingroup$ $c=a⋅b\bmod n$ with $a$ and $b$ of the same order of magnitude as $n$, and classical arithmetic algorithms (used in java.math.BigInteger last 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$ – fgrieu Jan 20 '13 at 21:45

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.

| improve this answer | |
  • $\begingroup$ Thank you for your answer. In my thesis I have two algorithm first encrypt and second decrypt. I want know best in time complexity. Is it encrypt or decrypt? Is it good method for compare? or tell me any other way for compared $\endgroup$ – almodawan Jan 21 '13 at 18:36
  • $\begingroup$ @almodawan: if that's enough for you: as explained $m=a^{-1}·b\bmod n$ is going to be more costly than $a⋅b\bmod n$ when comparable algorithms are used for what's common to the two. That's true asymptotically, and even more so with 256 bits and Java. $\endgroup$ – fgrieu Jan 21 '13 at 21:12
  • $\begingroup$ Can I say that a . b mod n is takes less time from a^-1 . b mod n. If That's true I'm very hope. $\endgroup$ – almodawan Jan 22 '13 at 10:41
  • $\begingroup$ @almodawan: Yes! $\endgroup$ – fgrieu Jan 22 '13 at 14:49
  • $\begingroup$ Tiny point of order: The question uses the term "how can" and not "what is". Rather than stating $O(\log(n)^2)$ outright, it would be useful to see how this is mathematically determined. But I guess that might then wander even further off topic :-( $\endgroup$ – Paul Uszak Oct 28 '18 at 12:32

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.