Change of bases

From Wikipedia, the free encyclopedia

You have new messages (last change).

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(pm).

A basis for GF(pm) 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.

[edit] Example

Let α ∈ GF(23) be a root of the primitive polynomial x3 + x2 + 1. The polynomial basis for the elements of GF(23) is

{1,α,α2}

and the normal basis for the elements of GF(23) is

{α,α2,α4}

To convert from one basis to the other we write

\begin{bmatrix} \alpha^4 \\ \alpha^2 \\ \alpha \end{bmatrix} = \begin{bmatrix} 1 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{bmatrix} \begin{bmatrix} \alpha^2 \\ \alpha \\ 1 \end{bmatrix}

Note that since α is a root of x3 + x2 + 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.

Retrieved from "http://en.wikipedia.org../../../c/h/a/Change_of_bases.html"
In other languages