| 摘要 |
PROBLEM TO BE SOLVED: To improve the calculation efficiency of Montgomery multiplication while suppressing the increase of computational complexity when calculating a Montgomery conversion parameter.SOLUTION: An arithmetic circuit for executing Montgomery multiplication with divisor data expressed by n bits as a modulus includes: a selection unit which divides second data into g blocks by k bits and selects the k-bit blocks sequentially from the least significant bit side of the second data; and an arithmetic unit which executes, for each block, arithmetic processing of Montgomery multiplication in which at least one piece of input data is divided into fixed-size blocks and is processed, and in arithmetic processing for the g-th block, executes bit operation based on the number h of bits of the last group on the most significant bit side out of the groups into which the divisor data is divided by k bits sequentially from the least significant bit side, so that the result of arithmetic processing for the g-th block is equal to the result of Montgomery multiplication without division of the input data. |
