Cryptography Reference
In-Depth Information
Figure 9.5. A Naive Implementation of the Hybrid Method
A new strategy for improving the hybrid method is by employing more registers to
suppress the carry propagation. As well as using 2 d column registers to hold the sum of
each now wider column, extra 2 d- 1 registers are deployed as “carry catchers.” These reg-
isters are initialized to zero at the top of the column and catch any carries that may arise,
without the possibility of further carry propagation. When the column is finished,
these carry catchers are simply added with carry to the main set of column registers.
The case for d = 2 is shown in Figure 9.6. The most significant carry-catcher register
performs exactly the same role as the fifth register in the native implementation. The
d×d row-wise multiplication requires d + 1 registers: d registers to hold the entire row,
each element of which is then multiplied by another register (which stores the cur-
rent multiplier) to create d partial products. There are 2 d column registers and 2 d- 1
carry-catchers, for a total of 5 d registers. For d = 1, this is the original Comba method,
which requires five registers, just possible if the number of general-purpose registers is
r = 8. The choice d = 2 requiring 10 registers is a good fit for a processor with a total
of r = 16 registers, and d = 4 will take 20 registers for the case r = 32. The improved
hybrid method can exploit even more registers if they are available on the target plat-
form. The above figures are approximate and may require modification for a particular
architecture. Not all of the r registers on a given type of CPU might be available to the
developer. At least three registers will be required to store the memory address of the
operands and of the result.
Search WWH ::




Custom Search