Proving a function in $\operatorname{GF}(2^n)$ is differentially k-uniform

mathd

1/10/23, 8:00 AM

I want to show that $F(x) = x^{-1}$ in $\operatorname{GF}(2^{n})$ is differentially 4-uniform for even $n$, and is differentially 2-uniform for odd $n$, without looking at the Differential Distribution Table.

My attempt:

Let $\alpha, \beta \in \operatorname{GF}(2^{n})$ and $\alpha \neq 0$

$$(x+\alpha)^{-1} - x^{-1} = \beta$$

$$\Rightarrow \frac{1}{x + \alpha} - \frac{1}{x} = \beta$$

$$\Rightarrow \beta x^{2}+ \alpha \beta x + \alpha = 0$$

How can we show the equation has at most 4 or 2 solutions in $\operatorname{GF}(2^{n})$?

0 + 0

finite-field

Daniel S

1/10/23, 9:16 AM

It's a polynomial in one variable over a field. You should know of a result that bounds the number of solutions.

mathd

1/10/23, 10:40 AM

It has at most 4 solutions, i think we don't need the bound.

poncho

1/10/23, 11:59 AM

It has at most 2 solutions; as Daniel said, in a field, a nontrivial quadratic over a single variable has at most 2 solutions, and that's a quite well known result.

fgrieu

1/12/23, 7:46 AM

For reference: $F$ being $k$-uniform is defined as meaning: $k$ is the maximum number of solutions $x$ to $F(x+\alpha)+F(x)=\beta$ when $\alpha\ne0$ and $\beta$ take all possible pairs of values. Note: I guess the definition of this question's $F$ assumes $F(0)=0$. Hint: do the algebra carefully. $u=v\mathrel{\mathord{\rlap{\hspace{.55em}\not}}\mathord{\Longleftrightarrow}}u\,w=v\,w$.

Elon Musk

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

EN: Proving a function in $\operatorname{GF}(2^n)$ is differentially k-uniform

TH: การพิสูจน์ฟังก์ชันใน $\operatorname{GF}(2^n)$ เป็น k-uniform ที่แตกต่างกัน

RO: Demonstrarea unei funcții în $\operatorname{GF}(2^n)$ este k-uniformă diferențial

RU: Доказательство функции в $\operatorname{GF}(2^n)$ дифференциально k-равномерно

VI: Chứng minh một hàm trong $\operatorname{GF}(2^n)$ khác biệt k-uniform

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.