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