Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Say I have numbers with known factorizations $n = \prod \limits _i p_i ^{n_i}$ and $m = \prod \limits _i p_i ^{m_i}$ (where $p_i$ is the $i$th prime).

How hard is it to factorize $m+n$? Is there a more intelligent algorithm than if factorizations of $m$ and $n$ were not known? Assume $n$ and $m$ coprime as it is trivial to make them so.

The fact that $m+n$ will share no factors with $n$ or $m$ seems very helpful for small numbers, but I doubt it offers much for large ones.

share|cite|improve this question
An easier question might be this: Say I have a prime p. Is it easier than for general numbers to factorize p-1? – adrianN Jan 13 '13 at 12:07
@adrianN, well, we know that $p-1$ is even, so it definitely is slightly easier. Maybe $p-2$ is a better simplification. Though I don't know if there is any benefit from it. – Karolis Juodelė Jan 13 '13 at 12:22
Given Goldbach's conjecture, even the case $n$ prime and $m=2$ is already likely to be hard. – Gilles Jan 13 '13 at 18:07
Indeed additive number theory is a tough field. For a nice (non directly related to CS) lecture see this video of Terrence Tao – Jernej Jan 15 '13 at 11:31
up vote 3 down vote accepted

There is currently no known (asymptotical) more intelligent algorithm (and it is also not expected that there should be one) than if factorizations of $m$ and $n$ were not known (assuming $m$ and $n$ to be coprime). Even the case where $2$ is a prime factor doesn't count, because checking some of the smallest prime numbers can be done without much effort anyway.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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