# Model of polynomial over $GF(2^n)$ as polynomials over $GF(2)$

Let's say $F = GF(2^n)$ and $P(x) = x^e, P : F \rightarrow F$. Is there a way, not necessarily optimal, to write each bit of the output of $P$ as a function of input bits?

edit retag close merge delete

Sort by » oldest newest most voted Here is a way:

sage: p = 2
sage: n = 4
sage: F.<a> = GF(p^n)
sage: R = PolynomialRing(F, n, names='c')
sage: c = R.gens()
sage: f = sum(c[i]*a^i for i in range(n)); f
c0 + a*c1 + (a^2)*c2 + (a^3)*c3
sage: I = R.ideal([g^p - g for g in c])
sage: P = sum(vector(b)*m.reduce(I) for b,m in f^3); P
(c0*c2 + c1*c2 + c1*c3 + c0, c0*c1 + c0*c2 + c2*c3 + c3, c0*c1 + c0*c2 + c1*c2 + c0*c3 + c1*c3 + c2*c3 + c2, c1*c3 + c2*c3 + c1 + c2 + c3)


Confirmation:

sage: for z in F:
....:     print([P[k](z.list()) for k in range(n)] == (z^3).list())
True
True
True
True
True
True
True
True
True
True
True
True
True
True
True
True

more

That is one (non-optimal) way

sage: k = GF(2^4)
sage: R.<x> = k[]
sage: p = x^3
sage: for a in k:
....:     print("".join(map(str,a)), "->", "".join(map(str,p(a))))
0000 -> 0000
0100 -> 0001
0010 -> 0011
0001 -> 0101
1100 -> 1111
0110 -> 1000
0011 -> 0001
1101 -> 0011
1010 -> 0101
0101 -> 1111
1110 -> 1000
0111 -> 0001
1111 -> 0011
1011 -> 0101
1001 -> 1111
1000 -> 1000

more

1

How can I then write output bits as functions of input bits? like y_0 = f(x_0, x_1, x_2, x_3)? Does sage have some function to do it for me?

A small variation:

k = GF(2^4)
R.<x> = k[]
p = x^3
F={}
for a in k:
F["".join(map(str,a))]="".join(map(str,p(a)))

def f(a,i): return F[a][i]
f('1001',3)
'1'