×

zbMATH — the first resource for mathematics

Modifications to the number field sieve. (English) Zbl 0806.11071
The number field sieve, due to Lenstra et al. and Buhler et al., is a routine for factoring integers. The running time of this algorithm is estimated at \(e^{1.923+ \sigma(1) (\log N)^{1/3} (\log\log N)^{2/3}}\), where \(N\) is the number to be factored and \(\sigma(1)\) tends to 0 as \(N\to\infty\).
The paper gives a brief description of the sieve method and describes a modification which reuses the computations of the initial sieve to reduce the exponent in the running time expression from 1.923 to 1.902.
Furthermore, the same ideas are used to describe a way to precompute tables which are useful in factoring any integers in a large range. Ignoring the cost of the precomputations, an individual integer can be factored in time \(e^{1.639+ \sigma(1) (\log N)^{1/3} (\log\log N)^{2/3}}\). This substantial decrease in the time for factoring integers could have implications for the choice of prime parameters in cryptography.

MSC:
11Y05 Factorization
11Y16 Number-theoretic algorithms; complexity
94A60 Cryptography
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] L. M. Adleman, Factoring numbers using singular integers, Proc. 23rd Annual ACM Symposium on the Theory of Computing, 1991, pp. 64-71.
[2] J. P. Buhler, H. W. Lenstra, Jr., and C. Pomerance, Factoring Integers with the Number Field Sieve, Springer-Verlag, Berlin, Lecture Notes in Mathematics, to appear. · Zbl 0806.11067
[3] Canfield, E. R.; Erdös, P.; Pomerance, C., On a problem of Oppenheim concerning “Factorisatio Numerorum”, J. Number Theory, 17, 1-28 (1983) · Zbl 0513.10043
[4] Coppersmith, D., Solving Linear Equations over GF(2) II: Block Wiedemann Algorithm (171991), Yorktown Heights, NY: IBM T. J. Watson Research Center, Yorktown Heights, NY
[5] de Bruijn, N. G., On the number of positive integers ≤x and free of prime factors >y, II, Nederl. Akad. Wetersch. Indag. Math., 38, 239-247 (1966) · Zbl 0139.27203
[6] Lenstra, H. W. Jr., Factoring integers with elliptic curves, Ann. of Math., 126, 649-673 (1987) · Zbl 0629.10006
[7] A. K. Lenstra, H. W. Lenstra, Jr., M. S. Manasse, and J. M. Pollard, The number field sieve, Proc 22nd Annual ACM Symposium on the Theory of Computing, 1990, pp. 564-572.
[8] Pomerance, C.; Johnson, D. S.; Nishizeki, T.; Nozaki, A.; Wilf, H. S., Fast, rigorous factorization and discrete logarithm algorithms, Discrete Algorithms and Complexity, 119-143 (1987), Orlando, FL: Academic Press, Orlando, FL
[9] Schnorr, C. P., Refined analysis and improvements on some factoring algorithms, J. Algorithms, 3, 101-127 (1982) · Zbl 0485.10004
[10] Wiedemann, D. H., Solving sparse linear equations over finite fields, IEEE Trans. Inform. Theory, 32, 54-62 (1986) · Zbl 0607.65015
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.