Finite field and its element with symbols [Sage / Python / ...] I have a finite field $T=GF(2^3)$, normal basis $(a, a^2, a^4)$ and polynomial $f$ from field $T$, which contains unknown variables / symbols.
Is it possible to get vector with coordinates of f in normal basis?
Example in Sage:
T.<x> = GF(2^3)
V = T.vector_space()
alpha = x^2+1
normalBasis = [ alpha^(2^i) for i in range(T.degree()) ]

W = [ b._vector_() for b in normalB ] 
normalBasisVector = V.span_of_basis(W)

def linearCombination(coords, basis):
    return sum( [ coords[i] * basis[i] for i in range(len(basis)) ] )

a,b,c = var('a','b','c')
gB = [a,b,c] # vector g in normal basis
g = linearCombination(gB, normalB)

normalBasisVector.coordinates(g) # I'd like to get back g in normal basis (that is (a,b,c))
-> TypeError: can't initialize vector from nonzero non-list

If this is impossible in Sage, is it possible in any other Mathematic / Programming Language e.g. in Python?
I hope I presented my problem clearly. If you didn't get anything, feel free to ask me.
Thanks, 
Denholm
 A: Finite fields don't mix well with Sage's symbolic ring, the place where
Sage's symbolic variables, like a, b, c in the question, live.
The trick is to do the linear algebra over GF(2) and to go back
and forth between matrices over GF(2) and matrices over ZZ when
we need to involve symbolic variables.
Setting (as in the question).
sage: T.<x> = GF(2^3)
sage: T
Finite Field in x of size 2^3
sage: V = T.vector_space()
sage: V
Vector space of dimension 3 over Finite Field of size 2
sage: alpha = x^2 + 1
sage: alpha
x^2 + 1
sage: normal_basis = [alpha^(2^i) for i in range(T.degree())]
sage: normal_basis
[x^2 + 1, x^2 + x + 1, x + 1]

With V as above, field elements transform into vectors as follows.
sage: W = [V(b) for b in normal_basis]
sage: W
[(1, 0, 1), (1, 1, 1), (1, 1, 0)]

We can then form the corresponding matrix
sage: M = matrix(W)
sage: M
[1 0 1]
[1 1 1]
[1 1 0]

and compute its inverse
sage: ~M
[1 1 1]
[1 1 0]
[0 1 1]

Define our symbolic variables.
sage: vars = SR.var('a b c')

In order to work with symbolic variables, switch
to matrices over ZZ.
sage: Mz = matrix(ZZ, M)
sage: Mz
[1 0 1]
[1 1 1]
[1 1 0]

Multiply on the correct side.
sage: vector(vars) * Mz
(a + b + c, b + c, a + b)

This expresses that $a(x^2 + 1) + b(x^2 + x + 1) + c(x + 1)$
equals $(a + b + c)1 + (b + c)x + (a + b)x^2$.
Conversely, one would like to know how to express
$a*x^2 + b*x + c$ in the normal basis.
Just invert the matrix.
sage: iMz = matrix(ZZ, ~M)
sage: vector(vars) * iMz
(a + b, a + b + c, a + c)

This expresses that, in the finite field $T$,
$a + bx + cx^2$ (watch the order) can also be written as
$(a + b)(x^2 + 1) + (a + b + c)(x^2 + x + 1) + (a + c)(x + 1)$.
Summary:


*

*the matrix M and its inverse allow to switch
from the basis $(1, x, x^2)$ to the basis 
$(x^2 + 1, x^2 + x + 1, x + 1)$ and back;

*to work with symbolic variables, some gymnastics
is required, changing from GF(2) to ZZ, but
the inverse is computed on the GF(2) side.
Regarding what side to multiply matrices and vectors:
we defined M = matrix(W), so we used the vectors in
W as rows of M. We could instead have defined
M = column_matrix(W) and then multiplied matrices
and vectors on the other side.

Note: with actual numbers and no symbolic variables,
no need to switch to the ZZ side.
Three examples to illustrate this, with notations close to those in the question:
sage: def linear_combination(coords, basis):
....:     return sum(c*b for c, b in zip(coords, basis))
....:

sage: gb = (1, 1, 1)
sage: g = linear_combination(gb, normal_basis)
sage: g
1
sage: normal_basis_vector.coordinates(g)
[1, 1, 1]

sage: gb = (1, 0, 1)
sage: g = linear_combination(gb, normal_basis)
sage: g
x^2 + x
sage: normal_basis_vector.coordinates(g)
[1, 0, 1]

sage: gb = (1, 1, 0)
sage: g = linear_combination(gb, normal_basis)
sage: g
x
sage: normal_basis_vector.coordinates(g)
[1, 1, 0]

The same three examples, using matrices instead
of linear_combination and .coordinates:
sage: gb = V((1, 1, 1))
sage: g = gb * M
sage: g
(1, 0, 0)
sage: gt = T(g)
sage: gt
1
sage: V(gt)
(1, 0, 0)
sage: V(gt) * ~M
(1, 1, 1)

sage: gb = V((1, 0, 1))
sage: g = gb * M
sage: g
(0, 1, 1)
sage: gt = T(g)
sage: gt
x^2 + x
sage: V(gt)
(0, 1, 1)
sage: V(gt) * ~M
(1, 0, 1)

sage: gb = V((1, 1, 0))
sage: g = gb * M
sage: g
(0, 1, 0)
sage: gt = T(g)
sage: gt
x
sage: V(gt)
(0, 1, 0)
sage: V(gt) * ~M
(1, 1, 0)

