# P with integer factorization oracle

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?

• @Vor that part P(Q is trivial)=1 is a joke, isn't it? Feb 7, 2011 at 15:35
• 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? Feb 7, 2011 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? Feb 8, 2011 at 4: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 Feb 8, 2011 at 8:07
• Feb 24, 2011 at 9:53

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:

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.

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.

• Here's a related post in MO concerning the complexity of computing totient function. Feb 8, 2011 at 5: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. Jul 15, 2014 at 9:58

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

• Thanks for the new answer. BTW, are you aware of papers/results about reducibility among problems in $NP \cap coNP$? Mar 31, 2014 at 16:09
• It's even in $\mathsf{UP} \cap \mathsf{coUP}$ (the same reasoning as in your answer holds). Mar 31, 2014 at 22:51

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

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