# A factoring conversion

There was a comment here that " It is possible in principle to reduce the factorization of a $256$-bit number (which is computable in TFNP) to the Permanent on a matrix of dimension $N\times N$ where $N\leq c\cdot256^c + c$ for some hopefully small constant $c$. However the computation of a nice upper bound on $c$ would probably take substantial effort. It's possible c is no more than 2 or 3."

Is it possible to convert factoring integers to calculating permanent? That is given $\log N$ bit integer to factor, how can one reduce factoring such an integer to calculating permanent of $(\log n)^c\times(\log n)^c$ matrix for a fixed $c$?

I also ask if computing $a(a+1)(a+2)\dots(a+n)$ with $a\in\Bbb N$ is also easy (done in $\log^cn$ steps if permanent of $N\times N$ matrix is easy (done in $N^c$ steps). Note that at $a=1$ we have $n!$, and permanent of all $1$ matrix needs $n\times n$ size and hence needs $n^c$ time even if permanent is easy.

## migrated from cstheory.stackexchange.comSep 30 '15 at 19:33

This question came from our site for theoretical computer scientists and researchers in related fields.

The language of tuples $\langle n,i,j,b \rangle$ such that the $j$th bit of the $i$th prime factor of $n$ is $b$ is in NP. In particular, it is in #P. More accurately, there is a #P algorithm that on input $\langle n,i,j \rangle$ gives the $j$th bit of the $i$th prime factor of $n$ (either $0$ or $1$). Since the permanent is #P-complete, we can reduce this algorithm to the computation of some polysize permanent.
• Actually problem you stated seems to be in $\mathsf{NP\cap coNP}$. I assume you are ordering prime factors of $n$ in terms of size and so you refer as $i$th prime factor of $n$. Does this have any issue with what you state later? Also what is the $\#P$ algorithm that gives $j$th bit of $i$th prime factor of $n$? – T.... Oct 3 '15 at 11:35
• The distinction between $\mathsf{NP}$ and $\mathsf{coNP}$ disappears when looking at it from the angle of $\mathsf{\#P}$. Your assumption regarding the meaning of $i$ is correct. The $\mathsf{\#P}$ algorithm guesses and verifies the factoring, but only accepts factorings in which the $j$th bit of the $i$th prime factor is $1$. – Yuval Filmus Oct 3 '15 at 12:51
• The proof of $\mathsf{\#P}$-completeness of the permanent gives an algorithm for constructing the permanent. Anything more explicit would be masochistic. – Yuval Filmus Oct 3 '15 at 13:05