I'm reading this Intel white paper on carry-less multiplication. It describes multiplication of polynomials in $\text{GF}(2^n)$. On a high level, this is performed in two steps: (1) multiplication of polynomials over $\text{GF}(2)$, and (2) reducing the result modulo an irreducible polynomial. We use the "standard" bitstring representation of polynomials, i.e. $x^3+x+1 = [1011]$.

The paper gives an algorithm for calculation of the remainder polynomial on page 16 in Algorithm 3. However, I'm having trouble understanding the reduction algorithm on pages 16-17 (Algorithm 4). Essentially, I think we need Algorithm 4 for larger fields when our or partial results don't fit 128 bits anymore. They give an example for multiplication of two polynomials in $\text{GF}(2^{128})$.

Where do the "magic constants" 63, 62, and 57 for right shifts, and the "magic constants" 1, 2, and 7 for left shifts come from?

For example, how does one generalize the algorithm for smaller fields, say $\text{GF}(2^{32})$? Would the corresponding shift values then be 15, 14, 9 and 1, 2, 7?

In the final step 4, the algorithm tells you to "XOR $[E_1:E_0]$, $[F_1:F_0]$, and $[G_1:G_0]$ with each other and $[X_3:D]$".

Why do we do this? As far as I can see, the result of this XOR operation is neither stored anywhere nor used anywhere. Is it somehow used for computing $[H_1 : H_0]$?

没有正确的解决方案

许可以下: CC-BY-SA归因
不隶属于 cs.stackexchange
scroll top