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

  • $\begingroup$ Another partial information is $F(a_1),\ldots ,F(a_{k-1})$ for distinct nonzero integers $a_i$. $\endgroup$
    – joro
    Jan 20 '15 at 10:33
  • $\begingroup$ @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)$. $\endgroup$ Jan 20 '15 at 18:31
  • $\begingroup$ Indeed, but if you factor n you can trivially find the whole $F_n(x)$, so your logic applies to all partial informations :-) $\endgroup$
    – joro
    Jan 21 '15 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.

  • $\begingroup$ 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? $\endgroup$ Jan 21 '15 at 15:47
  • $\begingroup$ @GoravJindal I strongly doubt this is possible. It would be exciting if you can compute this in practice. $\endgroup$
    – joro
    Jan 22 '15 at 10:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.