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

Question

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.

Answer 1

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...)

Terry Tao's answer to that question, by the way, is incredibly useful in thinking about these types of problems. It also indicates that we can sometimes compute the parity even when we can't do anything else, though; I don't know if that applies to number-of-prime-factors. (I am decidedly not a number theorist...)

Answer 2

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.