Faster truncated integer multiplication

Harvey, David

doi:10.1090/mcom/3939

Faster truncated integer multiplication
HTML articles powered by AMS MathViewer

by David Harvey;

Math. Comp. 93 (2024), 1265-1296

DOI: https://doi.org/10.1090/mcom/3939

Published electronically: February 2, 2024

HTML | PDF

Abstract:

We present new algorithms for computing the low $n$ bits or the high $n$ bits of the product of two $n$-bit integers. We show that these problems may be solved in asymptotically $75%$ of the time required to compute the full $2n$-bit product, assuming that the underlying integer multiplication algorithm relies on computing cyclic convolutions of sequences of real numbers.

References

Paul Barrett, Implementing the Rivest Shamir and Adleman public key encryption algorithm on a standard digital signal processor, Advances in cryptology—CRYPTO ’86 (Santa Barbara, Calif., 1986) Lecture Notes in Comput. Sci., vol. 263, Springer, Berlin, 1987, pp. 311–323. MR 907099, DOI 10.1007/3-540-47721-7_{2}4
D. Bernstein, Removing redundancy in high-precision Newton iteration, unpublished, available at http://cr.yp.to/papers.html\#fastnewton, 2004.
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
Peter Bürgisser, Michael Clausen, and M. Amin Shokrollahi, Algebraic complexity theory, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 315, Springer-Verlag, Berlin, 1997. With the collaboration of Thomas Lickteig. MR 1440179, DOI 10.1007/978-3-662-03338-8
M. Frigo, A Fast Fourier Transform Compiler, Proceedings of the ACM SIGPLAN 1999 Conference on Programming Language Design and Implementation (New York, NY, USA), PLDI ’99, ACM, 1999, pp. 169–180.
Ira M. Gessel, Lagrange inversion, J. Combin. Theory Ser. A 144 (2016), 212–249. MR 3534068, DOI 10.1016/j.jcta.2016.06.018
T. Granlund, The GNU Multiple Precision Arithmetic Library (Version 6.2.1), http://gmplib.org/.
D. Harvey and J. van der Hoeven, Faster integer and polynomial multiplication using cyclotomic coefficient rings, https://arxiv.org/abs/1712.03693, 2017.
David Harvey and Joris van der Hoeven, Faster integer multiplication using short lattice vectors, Proceedings of the Thirteenth Algorithmic Number Theory Symposium, Open Book Ser., vol. 2, Math. Sci. Publ., Berkeley, CA, 2019, pp. 293–310. MR 3952018
David Harvey and Joris van der Hoeven, Integer multiplication in time $O(n \log n)$, Ann. of Math. (2) 193 (2021), no. 2, 563–617. MR 4224716, DOI 10.4007/annals.2021.193.2.4
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
Peter L. Montgomery, Modular multiplication without trial division, Math. Comp. 44 (1985), no. 170, 519–521. MR 777282, DOI 10.1090/S0025-5718-1985-0777282-X
Thom Mulders, On short multiplications and divisions, Appl. Algebra Engrg. Comm. Comput. 11 (2000), no. 1, 69–88. MR 1817699, DOI 10.1007/s002000000037
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
UNSW Sydney PVC (Research Infrastructure), Katana high-performance computing cluster, DOI 10.26190/669X-A286, 2010.
Richard P. Stanley, Enumerative combinatorics. Vol. 2, Cambridge Studies in Advanced Mathematics, vol. 62, Cambridge University Press, Cambridge, 1999. With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin. MR 1676282, DOI 10.1017/CBO9780511609589
Joris van der Hoeven, The truncated Fourier transform and applications, ISSAC 2004, ACM, New York, 2004, pp. 290–296. MR 2126956, DOI 10.1145/1005285.1005327

AMS Website Down

Mathematics of Computation

Faster truncated integer multiplication
HTML articles powered by AMS MathViewer

Abstract: