[Math] Can a number be factored quickly, given the sum of its prime factors

algorithmscomputational complexitynt.number-theoryprime numbers

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.

Best Answer

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

Related Question