是從2[×]從2[X]mathbb{Z}_2[x]- 不可約性磷磷{bf P}?
傳統乘法的一種快速替代方法是無進位乘積。它的工作方式與可數二進制多項式上的乘法完全相同 $ \mathbb{Z}2[x] $ . 我們可以使用整數的二進製表示來辨識具有二進制多項式的任何非負整數（例如 $ 13{10} = 1101_2 $ 被辨識為 $ x^3 + x^2 + 1 \in \mathbb{Z}_2[x] $ ).
2004 年，開創性論文“Primes is in $ {\bf P} $ “出現了。
我想知道，是否有類似的結果，例如“ $ \mathbb{Z}_2[x] $ - 不可約性在 $ {\bf P} $ “持有？
作為獎勵，因式分解 $ \mathbb{Z}_2[x] $ 是“幾乎一樣難”的因素 $ \mathbb{N} $ ? （不需要接受答案，但我真的很想知道這一點。）
有限域上多項式的因式分解可以使用隨機算法在可能的多項式時間內求解（這比整數的因式分解要容易得多）。對於固定的地面場，例如 $ \mathbb F_2 $ ，這可以確定。自然地，這允許在相似的時間內進行不可約性測試。
如果我們只對是/否不可約性測試感興趣，可以節省一些小成本，算法如下。請注意，我們可以計算 $ X^{2^k}-X\mod{f(X)} $ 和 $ k $ 重複平方和減法等計算 $ \mathrm{GCD}(X^{2^k}-X,f(X)) $ 可以在時間多項式中完成 $ k $ 和程度 $ f(X) $ .
步驟 1. 我們計算 $ \mathrm{GCD}(X^{2^d}-X,f(X)) $ 在哪裡 $ d=\mathrm{deg}f $ . 如果這不是 $ f(X) $ 然後 $ f $ 不是不可約的，因為它要麼有重複的根，要麼有外根 $ \mathbb F_{2^d} $ . 如果是 $ f(X) $ 我們進行第 2 步。
步驟 2. 對於每個素數 $ p|d $ 我們讓 $ d’=d/p $ 併計算 $ \mathrm{GCD}(X^{2^{d’}}-X,f(X)) $ . 如果這不是 1 那麼 $ f(X) $ 在子欄位中有根 $ \mathbb F_{2^{d’}} $ 和 $ f(X) $ 不是不可約的。
如果第 2 步全部通過 $ p|d $ 那麼所有的根源都在 $ \mathbb F_{2^d} $ ，但不在子欄位中，因此 $ f(X) $ 是不可約的。