Fast convolutions meet Montgomery

Mihăilescu, Preda

doi:10.1090/S0025-5718-07-01956-4

Fast convolutions meet Montgomery
HTML articles powered by AMS MathViewer

by Preda Mihăilescu PDF

Math. Comp. 77 (2008), 1199-1221 Request permission

Abstract:

Arithmetic in large ring and field extensions is an important problem of symbolic computation, and it consists essentially of the combination of one multiplication and one division in the underlying ring. Methods are known for replacing one division by two short multiplications in the underlying ring, which can be performed essentially by using convolutions. However, while using school-book multiplication, modular multiplication may be grouped into $2 \mathsf {M}(\mathbf {R})$ operations (where $\mathsf {M}(\mathbf {R})$ denotes the number of operations of one multiplication in the underlying ring), the short multiplication problem is an important obstruction to convolution. It raises the costs in that case to $3 \mathsf {M}(\mathbf {R})$. In this paper we give a method for understanding and bypassing this problem, thus reducing the costs of ring arithmetic to roughly $2\mathsf {M}(\mathbf {R})$ when also using fast convolutions. The algorithms have been implemented with results which fit well the theoretical prediction and which shall be presented in a separate paper.

References

Richard E. Blahut, Fast algorithms for digital signal processing, Addison-Wesley Publishing Company, Advanced Book Program, Reading, MA, 1985. MR 777867
A. Bostan: Algorithmique efficace pour des opérations de base en Calcul formel, Thèse de doctorat à l’École polytechnique de Paris (2003).
Alin Bostan, Pierrick Gaudry, and Éric Schost, Linear recurrences with polynomial coefficients and computation of the Cartier-Manin operator on hyperelliptic curves, Finite fields and applications, Lecture Notes in Comput. Sci., vol. 2948, Springer, Berlin, 2004, pp. 40–58. MR 2092621, DOI 10.1007/978-3-540-24633-6_{4}
A. Bostan, G. Lecerf and É. Schost: Tellegen’s Principle into Practice, Proceedings of ISSAC’03 (2003), ACM Press, pp. 37–44.
A. Borodin and R. Moenck, Fast modular transforms, J. Comput. System Sci. 8 (1974), 366–386. MR 371144, DOI 10.1016/S0022-0000(74)80029-2
Alin Bostan and Éric Schost, Polynomial evaluation and interpolation on special sets of points, J. Complexity 21 (2005), no. 4, 420–446. MR 2152715, DOI 10.1016/j.jco.2004.09.009
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
S. A. Cook: On the Minimum Computation Time of Function, Ph.D. Thesis, Harvard (1966).
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
GNU Multiple Precision Library gmp, Version 4.12 http://www.swox.com/gmp/
Joachim von zur Gathen and Jürgen Gerhard, Modern computer algebra, Cambridge University Press, New York, 1999. MR 1689167
Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, Concrete mathematics, 2nd ed., Addison-Wesley Publishing Company, Reading, MA, 1994. A foundation for computer science. MR 1397498
G. Hanrot and P. Zimmermann, A long note on Mulders’ short product, J. Symbolic Comput. 37 (2004), no. 3, 391–401. MR 2092652, DOI 10.1016/j.jsc.2003.03.001
Donald E. Knuth, The art of computer programming. Vol. 2, 2nd ed., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms. MR 633878
H. T. Kung, On computing reciprocals of power series, Numer. Math. 22 (1974), 341–348. MR 351045, DOI 10.1007/BF01436917
LiDIA: A C++ Library For Computational Number Theory, http://www.informatik.tu-darmstadt.de/TI/LiDIA
P. Mihăilescu: Cyclotomy of Rings & Primality Testing, dissertation 12278, ETH Zürich, 1997.
Philip B. McLaughlin Jr., New frameworks for Montgomery’s modular multiplication method, Math. Comp. 73 (2004), no. 246, 899–906. MR 2031414, DOI 10.1090/S0025-5718-03-01543-6
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
V. Shoup: NTL: A Library for doing Number Theory, Version 5.3.1, http://www.shoup.net/ntl/
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
Victor Shoup, A new polynomial factorization algorithm and its implementation, J. Symbolic Comput. 20 (1995), no. 4, 363–397. MR 1384454, DOI 10.1006/jsco.1995.1055
M. Sieveking, An algorithm for division of powerseries, Computing (Arch. Elektron. Rechnen) 10 (1972), 153–156 (English, with German summary). MR 312701, DOI 10.1007/bf02242389
Volker Strassen, Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten, Numer. Math. 20 (1972/73), 238–251 (German, with English summary). MR 324947, DOI 10.1007/BF01436566
A. L. Toom: The Complexity of a Scheme of Functional Elements Realizing the Multiplication of Integers, Soviet Mathematics Doklady 4 (1963), pp. 714–716.
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
S. Winograd, On computing the discrete Fourier transform, Math. Comp. 32 (1978), no. 141, 175–199. MR 468306, DOI 10.1090/S0025-5718-1978-0468306-4