Adding integers represented by their factorization is as hard as factoring? Reference request

Question

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.

Answer 1

Assume that we can solve the problem (lets call it FactSum) in complexity class $C$ and $C$ is closed under $\log$-iteration (aka $\log$-bounded recursion)(e.g. if we can compute $x*y$ where $*$ is a binary function, we can computed $x_1*\ldots*x_{\log{n}}$) and contains $\mathsf{P}$ (this last condition can be made weaker). We show that factoring is in also in $C$.

Note that each number can be written as a sum of $\log n$ powers of $2$. Each of them are easy to factor.

Now given a number, write it as the sum of powers of it, then write each summand in the factoring representation, and then use the algorithm to sum them in the factoring representation. The result will be the factoring of the input number.

This shows that factoring is reducible to $\log$-iteration of your problem FactSum. Therefore factoring is in $\mathsf{P}^{\text{FactSum}}$ (and I think $\mathsf{P}$ can be replaced with $\mathsf{NC^1}$ here).

Answer 2

I'm not aware of a reference, but I think I came up with a proof:

Assume you have an oracle $\mathcal{O}$ which, on input two factored numbers

$x = \prod_{i=1}^n p_i^{\alpha_i}$

and

$y = \prod_{i=1}^m q_i^{\beta_i} \enspace$,

outputs the factorization of $x+y$.

Having access to $\mathcal{O}$, we can factor any number $N$ in polynomial time using the following recursive procedure.

PROCEDURE factor($N$)

1. Find a prime $x$ such that $N/2 \le x \le N-1$, and let $y = N - x$.
2. If $y$ is not a prime, get the factorization of $y$ by the recursive call factor($y$) and output $\mathcal{O}(x, factor(y))$.
3. Else output $\mathcal{O}(x,y)$.

---

Analysis:

By prime number theorem for large enough $N$, there are plenty of primes in between $N/2$ and $N-1$. If $N$ is so small that no prime falls in this interval, you can factor $N$ easily. Therefore, step 1 passes.

In step 2, you can use AKS or any other polynomial-time primality test.

The number of recursion is simply $O(\lg(N)) = O(|N|)$, since at each step $N$ is cut in half (at least)

---

PS-1: Assuming Goldbach's conjecture might help in speeding up the procedure for even (and possibly odd) integers.

PS-2: The reduction used is a Cook reduction. One might be interested in carrying out the proof using Karp reductions.

Answer 3

This response is independent of my previous answer. It's goal is to address @Kaveh's concern in the comments:

It is easy to do if we wanted $\log n$ numbers, but I don't see how to do it even with $\log \log n$ numbers.

I had a similar concern:

The reduction used is a Cook reduction. One might be interested in carrying out the proof using Karp reductions.

(Karp reductions are for decision problems. Here, by Karp reduction, I mean a single-query Cook reduction. Sorry for non-standard terminology!)

---

The answer below is based on the discussions here: https://math.stackexchange.com/questions/54580/factoring-some-integer-in-the-given-interval.

---

In this answer, I will provide a deterministic polynimial-time Karp reduction from factoring to factoring the sum of two integers represented by their factorizations. There's one catch, though: In the course of the proof, I will use the following number-theoretic assumption:

Cramér's conjecture: for any two consecutive prime numbers $p_n$ and $p_{n+1}$, we have $p_{n+1} - p_n = O(\log^2p_n)$.

Let $N$ be the input, and let $n=|N|=O(\log N)$. By Cramér's conjecture, for large enough $N$, there's at least one prime in the interval $[N - \log^3N, N]$. The length of this interval is $\log^3N = O(n^3)$. Therefore, this prime can be found in deterministic polynomial time by brute force.

Let $x$ be the prime number in $[N - \log^3N, N]$, and let $y=N-x$.

Since $0 \le y \le \log^3N$, we have $|y| = O(\log \log N) = O(\log n)$, and $y$ can be easily factorized (say, using trial division).

Finally, submit $(x,y)$ along with their factorizations to the oracle, and get the factorization of $N = x+y$.