6
$\begingroup$

I'm reading this Intel white paper on carry-less multiplication. For now, suppose I want to do multiplication in $\text{GF}(2^4)$. We are using the "usual" bitstring representation of polynomials here.

The algorithm for multiplying two numbers is given in Algorithm 3 on page 16. I tried executing the algorithm on paper for small inputs, but I'm getting the wrong answer. Below, I believe $t = 4$ and $s = 8$.

Let $$A = x^3 + x^2 + x = [1110]$$ and $$B = x^3 + x + 1 = [1011].$$ In $\text{GF}(2^4)$, the product of $A$ and $B$ is $x^3 = [1000]$, so this is the expected result of the algorithm. We can also compute the carry-less product of $A$ and $B$, which is

$$C = [0110 0010].$$

Our irreducible polynomial is $g = x^4 + x + 1 = [10011]$.

Now let us execute the preprocessing step, and then the three short steps of the algorithm. Note that below, $*$ denotes the carry-less multiplication (which should correspond to multiplication over $\text{GF}(2)$). I use a delimiter $|$ to improve readability of the bitstrings.

Preprocessing: The polynomial $g^*$ is of degree $t-1$ and consists of the $t$ least significant terms of $g$. So we have that $g^* = [0011]$. Then, $q^+$ will be the quotient of $x^{t+s} / g$. We have that the quotient of $x^{12} / g$ is $1 + 2x + x^2 - x^4 - x^5 + x^8$. This modulo $2$ is $1 + x^2 + x^4 + x^5 + x^8$, so we have that $q^+ = [1|0011|0101]$. See computation of $q^+$ on Wolfram Alpha.

Step 1: Compute $c * q^+$, which is $[0110] * q^+ = [0000|0110|1011|1110]$. See step 1 on Wolfram Alpha.

Step 2: The $s$ most significant terms of the polynomial resulting from step 1 are multiplied with $g^*$. So we compute $[0000|0110] * [0011] = [1010]$. See step 2 on Wolfram Alpha.

Step 3: The $t$ least significant bits of the previous polynomial is the result. So the answer is $[1010] = x^3 + x$.

This is incorrect, as the expected answer should be $x^3 = [1000]$. Where is my mistake?

$\endgroup$
5
  • $\begingroup$ GF(2) is the field of two elements: $\{0,1\}$ (with $1 + 1 = 0$). Polynomials over GF(2) are things like $x^7 + x^5 + x + 1$ (the coefficients are in GF(2), so the only possible coefficients are $0$0 and $1$). Addition and multiplication of those things go exactly as you think they'd go (except that it's over GF(2), so $1 + 1 = 0$). The polynomials can be represented by sequences of $0$'s and $1$'s by listing the coefficients from highest to lowest. $\endgroup$ Mar 30 '14 at 12:09
  • $\begingroup$ So just try the example $A \cdot B$ of your question yourself: just multiply the polynomials, remembering that $1 + 1 = 0$, and see what polynomial you get. If you list the coefficients of the result from highest to lowest you should get $C$. $\endgroup$ Mar 30 '14 at 12:10
  • $\begingroup$ I frankly don't understand the definition of $q^+$. What is $x^{12} / g$? (In what ring is this division?) $\endgroup$ Mar 30 '14 at 12:22
  • $\begingroup$ @Magdiragdag According to the white paper, $q^+$ is "the quotient of the division of $x^{t+s}$ with the polynomial $g$". The way I computed this was standard division of $x^{12}$ with $g$, took the quotient, and reduced it modulo 2. $\endgroup$
    – Gideon
    Mar 30 '14 at 12:24
  • $\begingroup$ @Magdiragdag: It seems to be a variant of the Montgomery multiplication algorithm for polynomials over $GF(2)$. But I have only implemented this algorithm for integers mod $p$, so I don't know the details. $\endgroup$
    – TonyK
    Mar 30 '14 at 19:50
3
$\begingroup$

What you have described so far is correct. But notice the discussion that is presented before the algorithm is given, which says "to reduce a 256-bit carry-less product modulo a polynomial g of degree 128, we first split it into two 128-bit halves. The least significant half is simply XOR-ed with the final remainder". In other words, you still need to XOR the lower half of your input with the final remainder.

In your current case, $C = [0110|0010]$, and you essentially only process the upper half of it, that is, your $c = [0110]$. After the third step, you obtain $[1010]$, which still needs to XOR'd with the lower half of $C$. So $[1010] \oplus [0010] = [1000]$, which represents $x^3$, and you are done.

$\endgroup$
2
$\begingroup$

You are performing ordinary integer arithmetic on your binary strings. So your computation of $c * q^+ = [0110] * [100110101]$ is already wrong. The product of the integers $0110_2$ and $100110101_2$ is indeed $6_{10} \times 309_{10} = 1854_{10} = 11100111110_2$, but this is not what you want

You should instead be performing polynomial multiplication over $\mathbb F_2$, which in practice is a series of shifts and XORs: $c=[0110]$ represents the polynomial $x^2+x$, so you need to XOR $q^+$ shifted left by $1$ (for the term $x$) with $q^+$ shifted left by $2$ (for the term $x^2$). You get:

$[1001101010] \oplus [10011010100] = [11010111110]$

(This assumes that your value for $q^+$ is correct $-$ I haven't checked it.)

$\endgroup$
1
  • $\begingroup$ Thanks, you definitely pushed me into the right direction by catching my (silly) mistake of not doing multiplication of polynomial over GF(2). I had only forgotten to XOR the lower half of the input with the answer the algorithm gives. (But it's also silly that the actual description of the algorithm doesn't tell you to do it, but oh well.) $\endgroup$
    – Gideon
    Apr 1 '14 at 16:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.