A modular multiplication algorithm with triangle additions
Naofumi Takagi · 2002
An algorithm for multiple-precision modular multiplication is proposed. In the algorithm, the upper half triangle of the whole partial products is first added up, and then the residue of the sum is calculated. Next, the sum of the lower half triangle of the whole partial products is added to the residue, and then the residue of the total amount is calculated. An efficient procedure for residue calculation that accelerates the algorithm is also proposed. Since it is both fast and uses a small amount of main memory, the algorithm is efficient for implementation on small computers, such as card computers, and is useful for application of a public-key cryptosystem to such computers.>