How to transform a univariate polynomial over $\mathbb{F}_{2^n}$ into a multivariate Boolean polynomial over $\mathbb{F}_2^n$

edit

ASSUMING a transformation along the lines of :

(a^7 + a^5 + a^3 + a^2 + 1)*x^2*y --> (x7+x5+x3+x2+1)^2*(y7+y5+y3+y2+1)

we may define the target ring as

R1=PolynomialRing(GF(2), ["x%d"%u for u in range(8)] +\
                  ["y%d"%u for u in range(8)])
R1.inject_variables`()`

We remark that the coefficients of any monomial of an element of R is either 0 or 1, and thus can be ignored.

We need to translate each element of F into a polynomial of R in x and in y according to the assumed meaning :

from sage.symbolic.operators import mul_vararg as mv
Dx={t:sum(map(mv, R1.gens()[:8],list(t))) for t in F}
Dy={t:sum(map(mv, R1.gens()[8:],list(t))) for t in F}
Dall=dict(zip(R.gens(), (Dx, Dy)))

The transcription function is then trivial using the properties of polynomials representation in Sage :

def trans(p):
    return sum([product([Dall[v][u[0]]^(u[1].degree(v))
                         for v in R.gens()])
                for u in list(p)])

A couple checks :

sage: trans(f)
x0 + y0 + 1
sage: foo=R.random_element(degree=2) ; foo
(a^7 + a^4 + a + 1)*x^2 + (a^7 + a^6 + a^4 + a^3 + a^2 + 1)*x*y + (a^6 + a^5 + a^4 + a^3 + a)*y^2 + (a^7 + a^6 + a + 1)*x + (a^6 + a^5 + a^3 + a + 1)
sage: trans(foo)
x0^2 + x1^2 + x4^2 + x7^2 + x0*y0 + x2*y0 + x3*y0 + x4*y0 + x6*y0 + x7*y0 + y1^2 + x0*y2 + x2*y2 + x3*y2 + x4*y2 + x6*y2 + x7*y2 + x0*y3 + x2*y3 + x3*y3 + x4*y3 + x6*y3 + x7*y3 + y3^2 + x0*y4 + x2*y4 + x3*y4 + x4*y4 + x6*y4 + x7*y4 + y4^2 + y5^2 + x0*y6 + x2*y6 + x3*y6 + x4*y6 + x6*y6 + x7*y6 + y6^2 + x0*y7 + x2*y7 + x3*y7 + x4*y7 + x6*y7 + x7*y7 + x0 + x1 + x6 + x7 + 1

HTH,