# Parameterized complexity of factoring

When multiplying integer numbers $$A$$ and $$B$$, one can use a 0-1 matrix to represent one of the multiplication steps. For example, given numbers (written in binary) $$A=1101$$ and $$B=1011$$ the matrix is: $$\begin{matrix} 1&0&1&1\\ 0&0&0&0\\ 1&0&1&1\\ 1&0&1&1 \end{matrix}$$

The top row of the matrix corresponds to the least significant bit of $$A$$, the bottom row corresponds to $$A$$'s most significant bit. The leftmost column and the rightmost column correspond to the most significant bit and the least significant bit of $$B$$ respectively.

The next step for multiplication is to count the sum of bits in each diagonal. Let's denote this array as $$D$$. In this case (we start from the most significant term), it's $$D=1,1,1,3,1,1,1$$.

The final step is to apply carry operation to $$D$$ until every element is $$0$$ or $$1$$. In this example it becomes $$1,0,0,0,1,1,1,1$$, i.e. the number is $$143$$ (in decimal).

Now, consider the following variant of factoring:

Given a number $$N$$ decide if there exists a factoring of depth at most $$d$$.

Where depth is defined as $$\max(D)$$ and $$d$$ is the parameter. For example, in case $$d=2$$, the answer would be negative for the above number (since it's a semiprime there is only one way to write the matrix (not counting $$AB=BA$$), and that matrix has a diagonal with $$3>2$$ positive bits).

Aside from that it's in $$\mathsf P$$ for $$d=1$$ (via polynomial factoring), can anything be said about the complexity of this problem?

• The $BA$ matrix would be $\begin{matrix}1&1&0&1\\\\1&1&0&1\\\\0&0&0&0\\\\1&1&0&1\end{matrix}$ which (as it should) creates the same array $D$. Basically, the matrix has an anti-diagonal symmetry (in respect to counting $D$). Commented Jan 15 at 13:38