The S-box is defined as the generalised inverse function $S:\mathbb{F}_{2^n}\rightarrow \mathbb{F}_{2^n}$,in quotient ring $\mathcal{R}:=\mathbb{F}_{2^n}[X]/(X^{2^n}-X)$ with $S(x)=x^{-1}$, is correct $S(X):=X^{2^n-2}$. But the Euler's theorem says $x^{\varphi(n)}\equiv1\pmod{n}$,so the answer is $x^{\varphi(n)-1}=x^{2^{n-1}-1}\equiv x^{-1}\pmod{n}$,why is $S(X):=X^{2^n-2}$


1 Answer 1


Euler's theorem is a special case of Lagrange's theorem applied to the group $(\mathbb Z/m\mathbb Z)^\times$. It can be applied in the case $m=2^n$ where $|(\mathbb Z/m\mathbb Z)^\times|=2^{n-1}$ to deduce that for any odd integer $x$ $x^{2^{n-1}-1}\equiv x^{-1}\pmod{2^n}$. However, this is different to the group $\mathbb F_{2^n}^\times$. In this case $|\mathbb F_{2^n}^\times|=2^n-1$ and we can use this to deduce that for any element $x\in\mathbb F_{2^n}^\times$ we have $x^{2^n-2}\equiv x^{-1}$. Elements of $\mathbb F_{2^n}$ are often written as polynomials in some variable, say $X$, over $\mathbb F_2$ modulo some irreducible polynomial, say $f(X)$ of degree $n$. Thus another way to express this is to say that for any polynomial $g(X)$ coprime to $f(X)$ over $\mathbb F_2$ we have $$g(X)^{2^n-2}\equiv g(X)^{-1}\pmod{\langle 2,f(X)\rangle}.$$

  • $\begingroup$ Can you explain the notation $\langle 2,f(X)\rangle$ ? I know from context that the outcome is the reduction polynomial, but I can't figure the logic behind the notation. Ah, or is it that coefficients of the polynomial $\langle m,f(X)\rangle$ are in $\mathbb Z/m\mathbb Z$? $\endgroup$
    – fgrieu
    Dec 6, 2022 at 16:57
  • $\begingroup$ generally $\langle x_1,x_2,\dots,x_k\rangle$ is notation for the (ring-theoretic) ideal generated by the elements $x_1, x_2,\dots, x_k$. So concretely $\langle 2, f(X)\rangle = \{2r_1 + r_2f(X)\mid r_i\in\mathbb{F}_2[X]\}.$ $\endgroup$
    – Mark Schultz-Wu
    Dec 6, 2022 at 21:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.