A SYSTOLIC, LINEAR-ARRAY MULTIPLIER FOR A CLASS OF RIGHT-SHIFT ALGORITHMS

A very simple multiplier cell is developed for use in a linear, purely systolic array forming a digit-serial multiplier for unsigned or 2' c omplement operands. Each cell produces two digit-product terms and acc umulates these into a previous sum of the same weight, developing the product least significant digit first. Grouping two terms per cell, th e ratio of active elements to latches is low, and only [n/2] cells are needed for a full n by n multiply. A modulo-multiplier is then develo ped by incorporating a Montgomery type of modulo-reduction. Two such m ultipliers interconnect to form a purely systolic modulo exponentiator , capable of performing RSA encryption at very high clock frequencies, but with a low gate count and small area. It is also shown how the mu ltiplier, with some simple back-end connections, can compute modular i nverses and perform modular division for a power of two as modulus.