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?
P with integer factorization oracle
cc.complexity theory;oracles;factoring
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.