Faster integer multiplication using plain vanilla FFT primes

Harvey, David; van der Hoeven, Joris

doi:10.1090/mcom/3328

Faster integer multiplication using plain vanilla FFT primes
HTML articles powered by AMS MathViewer

by David Harvey and Joris van der Hoeven HTML | PDF

Math. Comp. 88 (2019), 501-514

Abstract:

Assuming a conjectural upper bound for the least prime in an arithmetic progression, we show that $n$-bit integers may be multiplied in $O(n \log n 4^{\log ^* n})$ bit operations.

References

Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, PRIMES is in P, Ann. of Math. (2) 160 (2004), no. 2, 781–793. MR 2123939, DOI 10.4007/annals.2004.160.781
L. I. Bluestein, A linear filtering approach to the computation of discrete Fourier transform, IEEE Transactions on Audio and Electroacoustics 18 (1970), no. 4, 451–455.
David G. Cantor and Erich Kaltofen, On fast multiplication of polynomials over arbitrary algebras, Acta Inform. 28 (1991), no. 7, 693–701. MR 1129288, DOI 10.1007/BF01178683
Mei-Chu Chang, Short character sums for composite moduli, J. Anal. Math. 123 (2014), 1–33. MR 3233573, DOI 10.1007/s11854-014-0012-y
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
S. Covanov and E. Thomé, Fast integer multiplication using generalized Fermat primes, to appear in Math. Comp. DOI: https://doi.org/10.1090/mcom/3367.
Richard Crandall and Barry Fagin, Discrete weighted transforms and large-integer arithmetic, Math. Comp. 62 (1994), no. 205, 305–324. MR 1185244, DOI 10.1090/S0025-5718-1994-1185244-1
Martin Fürer, Faster integer multiplication, STOC’07—Proceedings of the 39th Annual ACM Symposium on Theory of Computing, ACM, New York, 2007, pp. 57–66. MR 2402428, DOI 10.1145/1250790.1250800
Martin Fürer, Faster integer multiplication, SIAM J. Comput. 39 (2009), no. 3, 979–1005. MR 2538847, DOI 10.1137/070711761
Torbjörn Granlund and the GMP development team, GNU Multiple Precision Arithmetic Library, version 6.1.2, available at http://gmplib.org/, 2017.
Andrew Granville and Carl Pomerance, On the least prime in certain arithmetic progressions, J. London Math. Soc. (2) 41 (1990), no. 2, 193–200. MR 1067261, DOI 10.1112/jlms/s2-41.2.193
David Harvey, Faster arithmetic for number-theoretic transforms, J. Symbolic Comput. 60 (2014), 113–119. MR 3131382, DOI 10.1016/j.jsc.2013.09.002
D. Harvey, Faster truncated integer multiplication, https://arxiv.org/abs/1703.00640, 2017.
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
D. Harvey, J. van der Hoeven, and G. Lecerf, Fast polynomial multiplication over $\mathbb {F}_{2^{60}}$, Proc. ISSAC ’16 (New York, NY, USA), ACM, 2016, pp. 255–262.
D. Harvey, J. van der Hoeven, and G. Lecerf, Faster polynomial multiplication over finite fields, J. ACM 63 (2017), no. 6, Article 52.
D. R. Heath-Brown, Almost-primes in arithmetic progressions and short intervals, Math. Proc. Cambridge Philos. Soc. 83 (1978), no. 3, 357–375. MR 491558, DOI 10.1017/S0305004100054657
D. R. Heath-Brown, Siegel zeros and the least prime in an arithmetic progression, Quart. J. Math. Oxford Ser. (2) 41 (1990), no. 164, 405–418. MR 1081103, DOI 10.1093/qmath/41.4.405
D. R. Heath-Brown, Zero-free regions for Dirichlet $L$-functions, and the least prime in an arithmetic progression, Proc. London Math. Soc. (3) 64 (1992), no. 2, 265–338. MR 1143227, DOI 10.1112/plms/s3-64.2.265
J. van der Hoeven, R. Larrieu, and G. Lecerf, Implementing fast carryless multiplication, Tech. report, HAL, 2017, http://hal.archives-ouvertes.fr/hal-01579863.
Junxian Li, Kyle Pratt, and George Shakan, A lower bound for the least prime in an arithmetic progression, Q. J. Math. 68 (2017), no. 3, 729–758. MR 3698292, DOI 10.1093/qmath/hax001
Christos H. Papadimitriou, Computational complexity, Addison-Wesley Publishing Company, Reading, MA, 1994. MR 1251285
J. M. Pollard, The fast Fourier transform in a finite field, Math. Comp. 25 (1971), 365–374. MR 301966, DOI 10.1090/S0025-5718-1971-0301966-0
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
V. Shoup, NTL: a library for doing number theory (Version 9.9.1), http://www.shoup.net/ntl/.
Igor Shparlinski, On finding primitive roots in finite fields, Theoret. Comput. Sci. 157 (1996), no. 2, 273–275. MR 1389773, DOI 10.1016/0304-3975(95)00164-6
GIMPS team, Mersenne Prime Number discovery - $2^{74207281}-1$ is Prime, http://www.mersenne.org/primes/?press=M74207281, 2016.
Joachim von zur Gathen and Jürgen Gerhard, Modern computer algebra, 3rd ed., Cambridge University Press, Cambridge, 2013. MR 3087522, DOI 10.1017/CBO9781139856065
Samuel S. Wagstaff Jr., Greatest of the least primes in arithmetic progressions having a given modulus, Math. Comp. 33 (1979), no. 147, 1073–1080. MR 528061, DOI 10.1090/S0025-5718-1979-0528061-7
Triantafyllos Xylouris, On the least prime in an arithmetic progression and estimates for the zeros of Dirichlet $L$-functions, Acta Arith. 150 (2011), no. 1, 65–91. MR 2825574, DOI 10.4064/aa150-1-4