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

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

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}.$$
• 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$?
• 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]\}.$