Fast arithmetic

General

[multapps] 60pp. (PDF) D. J. Bernstein. Fast multiplication and its applications. Document ID: 8758803e61822d485d54251b27b1a20d. URL: https://cr.yp.to/papers.html#multapps. Date: 2008.05.15. Supersedes: (PDF) 2008.05.03. (PDF) (PS) (DVI) 2004.10.07. (PDF) (PS) (DVI) 2003.01.19. Also supersedes: (PDF) (PS) (DVI) Kronecker matrices and polynomial GCDs.

The transposition principle

floatasm: write fast floating-point software

Relevant talks: 1998.02.13, ``Computing everything in essentially linear time.'' 2000.08.14 (slides and video available), ``Fast multiplication.'' 2000.08.15 (slides and video available), ``Applications of fast multiplication.''

FFT and product

Multiplication of polynomials over F_2

djbfft: compute power-of-2 complex DFTs

Zmult: compute integer products

Integer multiplication benchmarks

[tangentfft] 10pp. (PDF) D. J. Bernstein. The tangent FFT. Document ID: a9a77cef9a7b77f9b8b305e276d5fe25. URL: https://cr.yp.to/papers.html#tangentfft. Date: 2007.09.19. Supersedes: (PDF) 2007.08.09.

[m3] 19pp. (retypeset PDF) (type-3 PDF) (PS) (DVI) D. J. Bernstein. Multidigit multiplication for mathematicians. URL: https://cr.yp.to/papers.html#m3. Date: 2001.08.11.

[c3] D. J. Bernstein. The complexity of complex convolution.

[zmult] D. J. Bernstein. Faster multiplication of integers.

Relevant talks: 2000.04.08, ``Faster multiplication of integers.''

Quotient, square root, exp, log, pi, composition

Removing redundancy from high-precision Newton iteration

[logagm] 8pp, draft. (retypeset PDF) (type-3 PDF) (PS) (DVI) D. J. Bernstein. Computing logarithm intervals with the arithmetic-geometric-mean iteration. Document ID: 8f92b1e3ec7918d37b28b9efcee5e97f. URL: https://cr.yp.to/papers.html#logagm. Date: 2003.07.17.

[westinghouse] 21pp. (scanned version) D. J. Bernstein. New fast algorithms for pi and e. Paper for the Westinghouse competition, distributed widely at the Ramanujan Centenary Conference (1987). URL: https://cr.yp.to/papers.html#westinghouse.

[compose] 3pp. (retypeset PDF) (type-3 PDF) (PS) (DVI) D. J. Bernstein. Composing power series over a finite ring in essentially linear time. Journal of Symbolic Computation 26 (1998), 339–341. URL: https://cr.yp.to/papers.html#compose. Date: 1997.10.07. AP version: (PDF)

Relevant talks: 1987.06.01, ``New fast algorithms for pi and e.'' 1997.05.30, ``Composing power series over a finite ring in essentially linear time.''

Remainder tree, greatest common divisor, coprime base

[scaledmod] 8pp, draft. (PDF) (PS) (DVI) D. J. Bernstein. Scaled remainder trees. Document ID: e2b8da026cf72d01d97e20cf2874f278. URL: https://cr.yp.to/papers.html#scaledmod. Date: 2004.08.20.

Factoring into coprimes

Other arithmetic operations

[powers] 30pp. (retypeset PDF) (type-3 PDF) (PS) (DVI) D. J. Bernstein. Detecting perfect powers in essentially linear time. Mathematics of Computation 67 (1998), 1253–1283. URL: https://cr.yp.to/papers.html#powers. Date: 1997.11.06. AMS version: 31pp. (PDF) 1998.07. Version from Chapter 1, Ph.D. thesis, University of California at Berkeley, May 1995 (not superseded; e.g., includes proofs of all lemmas): 40pp. (PDF) 1995.05.18.

[powers2] 4pp. (PDF, AMS version) (PDF) (PS) (DVI) D. J. Bernstein, Hendrik W. Lenstra, Jr., and Jonathan Pila. Detecting perfect powers by factoring into coprimes. Mathematics of Computation 76 (2007), 385–388. Document ID: bbd41ce71e527d3c06295aadccf60979. URL: https://cr.yp.to/papers.html#powers2. Date: 2005.05.09. Supersedes: (PDF) (PS) (DVI) 2004.06.30. (PDF) (PS) (DVI) 2004.11.13.

[logfloor] 4pp, draft. (retypeset PDF) (type-3 PDF) (PS) (DVI) D. J. Bernstein. Computing logarithm floors in essentially linear time. Document ID: 97bbdc1ce6aff974c789eab21b9cfba1. URL: https://cr.yp.to/papers.html#logfloor. Date: 2003.06.30.

[kdvseries] 4pp. (PDF) D. J. Bernstein. Using fast power-series arithmetic in the Kedlaya-Denef-Vercauteren algorithm. Document ID: 4e30a3e7f413533744a20c9c48e7025f. URL: https://cr.yp.to/papers.html#kdvseries. Date: 2006.10.19.

[fastgraeffe] D. J. Bernstein. High-precision roots of high-degree polynomials.

Relevant talks: 1994.10.12, preliminary report on detecting perfect powers. 1995.02.06, Detecting perfect powers. 1995.03.01, Detecting perfect powers. 1995.04.05, ``Detecting perfect powers.'' 2000.06.27, ``High-precision high-degree polynomial factorization (preliminary report).'' 2002.04.24 (slides available), ``Finding roots of high-degree polynomials.'' 2003.07.24, ``Translating Chudnovsky into English.''

For modular exponentiation, see my Authenticators and signatures page.