Research on the applications of Register Blocking Technique and Carry Save Technique to Ohta Method

摘要

Carry save technique, which delays propagations of carries, is a classical technique for fast hardware multiplication and register blocking technique is a efficient coding technique for matrix multiply, both of which was shown by Ohta to be applicable to multiprecision multiplication. In this paper, effectiveness of carry save and register blocking techniques for Ohta Multiplication, which is a modular multiplication using multiprecision multiplications, is compared against Montgomery Multiplication with most efficient coding known so far on Intel Pentium4 (1.8GHz) processor. For 220 bits of modular multiplication coded with C, Ohta Multiplication and Montogomery one take 1.74us and 1.79us, correspondingly, that Ohta Multiplication is about 3% faster than Montgomery one. The program is expected to be applicable to computations of public key cryptography, esiecially Elliptic one.