Is it possible to solve the FACT (integer factorization) problem in polynomial time if we know the polynomial Subset Sum algorithm?
We assume that we know the algorithm solving the problem of Subset Sum with complexity: $n ^ 4 \cdot m ^ 4$ (for example), where $n$ is the number of elements in the set, and $m$ is the size of the largest element (absolute value).
Theoretically, we can perform a reduction from FACT to 3SAT and from 3SAT to Subset Sum.
However, the reduction from 3SAT to Subset Sum has a problem.
After such a reduction (from 3SAT), the numbers in Subset Sum are very large.
For example, let's see page number four in this document.
The search number is: $11133$ for a logic function composed of only three variables and two clauses.
The number we are looking for is always around $ 10 ^ {v + c} $ where $v$ is number of variables and $c$ is number of clauses.
We can solve the Subset Sum in time $n ^ 4 \cdot m ^ 4$ but if $m$ grows exponentially, then the whole grows exponentially.
Is there any way to solve this?
---- Update:
I found this answer. It directs me to the conclusion that there is no classic decimal notation. Maybe this is some unary notation? Do I presume well? I am concerned, however, about the value of "3" in $k$ (the last row in the table on the fourth page in document). How can we encode it in decimal / binary form?
