Finite-Field
如何計算函式的倒數X3X3x^3在F2nF2nmathbb{F}_{2^n}
如何計算函式的倒數 $ x^3 $ 在 $ \mathbb{F}{2^n} $ ?, 任意單項式 $ x^d $ 是域中的一個排列 $ \mathbb{F}{2^n} $ 當且當 $ gdc(d,2^{n}-1)=1 $ ，為什麼？
乘法群的順序 $ \mathbb F_{2^n} $ 是 $ 2^n-1 $ . 如果 3 互質於 $ 2^n-1 $ 那麼存在 $ d\in [1,\ldots,2^n=1] $ 這樣 $ 3d\equiv 1\pmod{2^n-1} $ . 我們可以找到這樣一個 $ d $ 使用擴展歐幾里得算法。
上的功能 $ \mathbb F_{2^n} $ $ y\mapsto y^d $ 然後是地圖的倒數 $ x\mapsto x^3 $ 因此 $ x\in\mathbb F_{2^n}^\times $ 我們有 $ (x^3)^d=x^{3d}=x^1 $ （案子 $ x=0 $ 很明顯）。
這意味著 $ x\mapsto x^3 $ 是雙射的，因此是一個排列。
在這種情況下 $ 3|2^n-1 $ ， 如果 $ x^3=y $ 在 $ \mathbb F_{2^n} $ 那麼也一樣 $ (\omega x)^3=y $ 和 $ (\omega^2 x)^3=y $ 在哪裡 $ \omega $ 是 1 in 的立方根 $ \mathbb F_{2^n} $ . 因此，在這種情況下，映射不是單射的，因此不是排列。