SPRUJ17H March 2022 – October 2024 AM2631 , AM2631-Q1 , AM2632 , AM2632-Q1 , AM2634 , AM2634-Q1
To reduce the number of multiplications within the MMEXP function, the LNME unit can optionally use a technique called 'sliding window exponent re-coding'. This embedded functionality requires external software to prepare a table with 'odd powers' before the operation is started. The example from Table 7-107 shows an exponentiation, using exponent B = 10110101b (181 decimal), without re-coding and with re-coding using four 'odd powers'.
Exponent | Without re-coding | With re-coding (4 odd powers: X1, X3, X5, X7) |
---|---|---|
B[7] = 1 | - | - |
B[6] = 0 | Y = X2 | Y = X2 |
B[5] = 1 | Y = (Y)2 * X = X5 | Y = (Y)2 = X4 |
B[4] = 1 | Y = (Y)2 * X = X11 | Y = (Y)2 * X3 = X11 |
B[3] = 0 | Y = (Y)2 = X22 | Y = (Y)2 = X22 |
B[2] = 1 | Y = (Y)2 * X = X45 | Y = (Y)2 = X44 |
B[1] = 0 | Y = (Y)2 = X90 | Y = (Y)2 = X88 |
B[0] = 1 | Y = (Y)2 * X = X181 | Y = (Y)2 * X5 = X181 |
Without re-coding:
With re-coding: A number of 'odd powers' of the X-operand are pre-calculated and stored in a table. The first one is always X, the following ones successively multiply their predecessors by X2.
In the example above, with re-coding there are only 2 multiplications, whereas without re-coding 4 multiplications are needed. The total amount of square and multiply operations is 9 versus 11, a speed gain of approximately 22%. It can be shown that the mean speed gain for long vectors is approximately 25% when four 'odd powers' are used. The maximum number of 'odd powers' supported by the LNME unit is 32.
Setting the number of 'odd powers' to 1 performs a basic exponentiation without exponent recoding. Also note that the highest B bit is not parsed at all - it is assumed to be '1'. This is the reason that that bit need not actually be stored in the PKA RAM exponent vector and that the minimum amount of bits in the (actual) exponent equals 2.