In this paper, we propose a new modulo multiplier suitable for repeated operations using redundant representations. First, we consider a computation rule for radix-2 modulo multiplications. In radix-2 operation, we show two methods to calculate (2^i-1 mod n) from (2ⁱ mod n) and decide product digits sequentially from upper side. These methods make it possible to perform (2^i-1 mod n) and multiplications simultaneously. Second, we attempt to apply these methods to radix-4 operations which enables us to reduce clock cycles by only shift and sign change. We propose some structures to perform each part efficiently for radix-4 modulo multiplications. The high-speed redundant binary adder/subtractor which we have already proposed is applied to these structures. By using this adder/subtractor, the longest delay path of this modulo multiplier becomes very short. Finally, by using PARTHENON which is a design system for VLSI, this modulo multiplier is designed and evaluated. As a result, we show the speed of this proposed modulo multiplier becomes over 2.5 times as compared with the conventional structures.