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.''