Methods Based on Heuristics

The strength of the m-ary method and Thurber’s modification is the upper bound on the worst case computing time and on the number of required registers. Furthermore, the methods are easy to express and therefore they are easy to implement in a computer program or into a dedicated hardware circuitry. For both methods the resource requirements in the average case are very close to the requirements in the worst case.

In the methods based on heuristics the aim is to find a good individual computation rule for each individual exponent value such that a better per-formance is obtained. For the particular exponent value in consideration, heuristics are used to find a computation rule which, hopefully, is superior to the rules obtained from other methods. Of course the rules can be compared,

such that the best one is selected for the exponentiation. The drawbacks of the heuristic methods are the complicated descriptions and, for some heuris-tics, the required computing time for finding a good rule. This implies that the heuristic methods are not well-suited for hardware implementation. They are best suited for applications where the particular exponent value is used for many consecutive exponentiations, i.e. applications with a fixed expo-nent such as the RSA crypto system, or in applications where the expoexpo-nent value has been known for long prior to the exponentiation. As a consequence, Sauerbrey and Dietel [SD92] suggest that an exponentiation rule for a partic-ular exponent be value can be precomputed by heuristic methods and then be part of the input to dedicated hardware.

The strategy of most heuristic methods follows the strategy of them-ary method and Thurber’s modification: Split the binary encoded representation of the exponenteinto windows, where the value of theith window is denoted ei. Then precompute a table that holds a powerb^ei for each window valueei. Finally, perform the exponentiation, by means of the table, in approximately log₂ e − log₂ en−1 squarings and n −1 multiplications, where n is the number of windows and en−1 is the value of the most significant window.

The way in which the exponent is split into windows is called the window distribution. As seen in Section 2.1.1 and 2.1.2 the window distribution has influence on the computing time and on the number of required registers. By choosing a large window size the number of windows becomes small and the number of multiplications for the final phase of the computation becomes small. But simultaneously the number of possible window values increases and a large number of operations may be required to precompute the table.

So the window distribution is closely related to the precomputation time, and a tradeoff between the number of operations required in the last phase of the computation and the number of operations required in the precomputation must be done.

Bos and Coster [BC89] were first to apply heuristics in exponentiation.

Bos and Coster proposed a window distribution with much bigger window sizes than in Thurber’s modification. The idea is to precompute only the powers of b that are needed and hereby avoid to precompute all possible powers. To be successful this idea demands an efficient precomputation tech-nique. In addition to some guidelines to optimise the window distribution, Bos and Coster provide heuristics to construct an efficient precomputation of the powersb^e0, b^e1, . . . , b^en−1. It is found that “in all cases we tried . . . with

2.1. FEWER MULTIPLICATIONS 35 ej ≤1000” [BC89, p. 405] the number of operations can be estimated to be less than or equal to ³₂ log₂ ej+n+ 1, whereej is the largest of thenwindow values. Even though it is an estimate this result is remarkable: The absolute minimal number of operations required to compute b^ej is log₂ ej (see Section 2.2) and all methods described so far have a worst case computing time very close to ³₂ log₂ ej for ej ≤ 1000. Hence, the overhead for computing n−1 additional powers of b is only slightly more than n−1 operations. Bos and Caster state that their method is capable of compute exponentials with 512 bit exponents in 605 operations on average. This is an improvement of 3 percents over the worst case time in Thurber’s modification.

In [SD92] Sauerbrey and Dietel examine different window distribution methods with emphasis on the relationship between the number of opera-tions and the number of required registers. The examination is based on experiments with 100 random selected 512 bit exponents. The heuristics by Bos and Coster are applied for the precomputation. None of the methods use less than 610 operations on average. It is not clear whether one of the examined window distribution methods is identical to the method of Bos and Coster. Sauerbrey and Dieted observe that window distributions leading to good results for the number of operations require a lot of registers, and vice versa. Motivated by the fact that memory is a scarce resource for a VLSI implementation, Sauerbrey and Dietel propose a new window distribution method. It shows a better compromise between operation count and register demand than previously known methods: For 512 bit exponents about 620 operations are used on average and 10-15 registers are required on average.

Compared to the worst case of Thurber’s modification in Table 2.3 this is an improvement of less than 0.5 percent (3 operations) in computing time and about 50-70 percents in register demand.

The results obtained by applying heuristics show a better average per-formance than Thurber’s modification. But, if an exponentiation method is going to be hardware implemented the adequacy of the average case analysis can be questioned: The hardware implementation must be able to cope with even the worst case input. This means that the available memory must fit the worst case register demand. Furthermore, if the exponentiation is part of a real-time application, the worst case computing time is often of greater importance than the average computing time.