Fast computation of A * B modulo N
P.W. Baker · Electronics Letters · 1987
The computation of A*BmoduloN is an important arith-metic operation in security cryptosystems. Since the word length n involved is large, speed-up techniques are important. The letter demonstrates that, for n-bit arguments, at most 2n carry-save additions are required, followed by at most two carry-propagate additions for final assimilation, using components no more than n + 3 bits wide.