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(2³) be a root of the primitive polynomial "x"³ + "x"² + 1. The polynomial basis for the elements of GF(2³) is

:$\{\; 1,\; alpha,\; alpha^2\; \}$

and the normal basis for the elements of GF(2³) is

:$\{\; alpha,\; alpha^2,\; alpha^4\; \}$

To convert from one basis to the other we write

:

Note that since α is a root of "x"³ + "x"² + 1 then that means α³ + α² + 1 = 0, or if we recall that since all coefficients are in GF(2), subtraction is the same as addition, we obtain α³ = α² + 1. Thus, α⁴ = α³α = (α² + 1)α = α³ + α = α² + α + 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.