How to write monomials in $GF(2^n)$ as a system of equations in $GF(2)$

Mairon

6/28/24, 12:20 PM

Let $F = GF(2^n)$ and $P(x) = x^e, P : F \rightarrow F$ be a monomial of degree $e$. How to write each bit of the output of $P$ as a function of input bits? In other words, how to write it as a system of polynomials over $GF(2)$? One way is to use computer algebra systems such as sage and work as follow:

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)

But this is inefficient, especially when n is large (128 or more). What is the better way to do it?

1 + 2

finite-field

symmetric

pseudo-random-function

poncho

6/28/24, 12:35 PM

In $GF(2^n)$, the polynomial $x^e$ is linear in $GF(2)$ when $e$ is a power of 2; that is, it has a fairly simple representation (all terms are of degree one). One approach would be to express $e$ as a sum of powers of two (that is, in binary), express each power of two as the simple polynomial in $GF(2)$, and then multiply them together. The last step is tricky; however for nonpowers of 2, I believe the ultimate expression will be somewhat complicated anyways...

j.p.

6/29/24, 3:04 PM

May I ask, why you want to represent each output bit as function of input bits? What do you want to achieve using this representation? (If the Hamming weight of the exponent e is big, the functions will be quite complicated and the expression as ands/xors might be huge - the Hamming weight is the algebraic degree of your monomial, i.e. the maximal number of input bits in an and.)

Score:1

Crypto

yoyo

6/29/24, 2:58 PM

Generally, you can take a table of values for $P$ and convert it to algebraic normal form via the M"{o}bius transform. For $n$ as large as you're talking about, anything you do will be unwieldy unless the algebraic degree of $x^e$ (i.e. the Hamming weight of $e$) is small. The output bits of the ANF are polynomials in $n$ variables and there are $2^n$ possible monomials that can appear.

For example, here is a picture of the ANF for $x^{254}$ over $GF(2^8)$ (AES inversion), showing which monomials appear in each of the 8 output bits:

+ 3

j.p.

6/29/24, 3:05 PM

Nice picture, where did you get it from?

yoyo

6/29/24, 6:47 PM

I made it following the description in my answer (python, matplotlib.pyplot.imshow, it's a heat map of the zero-one values).

Mairon

7/6/24, 9:45 AM

Indeed, when the algebraic degree is small the representation should not be big. But using Mobius transform requires the truth table which in my case is not feasible.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: How to write monomials in $GF(2^n)$ as a system of equations in $GF(2)$

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.