AN RNS MONTGOMERY MODULAR MULTIPLICATION ALGORITHM

We present a new RNS modular multiplication for very large operands. T he algorithm is based on Montgomery's method adapted to mixed radix, a nd is performed using a Residue Number System. By choosing the moduli of the RNS system reasonably large and implementing the system on a ri ng of fairly simple processors, an effect corresponding to a redundant high-radix implementation is achieved. The algorithm can be implement ed to run in O(n) time on O(n) processors. where n is the number of mo duli in the RNS system, and the unit of time is a simple residue opera tion, possibly by table look-up. Two different implementations are pro posed, one based on processors attached to a broadcast bus, another on an oriented ring structure.