# On the Oracle Complexity of Factoring Integers

## Ueli Maurer

```
```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
questions. Let $N$ be a given composite $n$-bit integer to be factored,
where $n=\lceil\log_2 N\rceil$. The trivial method of asking for the
bits of the smallest 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 for the special case where $N$ is the product of
two $n/2$-bit primes. In this paper, a polynomial-time oracle factoring
algorithm for general integers is presented which, for any $\ep>0$,
asks at most $\ep n$ oracle questions for sufficiently large $N$, thus
solving an open problem posed by Rivest and Shamir. Based on a
plausible conjecture related to Lenstra's conjecture on the running
time of the elliptic curve factoring algorithm it is shown that the
algorithm fails with probability at most $N^{-\ep/2}$ for all
sufficiently large $N$.

Keywords: Oracle complexity, Number theory, Factoring, Elliptic Curves,
Cryptography.