- Change of bases
The change of bases is the process of converting elements in one basis to another when both describe the same elements of the
finite field GF("p""m").A basis for GF("p""m") has "m" elements. A "m" × "m" square matrix can be created by writing the elements of one basis in terms of the other. This matrix can then be used to convert any individual element of the finite field in the alternate basis.
Example
Let α ∈ GF(23) be a root of the
primitive polynomial "x"3 + "x"2 + 1. Thepolynomial basis for the elements of GF(23) is:1, alpha, alpha^2 }
and the
normal basis for the elements of GF(23) is:alpha, alpha^2, alpha^4 }
To convert from one basis to the other we write
:egin{bmatrix}alpha^4 \alpha^2 \alphaend{bmatrix} = egin{bmatrix}1 & 1 & 1 \1 & 0 & 0 \0 & 1 & 0end{bmatrix}egin{bmatrix}alpha^2 \alpha \1end{bmatrix}
Note that since α is a root of "x"3 + "x"2 + 1 then that means α3 + α2 + 1 = 0, or if we recall that since all coefficients are in GF(2), subtraction is the same as addition, we obtain α3 = α2 + 1. Thus, α4 = α3α = (α2 + 1)α = α3 + α = α2 + α + 1, and the top row of the square matrix is correct.
Now, any element in the polynomial basis can be written as an element in the normal basis. To convert from the normal basis to the polynomial basis we would need to create a new matrix.
Wikimedia Foundation. 2010.