Parallel Algorithm for Multiplying Integer Polynomials and Integers

摘要

This chapter aims to develop and analyze an effective parallel algorithm for multiplying integer polynomials and integers. Multiplying integer polynomials is of fundamental importance when generating parameters for public key cryptosystems, whereas their effective implementation translates directly into the speed of such algorithms in practical applications. The algorithm has been designed specifically to accelerate the process of generating modular polynomials, but due to its good numerical properties it may surely be used to multiply integers. The basic idea behind this new method was to adapt it to parallel computing. Nowadays, it is a very important property, as it allows us to fully exploit the computing power offered by modern processors. The combination of the Chinese Remainder Theorem and the Fast Fourier Transform made it possible to develop a highly effective multiplication method. Under certain conditions our integer polynomial multiplication method is asymptotically faster than the algorithm based on Fast Fourier Transform when applied to multiply both: polynomials and their coefficients. Undoubtedly, this result is the major theoretical conclusion of this chapter.