<p>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.  </p>

<p>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.</p>

CC BY-SA 2.5
2011-02-08T05:04:11.047Z
Here's a [related post in MO](http://mathoverflow.net/questions/3274/how-hard-is-it-to-compute-the-euler-totient-function) concerning the complexity of computing totient function.
Hsien-Chih Chang 張顯之
CC BY-SA 3.0
2014-07-15T09:58:19.157Z
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](http://dl.acm.org/citation.cfm?id=1529931) dedicates a chapter to this.
Juan Bermejo Vega
CC BY-SA 2.5
2011-02-08T04:58:15.233Z
2011-02-08T04:58:15.233Z
Robin Kothari
<p>Elaborating on Joe's earlier answer: note that $\textrm{FACTORING} \in \mathsf{NP \cap coNP}$. The latter is the <a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo%3aL#lkp">second lowest class in the "low" hierarchy</a>: 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}.$$</p>

CC BY-SA 3.0
2014-03-31T16:09:33.303Z
Thanks for the new answer. BTW, are you aware of papers/results about reducibility among problems in $NP \cap coNP$?
Marzio De Biasi
CC BY-SA 3.0
2014-03-31T22:51:06.063Z
It's even in $\mathsf{UP} \cap \mathsf{coUP}$ (the same reasoning as in your answer holds).
Joshua Grochow
CC BY-SA 3.0
2014-03-31T15:59:34.687Z
2014-03-31T16:04:53.950Z
2014-03-31T16:04:53.950Z
Niel de Beaudrap
<p>Since factorization is in NP, you can at least say that $P^A\subseteq \Delta_2^P$.</p>

CC BY-SA 2.5
2011-02-07T12:27:59.843Z
2011-02-07T12:27:59.843Z
Marcus Ritt
<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}$.</p>

CC BY-SA 2.5
2011-02-24T00:46:10.423Z
2011-02-24T00:46:10.423Z
Joe Fitzsimons
<p>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."</p>

<p>The first paper studying this concept is <a href="http://portal.acm.org/citation.cfm?id=1007394" rel="nofollow noreferrer">Prabhakaran &amp; Sahai (STOC '04)</a>. In particular, they wrote in the abstract:</p>

<blockquote>
  <p>[... we give the] adversary access to some super-polynomial computational power.</p>
</blockquote>

<p>Another important paper which discusses this notion is that of <a href="http://www.computer.org/portal/web/csdl/doi/10.1109/FOCS.2010.86" rel="nofollow noreferrer">Canetti, Lin, &amp; Pass (FOCS 2010)</a>. I watched some parts of their conference presentation (on <a href="http://techtalks.tv/focs/2010" rel="nofollow noreferrer">techtalks</a>), and if I recall correctly, they start with an example similar to what you mentioned in the question.</p>

CC BY-SA 3.0
2011-02-07T10:47:38.313Z
2016-12-07T21:14:02.297Z
2016-12-07T21:14:02.297Z
Sadeq Dousti
<p>I just read the "<a href="https://cstheory.stackexchange.com/q/159/1800">Is integer factorization an NP-complete problem?</a>" question ... so I decided to spend some of my reputation :-) asking another question $Q$ having $P(\text{Q is trivial}) \approx 1$:</p>

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

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

CC BY-SA 2.5
2011-02-07T15:35:50.823Z
@Vor that part `P(Q is trivial)=1` is a joke, isn't it?
Pratik Deoghare
CC BY-SA 2.5
2011-02-07T17:10:39.107Z
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
CC BY-SA 2.5
2011-02-08T04:54:06.517Z
@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
CC BY-SA 2.5
2011-02-08T08:07:39.970Z
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
CC BY-SA 2.5
2011-02-08T09:56:14.320Z
a related question is [What are the consequences of factoring being NP-complete?](http://cstheory.stackexchange.com/q/167/186), also see Lance Fortnow's [Blog post](http://blog.computationalcomplexity.org/2002/09/complexity-class-of-week-factoring.html)
Kaveh
CC BY-SA 2.5
2011-02-24T09:53:16.880Z
See also [Consequences of Factoring being in P?](http://cstheory.stackexchange.com/questions/5096/consequences-of-factoring-being-in-p)
Jukka Suomela
<cc.complexity-theory><oracles><factoring>
P with integer factorization oracle
Marzio De Biasi
# P with integer factorization oracle

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

I just read the "[Is integer factorization an NP-complete problem?](https://cstheory.stackexchange.com/q/159/1800)" 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?

**Tags:** cc.complexity-theory, oracles, factoring

> **Comments:**
> **username_1**: @Vor that part `P(Q is trivial)=1` is a joke, isn't it?  
> **username_2**: 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?  
> **username_3**: @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?  
> **username_0**: 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  
> **username_4**: a related question is [What are the consequences of factoring being NP-complete?](http://cstheory.stackexchange.com/q/167/186), also see Lance Fortnow's [Blog post](http://blog.computationalcomplexity.org/2002/09/complexity-class-of-week-factoring.html)  
> **username_5**: See also [Consequences of Factoring being in P?](http://cstheory.stackexchange.com/questions/5096/consequences-of-factoring-being-in-p)  

---

## 5 answers

### Answer by username_12 on 2011-02-07. Score: 11 | Accepted answer

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)](http://portal.acm.org/citation.cfm?id=1007394). 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)](http://www.computer.org/portal/web/csdl/doi/10.1109/FOCS.2010.86). I watched some parts of their conference presentation (on [techtalks](http://techtalks.tv/focs/2010)), and if I recall correctly, they start with an example similar to what you mentioned in the question.


---

### Answer by username_6 on 2011-02-08. Score: 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.

> **Comments:**
> **username_7**: Here's a [related post in MO](http://mathoverflow.net/questions/3274/how-hard-is-it-to-compute-the-euler-totient-function) concerning the complexity of computing totient function.  
> **username_8**: 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](http://dl.acm.org/citation.cfm?id=1529931) dedicates a chapter to this.  

---

### Answer by username_9 on 2014-03-31. Score: 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](https://complexityzoo.uwaterloo.ca/Complexity_Zoo%3aL#lkp): 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}.$$

> **Comments:**
> **username_0**: Thanks for the new answer. BTW, are you aware of papers/results about reducibility among problems in $NP \cap coNP$?  
> **username_3**: It's even in $\mathsf{UP} \cap \mathsf{coUP}$ (the same reasoning as in your answer holds).  

---

### Answer by username_10 on 2011-02-07. Score: 6

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


---

### Answer by username_11 on 2011-02-24. Score: 5

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


---

