×

On the oracle complexity of factoring integers. (English) Zbl 0851.68044

Summary: 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 \(\varepsilon> 0\), asks at most \(\varepsilon 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^{- \varepsilon/2}\) for all sufficiently large \(N\).

MSC:

68Q25 Analysis of algorithms and problem complexity
68P25 Data encryption (aspects in computer science)
90C60 Abstract computational complexity for mathematical programming problems
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] 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. · Zbl 0877.94026
[2] E. Bach andJ. Shallit, Factoring with cyclotomic polynomials.Mathematics of Computation 52 (1989), 201-219. · Zbl 0661.10008 · doi:10.1090/S0025-5718-1989-0947467-1
[3] E.R. Canfield, P. Erdös, andC. Pomerance, On a problem of Oppenheim concerning ?Factorisatio Numerorum,?.Journal of Number Theory 17 (1983), 1-28. · Zbl 0513.10043 · doi:10.1016/0022-314X(83)90002-1
[4] B. Chor andO. Goldreich, On the power of two-point based sampling.Journal of Complexity 5(1) (1989), 96-106. · Zbl 0672.60105 · doi:10.1016/0885-064X(89)90015-0
[5] 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. · Zbl 0811.11078
[6] 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. · Zbl 0806.11065
[7] 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.
[8] H.W. Lenstra, Jr., Factoring integers with elliptic curves.Annals of Mathematics 126 (1987), 649-673. · Zbl 0629.10006 · doi:10.2307/1971363
[9] A. Menezes,Elliptic curve public key cryptosystems. Kluwer Academic Publishers, 1993. · Zbl 0806.94011
[10] J.M. Pollard, Theorems on factorization and primality testing.Proceedings of the Cambridge Philosophical Society 76 (1974), 521-528. · Zbl 0294.10005 · doi:10.1017/S0305004100049252
[11] 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.
[12] M.O. Rabin, Probabilistic algorithm for testing primality.Journal of Number Theory 12 (1980), 128-138. · Zbl 0426.10006 · doi:10.1016/0022-314X(80)90084-0
[13] 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.
[14] 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. · Zbl 0368.94005 · doi:10.1145/359340.359342
[15] 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.
[16] C.P. Schnorr andH.W. Lenstra, A Monte Carlo factoring algorithm with linear storage.Mathematics of Computation 43(167) (July 1984), 289-311. · Zbl 0559.10004 · doi:10.1090/S0025-5718-1984-0744939-5
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.