# 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 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 at 12:22
Given Goldbach's conjecture, even the case $n$ prime and $m=2$ is already likely to be hard. –  Gilles Jan 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 at 11:31
add comment