Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Fast convolutions meet Montgomery

Author: Preda Mihailescu
Journal: Math. Comp. 77 (2008), 1199-1221
MSC (2000): Primary 11D61
Published electronically: November 15, 2007
MathSciNet review: 2373198
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [Bl] R. Blahut: Fast Algorithm for Digital Signal Processing, Addison-Wesley (1985). MR 0777867 (86h:94005)
  • [Bo] A. Bostan: Algorithmique efficace pour des opérations de base en Calcul formel, Thèse de doctorat à l'École polytechnique de Paris (2003).
  • [BGS] A. Bostan, P. Gaudry and É. Schost: Linear Recurrences with Polynomial Coefficients and Computation of the Cartier-Manin Operator on Hyperelliptic Curves, in Proceedings Fq7, LNCS 2948, pp. 40-58. MR 2092621 (2006f:11070)
  • [BLS] A. Bostan, G. Lecerf and É. Schost: Tellegen's Principle into Practice, Proceedings of ISSAC'03 (2003), ACM Press, pp. 37-44.
  • [BM] A. Borodin and R.T. Moenck: Fast modular transforms, Computer System Sci. 8, Nr. 3 (1974), pp. 366-386. MR 0371144 (51:7365)
  • [BS] A. Bostan and É. Schost: Polynomial evaluation and interpolation on special sets of points, Journal of Complexity, vol. 21, no. 4, pp. 420-446, Aug. 2005. MR 2152715 (2006g:12016)
  • [CF] R. Crandall and B. Fagin: Discrete weighted transforms and large-integer arithmetic, Math. Comp. 62 (1994), pp. 305-324. MR 1185244 (94c:11123)
  • [Co] S. A. Cook: On the Minimum Computation Time of Function, Ph.D. Thesis, Harvard (1966).
  • [CT] J. Cooley and W. Tukey: An algorithm for the machine computation of complex Fourier series, Mathematics of Computation 19 (1965), pp. 297-301. MR 0178586 (31:2843)
  • [gmp] GNU Multiple Precision Library gmp, Version 4.12
  • [GG] J. von zur Gathen and J. Gerhard: Modern Computer Algebra, Cambridge University Press (2000). MR 1689167 (2000j:68205)
  • [GKP] R. Graham, D. Knuth and O. Patashnik: Concrete Mathematics: A Foundation for Computer Science, Addison-Wesley 1990 MR 1397498 (97d:68003)
  • [HZ] G. Hanrot and P. Zimmerman: A Long Note on Mulders' Short Product, Journal of Symbolic Computation, 37 (2004), pp. 391-401. MR 2092652 (2005g:65011)
  • [Kn] D. Knuth: The Art of Computer Programming, Vol II: Seminumerical Algorithms, Addison and Wesley (1998), 3rd Edition. MR 633878 (83i:68003)
  • [Ku] H. T. Kung: On computing reciprocals of power series, Numerische Mathematik 92 (1974), pp. 341-348. MR 0351045 (50:3536)
  • [Li] LiDIA: A C++ Library For Computational Number Theory,
  • [Mi] P. Mihailescu: Cyclotomy of Rings & Primality Testing, dissertation 12278, ETH Zürich, 1997.
  • [Ml] P. McLaughlin, Jr.: New Frameworks for Montgomery's Modular Multiplication Method, Math. Comp 73, Nr. 246 (2003) pp. 899-906. MR 2031414 (2004j:11149)
  • [Mo] P. Montgomery: Modular Multiplication without Trial Division, Math. Comp. 44 (1985), 519-521. MR 777282 (86e:11121)
  • [Mu] T. Mulders: On Short Multiplications and Divisions, Proceedings AAECC 11 (2000), pp. 69-88. MR 1817699 (2001m:68187)
  • [NTL] V. Shoup: NTL: A Library for doing Number Theory, Version 5.3.1,
  • [ScSt] A. Schönhage and V. Strassen: Schnelle Multiplikation großer Zahlen, Computing 7, (1971) pp. 281-292. MR 0292344 (45:1431)
  • [Sh] V. Shoup: A New Polynomial Factorization Algorithm and its Implementation, Journal of Symbolic Computation, 20 (1996) pp. 363-397. MR 1384454 (97d:12011)
  • [Si] M. Sieveking: An Algorithm for Division of Power Series, Computing 10 (1972), pp. 153-156. MR 0312701 (47:1257)
  • [St] V. Strassen: Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten, Numerische Mathematik 20 (1972/73), pp. 238-251. MR 0324947 (48:3296)
  • [To] A. L. Toom: The Complexity of a Scheme of Functional Elements Realizing the Multiplication of Integers, Soviet Mathematics Doklady 4 (1963), pp. 714-716.
  • [vH] J. van der Hoeven: The Truncated Fourier Trnsform and Applications, Proceedings ISSAC 2004 MR 2126956
  • [Wn] S. Winograd: On Computing the Discrete Fourier Transform, Math. Comp. 32 (1978), pp. 175-199. MR 0468306 (57:8142)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11D61

Retrieve articles in all journals with MSC (2000): 11D61

Additional Information

Preda Mihailescu
Affiliation: Mathematisches Institut der Universität Göttingen, Bunsenstraße 3–5, D-37073 Göttingen, Germany

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.
Article copyright: © Copyright 2007 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society