The problem of factoring integers in polynomial time with the help of
an infinitely powerful oracle who answers arbitrary questions with yes
or no is considered. The goal is to minimize the number of oracle que
stions. Let N be a given composite n-bit integer to be factored, where
n = [log(2) N]. The trivial method of asking for the bits of the smal
lest prime factor of N requires n/2 questions in the worst case. A non
-trivial algorithm of Rivest and Shamir requires only n/3 questions fo
r the special case where N is the product of two n/2-bit primes. In th
is paper, a polynomial-time oracle factoring algorithm for general int
egers is presented which, for any epsilon > 0, asks at most En oracle
questions for sufficiently large N, thus solving an open problem posed
by Rivest and Shamir. Based on a plausible conjecture related to Lens
tra's conjecture on the running time of the elliptic curve factoring a
lgorithm, it is shown that the algorithm fails with probability at mos
t N-(epsilon/2) for all sufficiently large N.