19
$\begingroup$

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?

Improve this question
$\endgroup$
6
  • 3
    $\begingroup$ @Vor that part P(Q is trivial)=1 is a joke, isn't it? $\endgroup$
    – Pratik Deoghare
    Feb 7, 2011 at 15:35
  • $\begingroup$ 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? $\endgroup$
    – John Sidles
    Feb 7, 2011 at 17:10
  • 2
    $\begingroup$ @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? $\endgroup$
    – Joshua Grochow
    Feb 8, 2011 at 4:54
  • $\begingroup$ 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 $\endgroup$
    – Marzio De Biasi
    Feb 8, 2011 at 8:07
  • 1
    $\begingroup$ See also Consequences of Factoring being in P? $\endgroup$
    – Jukka Suomela
    Feb 24, 2011 at 9:53

5 Answers 5

Reset to default
11
$\begingroup$

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.

Improve this answer
$\endgroup$
13
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ Here's a related post in MO concerning the complexity of computing totient function. $\endgroup$
    – Hsien-Chih Chang 張顯之
    Feb 8, 2011 at 5:04
  • $\begingroup$ 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. $\endgroup$
    – Juan Bermejo Vega
    Jul 15, 2014 at 9:58
10
$\begingroup$

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

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

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

Improve this answer
$\endgroup$
5
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.