Как вычислить обратную функцию $x^3$ в $\mathbb{F}_{2^n}$

Порядок мультипликативной группы $\mathbb F_{2^n}$ является $2^n-1$. Если 3 взаимно просто с $2^n-1$ тогда существует $d\in [1,\ldots,2^n=1]$ такой, что $3d\экв 1\pmod{2^n-1}$. Мы можем найти такой $д$ с помощью расширенного алгоритма Евклида.

Функция на $\mathbb F_{2^n}$ $y\mapsto y^d$ тогда является инверсией карты $x\mapsto x^3$ так как для $x\in\mathbb F_{2^n}^\times$ у нас есть $ (х ^ 3) ^ д = х ^ {3d} = х ^ 1 $ (случай $х=0$ очевидно).

Это означает, что $x\mapsto x^3$ биективна и, следовательно, является перестановкой.

В случае, когда $3|2^n-1$, если $х^3=у$ в $\mathbb F_{2^n}$ тогда так делать $(\омега х)^3=у$ и $(\омега^2 х)^3=у$ куда $\омега$ это кубический корень из 1 в $\mathbb F_{2^n}$. Отсюда следует, что в этом случае отображение не является инъективным и, следовательно, не является перестановкой.