Downward self-reducibility of factorization

• @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 Jan 13 '15 at 8:45
• @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 Jan 15 '15 at 20:30
• 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 Jan 15 '15 at 20:31
• @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 supports Monica Jan 15 '15 at 21:04
• @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 Jan 15 '15 at 21:52

The state of the art here is: We can decide primality in polynomial time, 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}$.

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.

• 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 supports Monica Jan 15 '15 at 20:56
• 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 Jan 15 '15 at 21:54
• 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 supports Monica Jan 15 '15 at 22:29
• Sure. I'll re-word it. – Daniel Apon Jan 15 '15 at 22:35
• @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 Jan 19 '15 at 22:16