Abstract
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. LetN be a given compositen-bit integer to be factored, wheren = ⌈log2 N⌉. The trivial method of asking for the bits of the smallest prime factor ofN requiresn/2 questions in the worst case. A non-trivial algorithm of Rivest and Shamir requires onlyn/3 questions for the special case whereN is the product of twon/2-bit primes. In this paper, a polynomial-time oracle factoring algorithm for general integers is presented which, for any ε>0, asks at most εn oracle questions for sufficiently largeN, 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 mostN −ε/2 for all sufficiently largeN.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
D. Atkins, M. Graff, A. K. Lenstra, andP. C. Leyland, The magic words are squeamish ossifrage. InAdvances in Cryptology-Asiacrypt '94 Lecture Notes in Computer Science917, Springer-Verlag (Berlin), 1994, 263–277.
E. Bach andJ. Shallit, Factoring with cyclotomic polynomials.Mathematics of Computation 52 (1989), 201–219.
E.R. Canfield, P. Erdös, andC. Pomerance, On a problem of Oppenheim concerning “Factorisatio Numerorum,”.Journal of Number Theory 17 (1983), 1–28.
B. Chor andO. Goldreich, On the power of two-point based sampling.Journal of Complexity 5(1) (1989), 96–106.
B. Dixon andA.K. Lenstra, Massively parallel elliptic curve factoring. InAdvances in Cryptology-EUROCRYPT '92, Lecture Notes in Computer Science658, Springer-Verlag (Berlin), 1993, 183–193.
A.K. Lenstra, H.W. Lenstra, M.S. Manasse, and J.M. Pollard, The number field sieve. InProceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990, 564–572.
A.K. Lenstra andM.S. Manasse, Factoring with two large primes. InAdvances in Cryptology-EUROCRYPT '90, Lecture Notes in Computer Science473, Springer-Verlag (Berlin), 1991, 69–80.
H.W. Lenstra, Jr., Factoring integers with elliptic curves.Annals of Mathematics 126 (1987), 649–673.
A. Menezes,Elliptic curve public key cryptosystems. Kluwer Academic Publishers, 1993.
J.M. Pollard, Theorems on factorization and primality testing.Proceedings of the Cambridge Philosophical Society 76 (1974), 521–528.
C. Pomerance, Factoring. InCryptology and computational number theory, ed.C. Pomerance,Proceedings of the Symposium in Applied Mathematics 42, American Mathematical Society, 1990, 27–47.
M.O. Rabin, Probabilistic algorithm for testing primality.Journal of Number Theory 12 (1980), 128–138.
R.L. Rivest andA. Shamir, Efficient factoring based on partial information. InAdvances in Cryptology-EUROCRYPT '85, Lecture Notes in Computer Science219, Springer-Verlag (Berlin), 1986, 31–34.
R.L. Rivest, A. Shamir, andL. Adleman, A method for obtaining digital signatures and public-key cryptosystems.Communications of the ACM 21(2) (1978), 120–126.
P. Shor, Algorithms for quantum computation: discrete logarithms and factoring. InProceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science, 1994, 124–134.
C.P. Schnorr andH.W. Lenstra, A Monte Carlo factoring algorithm with linear storage.Mathematics of Computation 43(167) (July 1984), 289–311.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Maurer, U.M. On the oracle complexity of factoring integers. Comput Complexity 5, 237–247 (1995). https://doi.org/10.1007/BF01206320
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF01206320