# Is factoring a semiprime easier than matrix multiplication?

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!

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.
• @polarbear Always try to be aware of what the notation is measuring and what the parameters are. O notation on its own is ambiguous, but good authors will say things like "sorting takes $\Omega(n\,\lg n)$ comparisons for a list of $n$ elements". Saying "sorting is $\Omega(n\,\lg n)$" is underspecified. – Tavian Barnes Aug 18 '14 at 15:06
• ah, I see; so the thing is that in this calculation, $n$ just stands for the number of rows/columns but is itself not used directly in the algorithm (whereas the entries of the matrix are); that's why the transformation to number of bits doesn't work; or that's how I understood your answer. – polarbear Aug 18 '14 at 12:38