Как вычислить функцию инверсии S:S:\mathbb{F}_{2^n}\rightarrow \mathbb{F}_{2^n}, где S(x)=x^{-1}

Теорема Эйлера является частным случаем Теорема Лагранжа подал заявку в группу $(\mathbb Z/m\mathbb Z)^\times$. Может применяться в случае $ м = 2 ^ п $ куда $|(\mathbb Z/m\mathbb Z)^\times|=2^{n-1}$ вывести, что для любого нечетного целого числа $х$ $х^{2^{n-1}-1}\эквив х^{-1}\pmod{2^n}$. Однако это отличается от группы $\mathbb F_{2^n}^\times$. В таком случае $|\mathbb F_{2^n}^\times|=2^n-1$ и мы можем использовать это, чтобы вывести это для любого элемента $x\in\mathbb F_{2^n}^\times$ у нас есть $ х ^ {2 ^ n-2} \ эквив х ^ {- 1} $. Элементы $\mathbb F_{2^n}$ часто записываются в виде многочленов от некоторой переменной, скажем $Х$, над $\mathbb F_2$ по модулю некоторого неприводимого многочлена, скажем $ф(Х)$ степени $n$. Таким образом, другой способ выразить это состоит в том, чтобы сказать, что для любого многочлена $г(Х)$ взаимное преимущество $ф(Х)$ над $\mathbb F_2$ у нас есть $$g(X)^{2^n-2}\equiv g(X)^{-1}\pmod{\langle 2,f(X)\rangle}.$$