I need to decompose a large integer (30-40 digits) to an integer unknown with a factorizable polynomial. As a small example:
$$
\begin{cases}
119=2x^2+3x \\
x=7 \\
\end{cases}
$$
For example:
$$54026707855643784^2+2 \cdot 54026707855643784$$
$$= 2918885161719081869258276809126224$$
This is easy to do for a specific form such as $x^2-y^2 = (x-y)(x+y) $. For instance, if we wanted to find a polynomial of that form for the number $2960$, we could search $x$ such that $x^2-2960$ is a perfect square. We have a lower bound of $\text{ceil}(\sqrt{2960}) = 55$. We soon find that $57^{2}-2960 = 289$, the perfect square of 17, so we get the expression:
$$
\begin{cases}
2960=x^2-289 \\
x=57 \\
\end{cases}
$$
However, there is not such an expression for all numbers, such as even very small numbers like $6$. Plus, for larger numbers it could take hundreds of trials till you hit a solution. Thus, I'm trying to find a more general effiicient algorithm for any reducible/factorizable polynomial (making it less likely for flanks like 6 to appear). However, I can find no methods that aren't computationally expensive (e.g. searching a lookup table would take a long time). So is there an algorithm for this?
Best Answer
You could try representing the integer $z$ in its base-$b$ form for different $b$.
For eg: In base-10,
$$z = 2960 = 2.10^3 + 9.10^2 + 6.10 + 0 = 2960_{10}$$
So,
$$(x, f(x) = (10, 2x^3 + 9x^2 + 6x)$$
In base-$7$, we have $2960 = 11426_7$. So,
$$(x, f(x)) = (7, x^4 + x^3 + 4x^2 + 2x + 6)$$
You can represent $2960$ in many bases $b \in [2,z-1]$ and get different $f(x)$. You can then check if the polynomial is reducible (or irreducible).
See: Methods to see if a polynomial is irreducible
However, this is not any more efficient than factoring $z$. There are faster algorithms for factoring $z$ than this.