Computational Complexity - When is it really exponential time?

Question

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!

Answer 1

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.

Answer 2

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