<p>This is not really an answer, yet it sheds some light on the difficulty of demonstrating such reductions.</p>

<hr>

<p>The problem can be summarized as follows:
Let $\mathcal{A}$ be an algorithm which solves the INTEGER-MULT problem with non-negligible probability. Let this probability be at least $n^{-c}$, for some constant $c \in \mathbb{N}$ (when the size of input is $n$). Prove that there exists a PPT (probabilistic polynomial-time) algorithm $\mathcal{A}&#39;$ which, uses $\mathcal{A}$ as subroutine, and solves an instance of the FACTORING problem of size $n$ with probability at least $n^{-d}$, for some constant $d \in \mathbb{N}$.</p>

<p>Consider an algorithm $\mathcal{A}^*$ which solves the INTEGER-MULT problem if and only if the input $N$ has the <strong>special from</strong> $N = PQR$, where $P$ and $Q$ are primes of size $n/4$ and $R$ is a prime of size $n/2$, and otherwise fails. Moreover, on input an integer $N$ of the above form, it outputs $PQ$ and $R$. We first show that $\mathcal{A}^*$ has a non-negligible probability of solving the INTEGER-MULT problem. To this end, it suffices to find the fraction of $n$-bit integers of the special form, as this fraction bounds the success probability of $\mathcal{A}^*$ from below.</p>

<p>By <a href="http://en.wikipedia.org/wiki/Prime_number_theorem" rel="nofollow">prime number theorem</a>, the number of primes whose size is $k$-bits is:</p>

<p>$2^k / \ln(2^k) - 2^{k-1} / \ln(2^{k-1}) = \Theta(2^k / k)$</p>

<p>Therefore, the fraction of $n$-bit integers of the special form is:</p>

<p>$\frac{\Theta(2^{n/4} / (n/4))^2 \cdot \Theta(2^{n/2} / (n/2))}{2^{n-1}} = \Theta(n^{-3})$</p>

<p>which is non-negligible in $n$.</p>

<p>Therefore, one should be able to prove the existence of a PPT algorithm $\mathcal{A}&#39;$ which, uses $\mathcal{A}^*$ as subroutine, and solves an instance of the FACTORING problem of size $n$ with probability at least $n^{-d}$, for some constant $d \in \mathbb{N}$.</p>

<p>IMHO, this seems a very difficult task, since $\mathcal{A}^*$ only (partially) decomposes integers of the special form, and there does not seem to be a way to use it to decompose integers of the form $PQ$.</p>

CC BY-SA 3.0
2011-07-29T10:52:15.600Z
2011-07-29T12:24:25.283Z
2011-07-29T12:24:25.283Z
Sadeq Dousti
<p>My question is about the equivalence of the security of various candidate one-way functions that can be constructed based on the hardness of factoring. </p>

<p>Assuming the problem of</p>

<blockquote>
  <p>FACTORING:[Given $N = PQ$ for random primes $P, Q &lt; 2^n$, find $P$, $Q$.]</p>
</blockquote>

<p>cannot be solved in polynomial time with nonnegligible probability, the function</p>

<blockquote>
  <p>PRIME-MULT: [Given bit string $x$ as input, use $x$ as a seed to generate two random primes $P$ and $Q$ (where the lengths of $P$, $Q$ are only polynomially smaller than the length of $x$); then output $PQ$.]</p>
</blockquote>

<p>can be shown to be one-way.</p>

<p>Another candidate one-way function is</p>

<blockquote>
  <p>INTEGER-MULT: [Given random integers $A, B &lt; 2^n$ as input, output $A B$.]</p>
</blockquote>

<p>INTEGER-MULT has the advantage that it is easier to define compared to PRIME-MULT. (Notice in particular that in PRIME-MULT, there is a chance (though fortunately negligible) that the seed $x$ fails to generate $P, Q$ that are prime.) </p>

<p>At least in two different places (Arora-Barak, Computational Complexity, page 177, footnote 2) and (<a href="http://people.seas.harvard.edu/~salil/cs120/docs/lec7.pdf" rel="nofollow">Vadhan's Introduction to Cryptography lecture notes</a>) it is mentioned that INTEGER-MULT is one-way assuming average hardness of factoring. However, neither of these two gives the reason or a reference for this fact.</p>

<p>So the question is:</p>

<blockquote>
  <p>How can we reduce in polynomial time factoring of $N = PQ$ with nonnegligible probability to inverting INTEGER-MULT with nonnegligible probability?</p>
</blockquote>

<p>Here is a possible approach (that as we will see does NOT work!):
Given $N = PQ$, multiply $N$ by a much (though polynomially) longer random integer $A&#39;$ to get $A = NA&#39;$. The idea is that $A&#39;$ is so large that it has lots of prime factors of size roughly equal to $P, Q$, so that $P, Q$ do not "stand out" among the prime factors of $A$. Then $A$ has approximately the distribution of a uniformly random integer at a given range (say $[0,2^n-1]$). Next choose integer $B$ randomly from the same range $[0,2^n-1]$.</p>

<p>Now if an inverter for INTEGER-MULT can, given $AB$, with some probability find $A&#39;, B&#39; &lt; 2^n$ such that $A&#39;B&#39; = AB$, the hope is that one of $A&#39;$ or $B&#39;$ contains $P$ as a factor and the other contains $Q$. If that was the case, we can find $P$ or $Q$ by taking gcd of $A&#39;$ with $N = PQ$. </p>

<p>The problem is that the inverter may choose to separate the prime factors, for example, putting the small factors of $AB$ in $A&#39;$ and the large ones in $B&#39;$, so that $P$ and $Q$ end up both in $A&#39;$ or both in $B&#39;$.</p>

<p>Is there another approach that works?</p>

CC BY-SA 3.0
2011-07-29T03:36:04.617Z
can we reduce the probability of failure for INT-FACT to be exponentially small and then use the density of primes to say that it will not fail on most products of two primes?
Kaveh
CC BY-SA 3.0
2011-07-29T04:02:03.177Z
If we could invert INTEGER-MULT for all instances except exponentially small fraction of the instances, indeed FACTORING products of primes would be easy. But I don't know of a way of getting a strong inverter from a weak inverter.
Omid Etesami
CC BY-SA 3.0
2011-07-29T14:24:58.287Z
The (somehow) inverse of this problem has already been discussed [here](http://cstheory.stackexchange.com/questions/6704/is-the-integer-factorization-problem-harder-than-rsa-factorization-n-pq).
Sadeq Dousti
CC BY-SA 3.0
2011-07-29T23:28:05.340Z
http://mathoverflow.net/questions/71604/reducing-factoring-prime-products-to-factoring-integer-products-in-average-case
Tsuyoshi Ito
<reference-request><cr.crypto-security><nt.number-theory><average-case-complexity><one-way-function>
Reducing factoring prime products to factoring integer products (in average-case)
Omid Etesami
# Reducing factoring prime products to factoring integer products (in average-case)

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

My question is about the equivalence of the security of various candidate one-way functions that can be constructed based on the hardness of factoring.

Assuming the problem of

> FACTORING:[Given $N = PQ$ for random primes $P, Q < 2^n$, find $P$, $Q$.]

cannot be solved in polynomial time with nonnegligible probability, the function

> PRIME-MULT: [Given bit string $x$ as input, use $x$ as a seed to generate two random primes $P$ and $Q$ (where the lengths of $P$, $Q$ are only polynomially smaller than the length of $x$); then output $PQ$.]

can be shown to be one-way.

Another candidate one-way function is

> INTEGER-MULT: [Given random integers $A, B < 2^n$ as input, output $A B$.]

INTEGER-MULT has the advantage that it is easier to define compared to PRIME-MULT. (Notice in particular that in PRIME-MULT, there is a chance (though fortunately negligible) that the seed $x$ fails to generate $P, Q$ that are prime.)

At least in two different places (Arora-Barak, Computational Complexity, page 177, footnote 2) and ([Vadhan's Introduction to Cryptography lecture notes](http://people.seas.harvard.edu/~salil/cs120/docs/lec7.pdf)) it is mentioned that INTEGER-MULT is one-way assuming average hardness of factoring. However, neither of these two gives the reason or a reference for this fact.

So the question is:

> How can we reduce in polynomial time factoring of $N = PQ$ with nonnegligible probability to inverting INTEGER-MULT with nonnegligible probability?

Here is a possible approach (that as we will see does NOT work!):
Given $N = PQ$, multiply $N$ by a much (though polynomially) longer random integer $A'$ to get $A = NA'$. The idea is that $A'$ is so large that it has lots of prime factors of size roughly equal to $P, Q$, so that $P, Q$ do not "stand out" among the prime factors of $A$. Then $A$ has approximately the distribution of a uniformly random integer at a given range (say $[0,2^n-1]$). Next choose integer $B$ randomly from the same range $[0,2^n-1]$.

Now if an inverter for INTEGER-MULT can, given $AB$, with some probability find $A', B' < 2^n$ such that $A'B' = AB$, the hope is that one of $A'$ or $B'$ contains $P$ as a factor and the other contains $Q$. If that was the case, we can find $P$ or $Q$ by taking gcd of $A'$ with $N = PQ$.

The problem is that the inverter may choose to separate the prime factors, for example, putting the small factors of $AB$ in $A'$ and the large ones in $B'$, so that $P$ and $Q$ end up both in $A'$ or both in $B'$.

Is there another approach that works?

**Tags:** reference-request, cr.crypto-security, nt.number-theory, average-case-complexity, one-way-function

> **Comments:**
> **username_1**: can we reduce the probability of failure for INT-FACT to be exponentially small and then use the density of primes to say that it will not fail on most products of two primes?  
> **username_0**: If we could invert INTEGER-MULT for all instances except exponentially small fraction of the instances, indeed FACTORING products of primes would be easy. But I don't know of a way of getting a strong inverter from a weak inverter.  
> **username_2**: The (somehow) inverse of this problem has already been discussed [here](http://cstheory.stackexchange.com/questions/6704/is-the-integer-factorization-problem-harder-than-rsa-factorization-n-pq).  
> **username_3**: http://mathoverflow.net/questions/71604/reducing-factoring-prime-products-to-factoring-integer-products-in-average-case  

---

## 1 answers

### Answer by username_2 on 2011-07-29. Score: 4

This is not really an answer, yet it sheds some light on the difficulty of demonstrating such reductions.

---

The problem can be summarized as follows:
Let $\mathcal{A}$ be an algorithm which solves the INTEGER-MULT problem with non-negligible probability. Let this probability be at least $n^{-c}$, for some constant $c \in \mathbb{N}$ (when the size of input is $n$). Prove that there exists a PPT (probabilistic polynomial-time) algorithm $\mathcal{A}'$ which, uses $\mathcal{A}$ as subroutine, and solves an instance of the FACTORING problem of size $n$ with probability at least $n^{-d}$, for some constant $d \in \mathbb{N}$.

Consider an algorithm $\mathcal{A}^\*$ which solves the INTEGER-MULT problem if and only if the input $N$ has the **special from** $N = PQR$, where $P$ and $Q$ are primes of size $n/4$ and $R$ is a prime of size $n/2$, and otherwise fails. Moreover, on input an integer $N$ of the above form, it outputs $PQ$ and $R$. We first show that $\mathcal{A}^\*$ has a non-negligible probability of solving the INTEGER-MULT problem. To this end, it suffices to find the fraction of $n$-bit integers of the special form, as this fraction bounds the success probability of $\mathcal{A}^\*$ from below.

By [prime number theorem](http://en.wikipedia.org/wiki/Prime_number_theorem), the number of primes whose size is $k$-bits is:

$2^k / \ln(2^k) - 2^{k-1} / \ln(2^{k-1}) = \Theta(2^k / k)$

Therefore, the fraction of $n$-bit integers of the special form is:

$\frac{\Theta(2^{n/4} / (n/4))^2 \cdot \Theta(2^{n/2} / (n/2))}{2^{n-1}} = \Theta(n^{-3})$

which is non-negligible in $n$.

Therefore, one should be able to prove the existence of a PPT algorithm $\mathcal{A}'$ which, uses $\mathcal{A}^\*$ as subroutine, and solves an instance of the FACTORING problem of size $n$ with probability at least $n^{-d}$, for some constant $d \in \mathbb{N}$.

IMHO, this seems a very difficult task, since $\mathcal{A}^\*$ only (partially) decomposes integers of the special form, and there does not seem to be a way to use it to decompose integers of the form $PQ$.


---

