In the preceeding section it was shown how redundant representations can lead to very fast addition and multiplication of integers. Unfortunately, parison cannot be performed as fast as addition and, consequently, the com-parison operation needed in the modular addition method is limiting the efficiency of modular addition. Further, while integer doubling is obtained by a simple shift operation, the comparison operation makes modular dou-bling about just as hard as modular addition. In the preceeding section it was also discussed how the quotient estimation technique can improve the ef-ficiency of modular reduction. However, the result from a modular reduction based on a quotient estimate, see p. 73, may differ from the correct result by a multiple of the modulus. In the following it will be discussed how these results can be viewed as other valid representations of the result obtained from a correct computation.
3.3. RESIDUE REPRESENTATION AND ARITHMETIC 75 Consider a modular reduction of z, i.e. the computation of z mod m. If the quotient estimation technique is applied the result of the computation may not be z mod m but, certainly, it will belong to the set
[z] ={x:x=z mod m+k·m, k∈Z}={x: x=z+k·m, k ∈Z}. (3.7) An element x ∈ [z] is called a residue of z modulo m and [z] is called the residue class of z modulo m. If two elements, sayxandy, both are residues of z module m then x is congruent to y modulo m, which is written by the notationx≡y(modm), or byx≡m y. Now, the aim in a modular reduction of z is to compute the smallest positive residue, denoted z mod m, in [z].
The result of a quotient estimation technique is not necessarilyzmodmbut, indeed, it is a residue ofz modulom. Such a residue can be viewed as another representation of z mod m. By allowing more than a single representation of z mod m a kind of redundant residue representation is obtained. The redundancy of this representation must not be mixed up with the redundancy of the integer representation in Section 3.2.2. Indeed, these two types of redundancies are independent of each other. The advantage of the redundant integer representation is a fast addition operation while the advantage of the redundant residue representation is a fast quotient determination.
The following well known arithmetic rules, e.g. [Knu68, p. 39] or [Den82, p. 37], show that modular addition, subtraction and multiplication can be re-placed by the corresponding ordinary integer operations without the residue class of the result is being changed. Since modular exponentiation is com-puted by modular multiplication this observation applies to modular expo-nentiation as well.
x+y ≡m (x+y) mod m
x−y ≡m (x−y) mod m (3.8)
x·y ≡m (x·y) mod m
So, if it is allowed to represent an intermediate result, say z modm, by other residues in the same residue class [z] then the basic modular operations may be simplified. As example consider modular multiplication. This operation is computed by a number of modular additions. If redundancy is allowed in the representation of all intermediate results the quotient estimation technique can be used for obtaining a faster computation. It is only the final result
that has to be converted into the (non-redundant) residue in the intervalZm. Further, observe that if the modular multiplication is part of a computation of a modular exponential it is not necessary to perform this conversion on the intermediate modular products.
According to Equation (3.8) there is really no need to complicate the intermediate computations with modular reductions and, hence, quotient determinations. This is only required in the final conversion. In fact, an addition or subtraction of a multiple of m is just a change of representation in the same residue class,
z+q·m≡m z modm, where q∈Z.
However, since the cardinality of a residue class is infinite it is necessary to limit the number of allowable representations in order to limit the hard-ware consumption for registers and processing elements. Of course, if the number of intermediate operations is finite and the input is finite a com-putation will lead to a finite output. But for some modular operations the operand length may be significant if all intermediate modular operations are performed by the corresponding integer operation. An extreme example is modular exponentiation be mod m as used in the RSA crypto system where the input operands are, at least, 512 bits integers. Without any modular re-duction of the intermediate results these might achieve lengths up to 512·2512 bits! (This is a tremendous huge number. The reader is encouraged to esti-mate the number of atoms in the complete universe and make conclusions of his/her own). A less extreme example is modular multiplication (a·b) mod m. If a and b are n bit numbers then the product a·b may consume up to 2n bits. There are, indeed, several proposals for computing (a·b) mod m by an ordinary integer multiplication followed by a modular reduction, e.g.
[NS81, MA85, KH88, Eve90, Sau92]. In particular the early designs of de-dicated hardware for modular exponentiation uses this strategy for modular multiplication, e.g. [Riv80, ST83, VVDJ90]. Compared to a computation method based on the simple modular addition method, described in Section 3.1, these methods require an addition unit and registers that must be able to handle operands of double the length. Hence, an increased circuit size must be expected for dedicated hardware implementations of these modular multiplication methods. Furthermore, as will be shown in Section 3.5, the computing time for performing a modular reductionz modmby a SRT divi-sion method is about equal to the computing time for performing a modular
3.4. LEFT-TO-RIGHT MODULAR MULTIPLICATION METHOD 77