Polynomial multiplication apparatus, polynomial multiplication method, polynomial multiplication program, polynomial multiplication source code generation apparatus, polynomial multiplication source code generation method, and polynomial multiplication source code generation program

A polynomial multiplication source code generation apparatus comprising:

• an input part that takes as inputs a file containing the source code of a modular arithmetic function, the cycle ratio of the cycle count per one execution of the modular arithmetic function to the cycle count per one execution of multiplication, and a square matrix order;
• a number theoretic transform layer determination part that computes an optimal number of number theoretic transform layers from the cycle ratio and the order;
• an output constant generation part that generates a twiddle factor, a modulo, and a normalization factor for the optimal number of layers of number theoretic transforms and inverse number theoretic transforms to output a list thereof;
• a polynomial multiplication source file generation part that generates a file in which a function computing the product of a square matrix and a vector of the order is implemented in the same program as that of the source file;
• and
• a file output part that outputs the file and the list.

A polynomial multiplication source code generation method including:

• taking as inputs a file containing the source code of a modular arithmetic function, the cycle ratio of the cycle count per one execution of the modular arithmetic function to the cycle count per one execution of multiplication, and a square matrix order;
• computing an optimal number of number theoretic transform layers from the cycle ratio and the order;
• generating a twiddle factor, a modulo, and a normalization factor for the optimal number of layers of number theoretic transforms and inverse number theoretic transforms to output a list thereof;
• generating a file in which a function computing the product of a square matrix and a vector of the order is implemented in the same program as that of the source file;
• and
• outputting the file and the list.