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
Additional Information
- Preda Mihăilescu
- Affiliation: Mathematisches Institut der Universität Göttingen, Bunsenstraße 3–5, D-37073 Göttingen, Germany
- Email: preda@upb.de
- Received by editor(s): August 27, 2004
- Received by editor(s) in revised form: April 18, 2006
- Published electronically: November 15, 2007
- Additional Notes: Part of this work was developed while the author was a guest of LiX, the Laboratoire d’Informatique de l’École Polytechnique, Palaiseau, in March 2004.
- © Copyright 2007
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Math. Comp. 77 (2008), 1199-1221
- MSC (2000): Primary 11D61
- DOI: https://doi.org/10.1090/S0025-5718-07-01956-4
- MathSciNet review: 2373198