22
$\begingroup$

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.

$\endgroup$
  • 6
    $\begingroup$ I think a better title will be "Is factoring the sum of two integers represented by their factorization as hard as factoring?" $\endgroup$ – M.S. Dousti Jul 23 '11 at 16:54
  • 1
    $\begingroup$ 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. $\endgroup$ – Kaveh Jul 23 '11 at 17:14
  • 1
    $\begingroup$ some related questions on MO and Math.SE: 1, 2, 3 $\endgroup$ – Kaveh Aug 4 '11 at 15:22
15
$\begingroup$

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

$\endgroup$
10
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ I think it is open if we can find a prime in a given range efficiently so I don't see how you are doing 1. $\endgroup$ – Kaveh Jul 23 '11 at 17:33
  • 1
    $\begingroup$ @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). $\endgroup$ – M.S. Dousti Jul 23 '11 at 17:43
  • 2
    $\begingroup$ 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). $\endgroup$ – Kaveh Jul 23 '11 at 17:47
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Kaveh Aug 1 '11 at 19:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.