General modular multiplication by block multiplication and table lookup
Cheng‐Wen Wu, Yung-Fa Chou · 2002
This paper deals with the problem of general modular multiplication, i.e., A/spl times/B mod M. To solve it in hardware, we suggest a simple lookup-table based approach and use the novel block multiplier which we have developed earlier on. The area (A) and time (T) complexities of this multiplier are both O(n log n) if carry-lookahead adders are used. Most previously proposed modular multipliers have put restriction on the ranges of the multiplicand A, the multiplier B, and the modulus M. Our modular multiplier is general, which releases the restriction on those operands.>