# Computational Complexity - When is it really exponential time?

I'm currently working on the discrete logarithm problem and the relevant attacks. I'm fine on the mathematical side of things, but when it comes to estimation of running times I run into problems. More specifically: if we take a generic square algorithm like Baby Step Giant Step for a cyclic group of size $n$, we usually arrive at $O(\sqrt{n})$ necessary operations to find a discrete logarithm. With the argument that the input of the algorithm is measured in bits, we arrive at a running time of $O(2^{b/2})$ where $b$ is the bitlength of $n$. So far so good.

But this argument does not work for say, matrix multiplication. Let's take $A,B \in Mat(n \times n, \mathbb{Z})$, so computing $A \cdot B$ obviously takes $n^2$ operations in $\mathbb{Z}$. This is, in contrast to the above, considered efficient. So why can't I argue as above and say that matrix multiplication takes exponential time as well?

On a more general level, I often encounter the argument that some algorithm requires $O(p(n)$ (p(n) being some polynomial) operations that themselves can be computed efficiently and thus the whole algorithm is considered efficient. This runs counter to my intuition I gained from looking at Pollard's Rho etc.

I know I'm probably making a stupid mistake somewhere, but I'm not seeing it at the moment.

Thanks for any help!

• You can't use $n$ to refer both the order of the group and its bitlength. Rename one of them, e.g. use $n = \log_2 N$ – CodesInChaos Aug 11 '14 at 13:31
• OK, but as I wrote it, $n$ never refers to the bitlength of the group order or does it? That's why I wrote $bitlength(n)$ to avoid confusion – polarbear Aug 11 '14 at 13:38
• You wrote $n=2^{log_2 n}$ which makes no sense. DL has polynomial cost in the order of the group and exponential cost in the bitlength of the group order. If you want to be precise you can't say "this algorithm has exponential cost", you need to specify in which variable it is exponential. Colloquially we omit that specification if everybody knows which variable we're talking about. – CodesInChaos Aug 11 '14 at 13:46
• Ah, ok. Is it clearer now? – polarbear Aug 11 '14 at 13:56
• To your last point, that encryption algorithms need to be O(p(n)) to be considered efficient: This is just a reference to the fact that attacks should be NP while evaluation with a known key should be P. That's just a statement that evaluation with a known key is far faster than attacking the algorithm for an unknown key, which should be rather an obvious statement. – Jeff-Inventor ChromeOS Aug 12 '14 at 2:37

To determine the complexity class of an algorithm, you have to determine which operation can be done in unit time. For example, a typical PC will to word-size, $w$-bit (32- or 64-bit) addition and multiplication in constant time.

From that, you can calculate how many of those primitive operations an algorithm requires. To multiply two $2w$-bit numbers using schoolbook multiplication, you use 4 $w$-bit multiplies and 3 $w$-bit additions – which is $O(b^2)$ in general, where $b$ is the bit length ($w$ only affects the constant). For other multiplication algorithms it takes $O(b^j)$ for some slightly lower exponent.

So, how about square matrix multiplication?

If the matrix elements are $w$-bit, you can do modular multiplication of elements in $O(1)$ and thus the whole matrix multiply in $O(n^k)$, where $n$ is the width of the matrix and $k$ depends on which multiplication algorithm you use ($k=3$ for schoolbook matrix multiplication).

If your matrix elements are $b$-bit, however, each of those $O(n^k)$ multiplies takes $O(b^j)$, for $O(b^jn^k)$ total – still polynomial.

Baby-step-giant-step?

The algorithm requires $O(n^{1/2})$ exponentiations, where $n$ is the order, so $O(2^{b/2})$ for $b$-bit groups. Each of those exponentiations also takes time that also depends on $b$: for example, exponentiation by squaring takes $O(b)$ $b$-bit multiplies. Total cost is $O(b^c2^{b/2})$ for some constant $c$.

However:

1. That's just a polynomial, small compared to the number of exponentiations.
2. When analyzing a cryptographic algorithm, an attack's cost is usually given in terms of normal operations using the primitive that the user also needs to do.
• I agree with everything, my confusion lay in the fact that if you view matrix multiplication relative to the size of the matrix measured in bits (meaning you write $n=2^{b}$ where $b$ is the bitlength of n) you arrive per your calculation at $O(b^j2^{kb})$ operations - more costly than the DLP, which I thought weird. – polarbear Aug 11 '14 at 16:32
• @polarbear : $\:$ That's why we "view matrix multiplication relative to the size of the" $\hspace{1.2 in}$ matrices (since those are the inputs). $\;\;\;\;$ – user991 Aug 11 '14 at 19:26

The names of complexities normally refer to $b$, not the bitlength $n$.

$\mathcal{O}(log\ n) = \mathcal{O}(b)$ is polynomial time, $\mathcal{O}(n) = \mathcal{O}(2^b)$ is exponential time.

Matrix multiplication of a matrix of length $n$ would involve more operations than multiplying all elements of your group with all others. It has complexity of $\mathcal{O}(n^3) = \mathcal{O}(2^{3b})$ which is exponential time - it is not considered effective. In $\mathcal{O}(n^2)$, you could create the multiplication table of your group, which is basically a lookup table. If you have that, you're basically done with the DLP, so it should be obvious, that solving the DLP should be less complex than matrix multiplication.

Also, this does not seem to be consistent. In some cases (like crypto) it makes sense to say that $\mathcal{O}(n)$ is exponential time since the thing that grows is the bitsize, and thus $n$ grows by $2^b$. In other cases, when we're talking outside of crypto $\mathcal{O}(n)$ might be considered polynomial, since n is the thing that grows (like sorting algorithms).

• thanks, your argument that matrix multiplication takes more operations than constructing a multiplication table for the group makes a lot of sense. I was just taken aback by the fact than matrix multiplication is more costly than the DLP. It let me wonder why we don't create cryptosystems based on matrix multiplication. But this would be a folly of course since matrix multiplication is hard for BOTH parties. – polarbear Aug 11 '14 at 16:26