# Integer factorization using polynomial whose roots are prime factors

Let $n$ be a square-free positive integer, let $n=p_{1}p_{2}\ldots p_{k}$ be the prime factorization of $n$ into $k$ distinct primes $p_{i}$. For such $n$, define $F_{n}(x)\triangleq\prod_{i=1}^{k}(x-p_{i})$. That is, $F_{n}(x)\in\mathbb{Z}[x]$ is the monic polynomial whose roots are distinct prime factors of $n$. If we know $F_{n}(x)$, we can obviously factorize $n$ in polynomial time. Now suppose that we are given some partial information on $F_{n}(x)$ instead of complete $F_{n}(x)$. We would like to know

What kind of partial information on $F_{n}(x)$ would allow factorization of $n$ in polynomial time?

For example, it was demonstrated in SUMS OF DIVISORS, PERFECT NUMBERS AND FACTORING that knowing just the sum of absolute values of coefficients of $F_{n}(x)$ is enough to factorize $n$. What other partial information on $F_{n}(x)$ allows factorization of $n$ in polynomial time?

After seeing comments, I am adding for kind of "partial information" we should be looking for. As pointed out by @joro, knowing $F_n(1)$ or $F_n(-1)$ allows factorization of $n$. First question is that, does knowing value of $F_n(x)$ at any non-zero integer allow factorization of $n$? Second question is that, does knowing only constant many coefficients of $F_n(x)$ allow factorization of $n$?

• Another partial information is $F(a_1),\ldots ,F(a_{k-1})$ for distinct nonzero integers $a_i$.
– joro
Commented Jan 20, 2015 at 10:33
• @joro, I agree that my question is not very precise but asking values of $F(a_1),\ldots ,F(a_{k-1})$ is asking the whole $F_n(x)$. Commented Jan 20, 2015 at 18:31
• Indeed, but if you factor n you can trivially find the whole $F_n(x)$, so your logic applies to all partial informations :-)
– joro
Commented Jan 21, 2015 at 7:10

Knowing $F_n(1)$ or $F_n(-1)$ gives good randomized polynomial algorithm for the factorization of $n$.

We have $|F_n(1)|=\phi(n)$ and $|F_n(-1)|=\sigma(n)$ by definition.

$\phi(n)$ is Euler's totient function and $\sigma(n)$ is the sum of divisors function.

The paper you link to proves the case for $\sigma(n)$.

The same paper cites that the case for $\phi(n)$ is known and is derandomized assuming ERH (p. 1).

I am pretty sure both algorithms will be quite fast in practice.

• Yeah this is what they show in the linked paper. What I would be more interested in knowing is that if we are given some constants number of coefficients of $F_n(x)$, does that allow factorization of $n$? Also, an obvious conjecture of results in this paper would be that value of $F_n(x)$ at any non-zero integer allow factorization of $n$. Do you know if anything is known about these two questions? Commented Jan 21, 2015 at 15:47
• @GoravJindal I strongly doubt this is possible. It would be exciting if you can compute this in practice.
– joro
Commented Jan 22, 2015 at 10:03