# How hard is it to factorize sum of two numbers

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.

-
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 youtube.com/watch?v=PtsrAw1LR3E – Jernej Jan 15 '13 at 11:31

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.