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.

  • $\begingroup$ 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. $\endgroup$ Sep 29 '10 at 6:15
  • $\begingroup$ That was my feeling too -- even over a wider range, once n is sufficiently large. $\endgroup$
    – Charles
    Sep 29 '10 at 6:18
  • 23
    $\begingroup$ Charles- knowing the sum and product of two integers tells you what they are by the quadratic formula. $\endgroup$
    – Ben Webster
    Sep 29 '10 at 6:18
  • 5
    $\begingroup$ 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$. $\endgroup$
    – felix
    Sep 29 '10 at 6:20
  • 1
    $\begingroup$ 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. $\endgroup$ 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...)

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


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.

  • 2
    $\begingroup$ 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. $\endgroup$
    – S. Carnahan
    Mar 7 '11 at 4:10

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.