In a recent publication [l], we introduced the main outlines of a new algorithm for division in Residue Number System, which can be applied to any moduli set. Simulation results proved that the algorithm was many times faster than most competitive published work [2]. Determining the position of the most significant nonzero bit of any residue number in that algorithm is the major speed limiting factor. In this paper, we customize the same algorithm to serve two specific moduli sets: (2k, 2k - 1, 2k-l - 1) and (2k + 1,2k, 2k-l), and thus, eliminate that speed limiting factor. Based on this work, hardware needed to determine most significant bit position has been reduced to a single adder. Therefore, computation time and hardware requirements are substantially improved. This would enable RNS to be a stronger force in building general purpose computers.

The authors present a new RNS modular multiplication for very large operands. The algorithm is based on Montgomery's method adapted to mixed radix, and is performed using a residue number system. By choosing the moduli of the RNS system reasonably large, and implementing the system an a ring of fairly simple processors, an effect corresponding to a redundant high-radix implementation is achieved. The algorithm call be implemented to run in O(n) time on O(n) processors, where n is the number of moduli in the RNS system, and the unit of time is a simple residue operation, possibly by table look-up.