摘要 |
A modular multiplication processing apparatus is provided that can process modular multiplication of data exceeding a bit length which a coprocessor can process, by using the coprocessor based upon Montgomery multiplication. In the apparatus, data to be subjected to modular multiplication is decomposed, and the decomposed data elements are respectively transformed into a form suitable for Montgomery multiplication. After respective data elements are transformed to have sizes that can be inputted into a coprocessor, Montgomery multiplication is repeatedly performed in the coprocessor. A remainder of Montgomery multiplication of an original bit length is restored from the obtained remainder.
|