Fast convolutions meet Montgomery
Preda Mihăilescu · Mathematics of Computation · 2007
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 M ( R ) 2 \mathsf {M}(\mathbf {R}) operations (where M ( R ) \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 M ( R ) 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 M ( R ) 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.