Ask Your Question
1

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

asked 2023-01-23 19:48:21 +0100

Mairon gravatar image

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 flag offensive close merge delete

2 Answers

Sort by ยป oldest newest most voted
1

answered 2023-01-24 12:43:43 +0100

rburing gravatar image

updated 2023-01-24 14:19:14 +0100

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
edit flag offensive delete link more
0

answered 2023-01-23 22:23:36 +0100

vdelecroix gravatar image

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
edit flag offensive delete link more

Comments

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?

Mairon gravatar imageMairon ( 2023-01-23 23:24:15 +0100 )edit

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'
achrzesz gravatar imageachrzesz ( 2023-01-24 12:09:15 +0100 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2023-01-23 19:48:21 +0100

Seen: 81 times

Last updated: Jan 24