Is factoring a semiprime easier than matrix multiplication?

Question

I'm currently dealing with complexity estimates of various algorithms and the connected mathematical problems. Up until now, I had in mind that problems such as integer factorization and the discrete logarithm problem are among the hardest problems we know about. However, I've done some concrete examples which to me indicate that even something as mundane as matrix multiplication can be more difficult than these particular problems. Here are my observations:

Compare the brute force factorization of a semiprime $n=p \cdot q$ to the 'schoolbook' matrix multiplication algorithm. We can multiply all numbers below $\lfloor \sqrt{n} \rfloor$ with each other and we're guaranteed to find $n$ among the results; so this has $O(n)$ as a worst case complexity. Naive matrix multiplication, however, has $O(n^3)$ as a worst case complexity. So is naive matrix multiplication really harder than factoring semiprimes?

I had in mind that matrix multiplication can be done with polynomial-time algorithms whereas integer factorization has subexponential algorithms at best. If we view the complexity of the above factoring algorithm relative to the input-size in bits, we arrive at $O(2^b)$ where $b$ is the bitsize of $n$, so there is an argument for 'exponentiality'. But then the same argument can be made for the naive matrix multiplication, so it can viewed as an exponential-time algorithm as well.

Are these observations correct, or am I confusing something? As it stands, my traditional view has been turned on its head, but I don't wholly trust these arguments yet...

Thanks for any help!

Answer 1

Your intuition to examine the complexity in terms of the input size is correct. In this sense, your factoring algorithm is $\Omega(2^b \, M(b))$, where $M(b)$ is the time it takes to multiply two $b$-bit integers.

But an $n \times n$ matrix of $n$-bit integers has size $b = n^3$, so matrix multiplication takes only $O(b\,M(\sqrt[3]{b}))$ time.

In essence, your confusion is caused by $n$ meaning different things for the two problems. $O(n)$ and $O(n^3)$ aren't comparable when the $n$s are measuring different things. Any algorithm that takes time proportional to the numerical value of the input is already exponential in the length of the input.

Answer 2

Number of entries in a matrix or other complex object is more like number of digits than it is like number: a 100x100 matrix with 32-bit entries is 320,000 bits, not 50 bits (as "a 32 bit number times ten thousand" would fit in). So the argument that your number -> number of bits transformation makes it harder doesn't hold water: the size of the matrix is already directly associated with the number of bits.