I am currently reading a paper on the Mathematics of RAID 6 by Peter Anvin and cannot get my head around the notation or results used describing multiplication by {02} (hexadecimal).
Here is how he describes Multiplication (.) by {02} (00000010):
\begin{align} (x.\{02\})_{7} & = x_{6} \\ (x.\{02\})_{6} & = x_{5} \\ (x.\{02\})_{5} & = x_{4} \\ (x.\{02\})_{4} & = x_{3} + x_{7} \\ (x.\{02\})_{3} & = x_{2} + x_{7} \\ (x.\{02\})_{2} & = x_{1} + x_{7} \\ (x.\{02\})_{1} & = x_{0} \\ (x.\{02\})_{0} & = x_{7}\\ \end{align}
He then goes on to say:
Hardware engineers will recognize this as a linear feedback shift register (LFSR), and mathematicians as boolean polynomial multiplication modulo the irreducible polynomial $x^8 + x^4 + x^3 + x^2 +1$.
Can anyone explain the notation used (the subscripts) and the results please? I am struggling with this bit of the paper.
What is $x$ and what is the subscript? I am familiar with LFSR but I ran through a few possibilities and none came out right.
The idea is the following. Consider the element (of the field $GF(256)$ that is now realized as the quotient ring $GF(2)[x]/\langle p(x)\rangle, p(x)= x^8+x^4+x^3+x^2+1$). $$ z=x_7x^7+x_6x^6+\cdots+x_1x+x_0. $$ We want to multiply it by (the coset of) $x$. Normal polynomial multiplication would give us $$ zx=x_7x^8+x_6x^7+\cdots+x_1x^2+x_0x. $$ But here we equate any two polynomials that differ by a multiple of $p(x)$. To get a unique presentation of each element we must then reduce modulo $p(x)$ and use the remainder of degree at most seven. To that end we do the following $$ \begin{aligned} zx&=zx+x_7p(x)\\ &=(x_7x^8+x_6x^7+\cdots+x_1x^2+x_0x)+x_7p(x)\\ &=(x_7x^8+x_6x^7+\cdots+x_1x^2+x_0x)+x_7(x^8+x^4+x^3+x^2+1)\\ &=(x_7+x_7)x^8+x_6x^7+x_5x^6+x_4x^5+(x_3+x_7)x^4+(x_2+x_7)x^3+(x_1+x_7)x^2+x_0x+x_7\\ &=x_6x^7+x_5x^6+x_4x^5+(x_3+x_7)x^4+(x_2+x_7)x^3+(x_1+x_7)x^2+x_0x+x_7. \end{aligned} $$ In the last step we used that $x_7+x_7=0$ irrespective of whether $x_7=0$ or $1$ (arithmetic of coefficients is done modulo two). You can read the coefficients from this. Presumably the author's $(z.{02})_k$ is just the coefficient of $x^k$ above.
Often programmers store a polynomial $r(x)$ with binary coefficients as the integer $r(2)$ (and doing usual integer arithmetic when calculating powers of two). Therefore the polynomial $x$ is internally stored as the byte 0x02 et cetera.
The remark about LFSRs means that you are to initialize an LFSR with feedback polynomial $p(x)$ with the sequence of coefficients $x_0,x_1,\ldots,x_7$, and then do a single iteration. Because the taps are positions determined by the non-zero coefficients of $p(x)$, the bit pushed out of the register (i.e. $x_7$) will be added modulo two to the positions indicated by the taps.