"Efficient VLSI Implementation of Modulo (2^ną1) Addition and Multiplication"

R. Zimmermann

Abstract
--------

New VLSI circuit architectures for addition and multiplication modulo (2^n-1)
and (2^n+1) are proposed that allow the implementation of highly efficient
combinational and pipelined circuits for modular arithmetic.  It is shown that
the parallel-prefix adder architecture is well suited to realize fast
end-around-carry adders used for modulo addition.  Existing modulo multiplier
architectures are improved for higher speed and regularity.  These allow the
use of common multiplier speed-up techniques like Wallace-tree addition and
Booth recoding, resulting in the fastest known modulo multipliers.  Finally, a
high-performance modulo multiplier-adder for the IDEA block cipher is
presented.  The resulting circuits are compared qualitatively and
quantitatively, i.e., in a standard-cell technology, with existing solutions
and ordinary integer adders and multipliers.