P with integer factorization oracle

Question

I just read the "Is integer factorization an NP-complete problem?" question ... so I decided to spend some of my reputation :-) asking another question $Q$ having $P(\text{Q is trivial}) \approx 1$:

If $A$ is an oracle that solves integer factorization, what is the power of $P^A$?

I think it makes RSA-based public-key cryptography insecure ... but apart from this, are there other remarkable results?

This question suggests a related and (perhaps) more natural question: if R is an oracle that returns f(M,n) as the maximal runtime of a polynomial-time Turing machine M over all inputs of length n, what is the power of P^R? — John Sidles, Feb 07 '11 at 17:10
@Vor: Isn't this the same as asking "Which problems can be polynomial-time Turing reduces to integer factorization?" Or did you intend to ask something else? — Joshua Grochow, Feb 08 '11 at 04:54
I'm a newbie, so my question is almost a curiosity. All started from a simple thought: out "in the real world" I see many NP-complete problems (a postman trying to reserve his strength, a family that is moving and want to fit its furniture in a truck, ... :-))). But I don't see "factoring problems" ... although they MAY be simpler (between P and NPC). ... perhaps reality hates multiplications :-D :-D — Marzio De Biasi, Feb 08 '11 at 08:07
a related question is What are the consequences of factoring being NP-complete?, also see Lance Fortnow's Blog post — Kaveh, Feb 08 '11 at 09:56

score 13 · Answer 1 · answered Feb 08 '11 at 04:58

13

Obviously any decision problem that can be reduced to factoring can be solved with a factoring oracle. But since we're given the ability to make multiple queries, I tried to think of a non-trivial problem for which one would want to make multiple queries.

The problem of computing the Euler totient function seems like such a problem. I don't know how to solve the decision version of this problem by a Karp-reduction to the decision version of factoring. But with Turing reductions, it's easy to reduce this to factoring.

answered Feb 08 '11 at 04:58

Robin Kothari

13,617
2
60
116

3

Here's a related post in MO concerning the complexity of computing totient function. – Hsien-Chih Chang 張顯之 Feb 08 '11 at 05:04
Small addition: there are also polynomial time reductions in the other direction, computing Euler's Totient function -> Factoring. I have not checked whether the known reductions work for the decision version of these problems though. Still, being able to compute the Totient function (or even a fixed multiple of it) gives you the ability to factorize. Shoup's book dedicates a chapter to this. – Juan Bermejo Vega Jul 15 '14 at 09:58

Sadeq Dousti · Accepted Answer · 2016-12-07T21:14:02.297

I don't have an answer to you question, but I know that a similar notion has very recently been studied, under the name of "angel-based security."

The first paper studying this concept is Prabhakaran & Sahai (STOC '04). In particular, they wrote in the abstract:

[... we give the] adversary access to some super-polynomial computational power.

Another important paper which discusses this notion is that of Canetti, Lin, & Pass (FOCS 2010). I watched some parts of their conference presentation (on techtalks), and if I recall correctly, they start with an example similar to what you mentioned in the question.

Niel de Beaudrap · Answer 3 · 2014-03-31T16:04:53.950

10

Elaborating on Joe's earlier answer: note that $\textrm{FACTORING} \in \mathsf{NP \cap coNP}$. The latter is the second lowest class in the "low" hierarchy: which is to say that $\mathsf{NP^{NP \cap coNP} = NP}$. This implies in particular that $$\mathsf{P^{\textrm{FACTORING}} \subseteq NP^{\textrm{FACTORING}}} \subseteq \mathsf{NP}.$$ We may make similar remarks for $\mathsf{coNP}$ and $\mathsf{BQP}$, to show that at least on a coarse-grained level, $\mathsf P^{\textrm{FACTORING}}$ has the same complexity bounds as the problem $\textrm{FACTORING}$ itself, which is to say $$ \mathsf{P^{\textrm{FACTORING}} \subseteq NP \cap coNP \cap BQP}.$$

edited Mar 31 '14 at 16:04

answered Mar 31 '14 at 15:59

Niel de Beaudrap

8,821
31
70

Thanks for the new answer. BTW, are you aware of papers/results about reducibility among problems in $NP \cap coNP$? – Marzio De Biasi Mar 31 '14 at 16:09
3

It's even in $\mathsf{UP} \cap \mathsf{coUP}$ (the same reasoning as in your answer holds). – Joshua Grochow Mar 31 '14 at 22:51

score 6 · Answer 4 · answered Feb 07 '11 at 12:27

6

Since factorization is in NP, you can at least say that $P^A\subseteq \Delta_2^P$.

answered Feb 07 '11 at 12:27

Marcus Ritt

1,450
14
21

score 5 · Answer 5 · answered Feb 24 '11 at 00:46

Well, as others noted factorization is in $\mbox{FNP}$, so we have $P \subseteq P^A \subseteq \Delta_2^p$ (i.e. $P^{NP}$). However, the decision version of factoring is also in $\mbox{BQP}$, so in fact we can do slightly better and get $P \subseteq P^A \subseteq P^{NP \cap BQP}$.

P with integer factorization oracle

5 Answers5

Linked