How is D.Knuth MMIX instruction MXOR useful for finite field multiplication?

Question

Knuths TAOCP, Fascicle 1, exercise 37 (page 26) - http://mmix.cs.hm.edu/doc/fasc1.pdf:

Explain how to use MXOR for arithmetic in a field of 256 elements; each element of the field should be represented by a suitable octabyte.

I'm not more wiser from exercise answer on page 96. :-(

I have for example 2 elements in $GF(2^8)$: 0xCA and 0x53, irreducible polynomial 0x11B: $x^8+x^4+x^3+x+1$. How EXACTLY these two bytes can be multiplied by MXOR and correct result (0x01 - they are inverse of each other) can be achieved?

Answer 1

One-sentence summary: the idea is to think of GF(256) as an 8-dimensional vector space over GF(2), and to represent an element $t$ of GF(256) by the 8x8 matrix describing the linear transformation on this vector space "multiplication by $t$. Details follow:

With your chosen irreducible poly, we have $x^8=x^4+x^3+x+1$. Now, temporarily represent an element of the field by an 8-element column vector whose entries are the coeffs of $1,x,\dots,x^7$. (This is not the representation Knuth is looking for. It's part of the explanation.) Multiplication by $x$ corresponds to multiplying this vector on the left by some matrix; call it $A$. This will send $1$ to $x$, ..., $x^6$ to $x^7$ ... and $x^7$ to $1+x+x^3+x^4$. So $A$ has to be

$$\left(\matrix{0&0&0&0&0&0&0&1 \\ 1&0&0&0&0&0&0&1 \\ 0&1&0&0&0&0&0&0 \\ 0&0&1&0&0&0&0&1 \\ 0&0&0&1&0&0&0&1 \\ 0&0&0&0&1&0&0&0 \\ 0&0&0&0&0&1&0&0 \\ 0&0&0&0&0&0&1&0}\right)$$

which looking at Knuth's answer is not quite the same convention as he's using (he's thinking of row rather than column vectors) but it doesn't matter.

OK. Now, the representation of any element of the field is going to be what we get by replacing $x$ with $A$ everywhere. (And then turning the resulting matrix into an "octabyte" in standard MMIX fashion.) So, e.g., if I'm understanding you correctly then 0xCA means $x+x^3+x^6+x^7$ which means we need $A+A^3+A^6+A^7$, and 0x53 means $1+x+x^4+x^6$ which means we need $1+A+A^4+A^6$ where of course $1$ here means the identity matrix.

These work out to be

$$\left(\matrix{0&1&1&0&0&0&0&0 \\ 1&1&0&1&0&0&0&0 \\ 0&1&1&0&1&0&0&0 \\ 1&1&0&1&0&1&0&0 \\ 0&0&0&0&1&0&1&0 \\ 0&0&0&0&0&1&0&1 \\ 1&0&0&0&0&0&1&0 \\ 1&1&0&0&0&0&0&1}\right) \hbox{and} \left(\matrix{1&0&1&0&1&0&1&0 \\ 1&1&1&1&1&1&1&1 \\ 0&1&1&1&1&1&1&1 \\ 0&0&0&1&0&1&0&1 \\ 1&0&1&0&0&0&0&0 \\ 0&1&0&1&0&0&0&0 \\ 1&0&1&0&1&0&0&0 \\ 0&1&0&1&0&1&0&0}\right)$$

if I haven't mistranscribed them; and you can check that their product mod 2 (i.e., the result of MXOR) is the identity matrix, as it should be. (I have done so, so if it doesn't work out then I probably did mistranscribe.)

In some sense this is a very inefficient way to represent elements of GF(256) -- we are using 64 bits when 8 bits really should suffice. But it plays well with the capabilities of MMIX: the field operations are just ordinary addition and MXOR.