How to calculate the inversion fucntion $S: \mathbb{F}_{2^n} \rightarrow \mathbb{F}_{2^n}$,with $S(x)=x^{-1}$

Question

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}$

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}.$$