Factoring with an Oracle

Ueli Maurer

Advances in Cryptology — EUROCRYPT '92, Lecture Notes in Computer Science, Springer-Verlag, vol. 658, pp. 429–436, May 1992, Final version: [Maurer96].

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. 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 $\epsilon>0$, asks at most $\epsilon n$ oracle questions for sufficiently large $N$. Based on a 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^{-\epsilon/2}$ for all sufficiently large $N$.

BibTeX Citation

@inproceedings{Maurer92f,
    author       = {Ueli Maurer},
    title        = {Factoring with an Oracle},
    editor       = {Rainer Rueppel},
    booktitle    = {Advances in Cryptology --- EUROCRYPT~'92},
    pages        = {429--436},
    series       = {Lecture Notes in Computer Science},
    volume       = {658},
    year         = {1992},
    month        = {5},
    note         = {Final version: \cite{Maurer96}},
    publisher    = {Springer-Verlag},
}

Files and Links

There are currently no associated files available.