*Modulo adders*

We need to find *(A+B)* mod *m _{i}* where

*m*is the modulus and

_{i}*b*bits are used to represent

_{i}*m*i.e.

_{i}*b*= ⌈

_{i}*log*⌉. Normally, we need to find

_{2}m_{i}*C*= (A+B) first and then subtract

_{1}*m*from

_{i}*C*to get

_{1}*C*=

_{2}*(A+B-m*. Then the answer

_{i})*Z*is

*C*or

_{1}*C*depending on the sign of

_{2}*C*. Thus the computation time is that two

_{2}*b*-bit additions. The hardware requirement is two

_{i}*b*-bit adders and one Multiplexer (see Figure 2 (a)). Note, however, you can simplify hardware in case of special

_{i}*m*which we have considered above. In case of modulus 2

_{i}*, we need one adder but we can ignore the carry. As an example for modulus 16, A = 10, B = 13 gives C*

^{n}_{1}= 23 = 10111

_{2}= 0111 ignoring carry since (23) mod 16 = 7. Note that (subscript 2 indicates binary number). In case of modulus (2

^{n}-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 2

^{n}mod (2

^{n}-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

*C*and

_{3}= A-B*C*and select

_{4}= A-B+m_{i}*C*or

_{3}*C*based on the fact whether

_{4}*C*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 (2

_{3}^{n}+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.

*Modulo Multipliers*

We can use conventional multiplier (see Figure 3(a) first to find *(A×B)* and then find residue mod *m _{i}*. Multiplication mod 2

^{n}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 (2

^{n}-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 (2^{n}+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 (2^{n}+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 (2^{n}-1) and (2^{n}+1) [5]. We demonstrate this method in the case of mod (2^{n}-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 (2^{n}-1) multiplication, we write the bits beyond the MSB positions in LSB positions. This is because of the fact that (*a*×2^{n}) mod (2^{n}-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 2^{n} mod (2^{n}-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) D_{FA} for carry save adders and 2*n* D_{FA} for the final Carry propagate adder (CPA) where D_{FA} is a full-adder delay.

In the case of mod (2^{n}+1) multiplication, which is involved slightly, we use another property (*a*×2^{n}) mod (2^{n}-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 (2^{n}+1) reduction.

**Figure 2 (a) A modulo m_{i} adder (b) modulo (2^{n}-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**