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 Free Access

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?)

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.