Fast integer multiplication using generalized Fermat primes
HTML articles powered by AMS MathViewer
- by Svyatoslav Covanov and Emmanuel Thomé;
- Math. Comp. 88 (2019), 1449-1477
- DOI: https://doi.org/10.1090/mcom/3367
- Published electronically: July 23, 2018
- HTML | PDF | Request permission
Abstract:
For almost 35 years, Schönhage-Strassen’s algorithm has been the fastest algorithm known for multiplying integers, with a time complexity $O(n \cdot \log n \cdot \log \log n)$ for multiplying $n$-bit inputs. In 2007, Fürer proved that there exists $K>1$ and an algorithm performing this operation in $O(n \cdot \log n \cdot K^{\log ^* n})$. Recent work by Harvey, van der Hoeven, and Lecerf showed that this complexity estimate can be improved in order to get $K=8$, and conjecturally $K=4$. Using an alternative algorithm, which relies on arithmetic modulo generalized Fermat primes (of the form $r^{2^{\lambda }}+1$), we obtain conjecturally the same result $K=4$ via a careful complexity analysis in the deterministic multitape Turing model.References
- D. J. Bernstein, Multidigit multiplication for mathematicians, 2001, http://cr.yp.to/papers.html#m3.
- Alin Bostan, Pierrick Gaudry, and Éric Schost, Linear recurrences with polynomial coefficients and application to integer factorization and Cartier-Manin operator, SIAM J. Comput. 36 (2007), no. 6, 1777–1806. MR 2299425, DOI 10.1137/S0097539704443793
- Paul T. Bateman and Roger A. Horn, A heuristic asymptotic formula concerning the distribution of prime numbers, Math. Comp. 16 (1962), 363–367. MR 148632, DOI 10.1090/S0025-5718-1962-0148632-7
- L. I. Bluestein, A linear filtering approach to the computation of discrete Fourier transform, IEEE Trans. Audio and Electroacoustics 18 (1970), no. 4, 451–455.
- Richard P. Brent and Paul Zimmermann, Modern computer arithmetic, Cambridge Monographs on Applied and Computational Mathematics, vol. 18, Cambridge University Press, Cambridge, 2011. MR 2760886
- James W. Cooley and John W. Tukey, An algorithm for the machine calculation of complex Fourier series, Math. Comp. 19 (1965), 297–301. MR 178586, DOI 10.1090/S0025-5718-1965-0178586-1
- Harvey Dubner and Yves Gallot, Distribution of generalized Fermat prime numbers, Math. Comp. 71 (2002), no. 238, 825–832. MR 1885631, DOI 10.1090/S0025-5718-01-01350-3
- Anindya De, Piyush Kurur, Chandan Saha, and Ramprasad Saptharishi, Fast integer multiplication using modular arithmetic, STOC’08, ACM, New York, 2008, pp. 499–505. MR 2582908, DOI 10.1145/1374376.1374447
- P. D. T. A. Elliott, Primes in progressions to moduli with a large power factor, Ramanujan J. 13 (2007), no. 1-3, 241–251. MR 2281164, DOI 10.1007/s11139-006-0250-4
- M. Fürer, On the complexity of integer multiplication (extended abstract), Tech. Report CS-89-17, Pennsylvania State University, 1989.
- Martin Fürer, Faster integer multiplication, SIAM J. Comput. 39 (2009), no. 3, 979–1005. MR 2538847, DOI 10.1137/070711761
- Pierrick Gaudry, Alexander Kruppa, and Paul Zimmermann, A GMP-based implementation of Schönhage-Strassen’s large integer multiplication algorithm, ISSAC 2007, ACM, New York, 2007, pp. 167–174. MR 2396199, DOI 10.1145/1277548.1277572
- Torbjörn Granlund and the GMP development team, GNU MP: The GNU Multiple Precision Arithmetic Library, 2016, version 6.1.0, http://gmplib.org/.
- David Harvey, Faster polynomial multiplication via multipoint Kronecker substitution, J. Symbolic Comput. 44 (2009), no. 10, 1502–1510. MR 2543433, DOI 10.1016/j.jsc.2009.05.004
- Joris van der Hoeven, Faster relaxed multiplication, ISSAC 2014—Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2014, pp. 405–412. MR 3239953, DOI 10.1145/2608628.2608657
- David Harvey, Joris van der Hoeven, and Grégoire Lecerf, Even faster integer multiplication, J. Complexity 36 (2016), 1–30. MR 3530637, DOI 10.1016/j.jco.2016.03.001
- A. A. Karatsuba and Y. Ofman, Multiplication of multidigit numbers on automata, Soviet Physics-Doklady 7 (1963), 595–596, (English translation).
- Christos H. Papadimitriou, Computational complexity, Addison-Wesley Publishing Company, Reading, MA, 1994. MR 1251285
- Carl Pomerance, On the distribution of amicable numbers, J. Reine Angew. Math. 293(294) (1977), 217–222. MR 447087, DOI 10.1515/crll.1977.293-294.217
- Arnold Schönhage, Asymptotically fast algorithms for the numerical multiplication and division of polynomials with complex coefficients, Computer algebra (Marseille, 1982) Lecture Notes in Comput. Sci., vol. 144, Springer, Berlin-New York, 1982, pp. 3–15. MR 680048
- A. Schönhage and V. Strassen, Schnelle Multiplikation grosser Zahlen, Computing (Arch. Elektron. Rechnen) 7 (1971), 281–292 (German, with English summary). MR 292344, DOI 10.1007/bf02242355
- A. L. Toom, The complexity of a scheme of functional elements simulating the multiplication of integers, Dokl. Akad. Nauk SSSR 150 (1963), 496–498 (Russian). MR 156494
- Joachim von zur Gathen and Jürgen Gerhard, Modern computer algebra, Cambridge University Press, New York, 1999. MR 1689167
Bibliographic Information
- Svyatoslav Covanov
- Affiliation: Université de Lorraine, CNRS, INRIA, LORIA, F-54000 Nancy, France
- MR Author ID: 1105937
- Email: svyatoslav.covanov@loria.fr
- Emmanuel Thomé
- Affiliation: Université de Lorraine, CNRS, INRIA, LORIA, F-54000 Nancy, France
- Email: emmanuel.thome@inria.fr
- Received by editor(s): January 27, 2016
- Received by editor(s) in revised form: July 10, 2017, January 25, 2018, and March 7, 2018
- Published electronically: July 23, 2018
- © Copyright 2018 American Mathematical Society
- Journal: Math. Comp. 88 (2019), 1449-1477
- MSC (2010): Primary 68W30; Secondary 11A41
- DOI: https://doi.org/10.1090/mcom/3367
- MathSciNet review: 3904152