Cheap and Secure Web Hosting Provider : See Now

# [Solved]: How hard is it to factorize sum of two numbers

, ,
Problem Detail:

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.

#### Answered By : Thomas Klimpel

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.