D. J. Bernstein

Integer factorization

Math 436, Number Theory II, Spring 2000
Integer factorization at Arizona Winter School 2006

[nfsi] 24pp. D. J. Bernstein, A. K. Lenstra. A general number field sieve implementation. Pages 103-126 in LNM 1554: The development of the number field sieve, edited by A. K. Lenstra and H. W. Lenstra, Jr., Springer, 1993.

Relevant talks: 1995.10.03, survey of topics related to number-field sieve. 2002.01.28, ``Is a 2048-bit factorization worth $200,000?'' 2004.06.14 (transcript and slides available), ``Factorization myths.'' 2004.07.29 (slides available), ``Factorization myths.'' 2004.11.15 (slides available), ``Three algorithms related to the number-field sieve.'' 2005.02.25 (slides available), ``Building circuits for integer factorization.''

The elliptic-curve method

The papers "ECM using Edwards curves" and "ECM on graphics cards" are now hosted at http://eecm.cr.yp.to/index.html#eecm-paper and http://eecm.cr.yp.to/index.html#gpuecm-paper respectively.

The list of good curves for ECM is now hosted at http://eecm.cr.yp.to/goodcurves.html.

Factorization hardware

Circuits for integer factorization

[nfscircuit] 11pp. (PDF) (PS) (DVI) D. J. Bernstein. Circuits for integer factorization: a proposal. URL: http://cr.yp.to/papers.html#nfscircuit. Typo: the second-to-last display omits alpha on both sides.

Relevant talks: 2001.03.23, ``The NSA sieving circuit.'' 2001.05.07 (slides available), ``The NSA sieving circuit.'' 2001.05.14 (slides available), ``An introduction to Schimmler sorting.'' 2002.08.20 (slides available), ``The cost of integer factorization.''

The distribution of smooth numbers

Psibound: compute bounds on smooth numbers

[psi] 18pp in print; 15pp here. (PDF) (PS) (DVI) D. J. Bernstein. Arbitrarily tight bounds on the distribution of smooth integers. Pages 49-66 in Number Theory for the Millennium I, edited by Bennett, Berndt, Boston, Diamond, Hildebrand, and Philipp, A. K. Peters, 2002. URL: http://cr.yp.to/papers.html#psi. Supersedes: [psi-abs] (PDF) (PS) (DVI) D. J. Bernstein. Bounding smooth integers (extended abstract). Pages 128-130 in LNCS 1423: Proceedings of the Algorithmic Number Theory Symposium III, edited by Joe Buhler, Springer, 1998. Also supersedes: (PDF) (PS) (DVI) D. J. Bernstein. Enumerating and counting smooth integers. Chapter 2, Ph.D. thesis, University of California at Berkeley, May 1995.

Relevant talks: 1992.12, computing Dickman's rho function. 1998.06.21, ``Bounding smooth integers.'' 1999.02.23, ``Fast, arbitrarily precise computation of Psi.'' 2000.05.22, ``Arbitrarily precise bounds on smooth integers.'' 2000.10.06, ``Arbitrarily precise bounds on smooth integers.''

Recognizing and factoring smooth numbers

smallfactors: find all small prime divisors

[smoothparts] 7pp, draft. (PDF) (PS) (DVI) D. J. Bernstein. How to find smooth parts of integers. Document ID: 201a045d5bb24f43f0bd0d97fcf5355a. URL: http://cr.yp.to/papers.html#smoothparts. Date: 2004.05.10.

[sf] 15pp. (PDF) (PS) (DVI) (2000 PDF) (2000 PS) (2000 DVI) D. J. Bernstein. How to find small factors of integers. Accepted to Mathematics of Computation; now being revamped. URL: http://cr.yp.to/papers.html#sf.

Relevant talks: 2000.06.10, ``Sieving in cache.'' 2000.07.27 (slides available), ``Rethinking the number field sieve.'' 2003.03.26, ``Rethinking the number-field sieve: an update.'' 2004.05.14 (transcript and slides available), ``How to find smooth parts of integers.'' 2004.07.07 (slides available), ``How to find smooth parts of integers.''

Combining smooth numbers; linear algebra

[gge] D. J. Bernstein. Generalized Gaussian elimination. Supersedes: (PDF) (PS) (DVI) D. J. Bernstein. Matrix inversion made difficult.

[smoothdep] D. J. Bernstein. Estimating the dependence time for smooth integers.

Relevant talks: 1995.10.17, generalized Gaussian elimination. 1998.09.12, ``Estimating the speed of the quadratic sieve (preliminary report).'' 1998.10.29, ``Ten topics in computational number theory.''

The distribution of polynomial values; choosing number fields

[senfs] D. J. Bernstein. Superelliptic integrals and the number-field sieve.

[nfspoly] D. J. Bernstein. Controlling three coefficients in number-field-sieve polynomials.

[mlnfs] 5pp. (PDF) (PS) (DVI) D. J. Bernstein. The multiple-lattice number field sieve. Chapter 3, Ph.D. thesis, University of California at Berkeley, May 1995.

Relevant talks: 1994.05.02, ``Practical aspects of the number field sieve.''