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

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

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

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

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

<p>I am pretty sure both algorithms will be quite fast in practice.</p>

CC BY-SA 3.0
2015-01-21T15:47:32.000Z
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?
Gorav Jindal
CC BY-SA 3.0
2015-01-22T10:03:23.857Z
@GoravJindal I strongly doubt this is possible. It would be exciting if you can compute this in practice.
joro
CC BY-SA 3.0
2015-01-21T07:17:39.517Z
2015-01-21T07:17:39.517Z
joro
<p>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 </p>

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

<p>For example, it was demonstrated in <a href="https://www.cs.cmu.edu/~glmiller/Publications/Papers/BMS86.pdf" rel="nofollow">SUMS OF DIVISORS, PERFECT NUMBERS
AND FACTORING</a> 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?</p>

<p>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$?</p>

CC BY-SA 3.0
2015-01-20T10:33:48.360Z
Another partial information is $F(a_1),\ldots ,F(a_{k-1})$ for distinct nonzero integers $a_i$.
joro
CC BY-SA 3.0
2015-01-20T18:31:01.287Z
@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)$.
Gorav Jindal
CC BY-SA 3.0
2015-01-21T07:10:53.127Z
Indeed, but if you factor n you can trivially find the whole $F_n(x)$, so your logic applies to all partial informations :-)
joro
<cc.complexity-theory><ds.algorithms><nt.number-theory><comp-number-theory>
Integer factorization using polynomial whose roots are prime factors
Gorav Jindal
# Integer factorization using polynomial whose roots are prime factors

(Asked by: username_0 on 2015-01-19)

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](https://www.cs.cmu.edu/~glmiller/Publications/Papers/BMS86.pdf) 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 @username_1, 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$?

**Tags:** cc.complexity-theory, ds.algorithms, nt.number-theory, comp-number-theory

> **Comments:**
> **username_1**: Another partial information is $F(a_1),\ldots ,F(a_{k-1})$ for distinct nonzero integers $a_i$.  
> **username_0**: @username_1, 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)$.  
> **username_1**: Indeed, but if you factor n you can trivially find the whole $F_n(x)$, so your logic applies to all partial informations :-)  

---

## 1 answers

### Answer by username_1 on 2015-01-21. Score: 1

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.

> **Comments:**
> **username_0**: 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?  
> **username_1**: @GoravJindal I strongly doubt this is possible. It would be exciting if you can compute this in practice.  

---

