置換多項式
我想在 GF(2^n) 中找到一個線性化多項式作為我的置換多項式。我知道唯一的根應該是 0。那麼，有沒有辦法找到這樣的多項式而不是選擇一個隨機的多項式並檢查根？
另外，我如何評估這個置換多項式，即置換的效果如何？
TL;DR下面連結的博士論文提到了線性化多項式，並沒有深入探勘細節。另見第三個參考文獻，其中討論了線性多項式排列。
正如@kelalaka 評論中連結的維基百科頁面所述，有限域上有許多排列多項式族。讓我們限製到特徵 2，即 $ GF(2^n): $
您詢問“評估”排列。這可以是它的循環結構（與特定排列的典型性有關，關於偽隨機性屬性）以及它的實現複雜性。
一個著名的置換多項式 $ GF(2^n) $ 在 AES Sbox 中用於 $ n=8 $ 是 $$ f(x)=x^{2^n-2}. $$ 請注意，它通常寫為 $ f(x)=x^{-1}, $ 為了 $ x\neq 0, $ 但是由於 $ x^{2^n-1}=1 $ 在 $ GF(2^n) $ （拉格朗日定理）這兩種表示是等價的。
至於循環結構，有一些結果是已知的，太詳細了，這裡就不贅述了。有關最近的一些結果，請參閱底部連結的論文。連結論文的開頭部分有一些例子，並且很好地描述了較早的文獻。
例如，線性多項式 $ f(x)=ax+b $ 顯然是身份 if $ b=0, $ $ a=1, $ 它只是一個翻譯，如果 $ a=0,b\neq 0. $ 在 $ GF(2^n) $ 翻譯將有長度為 2 的循環，因為 $ b=-b. $
單項式 $ f(x)=x^k $ 是一個排列當且僅當 $ \gcd(k,2^n-1)=1. $ 其循環結構是眾所周知的，與博士論文中的定理2.2相聯繫。
Dickson 多項式也具有完全已知的結構，請參閱相關博士論文中的定理 2.3。
線性化多項式 $ GF(2^n) $ 相當於一個線性映射 $ GF(2)^n \to GF(2)^n $ . 因此，置換多項式對應於可逆線性映射。
回答這個問題：我們可以隨機取一個 $ n\times n $ 可逆二進制矩陣並將其轉換為單變數多項式表示。但是，處理具體的基礎可能很麻煩。我們可以假設矩陣在基礎上起作用 $ {tr(\alpha_i x)}i $ ， 在哪裡 $ \alpha_0, \ldots, \alpha{n-1} $ 是任意線性無關的場元素，並且 $$ tr : GF(2^n) \to GF(2) : x \mapsto x + x^2 + x^4 + x^8 + \ldots + x^{2^{n-1}} $$是場跡。然後，我們可以簡單地將矩陣列轉換為欄位元素 $ c_0,c_1,\ldots,c_{n-1} $ （理想情況下，通過反轉基於蹟的變換，但沒有必要，因為我們有一個隨機矩陣）並將最終多項式定義為 $$ p(x) = c_0tr(\alpha_0x) + c_1tr(\alpha_1x) + \ldots + c_{n-1}tr(\alpha_{n-1}x), $$ 其中跡函式可以展開，得到一個純線性化多項式。這將是一個置換多項式當且僅當所有 $ c_i $ 是線性無關的，這是通過選擇一個可逆矩陣來保證的。
注意：直接以相同的方式選擇係數 $ x,x^2,x^4,\ldots $ 不保證映射的正確性：即使係數是線性無關的，結果也可能不是置換多項式。
這是 SageMath 程式碼，它適用於較大的值 $ n $ 比如100（ $ O(n^3) $ ，可以預先計算基矩陣，然後得到一個新的多邊形是 $ O(n^2) $ ):
def trace(a, x): # Sage stores polynomials as lists # => sparse polynomials with large powers are infeasible # return sum(x**(2**i) for i in range(n)) # replace by vector (index i => power 2**i) return vector(a**(2**i) for i in range(n)) n = 10 F = GF(2**n, name='w') randmat = GL(n, GF(2)).random_element().matrix() x = PolynomialRing(F, names='x').gen() poly = 0 for j, col in enumerate(randmat.columns()): poly += F(col) * vector(F.fetch_int(2**j)**(2**i) for i in range(n)) print( "poly", " + ".join(f"({a})*x^{2**i}" for i, a in reversed(list(enumerate(poly)))) ) if n <= 10: poly = sum(a*x**(2**i) for i, a in enumerate(poly)) assert len({poly(a) for a in F}) == len(F) print("is permutation ok") # poly (w^5 + w^2)*x^512 + (w^9 + w^8 + w^7 + w^6 + w^5 + w^4 + w + 1)*x^256 + (w^8 + w^5 + w^2 + 1)*x^128 + (w^5 + w^4 + w^2 + 1)*x^64 + (w^9 + w^5 + w^4 + w^3 + w^2 + w)*x^32 + (w^9 + w^5 + w^4 + 1)*x^16 + (w^9 + w^6 + w^5 + w^4 + w^2)*x^8 + (w^9 + w^8 + w^6 + w^5 + w^4 + w^2 + w + 1)*x^4 + (w^7 + w^5 + w^2 + w + 1)*x^2 + (w^9 + w^7 + w^6 + w^5 + w^4 + w^2 + 1)*x^1 # is permutation okPS：這種方法“僅”通過隨機二進制矩陣的可逆性檢查來代替隨機線性化多項式的根檢查，這很有幫助，因為標準根檢查大 $ n $ 將是不可行的。