We need to find (A+B) mod mi where mi is the modulus and bi bits are used to represent mi i.e. bi = ⌈log2mi⌉. Normally, we need to find C1 = (A+B) first and then subtract mi from C1 to get C2 = (A+B-mi). Then the answer Z is C1 or C2 depending on the sign of C2. Thus the computation time is that two bi-bit additions. The hardware requirement is two bi-bit adders and one Multiplexer (see Figure 2 (a)). Note, however, you can simplify hardware in case of special mi which we have considered above. In case of modulus 2n, we need one adder but we can ignore the carry. As an example for modulus 16, A = 10, B = 13 gives C1 = 23 = 101112= 0111 ignoring carry since (23) mod 16 = 7. Note that (subscript 2 indicates binary number). In case of modulus (2n-1) also, the second adder can be removed and instead we feedback the carry of adder 1 to carry input once again and add. Note that we have used the fact that 2n mod (2n-1) = 1. This adder shown in Figure 2(b) is called end-around-carry adder. The addition time is same as before since only after carry of first addition is available, another addition can be performed. Subtraction is similar to addition with the difference that we compute C3 = A-B and C4 = A-B+mi and select C3 or C4 based on the fact whether C3 is negative. (We need to add two’s complement of B to A i.e. invert the bits of B and add 1). In the case of modulus (2n+1), we can use the architecture of Figure 2(a) and we need a (n+1) bit adder 1 and (n+2) -bit adder 2.
We can use conventional multiplier (see Figure 3(a) first to find (A×B) and then find residue mod mi. Multiplication mod 2n is simple since we need to take only n LSBs of the product. As an illustration, consider finding (5×13) mod 16 = 1 since the product 65 = (0100 0001)2 and we ignore the four MSBs. Multiplication mod (2n-1) can be done in several ways. One method finds (A.B) first and then we add MSBs with LSB using an end-around-carry (EAC) adder. For the same example above, we have
5×13 mod 15 = 65 mod 15 = (0100 0001)2 mod 15 = (1+4) mod 15 = 5.
We can use the EAC adder of Figure 2(b) on the product (A.B). The multiplication time is sum of normal multiplication time followed by modulo 15 reduction time.
In the case of modulus (2n+1), we need to subtract MSBs of the product (A.B) from LSBs of the product and if the result is negative we need to add (2n+1). As an illustration, consider (5×13) mod 17 = (0100 0001) mod 17 = (1-4) mod 17 = 14.
Note however, that there are other elegant methods for modulo multiplication where we make use of the properties of the moduli (2n-1) and (2n+1) . We demonstrate this method in the case of mod (2n-1) multiplication. We use the well-known shift and add method of multiplication with a difference. The partial products in conventional shift and add extend beyond n bits for a n×n multiplication. In case of mod (2n-1) multiplication, we write the bits beyond the MSB positions in LSB positions. This is because of the fact that (a×2n) mod (2n-1) = a. Thus we get a square array of words which we add using a chain of Carry Save Adders (CSA) with end around carry followed by a Carry Propagate Adder (CPA). We are reducing the carry bit C of weight 2n mod (2n-1) as LSB of value C. The method can be understood by looking at the Figure 3(b) for an example (11×13) mod 15. Evidently, there will be n number of n-bit words for adding which we need (n-2) levels and finally, the carry and sum vectors are added using an adder of type Figure 2(b). (see Figure 3(c)). The multiplication time is thus (n-2) DFA for carry save adders and 2n DFA for the final Carry propagate adder (CPA) where DFA is a full-adder delay.
In the case of mod (2n+1) multiplication, which is involved slightly, we use another property (a×2n) mod (2n-1) = –a. Thus the MSBs of the partial products need to be subtracted from n LSBs. We realize this by adding one’s complementing (inverting all the bits) of the MSB word and adding a correction term. This can be understood as follows. If we want to subtract the 3 bit MSB word of value 5 = (101)2 , we write it as one’s complement i.e. 010 which means that we have added 7 since -5 is implemented as 7-5. We need hence to subtract 5 at the end. This operation applies to all the MSB words. The total quantity we have added is 13. Hence if we add 4, we would have added 17 where mod 17 is zero. We again present an example (11×13) mod 17 in Figure 3(d). This needs one final correction term to be added thus needing one more level in the carry save adder chain and final mod (2n+1) reduction.
Figure 2 (a) A modulo mi adder (b) modulo (2n-1) adder
Figure 3 (a) Normal multiplier (b) rewritten to perform mod 15 multiplication (c) Actual realization using Carry save adders and final EAC adder (d) mod 17 multiplier