A modulo m.sub.i adder and a modulo m.sub.i,j scaling unit for use with an RNS. The adder includes a modulo m.sub.i barrel shifter, and a dynamic storage unit coupled to the barrel shifter to store the output of the barrel shifter. In a preferred embodiment, the dynamic storage unit includes one dynamic latch for each output line of the barrel shifter, with each of the dynamic latches including a clocked inverter in cascade with an inverter. One modulo m.sub.i,j scaling unit includes a modified modulo m.sub.i barrel shifter that performs both residue conversion and an arithmetic operation. The residue conversion is performed without using combinational logic. In one preferred embodiment, the modified barrel shifter performs the residue conversion though m.sub.i m.sub.j additional columns that replicate normal columns for all modulo m.sub.i input lines that are congruent modulo m.sub.j. Another modulo m.sub.i,j scaling unit includes a barrel shifter-based arithmetic circuit, and a dynamic storage unit coupled to the arithmetic circuit to store the output of the arithmetic circuit.