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

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

Mairon
23 ●1 ●5

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

add a comment

2 Answers

Sort by » oldest newest most voted

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

rburing

10644 ●4 ●77 ●211 https://www.rburing.nl/

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

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

Comments

Is the reverse direction also possible? like taking n polynomials over $\mathbb{F}_p$ and write them as polynomials over $\mathbb{F}_{p^m}$?

Mairon ( 2023-02-02 14:22:00 +0200 )edit

@Mairon Good question, please submit it as a separate question (and add a link to this one).

rburing ( 2023-02-02 14:34:16 +0200 )edit

https://ask.sagemath.org/question/661...

Mairon ( 2023-02-02 14:42:51 +0200 )edit

Is it possible to convert this object to a polynomial over GF(2)?

Mairon ( 2023-07-11 11:50:47 +0200 )edit

add a comment

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

vdelecroix
7397 ●19 ●81 ●164 http://www.labri.fr/pe...

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

Comments

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 ( 2023-01-23 23:24:15 +0200 )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 ( 2023-01-24 12:09:15 +0200 )edit

add a comment

Your Answer

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

Add Answer

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

2 Answers

Comments

Comments

Your Answer

Question Tools

Stats

Related questions

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

2 Answers

Comments

Comments

Your Answer

Question Tools

Stats

Related questions

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