<p>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$.</p>

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

<p>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.</p>

<p>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). </p>

CC BY-SA 3.0
2011-07-23T17:25:33.390Z
2011-07-23T17:43:58.137Z
2011-07-23T17:43:58.137Z
Kaveh
<p>I'm not aware of a reference, but I think I came up with a proof:</p>

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

<p>$x = \prod_{i=1}^n p_i^{\alpha_i}$</p>

<p>and</p>

<p>$y = \prod_{i=1}^m q_i^{\beta_i} \enspace$,</p>

<p>outputs the factorization of $x+y$.</p>

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

<p><strong>PROCEDURE</strong> factor($N$)</p>

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

<hr>

<p><strong>Analysis:</strong> </p>

<p>By <a href="http://en.wikipedia.org/wiki/Prime_number_theorem" rel="nofollow">prime number theorem</a> 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.</p>

<p>In step 2, you can use <a href="http://en.wikipedia.org/wiki/AKS_primality_test" rel="nofollow">AKS</a> or any other  polynomial-time primality test.</p>

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

<hr>

<p><strong>PS-1:</strong> Assuming <a href="http://en.wikipedia.org/wiki/Goldbach%27s_conjecture" rel="nofollow">Goldbach's conjecture</a> might help in speeding up the procedure for even (and possibly odd) integers.</p>

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

CC BY-SA 3.0
2011-07-23T17:33:02.230Z
I think it is open if we can [find a prime in a given range efficiently](http://cstheory.stackexchange.com/questions/4882/finding-a-prime-greater-than-a-given-bound) so I don't see how you are doing 1.
Kaveh
CC BY-SA 3.0
2011-07-23T17:43:49.353Z
@Kaveh: You're right! With some extra steps, I think I can change the algorithm not to require $x$ to be prime and then factor it like $y$; or we can assume that the reduction is probabilistic (since in **probabilistic** polynomial time, we can find a prime in the given range).
Sadeq Dousti
CC BY-SA 3.0
2011-07-23T17:47:47.433Z
Yes, I think we had the same idea, i.e. wanted to find easy to factor integers which sum to the input, you tried to use primes, I used powers of 2. :) I still don't know if we can do it with less than logarithmic number of queries to the oracle, and that seems to be related to an interesting and natural number theory question (writing numbers as sum of easy to factor numbers).
Kaveh
CC BY-SA 3.0
2011-07-23T17:28:16.787Z
2013-06-17T20:40:44.320Z
2013-06-17T20:40:44.320Z
Sadeq Dousti
<p>This response is independent of <a href="https://cstheory.stackexchange.com/questions/7491/7493#7493">my previous answer</a>. It's goal is to address @Kaveh's concern in the comments: </p>

<blockquote>
  <p>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.</p>
</blockquote>

<p>I had a similar concern: </p>

<blockquote>
  <p>The reduction used is a Cook reduction. One might be interested in carrying out the proof using Karp reductions.</p>
</blockquote>

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

<hr>

<p>The answer below is based on the discussions here: <a href="https://math.stackexchange.com/questions/54580/factoring-some-integer-in-the-given-interval">https://math.stackexchange.com/questions/54580/factoring-some-integer-in-the-given-interval</a>.</p>

<hr>

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

<blockquote>
  <p><a href="http://en.wikipedia.org/wiki/Cram%C3%A9r&#39;s_conjecture" rel="nofollow noreferrer">Cramér's conjecture</a>: for any two consecutive prime numbers $p_n$ and $p_{n+1}$, we have $p_{n+1} - p_n = O(\log^2p_n)$.</p>
</blockquote>

<p>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 <em>deterministic</em> polynomial time by <strong>brute force</strong>.</p>

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

<p>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 <a href="http://en.wikipedia.org/wiki/Trial_division" rel="nofollow noreferrer">trial division</a>).</p>

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

CC BY-SA 3.0
2011-08-01T19:47:19.473Z
Thanks Sadeq, but conditional results was not what I was asking for. ps: I am interested in interesting representations of numbers and the representation that one gets from your answer (taking out a large prime) does not look very interesting to me. For giving the flavor of what I would be interesting to me: every natural number is [sum of four squares](http://en.wikipedia.org/wiki/Sum_of_four_squares).
Kaveh
CC BY-SA 3.0
2011-07-31T08:51:08.607Z
2011-07-31T08:51:08.607Z
2017-04-13T12:32:28.077Z
Sadeq Dousti
<p>I'm looking for a reference for the following result:</p>

<blockquote>
  <p>Adding two integers in the factored representation is as hard as factoring two integers in the usual binary representation.</p>
</blockquote>

<p>(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.)</p>

<p>"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.</p>

<p><strong>Update</strong>: 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 <strong>reference</strong>, 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.</p>

CC BY-SA 3.0
2011-07-23T16:54:01.280Z
I think a better title will be "Is factoring the sum of two integers represented by their factorization as hard as factoring?"
Sadeq Dousti
CC BY-SA 3.0
2011-07-23T17:14:06.687Z
Nice question. If we can write a given integer as sum of two easy to factor integers, then what you want follows. 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. May worth to look at the classes of numbers which are easy to factor.
Kaveh
CC BY-SA 3.0
2011-08-04T15:22:55.057Z
some related questions on MO and Math.SE: [1](https://mathoverflow.net/questions/72076/factoring-some-integer-in-the-given-interval), [2](http://math.stackexchange.com/questions/54580), [3](http://math.stackexchange.com/questions/54719)
Kaveh
<cc.complexity-theory><reference-request><time-complexity><factoring><encoding>
Adding integers represented by their factorization is as hard as factoring? Reference request
Joshua Grochow
# Adding integers represented by their factorization is as hard as factoring? Reference request

(Asked by: username_0 on 2011-07-23)

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 username_2 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.

**Tags:** cc.complexity-theory, reference-request, time-complexity, factoring, encoding

> **Comments:**
> **username_1**: I think a better title will be "Is factoring the sum of two integers represented by their factorization as hard as factoring?"  
> **username_2**: Nice question. If we can write a given integer as sum of two easy to factor integers, then what you want follows. 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. May worth to look at the classes of numbers which are easy to factor.  
> **username_2**: some related questions on MO and Math.SE: [1](https://mathoverflow.net/questions/72076/factoring-some-integer-in-the-given-interval), [2](http://math.stackexchange.com/questions/54580), [3](http://math.stackexchange.com/questions/54719)  

---

## 3 answers

### Answer by username_2 on 2011-07-23. Score: 15

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 by username_1 on 2011-07-23. Score: 10

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](http://en.wikipedia.org/wiki/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](http://en.wikipedia.org/wiki/AKS_primality_test) 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](http://en.wikipedia.org/wiki/Goldbach%27s_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.

> **Comments:**
> **username_2**: I think it is open if we can [find a prime in a given range efficiently](http://cstheory.stackexchange.com/questions/4882/finding-a-prime-greater-than-a-given-bound) so I don't see how you are doing 1.  
> **username_1**: @username_2: You're right! With some extra steps, I think I can change the algorithm not to require $x$ to be prime and then factor it like $y$; or we can assume that the reduction is probabilistic (since in **probabilistic** polynomial time, we can find a prime in the given range).  
> **username_2**: Yes, I think we had the same idea, i.e. wanted to find easy to factor integers which sum to the input, you tried to use primes, I used powers of 2. :) I still don't know if we can do it with less than logarithmic number of queries to the oracle, and that seems to be related to an interesting and natural number theory question (writing numbers as sum of easy to factor numbers).  

---

### Answer by username_1 on 2011-07-31. Score: 5

This response is independent of [my previous answer](https://cstheory.stackexchange.com/questions/7491/7493#7493). It's goal is to address @username_2'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](http://en.wikipedia.org/wiki/Cram%C3%A9r'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](http://en.wikipedia.org/wiki/Trial_division)).

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

> **Comments:**
> **username_2**: Thanks Sadeq, but conditional results was not what I was asking for. ps: I am interested in interesting representations of numbers and the representation that one gets from your answer (taking out a large prime) does not look very interesting to me. For giving the flavor of what I would be interesting to me: every natural number is [sum of four squares](http://en.wikipedia.org/wiki/Sum_of_four_squares).  

---

