I'm looking for a reference for the following result:
Adding two integers in the factored representation is as hard as factoring two integers in the usual binary representation.
(I'm pretty sure it's out there because this is something I had wondered at some point, and then was excited when I finally saw it in print.)
"Adding two integers in the factored representation" is the problem: given the prime factorizations of two numbers $x$ and $y$, output the prime factorization of $x+y$. Note that the naive algorithm for this problem uses factorization in the standard binary representation as a subroutine.
Update: Thanks Kaveh and Sadeq for the proofs. Obviously the more proofs the merrier, but I would also like to encourage more help in finding a reference, which as I said I'm fairly sure exists. I recall reading it in a paper with other interesting and not-often-discussed ideas in it, but I don't recall what those other ideas were or what the paper was about in general.