| 摘要 |
A method is described for multiplying two factors from the Galois field GF (2m*p), where each of the factors can be represented as a vector of p sub-blocks with a width of m bits and p, m are positive integers greater than 1, which method includes the following steps: a) selection of a reduction polynomial comprising a leading bit other than zero and p subsequent sub-blocks of m bits each, of which the r least-significant sub-blocks of m bits each can be selected as arbitrarily not equal to the zero vector and the other sub-blocks as zero, r being a positive integer less than p, and storing the r least-significant sub-blocks of the reduction polynomial in a first register, b) multiplicative linking of a sub-block of the first factor, starting with the most-significant sub-block of the first factor, with in succession all sub-blocks of the second factor, starting with the most-significant sub-block of the second factor, c) digit-aligned accumulation of all intermediate results of the multiplicative linking of the sub-blocks of the first and second factors according to an exclusive-OR function without carry, d) where, after each multiplicative linking of a sub-block of the first factor with a sub-block of the second factor, at the latest after accumulation of intermediate results of the multiplicative links of one sub-block of the first factor with all sub-blocks of the second factor, a reduction of the possibly accumulated intermediate result, is performed to a width of m bits while using the reduction polynomial in the following steps: d1) provision of the intermediate result to be reduced, d2) provision of at least one sub-block of the reduction polynomial, d3) multiplication of the reduction polynomial with the most-significant m bits of the possibly accumulated intermediate result to be reduced, giving a polynomial to be subtracted in which the value of the most-significant bit corresponds to the value of the most-significant bit of the intermediate result to be reduced, d4) subtraction of the polynomial to be subtracted from the intermediate result to be reduced and provision of the result of this subtraction as a new intermediate result to be reduced, d5) repeated execution of the steps d1) to d4) until the intermediate result to be reduced has a width equal to m. A multiplier is also described for carrying out the method. Savings can thus be achieved in respect of power consumption, crystal surface and calculation time.
|
