# Can a number be factored quickly, given the sum of its prime factors?

This is perhaps most naturally phrased as a promise problem. Given numbers $n$ and $s$, where $s$ is the sum of the prime factors of $n$ (distinct or with multiplicity; I imagine both variants will have the same answer), find the factorization of $n$. Can this be done in deterministic polynomial time?

Alternately, and slightly weaker: is FACTORIZATION (any of the standard decision-problem versions, perhaps "does $n$ have a prime factor between $a$ and $b$?") in $\text{P}^\text{sopf}$?

I'm essentially trying to prove to myself that sopf($n$) cannot be calculated faster than by factoring $n$, but the problem seems hopeless (unless $\text{FACTORIZATION}\in\text{P}$, in which case it is uninteresting). This is interesting because it seems 'obvious' that there could be no better approach, but I can't think of a way to formalize it that would be true, let alone have a hope to be proved.

Other approaches to this problem would be welcome.

• I would guess that if n is the product of two primes, one just a bit bigger than the square root of n, then knowing their sum isn't typically a help in factorising n. – Charles Matthews Sep 29 '10 at 6:15
• That was my feeling too -- even over a wider range, once n is sufficiently large. – Charles Sep 29 '10 at 6:18
• Charles- knowing the sum and product of two integers tells you what they are by the quadratic formula. – Ben Webster Sep 29 '10 at 6:18
• If $n$ is the product of exactly two primes, finding these from $n$ and $sopf(n)$ can be done by simply solving a quadratic equation in one variable: if $n = p q$ and $s = p + q$, then $p$ and $q$ are the solutions of $x^2 - s x + n = 0$. – felix Sep 29 '10 at 6:20
• However, knowing xyz and x + y + z isn't enough to determine x, y, z; knowing the sopf wouldn't help you factor non-semiprimes directly. – Harrison Brown Sep 29 '10 at 7:12

I don't know about the promise problem, but my educated hunch is that computing the sum of the prime factors should indeed be roughly as hard as factoring. Here's why: let $N$ be odd and squarefree. Then if we can compute $sopf(N)$, we'll know the parity of the number of prime factors of $N$, which I've gone on record as believing to be hard. (And nobody's contradicted me, so far...)
Let $N$ be the number to be factored. First, use an algorithm to quickly determine if $N$ is a perfect $k$-th power. Daniel Bernstein's papers say this can be done in "essentially linear time" (see this related MO post). Depending on the output of the first algorithm, use $A(\omega(N)) \ge G(\omega(N))$ (i.e. Arithmetic Mean-Geometric Mean Inequality) to reduce the search space:
$$\displaystyle\sum_{p|N}{p} \ge \omega(N)\left({\displaystyle\prod_{p | N}{p}}\right)^{\frac{1}{\omega(N)}}$$ with equality if and only if the previous algorithm gives an affirmative answer. Lastly, use number-theoretic techniques and your knowledge of the "structural properties" of $N$ to give "tight" lower bounds for $\omega(N)$, the number of distinct prime factors of $N$ and the radical $$rad(N) = \displaystyle\prod_{p | N}{p}$$ of $N$. This method will give you a priori knowledge (i.e. an estimate) for the true magnitude of the sum.
Of course, the same method gives you bounds for $\omega(N)$ and $rad(N)$ when either one is known, under the conditions of the problem that you are considering.
• Suppose someone gives you an arbitrary integer $N$ together with the sum of its prime factors. In general, you won't have any "structural properties" you can use. This question is asking about worst-case performance, not how well we can factor the rare numbers that happen to be nontrivial perfect powers. – S. Carnahan Mar 7 '11 at 4:10