證明X8+X4+X3+x+1X8+X4+X3+X+1x^8+x^4+x^3+x+1是不可約的從2[×]從2[X]mathbb{Z}_2[x]

我是這個領域的新手。我正在做一些密碼學課程並且遇到過 $ \text{GF}(2^8) $ 在著名的 AES 算法中。儘管我對這些東西（環/場）沒有很強的相關數學背景，但我對它真的很感興趣。我的教科書有一個問題要證明：

$$ x^8+x^4+x^3+x+1 $$是不可約的 $ \mathbb{Z}_2[x] $ . 我被困在這一點上，我對證明整體的不可約性沒有太多直覺 $ \mathbb{Z}_2[x] $ . 任何幫助都感激不盡！

**定義：如果一個非常數多項式不能分解為兩個非常數多項式的乘積，則稱該非常數多項式不可約。**換句話說; 如果 $ p(x) = q(x)t(x) $ 那麼它也是不可約的 $ q(x) $ 或者 $ t(x) $ 是一個常數多項式。

證明這一點的一種方法是 $ p(x) = x^8+x^4+x^3+x+1 $ 是不可約的 $ \operatorname{GF}(2)[x] $ 正在檢查低次不可約多項式的可分性。首先 1 階，然後 2 階，然後 3 階和 4 階將足以確定，因為 8 階可以分解為兩個多項式，可能的階為 $ 1\cdot 7,2\cdot 6, 3\cdot 5 $ ， 和 $ 4 \cdot 4 $ .

下面所有的算術都在 $ \operatorname{GF}(2)[x] $

1. 多項式是 $ x $ 和 $ x+1 $ . 我們可以通過設置檢查可分性 $ p(0) \stackrel{?}{=} 0 $ 或者 $ p(1) \stackrel{?}{=} 0 $ . $ p(0) = 1 \neq 0 $ 並且 $ p(1) = 1 \neq 0 $ . 因此一階多項式不除 $ p(x) $ . 這是因式定理，這是Math.SE 中的一個很好的證明。
2. 多項式，我們有四個多項式；

$$ \begin{align} & x^2+x+1\ & x^2+x \ & x^2+1\ & x^2\ \end{align} $$

讓我們看看為什麼 $ x^2+1 $ 不是不可約的；

$$ \begin{align} (x+1),(x+1)&=x,(x+1)+1,(x+1)&&\text{by distributivity}\ &=x^2+1,x+1,x+1&&\text{.}\ &=x^2+(1+1),x+1&&\text{.}\ &=x^2+(0),x+1&&\text{since the coefficients are in }\operatorname{GF}(2)\&=x^2+1 \end{align} $$

快速檢查，只有 $ x^2+x+1 $ 是不可約的。看到那個 $ p(x) $ 不能被 $ x^2+x+1 $ 執行除法並尋找餘數。可以使用這個 Sage 腳本

R = PolynomialRing(GF(2),'x')
x = R.gen()
p = x^8+x^4+x^3+x+1
q = x^2 + x + 1
p.quo_rem(q)

輸出是 $ (quo = x^6 + x^5 + x^3, rem = x + 1) $ , . 即不能分裂。

3. 次數不可約多項式

$$ \begin{align} & x^3 + x + 1 \ & x^3 + x^2 + 1 \end{align} $$

4. 次數不可約多項式

$$ \begin{align} & x^4 + x + 1 \ & x^4 + x^3 + 1\ & x^4 + x^3 + x^2 + x + 1 \end{align} $$

這些多項式是用 SageMath 生成的

degree=4
R = GF(2)['x']
for p in R.polynomials(degree):
    if p.is_irreducible():
        print(p)

要測試所有部門，請使用以下

R = PolynomialRing(GF(2),'x')
x = R.gen()
p = x^8+x^4+x^3+x+1
lst = [ x^2 + x + 1,  x^3 + x + 1,  x^3 + x^2 + 1,  x^4 + x + 1 , x^4 + x^3 + 1, x^4 + x^3 + x^2 + x + 1]

for t in lst:
   print(p.quo_rem(t))

輸出是

(x^6 + x^5 + x^3, x + 1)
(x^5 + x^3 + x^2 + 1, x^2)
(x^5 + x^4 + x^3, x + 1)
(x^4 + x, x^3 + x^2 + 1)
(x^4 + x^3 + x^2 + x + 1, x^3 + x^2)
(x^4 + x^3 + 1, x^3 + x^2)

所以 $ p(x) = x^8+x^4+x^3+x+1 $ 是不可約的 $ \operatorname{GF}(2)[x] $

---

**注 1：**低階不可約二進制多項式在密碼學中很重要，因為它們減少了所需的算術。Gadiel Seroussi 於 1998 年在低權二元不可約多項式表中列出了一個巨大的列表。該列表包含高達 10000 度的二進制不可約多項式。

注 2：來自 The On-Line Encyclopedia of Integer Sequences 的 A014580包含二進制多項式列表，以二進制編碼，或在以下情況下求值 $ x=2 $ . 這 $ p(2) $ 是 283。

2, 3, 7, 11, 13, 19, 25, 31, 37, 41, 47, 55, 59, 61, 67, 73, 87, 91, 97, 103, 109, 115, 117, 131, 137, 143, 145, 157, 167, 171, 185, 191, 193, 203, 211, 213, 229, 239, 241, 247, 253, 283, 285, 299, 301, 313, 319, 333, 351, 355, 357, 361, 369, 375,…

此答案中列出了粗體不可約數。

注 3： A001037保持 n 次不可約多項式的數量超過 $ \operatorname{GF}(2) $ . 8年級有18個， $ p(x) $ 在盡可能低的重量中。

degree 1  2  3  4  5  6  7   8
count  1, 2, 1, 2, 3, 6, 9, 18

這可以通過$$ L_q(n) = \frac{1}{2} \sum_{d|n} \mu (\frac{n}{d})q^d $$

引用自：https://crypto.stackexchange.com/questions/77952