Finite field and its element with symbols [Sage / Python / ...]

Question

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

Answer 1

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)