The selection of the elements of the bases in an RNS modular multiplication method is crucial and has a great impact in the overall performance.This work proposes specific sets of optimal RNS moduli with elements of Hamming weight three whose inverses used in the MRS reconstruction have very small Hamming weight. This property is exploited in RNS bases conversions, to completely remove and replace the products by few additions/subtractions and shifts, reducing the time complexity of modular multiplication.These bases are specially crafted to computation with operands of sizes 256 or more and are suitable for cryptographic applications such as the ECC protocols.

This paper proposes a new modular multiplication method that uses Montgomery residues defined by a modulusMand a Montgomery radixRwhose value is less than the modulusM. This condition enables the operand multiplier to be split into two parts that can be processed separately in parallel - increasing the calculation speed. The upper part of the split multiplier can be processed by calculating a product moduloMof the multiplicand and this part of the split multiplier. The lower part of the split multiplier can be processed by calculating a product moduloMof the multiplicand, this part of the split multiplier, and the inverse of a constantR. Two different implementations based on this method are proposed: One uses a classical modular multiplier and a Montgomery multiplier and the other generates partial products for each part of the split multiplier separately, which are added and accumulated in a single pipelined unit. A radix-4 version of a multiplier based on a radix-4 classical modular multiplier and a radix-4 Montgomery multiplier has been designed and simulated. The proposed method is also suitable for software implementation in a multiprocessor environment.

A mixed radix-4/2 algorithm for modular multiplication/division suitable for VLSI implementation is proposed. The algorithm is based on Montgomery method for modular multiplication and on the extended Binary GCD algorithm for modular division. Both algorithms are modified and combined into the proposed algorithm so that almost all the hardware components are shared. The new algorithm carries out both calculations using simple operations such as shifts, additions, and subtractions. The radix-2 signed-digit representation is used to avoid carry propagation in all additions and subtractions. A modular multiplier/divider based on the algorithm performs an n-bit modular multiplication/division in O(n) clock cycles where the length of the clock cycle is constant and independent of n. The modular multiplier/divider has a linear array structure with a bit-slice feature and can be implemented with much smaller hardware than that necessary to implement both multiplier and divider separately.

We propose an algorithm for modular multiplication/division suitable for VLSI implementation. The algorithm is based on Montgomery's method for modular multiplication and on the extended binary GCD algorithm for modular division. It can perform either of these operations with a reduced amount of hardware. Both calculations are carried out through iterations of simple operations such as shifts and additions/subtractions. The radix-2 signed-digit representation is employed so that all additions and subtractions are performed without carry propagation. A modular multiplier/divider based on this algorithm has a linear array structure with a bit-slice feature and carries out an n-bit modular multiplication in at most /spl lfloor/2(n+2)/3/spl rfloor/+3 clock cycles and an n-bit modular division in at most 2n+5 clock cycles, where the length of the clock cycle is constant and independent of n.