Representation of Intermediate Operands

Figure 3.6: Hardware architecture for computation of Ri = (2^kRi+1+aib)− 2^kqi+1m.

3.6 Representation of Intermediate Operands

In the light of the discussions on integer representations in Section 3.2 and on residue representations in Section 3.3 a general scheme for methods of com-putations of modular operations can be made. The scheme described below is based on the very general, and simple, observation that if the benefits of converting a computation into another “domain” are greater than the costs imposed by the conversion into and back from this domain then a more effi-cient computation is achieved. Furthermore, the scheme is directed toward recursive or iterative computation methods where a modular operation is computed by repeated application of an intermediate operation. Indeed, all the methods for computation of modular operations considered in this thesis have this property: Modular exponentiation is computed by repeated appli-cation of modular multipliappli-cation, and modular multipliappli-cation is computed by repeated application of an intermediate operation, e.g. 2^kRi+1+aib−2^kqi+1m.

Stimulus: All inputs that may be a result from a previous application of the present modular operation are imposed by a restriction on the residue range and on the integer representation. Denote this restriction byD. Response: The result from the present modular operation must fulfil re-striction D. This ensures that the present modular operation may be invoked repeatedly without any concerns about the validity of the residue range or integer representation of the intermediate results.

Method: The present modular operation is computed by means of repeated application of an intermediate modular operation. First, if the interme-diate operation has a restriction on the input values that differs from D, sayE a conversion of the input values from D into E must be per-formed. Then the intermediate operation can be applied repeatedly until the computation is completed. Finally, a conversion of the result fromE back toD is done.

As example, consider the evaluation of modular exponentials b^e mod m in the RSA crypto system. In this application D denotes non-redundant bi-nary represented integers in the range Zm. The intermediate operation in exponentiation is a multiplication operation with the restrictionE. An often used restriction on the multiplier, the multiplicand and, hence, the resulting product is that these must be non-redundant binary represented integers in the residue range [0; 2m[. Since D is included in E no conversion is needed before the intermediate modular multiplication operations are applied. A conversion of the final result from E into D is, however, required. This can be accomplished by a single non-redundant subtraction ofm.

Until now, the only restriction on the quotient digitqiis that it must be an integer. However, if the allowable range of residues is bounded an enhanced restriction on the quotient determination is imposed. Suppose the range of residues is bounded to the symmetric range [−αm;αm]³. Then the quotient determination in (3.11) and in (3.12) may be described by the operation,

{ Determine integerqi such that |Ri−qim| ≤αm }. (3.13) Obviously, the residue range must include at leastm integers, soα≥ ¹₂. The parameter α, in some sense, specifies the redundancy of the residue range.

If α = ¹₂ the residue range is non-redundant and the quotient estimation technique cannot be applied. For increasing values of α the computational efforts required to perform the quotient determination in (3.13) are expected to be decreasing. However, the complexity of the quotient determination also

3The notation and analysis in this chapter is inspired by Kornerup’s description in [Kor93b]. Kornerup considerssymmetricranges because he uses a redundant signed digit integer representation with digit set{σ, . . . , σ}to encode the multiplier digitsai and the quotient digitsqi. There are several descriptions of modular multiplication methods that use non-negative residue ranges and non-negative digit sets. The article in Appendix A is one example. In [Wal91a] Walter presents an analysis of a high-radix modular multiplica-tion method with non-negative residue ranges and non-negative digit sets.

3.6. REPRESENTATION OF INTERMEDIATE OPERANDS 85 depends on the range of Ri. If this range is large compared to [−αm;αm]

the quotient digit set, i.e. the set of quotient digit values that may be the result of (3.13), will be comparatively large. Therefore, the complexity of the quotient determination is expected to increase for increasing cardinality of the quotient digit set, too. Also the complexity of the computation of multiples qim is increasing for increasing cardinality of the quotient digit set. In the following, the range [−δαm;δαm] will denote the range of Ri, and q^max will denote the maximal required absolute value of a quotient digit in (3.13), i.e. |qi| ≤ q^max. With these range restrictions imposed on the intermediate operation 2^kSi+1+aib−qim the computation can be described as,

Algorithm 3.6—1 (Intermediate operation 2^kSi+1+aib−qim) Stimulus: Si+1, ai and b, where |Si+1| ≤αmand |aib| ≤(δ−2^k)αm.

Response: Si, where |Si| ≤αm.

Method: Ri := 2^kSi+1+aib;

{ Determine integer qi such that |Ri −qim| ≤αmand |qi| ≤q^max } Si :=Ri−qim;

Note that no restrictions on the integer representation of Si and Si+1 are stated in this description. However, in order to obtain fast addition and subtraction a redundant representation is usually applied. The range restric-tion on aib ensures that |Ri| ≤ δαm. Obviously, δ ≥ 2^k. In the same way, and with the same comments, the computation of the intermediate operation 2^kRi+1+aib−2^kqi+1m can be described by,

Algorithm 3.6—2 (Intermediate operation 2^kRi+1+aib−2^kqi+1m) Stimulus: Ri+1, ai and b, where|Ri+1| ≤δαm and |aib| ≤(δ−2^k)αm.

Response: Ri, where|Ri| ≤δαm.

Method: Ti := 2^kRi+1+aib;

{ Determine integer qi+1 such that |Ri+1 −qi+1m| ≤αm and |qi+1| ≤ q^max }

Ri :=Ti−2^kqi+1m;

The computing time for these intermediate operations depends on the time for performing addition and subtraction. As seen from the range restrictions the operand lengths can be expected to be longer than modulus m. Hence, in applications with moduli of several hundreds of bits, as in the RSA crypto system,the only reasonable choice of addition techique is redundant addition when aiming for fast modular multiplication. This implies that the operands S, R and T in the above descriptions are redundant represented. The times for computing multiples and for determining quotient digits also have influ-ence on the total computing time for the above intermediate operations. The next section will discuss methods for computation of multiples. Hereafter, the interdependencies ofα,δ and q^max will be made clear and techniques for estimation of quotient digits will be discussed.