More number-theoretic computations

Large primes

Distinguishing prime numbers from composite numbers

[quartic] 15pp. (PDF, AMS version) (PDF) (PS) (DVI) D. J. Bernstein. Proving primality in essentially quartic random time. Document ID: 43f1d5199196c0593c1e8442af682180. URL: https://cr.yp.to/papers.html#quartic. Date: 2004.12.03. Supersedes: (PDF) (PS) (DVI) 2003.01.28. (PDF) (PS) (DVI) 2003.03.06. (PDF) (PS) (DVI) 2003.04.17. (PDF) (PS) (DVI) 2004.02.13.

[abccong] 5pp. (PDF) D. J. Bernstein. Sharper ABC-based bounds for congruent polynomials. Journal de Theorie des Nombres de Bordeaux 17 (2005), 721–725. Document ID: 1d9e079cee20138de8e119a99044baa3. URL: https://cr.yp.to/papers.html#abccong. Date: 2005.12.24. Supersedes: (PDF) (PS) (DVI) 2003.03.14. (PDF) (PS) (DVI) 2003.10.01. (PDF) (PS) (DVI) 2004.02.10.

[aks] 15pp, draft. (retypeset PDF) (type-3 PDF) (PS) (DVI) D. J. Bernstein. Proving primality after Agrawal-Kayal-Saxena. URL: https://cr.yp.to/papers.html#aks. Date: 2003.01.25. Supersedes: "An exposition of the Agrawal-Kayal-Saxena primality-proving theorem." (PDF) 2002.08.09. (PDF) 2002.08.10. (PDF) (PS) (DVI) 2002.08.20.

Relevant talks: 2002.08.20 (slides available), ``Deterministic polynomial-time primality tests.'' 2002.10.31 (slides available), ``Proving primality.'' 2003.03.23 (slides available), ``A new proof that 83 is prime.'' 2003.03.25, ``Randomized primality proving in essentially quartic time.'' 2003.04.03 (slides available), ``Sharper ABC-based bounds for congruent polynomials.'' 2003.04.04 (slides available), ``Randomized primality proving in essentially quartic time.'' 2003.05.03, ``Sharper ABC-based bounds for congruent polynomials.'' 2003.05.10, ``Sharper ABC-based bounds for congruent polynomials.''

Small primes

primegen: generate prime numbers (in order)

[primesieves] 8pp. (retypeset PDF) (type-3 PDF) (PS) (DVI) A. O. L. Atkin, D. J. Bernstein. Prime sieves using binary quadratic forms. URL: https://cr.yp.to/papers.html#primesieves. Date: 2002.03.29. AMS version: Mathematics of Computation 73 (2004), 1023–1030. Supersedes: (PDF) (PS) (DVI) 1999 version.

Relevant talks: 1997.12.03, ``Improving on the Sieve of Eratosthenes.''

Sorted sums

sortedsums: enumerate solutions to some equations

[sortedsums] 6pp. (retypeset PDF) (type-3 PDF) (PS) (DVI) D. J. Bernstein. Enumerating solutions to p(a)+q(b)=r(c)+s(d). URL: https://cr.yp.to/papers.html#sortedsums. Date: 1999.09.28. AMS version: Mathematics of Computation 70 (2001), 389–394.

Relevant talks: 1999.07.06 (slides available), ``Counting rational points by brute force.''

Local squares

Doubly focused enumeration of locally square polynomial values

Lattice-basis reduction

[goppalist] Moved to new page on error-correcting codes.

[smallheight] 26pp. (PDF) D. J. Bernstein. Reducing lattice bases to find small-height values of univariate polynomials. Pages 421–446 in Surveys in Algorithmic Number Theory, edited by J. P. Buhler and P. Stevenhagen, to appear. Document ID: 82f82c041b7e2bdce94a5e1f94511773. URL: https://cr.yp.to/papers.html#smallheight. Date: 2008.05.02. Supersedes: (PDF) (PS) (DVI) 2003.09.18. (PDF) (PS) (DVI) 2004.02.10. (PDF) (PS) (DVI) 2005.10.09. (PDF) 2006.05.31. (PDF) 2007.07.27.

threecubes: find small sums of three cubes

Relevant talks: 2001.07.27 (slides available), ``Finding polynomial values of small height.''

Other number-theoretic computations

[nonsquare] 3pp, draft. (retypeset PDF) (type-3 PDF) (PS) (DVI) D. J. Bernstein. Faster algorithms to find non-squares modulo worst-case integers. URL: https://cr.yp.to/papers.html#nonsquare. Date: 2001.12.20.

[fiall] 8pp. (retypeset PDF) (type-3 PDF) (PS) (DVI) D. J. Bernstein. Fast ideal arithmetic via lazy localization. Pages 27–34 in LNCS 1122: Proceedings of the Algorithmic Number Theory Symposium II, edited by Henri Cohen, Springer, 1996. URL: https://cr.yp.to/papers.html#fiall.

[hblcs] D. J. Bernstein. Predicting a linear congruential sequence from its high bits.

Relevant talks: 1995.12.02, ``Fast ideal arithmetic via lazy localization.'' 1996.05.22, ``Fast ideal arithmetic via lazy localization.''