<p>The state of the art here is: We can <a href="http://en.wikipedia.org/wiki/AKS_primality_test" rel="nofollow">decide primality in polynomial time</a>, but the fastest, general-purpose algorithm to $\underline{\rm find}$ the factors of an n-bit composite integer <a href="http://en.wikipedia.org/wiki/General_number_field_sieve" rel="nofollow">takes time $\approx 2^{n^{1/3}\log^{2/3}n}$</a>.</p>

<p>More to your question, a primality test is the same thing as a compositeness test. Therefore, we can easily implement the 'primality decision oracle' required by <em>any</em> (supposed) Cook reduction from factoring to itself.</p>

<p>The reason, then, that factoring is commonly presented as an example of a problem that is "unlikely to be downward self-reducible" is because of the possibility that such a reduction identifies prime factors of the original integer. This can be phrased in many ways, but as Joshua points out in comments above, a good example is a reduction that takes $(n, k)$ (is there a factor of $n$ that is at most $k$?) to $(m, k')$ where $m|n$.</p>

<p>A reduction of this particular type would have the consequence of breaking the plethora of cryptosystems based on the hardness of factoring (without the need for a quantum computer), e.g. RSA.</p>

CC BY-SA 3.0
2015-01-15T20:56:32.773Z
How do you obtain a polynomial-time algorithm if the self-reduction does not obey the restriction in Joshua Grochow’s comment?
Emil Jeřábek
CC BY-SA 3.0
2015-01-15T21:54:47.803Z
To my knowledge, a reduction that doesn't respect algebraic structure is unknown as well. The reason that factoring is commonly taken as an example of a problem that is unlikely to be downward self-reducible is because of the likelihood that such a self-reduction would be algebraically meaningful.
Daniel Apon
CC BY-SA 3.0
2015-01-15T22:29:26.843Z
Then you should make clear in the answer that the claim is an unproved opinion, not a theorem. And I’m not convinced that this heuristic is sound: for example, when dealing with $N$, it is sometimes helpful to know the factorization of $N-1$ (that is, $(N-1)/2$, to make the bit-length strictly smaller), see e.g. the Lucas test.
Emil Jeřábek
CC BY-SA 3.0
2015-01-15T22:35:30.287Z
Sure. I'll re-word it.
Daniel Apon
CC BY-SA 3.0
2015-01-19T22:16:22.560Z
@DanielApon, can you explain why it identifies prime factors of the original integer? I do not understand your argument in "reduction that takes $(n,k)$ (is there a factor of $n$ that is at most $k$?) to $(m,k′)$ where $m|n$".
Gorav Jindal
CC BY-SA 3.0
2015-01-15T20:46:46.620Z
2015-01-15T22:46:10.607Z
2015-01-15T22:46:10.607Z
Daniel Apon
<p>Is integer factorization downward self-reducible? Is anything known about this?</p>

CC BY-SA 3.0
2015-01-13T01:22:58.287Z
All NP problems are downward self-reducible.
Kyle Jones
CC BY-SA 3.0
2015-01-13T08:45:40.723Z
@KyleJones: if I remember well all NP-*complete* problems are downward self-reducible. What happens for the so-called NPI problems is not knwon and probably FACTORING is one of the problems that suggest that not all problems are self-reducible. For example you can prove that there exist search problems that are not self-reducible if $P \neq NP \cap coNP$
Marzio De Biasi
CC BY-SA 3.0
2015-01-15T20:30:12.083Z
@MarzioDeBiasi: I think this is not even known for all NP-complete problems, though it may be true for all "natural" NP-complete problems (since all the known, natural ones are isomorphic by Berman and Hartmanis's padding result). I wonder if it is known to be true for the examples of Joseph and Young...
Joshua Grochow
CC BY-SA 3.0
2015-01-15T20:31:27.653Z
This may be trivial, but: if it is downward self-reducible in a way that respects factors, then factoring is in P. Namely, if the downward self-reduction reduces $(n,k)$ (is there a factor of $n$ that is at most $k$?) to $(m,k')$ where $m$ divides $n$, then you can use the self-reduction to do factoring....
Joshua Grochow
CC BY-SA 3.0
2015-01-15T20:53:34.560Z
Joshua: I'm pretty sure that's 'the' answer, not a trivial side point. :)
Daniel Apon
CC BY-SA 3.0
2015-01-15T20:56:11.627Z
Also, RE: Joshua's first comment: Here is a proof that *all* NP-complete languages are self-reducible; see Theorem 4 of http://www.cs.umd.edu/~jkatz/complexity/f11/lecture3.pdf
Daniel Apon
CC BY-SA 3.0
2015-01-15T21:04:05.250Z
@DanielApon: Under the standard definition, a language (or search problem, as here) is downward self-reducible if there is a polynomial-time algorithm that solves the problem on inputs of length $n$ using an oracle for the same problem restricted to inputs of length $< n$. That’s different from your lecture notes.
Emil Jeřábek
CC BY-SA 3.0
2015-01-15T21:52:49.160Z
@JoshuaGrochow: probably you are right, I confused (non downward) self-reducibility from search to decision (always possible for NPC problems). Note that there is also a downward self-reducibility definition in which the queries must be smaller than the input word *with respect to some polynomially related partial ordering on the alphabet*. Do you know an example of NPC problem for which downward self-reducibility is an open problem?
Marzio De Biasi
CC BY-SA 3.0
2015-01-15T22:52:12.527Z
@MarzioDeBiasi: I don't know for sure, but if it's open, I would imagine it's open for the k-creative sets of Joseph and Young: http://dx.doi.org/10.1016/0304-3975(85)90140-9
Joshua Grochow
<cc.complexity-theory><nt.number-theory><comp-number-theory>
Downward self-reducibility of factorization
Gorav Jindal
# Downward self-reducibility of factorization

(Asked by: username_0 on 2015-01-12)

Is integer factorization downward self-reducible? Is anything known about this?

**Tags:** cc.complexity-theory, nt.number-theory, comp-number-theory

> **Comments:**
> **username_1**: All NP problems are downward self-reducible.  
> **username_2**: @KyleJones: if I remember well all NP-*complete* problems are downward self-reducible. What happens for the so-called NPI problems is not knwon and probably FACTORING is one of the problems that suggest that not all problems are self-reducible. For example you can prove that there exist search problems that are not self-reducible if $P \neq NP \cap coNP$  
> **username_3**: @MarzioDeBiasi: I think this is not even known for all NP-complete problems, though it may be true for all "natural" NP-complete problems (since all the known, natural ones are isomorphic by Berman and Hartmanis's padding result). I wonder if it is known to be true for the examples of Joseph and Young...  
> **username_3**: This may be trivial, but: if it is downward self-reducible in a way that respects factors, then factoring is in P. Namely, if the downward self-reduction reduces $(n,k)$ (is there a factor of $n$ that is at most $k$?) to $(m,k')$ where $m$ divides $n$, then you can use the self-reduction to do factoring....  
> **username_4**: Joshua: I'm pretty sure that's 'the' answer, not a trivial side point. :)  
> **username_4**: Also, RE: Joshua's first comment: Here is a proof that *all* NP-complete languages are self-reducible; see Theorem 4 of http://www.cs.umd.edu/~jkatz/complexity/f11/lecture3.pdf  
> **username_5**: @DanielApon: Under the standard definition, a language (or search problem, as here) is downward self-reducible if there is a polynomial-time algorithm that solves the problem on inputs of length $n$ using an oracle for the same problem restricted to inputs of length $< n$. That’s different from your lecture notes.  
> **username_2**: @JoshuaGrochow: probably you are right, I confused (non downward) self-reducibility from search to decision (always possible for NPC problems). Note that there is also a downward self-reducibility definition in which the queries must be smaller than the input word *with respect to some polynomially related partial ordering on the alphabet*. Do you know an example of NPC problem for which downward self-reducibility is an open problem?  
> **username_3**: @MarzioDeBiasi: I don't know for sure, but if it's open, I would imagine it's open for the k-creative sets of Joseph and Young: http://dx.doi.org/10.1016/0304-3975(85)90140-9  

---

## 1 answers

### Answer by username_4 on 2015-01-15. Score: 4

The state of the art here is: We can [decide primality in polynomial time](http://en.wikipedia.org/wiki/AKS_primality_test), but the fastest, general-purpose algorithm to $\underline{\rm find}$ the factors of an n-bit composite integer [takes time $\approx 2^{n^{1/3}\log^{2/3}n}$](http://en.wikipedia.org/wiki/General_number_field_sieve).

More to your question, a primality test is the same thing as a compositeness test. Therefore, we can easily implement the 'primality decision oracle' required by *any* (supposed) Cook reduction from factoring to itself.

The reason, then, that factoring is commonly presented as an example of a problem that is "unlikely to be downward self-reducible" is because of the possibility that such a reduction identifies prime factors of the original integer. This can be phrased in many ways, but as Joshua points out in comments above, a good example is a reduction that takes $(n, k)$ (is there a factor of $n$ that is at most $k$?) to $(m, k')$ where $m|n$.

A reduction of this particular type would have the consequence of breaking the plethora of cryptosystems based on the hardness of factoring (without the need for a quantum computer), e.g. RSA.

> **Comments:**
> **username_5**: How do you obtain a polynomial-time algorithm if the self-reduction does not obey the restriction in username_3’s comment?  
> **username_4**: To my knowledge, a reduction that doesn't respect algebraic structure is unknown as well. The reason that factoring is commonly taken as an example of a problem that is unlikely to be downward self-reducible is because of the likelihood that such a self-reduction would be algebraically meaningful.  
> **username_5**: Then you should make clear in the answer that the claim is an unproved opinion, not a theorem. And I’m not convinced that this heuristic is sound: for example, when dealing with $N$, it is sometimes helpful to know the factorization of $N-1$ (that is, $(N-1)/2$, to make the bit-length strictly smaller), see e.g. the Lucas test.  
> **username_4**: Sure. I'll re-word it.  
> **username_0**: @DanielApon, can you explain why it identifies prime factors of the original integer? I do not understand your argument in "reduction that takes $(n,k)$ (is there a factor of $n$ that is at most $k$?) to $(m,k′)$ where $m|n$".  

---

