式與本原多項(xiàng)式：判定、手算與Python枚舉)
不可約多項(xiàng)式和本原多項(xiàng)式這兩個(gè)詞第一次撞見基本都在有限域、糾錯(cuò)編碼或者 LFSR 的教材里公式一擺、符號一多人就開始飄。我第一次做 GF(2^8) 上的乘法器時(shí)隨手從網(wǎng)上抄了個(gè)八次多項(xiàng)式當(dāng)模仿真跑起來乘法逆元全錯(cuò)寄存器值滿屏亂飛查了大半天才發(fā)現(xiàn)那個(gè)多項(xiàng)式是可約的——它連一個(gè)有限域都撐不起來談何求逆。從那以后我養(yǎng)成一個(gè)習(xí)慣凡是涉及不可約多項(xiàng)式、本原多項(xiàng)式的選型一律自己算一遍、跑一遍代碼再往工程里填絕不信手里的表。這篇內(nèi)容就是把這件事說透。我會(huì)先把不可約和本原這兩個(gè)概念釘死再用大量手算例子把判定過程走一遍包括 GF(2) 和 GF(3) 上的一堆具體多項(xiàng)式然后給出一套完整的 Python 實(shí)現(xiàn)讓你不查表也能枚舉任意次數(shù)的不可約多項(xiàng)式和本原多項(xiàng)式。如果你在做 CRC、LFSR、Reed-Solomon、AES 的 S 盒、隨機(jī)數(shù)發(fā)生器或者只是被教材上的定理繞暈了這篇應(yīng)該能幫你省下幾個(gè)小時(shí)。全文計(jì)算過程我都寫全了你可以拿紙筆跟著對一遍。1. 先把概念釘死不可約多項(xiàng)式到底不可約在哪1.1 從沒有實(shí)根這個(gè)直覺說起不可約多項(xiàng)式的定義課本上一句話在域 F 上一個(gè)次數(shù)大于等于 1 的多項(xiàng)式 f(x)如果它不能寫成兩個(gè)次數(shù)都小于 deg(f) 且大于 0 的多項(xiàng)式的乘積就叫在 F 上不可約。這個(gè)定義里有兩個(gè)關(guān)鍵詞最容易被忽略一個(gè)是在哪個(gè)域上另一個(gè)是次數(shù)都小于 deg(f) 且大于 0。這兩個(gè)點(diǎn)直接決定了后面所有的坑。先說在哪個(gè)域上。x^21 在實(shí)數(shù)域上不可約因?yàn)闆]有任何實(shí)數(shù) x 讓 x^210判別式是負(fù)的。但放到復(fù)數(shù)域上x^21(xi)(x-i)就變成可約的了。同樣的道理x^2-2 在有理數(shù)域上不可約但在實(shí)數(shù)域上可約成 (x-√2)(x√2)。所以不可約永遠(yuǎn)是一個(gè)相對概念離開域的定義談不可約是沒有意義的。我們后面討論的域主要是有限域 GF(p) 和 GF(p^n)其中最常用的是 GF(2)。再說次數(shù)都小于 deg(f) 且大于 0。這里排除了乘一個(gè)常數(shù)的情況。比如在 GF(2) 上x^2x x·(x1)兩個(gè)因子都是 1 次所以 x^2x 可約。但 2x^22x 這種寫法在 GF(2) 里就等于 0根本不用討論。換成 GF(3)3x^2 這種常數(shù)倍數(shù)不算因式分解因?yàn)槌?shù)不影響能不能再分常數(shù)是單位元不是真正的因子。我見過最常見的誤判就是有人把在 GF(2) 上沒有根直接等同于不可約。這個(gè)等價(jià)關(guān)系只在次數(shù)不超過 3 的時(shí)候成立。到了 4 次及以上就開始失效因?yàn)?4 次多項(xiàng)式可以拆成兩個(gè) 2 次的乘積而這兩個(gè) 2 次因子各自都沒有一次因子所以整個(gè) 4 次多項(xiàng)式在 GF(2) 上照樣沒有根卻明明是可約的。最經(jīng)典的例子就是 f(x) x^4 x^2 1。代 x0 進(jìn)去得到 1代 x1 進(jìn)去得到 1111兩個(gè)取值都不是 0所以在 GF(2) 上沒有根。但它實(shí)際上等于 (x^2x1)^2展開一下x^4 x^2 1中間項(xiàng) 2x^3、2x^2 在 GF(2) 里全被 2 消掉2 次項(xiàng)剩一個(gè) x^2。這就是一個(gè)標(biāo)準(zhǔn)的 4 次可約、卻無根的例子。類似的還有 x^41在 GF(2) 上它等于 (x1)^4因?yàn)?(x1)^2 x^21再平方就是 x^41。這兩個(gè)例子建議你記牢面試和排錯(cuò)都用得上。提示判斷無根只是排除了一次因子可約還包含兩個(gè)高次因子相乘的情況。次數(shù)大于 3 時(shí)無根是最低門檻不是充分條件。1.2 本原多項(xiàng)式是不可約多項(xiàng)式里的優(yōu)選生不可約多項(xiàng)式只是分不開的多項(xiàng)式而本原多項(xiàng)式是在此基礎(chǔ)上再挑一層出來它不僅不可約而且它的某個(gè)根還是擴(kuò)域乘法群的生成元。具體說設(shè) f(x) 是 GF(q) 上次數(shù)為 n 的不可約多項(xiàng)式α 是它的一個(gè)根那么 α 一定落在擴(kuò)域 GF(q^n) 里。GF(q^n) 去掉零元之后是一個(gè)乘法群這個(gè)群的階是 q^n - 1。如果 α 的階恰好等于 q^n - 1也就是說 α 的冪能遍歷所有非零元素那么 α 就是一個(gè)本原元f(x) 就叫做 GF(q) 上的 n 次本原多項(xiàng)式。反過來說不可約多項(xiàng)式的根 α 的階一定是 q^n - 1 的因子但不一定等于它。只有當(dāng)這個(gè)階剛好頂滿 q^n - 1 時(shí)才升級為本原多項(xiàng)式。所以本原多項(xiàng)式一定不可約不可約多項(xiàng)式的卻不一定本原。這個(gè)方向千萬不能記反。舉一個(gè)具體的例子。在 GF(2) 上x^4x^3x^2x1 是 4 次不可約的但它的根 α 滿足 α^51階只有 5而 2^4-1155 只是 15 的因子。所以它是不可約但非本原。而 x^4x1 和 x^4x^31 這兩個(gè)多項(xiàng)式的根階都是 15它們都是本原的。這個(gè)區(qū)別在工程上非常要命。用 LFSR 做偽隨機(jī)序列時(shí)特征多項(xiàng)式必須是本原的才能保證序列周期達(dá)到最大長度 2^n-1如果只保證不可約周期可能只有 2^n-1 的某個(gè)因子序列會(huì)提前重復(fù)隨機(jī)性和統(tǒng)計(jì)特性直接崩掉。反過來做有限域乘法的時(shí)候只要不可約就夠了因?yàn)槌朔嬖拇嬖谛灾灰蕾囉蚪Y(jié)構(gòu)不依賴是不是本原。所以選型之前先問自己一句我要的是能構(gòu)成域還是要有滿周期這個(gè)問題的答案決定了你得驗(yàn)到哪一層。1.3 一張表看清兩者關(guān)系與計(jì)數(shù)規(guī)律不可約多項(xiàng)式和本原多項(xiàng)式的個(gè)數(shù)都有閉式公式這在做枚舉和交叉驗(yàn)證時(shí)特別有用。GF(q) 上首一 n 次不可約多項(xiàng)式的個(gè)數(shù)是N_q(n) (1/n) · Σ_{d|n} μ(d) · q^(n/d)其中 μ 是莫比烏斯函數(shù)取值規(guī)則是μ(1)1μ(素?cái)?shù))-1μ(素?cái)?shù)平方)0μ(兩個(gè)不同素?cái)?shù)之積)1。GF(q) 上 n 次本原多項(xiàng)式的個(gè)數(shù)是P_q(n) φ(q^n - 1) / nφ 是歐拉函數(shù)。注意本原多項(xiàng)式的個(gè)數(shù)只跟 q^n - 1 的因式分解有關(guān)跟 n 的因數(shù)關(guān)系不大這一點(diǎn)很多人第一次看會(huì)覺得別扭。把 q2 代進(jìn)去算一張常用表n不可約個(gè)數(shù) N_2(n)本原個(gè)數(shù) P_2(n)本原占比12150%211100%322100%43267%566100%69667%71818100%8301653%9564886%10996061%1118617695%1233514443%164080204850%表里 n2、3、5、7 這幾個(gè)本原占比 100% 的次數(shù)都是因?yàn)?2^n-1 是素?cái)?shù)。2^2-13、2^3-17、2^5-131、2^7-1127 都是素?cái)?shù)而 q^n-1 為素?cái)?shù)時(shí)除 1 以外的任何元素階都是 q^n-1所有不可約多項(xiàng)式的根都自動(dòng)是生成元。這就是為什么小次數(shù)的效果看起來很整齊一旦到了 n82^8-12553×5×17 有多個(gè)因子情況立刻復(fù)雜起來。拿 n4 手算一遍確認(rèn)公式不是騙人的。n4 的因子是 1、2、4μ(1)1、μ(2)-1、μ(4)0所以N_2(4) (1/4) × [1×2^4 (-1)×2^2 0×2^1] (1/4) × [16 - 4] 3確實(shí)只有 3 個(gè) 4 次不可約多項(xiàng)式。本原的個(gè)數(shù)2^4-115φ(15)φ(3)×φ(5)2×48P_2(4)8/42正好 2 個(gè)。而 GF(2) 上 4 次首一多項(xiàng)式總共只有 2^416 個(gè)可約的有 13 個(gè)不可約 3 個(gè)本原 2 個(gè)。這個(gè)比例在選型時(shí)挺有用的你以為隨手一抓就不可約其實(shí)命中率只有兩成不到。再看 n8N_2(8) (1/8)[2^8 - 2^4] (256-16)/8 30。P_2(8)2553×5×17φ(255)255×(2/3)×(4/5)×(16/17)128128/816。30 個(gè)不可約里只有 16 個(gè)本原另外 14 個(gè)的根階分別是 85、51、17、15 這些因子。所以如果你從網(wǎng)上隨便抓一個(gè)八次不可約多項(xiàng)式當(dāng) LFSR 的特征多項(xiàng)式有超過一半的概率拿到的是非本原的周期直接腰斬甚至只有原來的十幾分之一。2. GF(p)上判定不可約的三條實(shí)用路線2.1 低次2 次、3 次直接試根就夠次數(shù)是 2 或 3 的時(shí)候判定邏輯最簡單把域里所有元素代進(jìn)去只要有一個(gè)取值為 0就說明有一次因子可約如果全都不為 0就不可約。道理很直白。一個(gè) 2 次多項(xiàng)式如果能分解只能是1 次 × 1 次那就必須有一個(gè)一次因子 (x-a)也就意味著 f(a)0。3 次同理能分解的話必然是 1 次乘 2 次同樣要有一個(gè)根。所以 2 次、3 次不存在兩個(gè)高次因子相乘的退化情況試根法在這里是完全充分的。在 GF(2) 上只有 0 和 1 兩個(gè)元素要試。所有 2 次首一多項(xiàng)式有 4 個(gè)x^2、x^21、x^2x、x^2x1。逐個(gè)代x^2代 0 得 0有根可約。x^21代 1 得 110有根可約等于 (x1)^2。x^2x代 0 得 0有根可約等于 x(x1)。x^2x1代 0 得 1代 1 得 1111都非 0不可約。所以 GF(2) 上只有 x^2x1 一個(gè) 2 次不可約多項(xiàng)式跟公式 N_2(2)(1/2)(4-2)1 完全對得上。3 次在 GF(2) 上有 8 個(gè)首一多項(xiàng)式其中能分解的占 6 個(gè)剩下 2 個(gè)不可約x^3x1 和 x^3x^21。這兩個(gè)互為反序多項(xiàng)式系數(shù)順序倒過來在 GF(2) 上這種配對很常見后面枚舉時(shí)你會(huì)發(fā)現(xiàn)大量這種情況。換到 GF(3) 上做一遍體會(huì)一下 p2 的感覺。GF(3) 的元素是 0、1、2。所有 2 次首一多項(xiàng)式形如 x^2bxcb、c 各有 3 種取法共 9 個(gè)。逐個(gè)篩多項(xiàng)式x0x1x2判定x^2011可約x^21122不可約x^22200可約x^2x020可約x^2x1101可約x^2x2212不可約x^22x002可約x^22x1110可約x^22x2221不可約三個(gè)不可約x^21、x^2x2、x^22x2。跟公式 N_3(2)(1/2)(9-3)3 一致。這里有個(gè)小技巧值得說在 GF(p) 上用試根法時(shí)與其老老實(shí)實(shí)代 p 個(gè)值不如先算一下判別式。對 2 次多項(xiàng)式 x^2bxc它不可約當(dāng)且僅當(dāng) b^2-4c 不是 GF(p) 中的平方數(shù)且 p 為奇素?cái)?shù)。在 GF(3) 里0^20、1^21、2^21平方數(shù)集合是 {0,1}。x^21 的判別式是 0-4-4≡2 mod 32 不在 {0,1} 里所以不可約x^2x2 的判別式是 1-8-7≡2 mod 3同樣不在平方數(shù)集合里不可約x^22x2 的判別式是 4-8-4≡2 mod 3也不可約。三次都能秒判不用逐個(gè)代入。這個(gè)判據(jù)只對 2 次有效3 次以上就不成立了。注意試根法在次數(shù) ≥4 時(shí)只是必要條件。真正做工程的時(shí)候我通常先用試根法快速篩掉一大半可約的剩下的再上 Rabin 或者直接跑代碼。2.2 4 次以上先看階再用分圓多項(xiàng)式拆結(jié)構(gòu)次數(shù)到 4 以上試根法就不夠用了得換個(gè)思路。一個(gè)非常有效的觀察角度是分圓多項(xiàng)式。賽道上有個(gè)常用結(jié)論在 GF(q) 上x^m - 1 的因式分解跟 m 的素因子以及 q 在模 m 下的乘法階密切相關(guān)。具體說x^m-1 分解出的每個(gè)不可約因子其次數(shù)都等于 ord_m(q)也就是 q 模 m 的乘法階m 與 q 互素時(shí)。所有不可約因子次數(shù)相同個(gè)數(shù)就是 φ(m)/ord_m(q)。拿 GF(2) 上的 x^5-1 舉例。在 GF(2) 里減法和加法一樣x^5-1 x^51。因式分解出來是x^5 1 (x1)(x^4x^3x^2x1)m5q2ord_5(2) 是讓 2^k ≡ 1 (mod 5) 的最小 k。2^12、2^24、2^38≡3、2^416≡1所以 ord_5(2)4。φ(5)44/41說明除了那個(gè)一次因子 (x1) 之外剩下的是一個(gè) 4 次不可約多項(xiàng)式。這就直接證明了 x^4x^3x^2x1 在 GF(2) 上不可約完全不需要試根。這個(gè)方法特別好用因?yàn)樗雅卸ú豢杉s變成了算一個(gè)模意義下的乘法階。再舉 x^71 的例子。m7ord_7(2)2^12、2^24、2^38≡1所以 ord_7(2)3。φ(7)66/32說明除了 (x1) 之外剩下 6 次的部分 x^6x^5x^4x^3x^2x1 會(huì)拆成兩個(gè) 3 次不可約多項(xiàng)式。實(shí)際拆出來是x^6x^5x^4x^3x^2x1 (x^3x1)(x^3x^21)正好是前面提到的那兩個(gè) 3 次不可約多項(xiàng)式完全吻合。再看 9 次的情況這個(gè)例子后面講本原的時(shí)候還要用。x^91 在 GF(2) 上分解涉及的是 Φ_9(x) x^6x^31 這個(gè)九次分圓的一部分。ord_9(2)2^12、2^24、2^38≡-1、2^416≡7、2^514≡5、2^610≡1所以 ord_9(2)6。φ(9)66/61說明 Φ_9 本身就是一個(gè) 6 次不可約多項(xiàng)式。也就是 x^6x^31 不可約。順手再算一個(gè) 21 次的為后面 6 次多項(xiàng)式的階分布做準(zhǔn)備。ord_21(2)2^38、2^664≡1 (mod 21)中間 2^12、2^24 都不等于 1所以 ord_21(2)6。φ(21)1212/62說明 Φ_21 會(huì)拆成兩個(gè) 6 次不可約多項(xiàng)式。這兩只的根階都是 21。所以 6 次不可約多項(xiàng)式一共有三組來源兩組來自 Φ_21階 21一個(gè)來自 Φ_9階 9再加上本原的那 6 個(gè)階 63正好湊出 N_2(6)2169。這個(gè)分解思路在做枚舉驗(yàn)證時(shí)非常有用可以拿它當(dāng)標(biāo)準(zhǔn)答案去對代碼輸出。2.3 Rabin 判定法一條公式管到底附手算全過程分圓法靠的是恰好能對上 x^m-1這個(gè)條件遇到不對應(yīng)的多項(xiàng)式就不好使了。要一個(gè)普適的判定得請出 Rabin 不可約性測試。定理是這么說的設(shè) f 是 GF(q) 上次數(shù)為 n 的多項(xiàng)式f 不可約當(dāng)且僅當(dāng)下面兩條同時(shí)成立一是 x^(q^n) ≡ x (mod f) 二是對 n 的每個(gè)素因子 d都有 gcd(x^(q^(n/d)) - x, f) 1。第一條保證 f 的根都在 GF(q^n) 里第二條保證根不會(huì)掉進(jìn)任何一個(gè)真子域 GF(q^(n/d)) 里。兩條合起來說明 f 的所有根都是真正的 n 次代數(shù)元也就是 f 不可約。先用它驗(yàn)一個(gè)已知答案f x^4x^3x^2x1n4q2。n4 的素因子只有 d2n/d2第二步需要算 gcd(x^(2^2) - x, f) gcd(x^4x, f)。先算第一步。記 f 的關(guān)系式x^4 x^3x^2x1因?yàn)?x^4x^3x^2x10移項(xiàng)即可GF(2) 上加減一樣。x^4 x^3x^2x1 x^5 x·x^4 x^4x^3x^2x (x^3x^2x1)x^3x^2x 1x^5 居然等于 1這個(gè)結(jié)果很關(guān)鍵。繼續(xù) x^8 x^5·x^3 x^3 x^16 x^15·x (x^5)^3·x 1·x x所以 x^16 ≡ x (mod f)第一條滿足。再算 gcd。x^4x x(x^31) x(x1)(x^2x1)它的所有不可約因子是 x、x1、x^2x1。f 是 4 次如果它跟 x^4x 有公因子公因子只能是 x^2x1因?yàn)?f 沒有一次因子前面試根已經(jīng)確認(rèn)。而 (x^2x1)^2 x^4x^21 ≠ f所以 x^2x1 不整除 f兩者互素gcd1第二條也滿足。結(jié)論f 不可約。跟分圓法的判斷一致兩條路殊途同歸。再用它驗(yàn)一個(gè)可約的例子看看它是怎么抓住漏洞的。取 f x^4x^21 (x^2x1)^2n 還是 4d2。第一步f 的關(guān)系式是 x^4 x^21。 x^4 x^21 x^8 (x^4)^2 (x^21)^2 x^41 (x^21)1 x^2 x^16 (x^8)^2 (x^2)^2 x^4 x^21我們需要 x^16 ≡ x也就是 x^21 ≡ x顯然不成立兩者差 x^2x1非零。所以第一條就直接掛了根本不用算第二步。這個(gè)對比很有意思本原與否會(huì)影響 x 的階但可約與否會(huì)直接讓 x^(q^n) ≡ x 這個(gè)整體條件失效。注意 x^16 ≡ x 這一條本質(zhì)上是要求f 的所有根都落在 GF(q^n) 里對可約多項(xiàng)式來說只要有一個(gè)因子的次數(shù)不整除 n這個(gè)條件就崩。而 gcd 那一條是專門用來排除根的次數(shù)是 n 的真因子這種情況的。舉個(gè)需要靠第二條才能抓住的例子。取 f (x^2x1)(x^2x1)不行剛用過。換 f x^4x^3x^2x1 的兄弟四次的另一個(gè)可約情形f (x^2x1)(x^21)。展開x^4x^2x^3xx^21 x^4x^31……等一下x^2x^20x 剩一個(gè)所以是 x^4x^3x1。驗(yàn)一下 x111110有根是可約的這個(gè)例子太容易被試根法抓住。要構(gòu)造一個(gè)第一條滿足、第二條不滿足的最典型的是 f 本身不可約但次數(shù)不是 n……那不可能。真正的場景是 f 不可約且次數(shù)為真因子。比如取 f x^2x12 次不可約如果我們錯(cuò)把它當(dāng)成 4 次來測n 會(huì)算錯(cuò)實(shí)際它滿足 x^4 ≡ x (mod f)因?yàn)?x^31x^4x。而此時(shí) n4 的 d2n/d2要算 gcd(x^4x, f)。x^4x mod f xx 0gcd 就是 f 本身不等于 1第二條直接判死。這就是第二條的作用它把根的階太小、落在了真子域里這種情況篩掉。手算 Rabin 的時(shí)候有兩個(gè)提速技巧我自己常用。一個(gè)是別硬算 x^(q^n)一路用平方遞推x^2 → 平方得 x^4 → 平方得 x^8 → 平方得 x^16每一步做完立刻用 f 化簡。另一個(gè)是 gcd 那一步別真的去展開 x^(q^(n/d)) 這個(gè)多項(xiàng)式直接在商環(huán)里算出它的化簡結(jié)果再求 gcd因?yàn)?gcd 只跟化簡結(jié)果有關(guān)。次數(shù)一高這兩點(diǎn)能省掉大量時(shí)間。3. 本原多項(xiàng)式判定把階算明白就贏了一半3.1 階的三個(gè)性質(zhì)記住就不會(huì)錯(cuò)判定本原的核心就是算一個(gè)數(shù)根 α 的乘法階。圍繞它有三條性質(zhì)必須刻在腦子里。第一條階一定整除 q^n - 1。這不是巧合是拉格朗日定理的直接推論GF(q^n) 的非零元素構(gòu)成一個(gè)階為 q^n-1 的乘法群群中任何元素的階都整除群的階。所以算階的時(shí)候不用一個(gè)個(gè)往上試只需要在 q^n-1 的因子集合里找。第二條不可約多項(xiàng)式所有根的階都相同。這一點(diǎn)非常省事。f 的 n 個(gè)根是彼此共軛的α、α^q、α^(q^2)、…、α^(q^(n-1))共軛元素的階必然相等。所以你隨便取哪個(gè)根算階結(jié)果都一樣也正因?yàn)槿绱宋覀儾拍苷f這個(gè)多項(xiàng)式的階而不用特指是哪個(gè)根。第三條本原等價(jià)于階等于 q^n - 1。不是能整除且最大是嚴(yán)格的相等一個(gè)字都不能差。由此可以得到一個(gè)很實(shí)用的判定流程先確認(rèn)不可約然后算出 x 在商環(huán) GF(q)[x]/(f) 中的階如果等于 q^n-1 就是本原。之所以能拿 x 代替 α 來算是因?yàn)?α 就是 x 在商環(huán)里的像兩者階完全一致。有個(gè)細(xì)節(jié)我踩過坑判斷 x^k 是不是 1 的時(shí)候別忘了 k 要最小的那個(gè)。有人算到 x^151 就宣布本原完全沒檢查 x^3、x^5 是不是也等于 1。萬一是 x^51那階就是 5 而不是 15結(jié)論直接反了。正確的做法是先確認(rèn) x^(q^n-1)1再對 q^n-1 的每個(gè)素因子 p驗(yàn)證 x^((q^n-1)/p) ≠ 1。全部通過階才等于 q^n-1。3.2 手算階的完整流程以 x^4x^31 為例光說流程太干直接上完整的冪表。取 f x^4x^31在 GF(2) 上n4目標(biāo)階是 2^4-115。關(guān)系式x^4 x^31。逐次往上推kx^k 的化簡結(jié)果說明011x2x^23x^34x^31用關(guān)系式5x^3x1x·x^4 x^4x6x^3x^2x17x^2x18x^3x^2x9x^2110x^3x11x^3x^2112x113x^2x14x^3x^2151回到單位元x^15 確實(shí)等于 1而且從表里能直接看出來1 到 14 次冪沒有任何一個(gè)等于 1。所以階就是 15等于 2^4-1f 是本原多項(xiàng)式。再看一個(gè)反面例子f x^4x^3x^2x1。前面已經(jīng)算過 x^4 x^3x^2x1一步就得到 x^5 1。所以階是 5而 2^4-1155≠15不是本原的。這個(gè)多項(xiàng)式在 LFSR 里用起來周期只有 5序列短得可憐。順手把另一個(gè)本原的 4 次多項(xiàng)式 x^4x1 的冪表也貼出來方便你對照kx^k 化簡結(jié)果011x2x^23x^34x15x^2x6x^3x^27x^3x18x^219x^3x10x^2x111x^3x^2x12x^3x^2x113x^3x^2114x^31151兩張表對比著看你會(huì)發(fā)現(xiàn) x^7 和 x^7 就不一樣了在 x^4x1 里 x^7x^3x1在 x^4x^31 里 x^7x^2x1。這說明兩個(gè)本原多項(xiàng)式雖然都撐起 GF(16) 的乘法群但元素的編號也就是離散對數(shù)表是不同的。所以工程里換多項(xiàng)式就等價(jià)于換了一套對數(shù)表S 盒、CRC 表全得重算。這也是為什么我在項(xiàng)目里從不輕易改特征多項(xiàng)式。三個(gè)階段性的檢查點(diǎn)總結(jié)一下先看 x^(q^n-1) 是否等于 1再對 q^n-1 的每個(gè)素因子 p 檢查 x^((q^n-1)/p) 是否不等于 1兩條都過階就是滿的。以 15 為例153×5素因子是 3 和 5所以要額外驗(yàn) x^5≠1 和 x^3≠1。15/35、15/53都在表里能查到x^5x^3x1≠1、x^3x^3≠1通過。3.3 6 次不可約多項(xiàng)式的分歧63、21、9 三種階前面用分圓法算過GF(2) 上 6 次不可約多項(xiàng)式有 9 個(gè)其中 6 個(gè)本原階 632 個(gè)階為 211 個(gè)階為 9。這個(gè)分布是理解不可約不等于本原最好的教材。2^6-1633^2×7。63 的因子有 1、3、7、9、21、63。一個(gè) 6 次不可約多項(xiàng)式的根階必須是 63 的因子。理論上可能的階是 3、7、9、21、63但受次數(shù)必須等于 ord_m(2) 整除性的約束實(shí)際能出現(xiàn)的就是 63、21、9 三種。階為 9 的那一個(gè)是 x^6x^31也就是 Φ_9(x)。驗(yàn)證一下它的階設(shè) α 是根α^6 α^31那么 α^9 α^3·α^6 α^3(α^31) α^6α^3 (α^31)α^3 1。確實(shí) α^91。而且 α^3≠1否則 α^6 α^31 11... 等等如果 α^31那 α^6α^31 111 1 ≠ 0矛盾α^1≠1所以階就是 9。階為 21 的那兩個(gè)來自 Φ_21 的分解它們的冪次只會(huì)落在 21 個(gè)值上永遠(yuǎn)到不了 63。這兩個(gè)多項(xiàng)式具體是什么不重要重要的是這個(gè)事實(shí)同樣是 6 次不可約多項(xiàng)式用它們做 LFSR周期會(huì)從 63 掉到 21 或 9掉了三分之二還多。我在實(shí)際項(xiàng)目里見過更慘的有人用了一個(gè) 16 次的多項(xiàng)式做流密碼的驅(qū)動(dòng)序列2^16-1655353×5×17×257階的因子很多。他挑的那個(gè)多項(xiàng)式的階只有 255周期短了兩個(gè)數(shù)量級測試時(shí)看著隨機(jī)性還行實(shí)際在長時(shí)間抓包下序列重復(fù)得非常明顯。這類問題在短測試?yán)锔颈┞恫怀鰜碇荒芸刻崆鞍央A算清楚。所以我的建議是任何人讓你用一個(gè)特征多項(xiàng)式先問一句話它的階是多少答不上來的就用代碼跑一遍再談。3.4 三項(xiàng)式、五項(xiàng)式怎么選以及 8 次為什么沒有三項(xiàng)式選本原多項(xiàng)式的時(shí)候工程上有兩個(gè)偏好項(xiàng)數(shù)越少越好最高次項(xiàng)系數(shù)固定為 1中間只有少量非零系數(shù)。原因是硬件上每個(gè)非零系數(shù)對應(yīng)一個(gè)異或門或者一個(gè)抽頭項(xiàng)數(shù)越少LFSR 的反饋邏輯越省資源軟件上計(jì)算也越快。系數(shù)只有三項(xiàng)的形如 x^n x^k 1叫三項(xiàng)式是最理想的形態(tài)。但三項(xiàng)式不存在萬能的情況。一個(gè)基本事實(shí)是如果 n 是偶數(shù)任何 x^n x^k 1 只要 k 也是偶數(shù)它就是完全平方必然可約。比如 x^8x^41(x^4x^21)^2、x^8x^21(x^4x1)^2、x^8x^61(x^4x^31)^2全是這個(gè)套路。所以在 GF(2) 上要找不可約三項(xiàng)式k 必須是奇數(shù)。更麻煩的是有些次數(shù)上根本不存在不可約三項(xiàng)式。8 次就是最著名的例子13 次、16 次、19 次這些也在列。這一點(diǎn)你自己跑一遍枚舉就能確認(rèn)代碼在后面第 4 節(jié)。所以做 8 位 LFSR 的時(shí)候市面上流傳的抽頭組合沒有一個(gè)三項(xiàng)式的全得用五項(xiàng)式比如 x^8x^4x^3x^21、x^8x^6x^5x^41 這類。這里我要提醒一句網(wǎng)上流傳的本原多項(xiàng)式表質(zhì)量參差不齊我遇到過至少兩次抄錯(cuò)系數(shù)的情況。有的是印刷錯(cuò)誤有的是把不可約當(dāng)成本原列進(jìn)去了。所以我的習(xí)慣是候選多項(xiàng)式一律先用代碼驗(yàn)一遍不可約和本原兩個(gè)性質(zhì)驗(yàn)過了再往 RTL 里寫?；ㄎ宸昼婒?yàn)證比在板子上調(diào)三天強(qiáng)得多。還有一個(gè)容易被忽略的取舍項(xiàng)數(shù)少不等于性能好。在軟件實(shí)現(xiàn)里非零項(xiàng)的分布位置會(huì)影響緩存和指令流水有時(shí)候一個(gè)五項(xiàng)式的實(shí)際跑分反而比三項(xiàng)式更穩(wěn)。這個(gè)只能實(shí)測別光看公式。4. 從零寫代碼驗(yàn)證不查表也能自己算4.1 GF(2) 多項(xiàng)式運(yùn)算的位運(yùn)算實(shí)現(xiàn)前面全在紙上推現(xiàn)在把它工程化。GF(2) 上的多項(xiàng)式有個(gè)天然的好處系數(shù)只有 0 和 1可以用一個(gè)整數(shù)的二進(jìn)制位直接表示。比如 0b1011 表示 x^3x1bit i 對應(yīng) x^i 的系數(shù)。加法和減法在 GF(2) 上都是異或乘法和取模也都是位運(yùn)算寫起來非常短。先把基礎(chǔ)函數(shù)搭起來# GF(2) 多項(xiàng)式用整數(shù)位掩碼表示bit i x^i 的系數(shù) # 例如 0b1011 表示 x^3 x 1 def deg(a): return a.bit_length() - 1 def poly_mod(a, m): 在 GF(2) 上求 a mod m加減統(tǒng)一用異或 dm deg(m) while a and deg(a) dm: a ^ m (deg(a) - dm) return a def poly_mul(a, b, mNone): 多項(xiàng)式乘法給了 m 就在商環(huán)里做 r 0 while b: if b 1: r ^ a b 1 a 1 return r if m is None else poly_mod(r, m) def poly_gcd(a, b): 歐幾里得算法求最大公因式 while b: a, b b, poly_mod(a, b) return apoly_mod用的是長除法只要被除式的次數(shù)不低于除式次數(shù)就把除式左移相應(yīng)位數(shù)再異或回去。這里能直接用異或代替減法是因?yàn)?GF(2) 上 1-10 和 110 完全一樣。這個(gè)特性也解釋了為什么代碼這么短。poly_mul是標(biāo)準(zhǔn)的俄羅斯農(nóng)民乘法乘數(shù)逐位右移被乘數(shù)逐位左移遇到 1 就累加。注意這里我用的是邊乘邊不進(jìn)模最后統(tǒng)一取模對小次數(shù)完全夠用。如果要做 32 次以上的多項(xiàng)式建議改成邊乘邊取模否則中間結(jié)果會(huì)膨脹得很大。再補(bǔ)一個(gè)快速冪Rabin 判定和階的計(jì)算都要用def poly_powmod(base, e, m): base^e mod m快速冪 r 1 base poly_mod(base, m) while e: if e 1: r poly_mul(r, base, m) base poly_mul(base, base, m) e 1 return r4.2 枚舉所有 n 次不可約多項(xiàng)式并與公式對照有了基礎(chǔ)運(yùn)算不可約判定可以先寫個(gè)樸素版把所有次數(shù)不超過 n/2 的首一多項(xiàng)式都拿來試除一遍。邏輯上無腦但勝在正確性一目了然。def is_irreducible(f): 樸素試除法用所有次數(shù) deg(f)/2 的首一多項(xiàng)式試除 n deg(f) if n 0: return False for d in range(1, n // 2 1): for g in range(1 d, 1 (d 1)): # d 次首一多項(xiàng)式全集 if poly_mod(f, g) 0: return False return Truerange(1 d, 1 (d1))這個(gè)寫法值得說一下。所有次數(shù)恰好為 d 的首一多項(xiàng)式最高位一定是 1所以最低的值是 1d最高是 1(d1)-1正好是這么個(gè)左閉右開區(qū)間。這個(gè)技巧在后面枚舉時(shí)反復(fù)用到。跑一遍枚舉把所有 n 次不可約多項(xiàng)式列出來for n in range(1, 13): irr [f for f in range(1 n, 1 (n 1)) if is_irreducible(f)] print(n, len(irr), [bin(f) for f in irr])n4 時(shí)會(huì)輸出 3 個(gè)0b10011 (x^4x1)、0b11011 (x^4x^31)、0b11111 (x^4x^3x^2x1)。跟我前面手算的完全一致。n6 時(shí)會(huì)輸出 9 個(gè)。n8 時(shí)會(huì)輸出 30 個(gè)。這些數(shù)字跟公式 N_2(n) 算出來的就一一對上了這也是驗(yàn)證代碼有沒有寫錯(cuò)的最好方式。順便說一句性能。這個(gè)樸素版本枚舉 12 次多項(xiàng)式時(shí)每個(gè)候選要試除大約 Σ(2^d) ≈ 2^(n/21) 個(gè)除式總計(jì)算量對 n≤16 完全能接受跑起來就是幾秒鐘。真要上 20 次以上就得換成 Rabin 或者 Berlekamp別硬扛。4.3 用 Rabin 和階來判本原性不可約判完了接著判本原。先把 Rabin 實(shí)現(xiàn)出來它比試除法快得多def prime_factors(n): fs, d set(), 2 while d * d n: while n % d 0: fs.add(d) n // d d 1 if n 1: fs.add(n) return fs def rabin_irreducible(f): Rabin 不可約判定僅針對 GF(2) n deg(f) if n 1: return False # 條件一x^(2^n) ≡ x (mod f) if poly_powmod(2, 1 n, f) ! poly_mod(2, f): return False # 條件二對每個(gè)素因子 dgcd(x^(2^(n/d)) x, f) 1 for d in prime_factors(n): h poly_powmod(2, 1 (n // d), f) ^ 2 # 異或 2 就是減 x if poly_gcd(poly_mod(h, f), f) ! 1: return False return True這里有個(gè)實(shí)現(xiàn)細(xì)節(jié)要注意條件二里的減 x在 GF(2) 上就是異或 2因?yàn)?x 的位掩碼是 0b10。寫別的域的時(shí)候要老老實(shí)實(shí)用減法GF(2) 才能這么省事。再看階的計(jì)算這是判本原的核心def poly_order(f): 求 x 在 GF(2)[x]/(f) 里的階返回 None 表示 f 不可約性有問題 n deg(f) cur, k 1, 0 while True: cur poly_mul(cur, 2, f) # 每次乘一個(gè) x k 1 if cur 1: return k if k (1 n): return None def is_primitive(f): n deg(f) return is_irreducible(f) and poly_order(f) (1 n) - 1最后把兩者串起來把前面那張表跑出來for n in range(1, 13): irr [f for f in range(1 n, 1 (n 1)) if is_irreducible(f)] pri [f for f in irr if poly_order(f) (1 n) - 1] print(fn{n:2d} 不可約{len(irr):3d} 本原{len(pri):3d})輸出會(huì)是 1:2/1、2:1/1、3:2/2、4:3/2、5:6/6、6:9/6、7:18/18、8:30/16、9:56/48、10:99/60、11:186/176、12:335/144跟第 1.3 節(jié)那張表一字不差。到這一步你已經(jīng)有了一個(gè)完全可以自證的驗(yàn)證工具以后不管誰給你一個(gè)多項(xiàng)式三十行代碼就能驗(yàn)完再也不用求人。有個(gè)小優(yōu)化值得提一句。poly_order是老老實(shí)實(shí)一次乘一個(gè) x對 n16 要循環(huán) 65535 次還行n32 就是 40 億次跑不動(dòng)了。真要做大次數(shù)應(yīng)該改成先算 x^(2^n-1) 確認(rèn)是 1再對 2^n-1 的每個(gè)素因子 p 驗(yàn)證 x^((2^n-1)/p)≠1這樣只需 O(log n × 素因子個(gè)數(shù)) 次快速冪。這是把前面 3.1 節(jié)的理論直接用上了。4.4 用現(xiàn)成庫交叉驗(yàn)證別只信自己的代碼自己寫實(shí)現(xiàn)最大的風(fēng)險(xiǎn)是錯(cuò)得一致——邏輯本身有 bug但輸出內(nèi)部自洽你反而更放心。所以我一定會(huì)拿現(xiàn)成庫對一遍。用 sympy 驗(yàn)不可約性最省事from sympy import Poly, GF, symbols x symbols(x) f Poly(x**8 x**4 x**3 x**2 1, x, domainGF(2)) print(f.is_irreducible) # True用 galois 庫可以直接把不可約和本原的列表一起拉出來import galois print(galois.irreducible_polys(2, 8, reverseTrue)) print(galois.primitive_polys(2, 8, reverseTrue))如果你有 Sage 環(huán)境那更簡單一行搞定R.x PolynomialRing(GF(2)) f x^8 x^4 x^3 x^2 1 print(f.is_irreducible(), f.is_primitive())我習(xí)慣的做法是用自己寫的代碼生成一份列表用庫再生成一份兩邊取集合做差。只要差集為空就說明實(shí)現(xiàn)沒問題。這個(gè)方法幫我抓出過兩次 bug一次是poly_mod里忘了處理 a 歸零的情況導(dǎo)致死循環(huán)一次是階的循環(huán)上限設(shè)成了 2^n 而不是 2^n-1邊界上多算了一輪。這種錯(cuò)誤光靠看代碼很難發(fā)現(xiàn)必須交叉驗(yàn)證。提示不同庫的版本 API 可能略有差異尤其是 galois 的返回類型和參數(shù)名。以上代碼以常見版本為準(zhǔn)跑之前建議先確認(rèn)一下自己環(huán)境里的函數(shù)簽名。5. 踩坑記錄與速查表5.1 五個(gè)最容易翻車的點(diǎn)第一個(gè)把無根當(dāng)成不可約。前面反復(fù)強(qiáng)調(diào)過了次數(shù) ≥4 時(shí)這個(gè)等價(jià)關(guān)系不成立。典型的反例 x^4x^21(x^2x1)^2。我現(xiàn)在看新人代碼的習(xí)慣動(dòng)作就是搜一遍有沒有只判根就返回不可約的實(shí)現(xiàn)十個(gè)里面能抓到三個(gè)。第二個(gè)階算錯(cuò)。最常見的兩種錯(cuò)法一種是查到 x^k1 就收工沒確認(rèn) k 是不是最小的另一種是循環(huán)邊界寫錯(cuò)把 q^n-1 寫成 q^n 或者 q^n-2。這兩種錯(cuò)誤都不會(huì)報(bào)異常只會(huì)讓結(jié)論靜悄悄地錯(cuò)掉。我的做法是在代碼里加一條斷言算出來的階必須整除 q^n-1不整除就說明實(shí)現(xiàn)有問題。第三個(gè)特征多項(xiàng)式選成了不可約但非本原的。這個(gè)坑最隱蔽因?yàn)榉抡媾芷饋硪磺卸颊Ｖ皇侵芷诒阮A(yù)期短。判斷辦法很簡單如果 LFSR 的周期不是 2^n-1先懷疑多項(xiàng)式的階。第四個(gè)混淆 p 和 n。GF(p^n) 里 p 是特征是模的素?cái)?shù)n 是擴(kuò)張次數(shù)是多項(xiàng)式的次數(shù)。這兩個(gè)量在很多公式里同時(shí)出現(xiàn)抄公式的時(shí)候特別容易串位。我一般會(huì)在草稿上把每個(gè)符號的含義寫一遍再代入。第五個(gè)跨域使用結(jié)論。GF(2) 上的表不能直接搬到 GF(3) 或者 GF(2^8) 上用。比如判別式是不是平方數(shù)這個(gè)判據(jù)只對奇素?cái)?shù) p 的 2 次多項(xiàng)式成立在 GF(2) 上根本不適用因?yàn)?2 是偶素?cái)?shù)判別式公式退化。換域就得重算沒有捷徑。5.2 癥狀—原因—處理速查表現(xiàn)象可能原因處理方式有限域乘法求逆失敗或結(jié)果異常模多項(xiàng)式可約商環(huán)不是域用 Rabin 或試除確認(rèn)不可約LFSR 周期遠(yuǎn)小于 2^n-1特征多項(xiàng)式不可約但非本原計(jì)算 x 的階換成本原多項(xiàng)式代碼判不可約但試除能拆開只做了試根漏了高次因子補(bǔ)上 d≤n/2 的完整試除階算出來不整除 q^n-1循環(huán)邊界或關(guān)系式化簡寫錯(cuò)加整除斷言重查 poly_mod同一多項(xiàng)式在不同資料里結(jié)論沖突一份資料把不可約當(dāng)本原了自己跑一遍代碼以計(jì)算結(jié)果為準(zhǔn)8 次找不到三項(xiàng)式該次數(shù)確實(shí)不存在不可約三項(xiàng)式改用五項(xiàng)式如 x^8x^4x^3x^21換了特征多項(xiàng)式后 CRC/S 盒全錯(cuò)換多項(xiàng)式等于換了整個(gè)對數(shù)表所有派生表全部重新生成這張表基本覆蓋了我自己遇到過的所有情況。最后一條尤其值得強(qiáng)調(diào)模多項(xiàng)式和它派生出來的表是強(qiáng)綁定的改一個(gè)系數(shù)整張表就全變了不存在改一點(diǎn)點(diǎn)、影響一點(diǎn)點(diǎn)的情況。5.3 我自己用的驗(yàn)證流程跑過這么多項(xiàng)目之后我形成了一個(gè)固定動(dòng)作幾乎每次都按這個(gè)順序走一遍。第一步拿到候選多項(xiàng)式先轉(zhuǎn)成位掩碼跑is_irreducible。這一步過濾掉最基礎(chǔ)的錯(cuò)誤。第二步跑poly_order拿到 x 的階跟 2^n-1 比。相等才算過。第三步用庫交叉驗(yàn)證一遍確認(rèn)自己的代碼沒寫歪。第四步如果這個(gè)多項(xiàng)式要用在硬件上再檢查一下非零項(xiàng)的位置和數(shù)量評估異或門的開銷。第五步如果它要派生 S 盒、CRC 表或者對數(shù)表生成完之后再做一次一致性自測比如驗(yàn)證任意元素乘它的逆等于 1。這五步加起來可能要多花二十分鐘但相比在板子上調(diào)三天的成本完全值。我印象最深的一次是做一個(gè) 16 位 CRC掐著時(shí)間上線多項(xiàng)式是從一份老文檔里直接抄的。結(jié)果 CRC 的檢錯(cuò)能力明顯不達(dá)標(biāo)突發(fā)錯(cuò)誤測試通過率異常最后發(fā)現(xiàn)那個(gè)多項(xiàng)式壓根就是可約的。從那以后我再也沒跳過第一步。最后分享一個(gè)小習(xí)慣我會(huì)把每次項(xiàng)目里用到的本原多項(xiàng)式、它的階、驗(yàn)證時(shí)間記在一個(gè)自己的小本子上同時(shí)把對應(yīng)的枚舉代碼段一起存下來。用的時(shí)候直接拿出來對一遍比重新推一遍快得多也比查網(wǎng)上的表放心得多。次數(shù)多了之后你會(huì)發(fā)現(xiàn)常用的就那么幾十個(gè)比如 4 次用 x^4x1、8 次用 x^8x^4x^3x^21、16 次用 x^16x^12x^3x1 這類手熟了之后看一眼系數(shù)就知道是不是三項(xiàng)式、奇偶性對不對直覺會(huì)變得很準(zhǔn)。 有限域不可約多項(xiàng)式與本原多項(xiàng)式：判定、手算與Python枚舉
不可約多項(xiàng)式和本原多項(xiàng)式這兩個(gè)詞第一次撞見基本都在有限域、糾錯(cuò)編碼或者 LFSR 的教材里公式一擺、符號一多人就開始飄。我第一次做 GF(2^8) 上的乘法器時(shí)隨手從網(wǎng)上抄了個(gè)八次多項(xiàng)式當(dāng)模仿真跑起來乘法逆元全錯(cuò)寄存器值滿屏亂飛查了大半天才發(fā)現(xiàn)那個(gè)多項(xiàng)式是可約的——它連一個(gè)有限域都撐不起來談何求逆。從那以后我養(yǎng)成一個(gè)習(xí)慣凡是涉及不可約多項(xiàng)式、本原多項(xiàng)式的選型一律自己算一遍、跑一遍代碼再往工程里填絕不信手里的表。這篇內(nèi)容就是把這件事說透。我會(huì)先把不可約和本原這兩個(gè)概念釘死再用大量手算例子把判定過程走一遍包括 GF(2) 和 GF(3) 上的一堆具體多項(xiàng)式然后給出一套完整的 Python 實(shí)現(xiàn)讓你不查表也能枚舉任意次數(shù)的不可約多項(xiàng)式和本原多項(xiàng)式。如果你在做 CRC、LFSR、Reed-Solomon、AES 的 S 盒、隨機(jī)數(shù)發(fā)生器或者只是被教材上的定理繞暈了這篇應(yīng)該能幫你省下幾個(gè)小時(shí)。全文計(jì)算過程我都寫全了你可以拿紙筆跟著對一遍。1. 先把概念釘死不可約多項(xiàng)式到底不可約在哪1.1 從沒有實(shí)根這個(gè)直覺說起不可約多項(xiàng)式的定義課本上一句話在域 F 上一個(gè)次數(shù)大于等于 1 的多項(xiàng)式 f(x)如果它不能寫成兩個(gè)次數(shù)都小于 deg(f) 且大于 0 的多項(xiàng)式的乘積就叫在 F 上不可約。這個(gè)定義里有兩個(gè)關(guān)鍵詞最容易被忽略一個(gè)是在哪個(gè)域上另一個(gè)是次數(shù)都小于 deg(f) 且大于 0。這兩個(gè)點(diǎn)直接決定了后面所有的坑。先說在哪個(gè)域上。x^21 在實(shí)數(shù)域上不可約因?yàn)闆]有任何實(shí)數(shù) x 讓 x^210判別式是負(fù)的。但放到復(fù)數(shù)域上x^21(xi)(x-i)就變成可約的了。同樣的道理x^2-2 在有理數(shù)域上不可約但在實(shí)數(shù)域上可約成 (x-√2)(x√2)。所以不可約永遠(yuǎn)是一個(gè)相對概念離開域的定義談不可約是沒有意義的。我們后面討論的域主要是有限域 GF(p) 和 GF(p^n)其中最常用的是 GF(2)。再說次數(shù)都小于 deg(f) 且大于 0。這里排除了乘一個(gè)常數(shù)的情況。比如在 GF(2) 上x^2x x·(x1)兩個(gè)因子都是 1 次所以 x^2x 可約。但 2x^22x 這種寫法在 GF(2) 里就等于 0根本不用討論。換成 GF(3)3x^2 這種常數(shù)倍數(shù)不算因式分解因?yàn)槌?shù)不影響能不能再分常數(shù)是單位元不是真正的因子。我見過最常見的誤判就是有人把在 GF(2) 上沒有根直接等同于不可約。這個(gè)等價(jià)關(guān)系只在次數(shù)不超過 3 的時(shí)候成立。到了 4 次及以上就開始失效因?yàn)?4 次多項(xiàng)式可以拆成兩個(gè) 2 次的乘積而這兩個(gè) 2 次因子各自都沒有一次因子所以整個(gè) 4 次多項(xiàng)式在 GF(2) 上照樣沒有根卻明明是可約的。最經(jīng)典的例子就是 f(x) x^4 x^2 1。代 x0 進(jìn)去得到 1代 x1 進(jìn)去得到 1111兩個(gè)取值都不是 0所以在 GF(2) 上沒有根。但它實(shí)際上等于 (x^2x1)^2展開一下x^4 x^2 1中間項(xiàng) 2x^3、2x^2 在 GF(2) 里全被 2 消掉2 次項(xiàng)剩一個(gè) x^2。這就是一個(gè)標(biāo)準(zhǔn)的 4 次可約、卻無根的例子。類似的還有 x^41在 GF(2) 上它等于 (x1)^4因?yàn)?(x1)^2 x^21再平方就是 x^41。這兩個(gè)例子建議你記牢面試和排錯(cuò)都用得上。提示判斷無根只是排除了一次因子可約還包含兩個(gè)高次因子相乘的情況。次數(shù)大于 3 時(shí)無根是最低門檻不是充分條件。1.2 本原多項(xiàng)式是不可約多項(xiàng)式里的優(yōu)選生不可約多項(xiàng)式只是分不開的多項(xiàng)式而本原多項(xiàng)式是在此基礎(chǔ)上再挑一層出來它不僅不可約而且它的某個(gè)根還是擴(kuò)域乘法群的生成元。具體說設(shè) f(x) 是 GF(q) 上次數(shù)為 n 的不可約多項(xiàng)式α 是它的一個(gè)根那么 α 一定落在擴(kuò)域 GF(q^n) 里。GF(q^n) 去掉零元之后是一個(gè)乘法群這個(gè)群的階是 q^n - 1。如果 α 的階恰好等于 q^n - 1也就是說 α 的冪能遍歷所有非零元素那么 α 就是一個(gè)本原元f(x) 就叫做 GF(q) 上的 n 次本原多項(xiàng)式。反過來說不可約多項(xiàng)式的根 α 的階一定是 q^n - 1 的因子但不一定等于它。只有當(dāng)這個(gè)階剛好頂滿 q^n - 1 時(shí)才升級為本原多項(xiàng)式。所以本原多項(xiàng)式一定不可約不可約多項(xiàng)式的卻不一定本原。這個(gè)方向千萬不能記反。舉一個(gè)具體的例子。在 GF(2) 上x^4x^3x^2x1 是 4 次不可約的但它的根 α 滿足 α^51階只有 5而 2^4-1155 只是 15 的因子。所以它是不可約但非本原。而 x^4x1 和 x^4x^31 這兩個(gè)多項(xiàng)式的根階都是 15它們都是本原的。這個(gè)區(qū)別在工程上非常要命。用 LFSR 做偽隨機(jī)序列時(shí)特征多項(xiàng)式必須是本原的才能保證序列周期達(dá)到最大長度 2^n-1如果只保證不可約周期可能只有 2^n-1 的某個(gè)因子序列會(huì)提前重復(fù)隨機(jī)性和統(tǒng)計(jì)特性直接崩掉。反過來做有限域乘法的時(shí)候只要不可約就夠了因?yàn)槌朔嬖拇嬖谛灾灰蕾囉蚪Y(jié)構(gòu)不依賴是不是本原。所以選型之前先問自己一句我要的是能構(gòu)成域還是要有滿周期這個(gè)問題的答案決定了你得驗(yàn)到哪一層。1.3 一張表看清兩者關(guān)系與計(jì)數(shù)規(guī)律不可約多項(xiàng)式和本原多項(xiàng)式的個(gè)數(shù)都有閉式公式這在做枚舉和交叉驗(yàn)證時(shí)特別有用。GF(q) 上首一 n 次不可約多項(xiàng)式的個(gè)數(shù)是N_q(n) (1/n) · Σ_{d|n} μ(d) · q^(n/d)其中 μ 是莫比烏斯函數(shù)取值規(guī)則是μ(1)1μ(素?cái)?shù))-1μ(素?cái)?shù)平方)0μ(兩個(gè)不同素?cái)?shù)之積)1。GF(q) 上 n 次本原多項(xiàng)式的個(gè)數(shù)是P_q(n) φ(q^n - 1) / nφ 是歐拉函數(shù)。注意本原多項(xiàng)式的個(gè)數(shù)只跟 q^n - 1 的因式分解有關(guān)跟 n 的因數(shù)關(guān)系不大這一點(diǎn)很多人第一次看會(huì)覺得別扭。把 q2 代進(jìn)去算一張常用表n不可約個(gè)數(shù) N_2(n)本原個(gè)數(shù) P_2(n)本原占比12150%211100%322100%43267%566100%69667%71818100%8301653%9564886%10996061%1118617695%1233514443%164080204850%表里 n2、3、5、7 這幾個(gè)本原占比 100% 的次數(shù)都是因?yàn)?2^n-1 是素?cái)?shù)。2^2-13、2^3-17、2^5-131、2^7-1127 都是素?cái)?shù)而 q^n-1 為素?cái)?shù)時(shí)除 1 以外的任何元素階都是 q^n-1所有不可約多項(xiàng)式的根都自動(dòng)是生成元。這就是為什么小次數(shù)的效果看起來很整齊一旦到了 n82^8-12553×5×17 有多個(gè)因子情況立刻復(fù)雜起來。拿 n4 手算一遍確認(rèn)公式不是騙人的。n4 的因子是 1、2、4μ(1)1、μ(2)-1、μ(4)0所以N_2(4) (1/4) × [1×2^4 (-1)×2^2 0×2^1] (1/4) × [16 - 4] 3確實(shí)只有 3 個(gè) 4 次不可約多項(xiàng)式。本原的個(gè)數(shù)2^4-115φ(15)φ(3)×φ(5)2×48P_2(4)8/42正好 2 個(gè)。而 GF(2) 上 4 次首一多項(xiàng)式總共只有 2^416 個(gè)可約的有 13 個(gè)不可約 3 個(gè)本原 2 個(gè)。這個(gè)比例在選型時(shí)挺有用的你以為隨手一抓就不可約其實(shí)命中率只有兩成不到。再看 n8N_2(8) (1/8)[2^8 - 2^4] (256-16)/8 30。P_2(8)2553×5×17φ(255)255×(2/3)×(4/5)×(16/17)128128/816。30 個(gè)不可約里只有 16 個(gè)本原另外 14 個(gè)的根階分別是 85、51、17、15 這些因子。所以如果你從網(wǎng)上隨便抓一個(gè)八次不可約多項(xiàng)式當(dāng) LFSR 的特征多項(xiàng)式有超過一半的概率拿到的是非本原的周期直接腰斬甚至只有原來的十幾分之一。2. GF(p)上判定不可約的三條實(shí)用路線2.1 低次2 次、3 次直接試根就夠次數(shù)是 2 或 3 的時(shí)候判定邏輯最簡單把域里所有元素代進(jìn)去只要有一個(gè)取值為 0就說明有一次因子可約如果全都不為 0就不可約。道理很直白。一個(gè) 2 次多項(xiàng)式如果能分解只能是1 次 × 1 次那就必須有一個(gè)一次因子 (x-a)也就意味著 f(a)0。3 次同理能分解的話必然是 1 次乘 2 次同樣要有一個(gè)根。所以 2 次、3 次不存在兩個(gè)高次因子相乘的退化情況試根法在這里是完全充分的。在 GF(2) 上只有 0 和 1 兩個(gè)元素要試。所有 2 次首一多項(xiàng)式有 4 個(gè)x^2、x^21、x^2x、x^2x1。逐個(gè)代x^2代 0 得 0有根可約。x^21代 1 得 110有根可約等于 (x1)^2。x^2x代 0 得 0有根可約等于 x(x1)。x^2x1代 0 得 1代 1 得 1111都非 0不可約。所以 GF(2) 上只有 x^2x1 一個(gè) 2 次不可約多項(xiàng)式跟公式 N_2(2)(1/2)(4-2)1 完全對得上。3 次在 GF(2) 上有 8 個(gè)首一多項(xiàng)式其中能分解的占 6 個(gè)剩下 2 個(gè)不可約x^3x1 和 x^3x^21。這兩個(gè)互為反序多項(xiàng)式系數(shù)順序倒過來在 GF(2) 上這種配對很常見后面枚舉時(shí)你會(huì)發(fā)現(xiàn)大量這種情況。換到 GF(3) 上做一遍體會(huì)一下 p2 的感覺。GF(3) 的元素是 0、1、2。所有 2 次首一多項(xiàng)式形如 x^2bxcb、c 各有 3 種取法共 9 個(gè)。逐個(gè)篩多項(xiàng)式x0x1x2判定x^2011可約x^21122不可約x^22200可約x^2x020可約x^2x1101可約x^2x2212不可約x^22x002可約x^22x1110可約x^22x2221不可約三個(gè)不可約x^21、x^2x2、x^22x2。跟公式 N_3(2)(1/2)(9-3)3 一致。這里有個(gè)小技巧值得說在 GF(p) 上用試根法時(shí)與其老老實(shí)實(shí)代 p 個(gè)值不如先算一下判別式。對 2 次多項(xiàng)式 x^2bxc它不可約當(dāng)且僅當(dāng) b^2-4c 不是 GF(p) 中的平方數(shù)且 p 為奇素?cái)?shù)。在 GF(3) 里0^20、1^21、2^21平方數(shù)集合是 {0,1}。x^21 的判別式是 0-4-4≡2 mod 32 不在 {0,1} 里所以不可約x^2x2 的判別式是 1-8-7≡2 mod 3同樣不在平方數(shù)集合里不可約x^22x2 的判別式是 4-8-4≡2 mod 3也不可約。三次都能秒判不用逐個(gè)代入。這個(gè)判據(jù)只對 2 次有效3 次以上就不成立了。注意試根法在次數(shù) ≥4 時(shí)只是必要條件。真正做工程的時(shí)候我通常先用試根法快速篩掉一大半可約的剩下的再上 Rabin 或者直接跑代碼。2.2 4 次以上先看階再用分圓多項(xiàng)式拆結(jié)構(gòu)次數(shù)到 4 以上試根法就不夠用了得換個(gè)思路。一個(gè)非常有效的觀察角度是分圓多項(xiàng)式。賽道上有個(gè)常用結(jié)論在 GF(q) 上x^m - 1 的因式分解跟 m 的素因子以及 q 在模 m 下的乘法階密切相關(guān)。具體說x^m-1 分解出的每個(gè)不可約因子其次數(shù)都等于 ord_m(q)也就是 q 模 m 的乘法階m 與 q 互素時(shí)。所有不可約因子次數(shù)相同個(gè)數(shù)就是 φ(m)/ord_m(q)。拿 GF(2) 上的 x^5-1 舉例。在 GF(2) 里減法和加法一樣x^5-1 x^51。因式分解出來是x^5 1 (x1)(x^4x^3x^2x1)m5q2ord_5(2) 是讓 2^k ≡ 1 (mod 5) 的最小 k。2^12、2^24、2^38≡3、2^416≡1所以 ord_5(2)4。φ(5)44/41說明除了那個(gè)一次因子 (x1) 之外剩下的是一個(gè) 4 次不可約多項(xiàng)式。這就直接證明了 x^4x^3x^2x1 在 GF(2) 上不可約完全不需要試根。這個(gè)方法特別好用因?yàn)樗雅卸ú豢杉s變成了算一個(gè)模意義下的乘法階。再舉 x^71 的例子。m7ord_7(2)2^12、2^24、2^38≡1所以 ord_7(2)3。φ(7)66/32說明除了 (x1) 之外剩下 6 次的部分 x^6x^5x^4x^3x^2x1 會(huì)拆成兩個(gè) 3 次不可約多項(xiàng)式。實(shí)際拆出來是x^6x^5x^4x^3x^2x1 (x^3x1)(x^3x^21)正好是前面提到的那兩個(gè) 3 次不可約多項(xiàng)式完全吻合。再看 9 次的情況這個(gè)例子后面講本原的時(shí)候還要用。x^91 在 GF(2) 上分解涉及的是 Φ_9(x) x^6x^31 這個(gè)九次分圓的一部分。ord_9(2)2^12、2^24、2^38≡-1、2^416≡7、2^514≡5、2^610≡1所以 ord_9(2)6。φ(9)66/61說明 Φ_9 本身就是一個(gè) 6 次不可約多項(xiàng)式。也就是 x^6x^31 不可約。順手再算一個(gè) 21 次的為后面 6 次多項(xiàng)式的階分布做準(zhǔn)備。ord_21(2)2^38、2^664≡1 (mod 21)中間 2^12、2^24 都不等于 1所以 ord_21(2)6。φ(21)1212/62說明 Φ_21 會(huì)拆成兩個(gè) 6 次不可約多項(xiàng)式。這兩只的根階都是 21。所以 6 次不可約多項(xiàng)式一共有三組來源兩組來自 Φ_21階 21一個(gè)來自 Φ_9階 9再加上本原的那 6 個(gè)階 63正好湊出 N_2(6)2169。這個(gè)分解思路在做枚舉驗(yàn)證時(shí)非常有用可以拿它當(dāng)標(biāo)準(zhǔn)答案去對代碼輸出。2.3 Rabin 判定法一條公式管到底附手算全過程分圓法靠的是恰好能對上 x^m-1這個(gè)條件遇到不對應(yīng)的多項(xiàng)式就不好使了。要一個(gè)普適的判定得請出 Rabin 不可約性測試。定理是這么說的設(shè) f 是 GF(q) 上次數(shù)為 n 的多項(xiàng)式f 不可約當(dāng)且僅當(dāng)下面兩條同時(shí)成立一是 x^(q^n) ≡ x (mod f) 二是對 n 的每個(gè)素因子 d都有 gcd(x^(q^(n/d)) - x, f) 1。第一條保證 f 的根都在 GF(q^n) 里第二條保證根不會(huì)掉進(jìn)任何一個(gè)真子域 GF(q^(n/d)) 里。兩條合起來說明 f 的所有根都是真正的 n 次代數(shù)元也就是 f 不可約。先用它驗(yàn)一個(gè)已知答案f x^4x^3x^2x1n4q2。n4 的素因子只有 d2n/d2第二步需要算 gcd(x^(2^2) - x, f) gcd(x^4x, f)。先算第一步。記 f 的關(guān)系式x^4 x^3x^2x1因?yàn)?x^4x^3x^2x10移項(xiàng)即可GF(2) 上加減一樣。x^4 x^3x^2x1 x^5 x·x^4 x^4x^3x^2x (x^3x^2x1)x^3x^2x 1x^5 居然等于 1這個(gè)結(jié)果很關(guān)鍵。繼續(xù) x^8 x^5·x^3 x^3 x^16 x^15·x (x^5)^3·x 1·x x所以 x^16 ≡ x (mod f)第一條滿足。再算 gcd。x^4x x(x^31) x(x1)(x^2x1)它的所有不可約因子是 x、x1、x^2x1。f 是 4 次如果它跟 x^4x 有公因子公因子只能是 x^2x1因?yàn)?f 沒有一次因子前面試根已經(jīng)確認(rèn)。而 (x^2x1)^2 x^4x^21 ≠ f所以 x^2x1 不整除 f兩者互素gcd1第二條也滿足。結(jié)論f 不可約。跟分圓法的判斷一致兩條路殊途同歸。再用它驗(yàn)一個(gè)可約的例子看看它是怎么抓住漏洞的。取 f x^4x^21 (x^2x1)^2n 還是 4d2。第一步f 的關(guān)系式是 x^4 x^21。 x^4 x^21 x^8 (x^4)^2 (x^21)^2 x^41 (x^21)1 x^2 x^16 (x^8)^2 (x^2)^2 x^4 x^21我們需要 x^16 ≡ x也就是 x^21 ≡ x顯然不成立兩者差 x^2x1非零。所以第一條就直接掛了根本不用算第二步。這個(gè)對比很有意思本原與否會(huì)影響 x 的階但可約與否會(huì)直接讓 x^(q^n) ≡ x 這個(gè)整體條件失效。注意 x^16 ≡ x 這一條本質(zhì)上是要求f 的所有根都落在 GF(q^n) 里對可約多項(xiàng)式來說只要有一個(gè)因子的次數(shù)不整除 n這個(gè)條件就崩。而 gcd 那一條是專門用來排除根的次數(shù)是 n 的真因子這種情況的。舉個(gè)需要靠第二條才能抓住的例子。取 f (x^2x1)(x^2x1)不行剛用過。換 f x^4x^3x^2x1 的兄弟四次的另一個(gè)可約情形f (x^2x1)(x^21)。展開x^4x^2x^3xx^21 x^4x^31……等一下x^2x^20x 剩一個(gè)所以是 x^4x^3x1。驗(yàn)一下 x111110有根是可約的這個(gè)例子太容易被試根法抓住。要構(gòu)造一個(gè)第一條滿足、第二條不滿足的最典型的是 f 本身不可約但次數(shù)不是 n……那不可能。真正的場景是 f 不可約且次數(shù)為真因子。比如取 f x^2x12 次不可約如果我們錯(cuò)把它當(dāng)成 4 次來測n 會(huì)算錯(cuò)實(shí)際它滿足 x^4 ≡ x (mod f)因?yàn)?x^31x^4x。而此時(shí) n4 的 d2n/d2要算 gcd(x^4x, f)。x^4x mod f xx 0gcd 就是 f 本身不等于 1第二條直接判死。這就是第二條的作用它把根的階太小、落在了真子域里這種情況篩掉。手算 Rabin 的時(shí)候有兩個(gè)提速技巧我自己常用。一個(gè)是別硬算 x^(q^n)一路用平方遞推x^2 → 平方得 x^4 → 平方得 x^8 → 平方得 x^16每一步做完立刻用 f 化簡。另一個(gè)是 gcd 那一步別真的去展開 x^(q^(n/d)) 這個(gè)多項(xiàng)式直接在商環(huán)里算出它的化簡結(jié)果再求 gcd因?yàn)?gcd 只跟化簡結(jié)果有關(guān)。次數(shù)一高這兩點(diǎn)能省掉大量時(shí)間。3. 本原多項(xiàng)式判定把階算明白就贏了一半3.1 階的三個(gè)性質(zhì)記住就不會(huì)錯(cuò)判定本原的核心就是算一個(gè)數(shù)根 α 的乘法階。圍繞它有三條性質(zhì)必須刻在腦子里。第一條階一定整除 q^n - 1。這不是巧合是拉格朗日定理的直接推論GF(q^n) 的非零元素構(gòu)成一個(gè)階為 q^n-1 的乘法群群中任何元素的階都整除群的階。所以算階的時(shí)候不用一個(gè)個(gè)往上試只需要在 q^n-1 的因子集合里找。第二條不可約多項(xiàng)式所有根的階都相同。這一點(diǎn)非常省事。f 的 n 個(gè)根是彼此共軛的α、α^q、α^(q^2)、…、α^(q^(n-1))共軛元素的階必然相等。所以你隨便取哪個(gè)根算階結(jié)果都一樣也正因?yàn)槿绱宋覀儾拍苷f這個(gè)多項(xiàng)式的階而不用特指是哪個(gè)根。第三條本原等價(jià)于階等于 q^n - 1。不是能整除且最大是嚴(yán)格的相等一個(gè)字都不能差。由此可以得到一個(gè)很實(shí)用的判定流程先確認(rèn)不可約然后算出 x 在商環(huán) GF(q)[x]/(f) 中的階如果等于 q^n-1 就是本原。之所以能拿 x 代替 α 來算是因?yàn)?α 就是 x 在商環(huán)里的像兩者階完全一致。有個(gè)細(xì)節(jié)我踩過坑判斷 x^k 是不是 1 的時(shí)候別忘了 k 要最小的那個(gè)。有人算到 x^151 就宣布本原完全沒檢查 x^3、x^5 是不是也等于 1。萬一是 x^51那階就是 5 而不是 15結(jié)論直接反了。正確的做法是先確認(rèn) x^(q^n-1)1再對 q^n-1 的每個(gè)素因子 p驗(yàn)證 x^((q^n-1)/p) ≠ 1。全部通過階才等于 q^n-1。3.2 手算階的完整流程以 x^4x^31 為例光說流程太干直接上完整的冪表。取 f x^4x^31在 GF(2) 上n4目標(biāo)階是 2^4-115。關(guān)系式x^4 x^31。逐次往上推kx^k 的化簡結(jié)果說明011x2x^23x^34x^31用關(guān)系式5x^3x1x·x^4 x^4x6x^3x^2x17x^2x18x^3x^2x9x^2110x^3x11x^3x^2112x113x^2x14x^3x^2151回到單位元x^15 確實(shí)等于 1而且從表里能直接看出來1 到 14 次冪沒有任何一個(gè)等于 1。所以階就是 15等于 2^4-1f 是本原多項(xiàng)式。再看一個(gè)反面例子f x^4x^3x^2x1。前面已經(jīng)算過 x^4 x^3x^2x1一步就得到 x^5 1。所以階是 5而 2^4-1155≠15不是本原的。這個(gè)多項(xiàng)式在 LFSR 里用起來周期只有 5序列短得可憐。順手把另一個(gè)本原的 4 次多項(xiàng)式 x^4x1 的冪表也貼出來方便你對照kx^k 化簡結(jié)果011x2x^23x^34x15x^2x6x^3x^27x^3x18x^219x^3x10x^2x111x^3x^2x12x^3x^2x113x^3x^2114x^31151兩張表對比著看你會(huì)發(fā)現(xiàn) x^7 和 x^7 就不一樣了在 x^4x1 里 x^7x^3x1在 x^4x^31 里 x^7x^2x1。這說明兩個(gè)本原多項(xiàng)式雖然都撐起 GF(16) 的乘法群但元素的編號也就是離散對數(shù)表是不同的。所以工程里換多項(xiàng)式就等價(jià)于換了一套對數(shù)表S 盒、CRC 表全得重算。這也是為什么我在項(xiàng)目里從不輕易改特征多項(xiàng)式。三個(gè)階段性的檢查點(diǎn)總結(jié)一下先看 x^(q^n-1) 是否等于 1再對 q^n-1 的每個(gè)素因子 p 檢查 x^((q^n-1)/p) 是否不等于 1兩條都過階就是滿的。以 15 為例153×5素因子是 3 和 5所以要額外驗(yàn) x^5≠1 和 x^3≠1。15/35、15/53都在表里能查到x^5x^3x1≠1、x^3x^3≠1通過。3.3 6 次不可約多項(xiàng)式的分歧63、21、9 三種階前面用分圓法算過GF(2) 上 6 次不可約多項(xiàng)式有 9 個(gè)其中 6 個(gè)本原階 632 個(gè)階為 211 個(gè)階為 9。這個(gè)分布是理解不可約不等于本原最好的教材。2^6-1633^2×7。63 的因子有 1、3、7、9、21、63。一個(gè) 6 次不可約多項(xiàng)式的根階必須是 63 的因子。理論上可能的階是 3、7、9、21、63但受次數(shù)必須等于 ord_m(2) 整除性的約束實(shí)際能出現(xiàn)的就是 63、21、9 三種。階為 9 的那一個(gè)是 x^6x^31也就是 Φ_9(x)。驗(yàn)證一下它的階設(shè) α 是根α^6 α^31那么 α^9 α^3·α^6 α^3(α^31) α^6α^3 (α^31)α^3 1。確實(shí) α^91。而且 α^3≠1否則 α^6 α^31 11... 等等如果 α^31那 α^6α^31 111 1 ≠ 0矛盾α^1≠1所以階就是 9。階為 21 的那兩個(gè)來自 Φ_21 的分解它們的冪次只會(huì)落在 21 個(gè)值上永遠(yuǎn)到不了 63。這兩個(gè)多項(xiàng)式具體是什么不重要重要的是這個(gè)事實(shí)同樣是 6 次不可約多項(xiàng)式用它們做 LFSR周期會(huì)從 63 掉到 21 或 9掉了三分之二還多。我在實(shí)際項(xiàng)目里見過更慘的有人用了一個(gè) 16 次的多項(xiàng)式做流密碼的驅(qū)動(dòng)序列2^16-1655353×5×17×257階的因子很多。他挑的那個(gè)多項(xiàng)式的階只有 255周期短了兩個(gè)數(shù)量級測試時(shí)看著隨機(jī)性還行實(shí)際在長時(shí)間抓包下序列重復(fù)得非常明顯。這類問題在短測試?yán)锔颈┞恫怀鰜碇荒芸刻崆鞍央A算清楚。所以我的建議是任何人讓你用一個(gè)特征多項(xiàng)式先問一句話它的階是多少答不上來的就用代碼跑一遍再談。3.4 三項(xiàng)式、五項(xiàng)式怎么選以及 8 次為什么沒有三項(xiàng)式選本原多項(xiàng)式的時(shí)候工程上有兩個(gè)偏好項(xiàng)數(shù)越少越好最高次項(xiàng)系數(shù)固定為 1中間只有少量非零系數(shù)。原因是硬件上每個(gè)非零系數(shù)對應(yīng)一個(gè)異或門或者一個(gè)抽頭項(xiàng)數(shù)越少LFSR 的反饋邏輯越省資源軟件上計(jì)算也越快。系數(shù)只有三項(xiàng)的形如 x^n x^k 1叫三項(xiàng)式是最理想的形態(tài)。但三項(xiàng)式不存在萬能的情況。一個(gè)基本事實(shí)是如果 n 是偶數(shù)任何 x^n x^k 1 只要 k 也是偶數(shù)它就是完全平方必然可約。比如 x^8x^41(x^4x^21)^2、x^8x^21(x^4x1)^2、x^8x^61(x^4x^31)^2全是這個(gè)套路。所以在 GF(2) 上要找不可約三項(xiàng)式k 必須是奇數(shù)。更麻煩的是有些次數(shù)上根本不存在不可約三項(xiàng)式。8 次就是最著名的例子13 次、16 次、19 次這些也在列。這一點(diǎn)你自己跑一遍枚舉就能確認(rèn)代碼在后面第 4 節(jié)。所以做 8 位 LFSR 的時(shí)候市面上流傳的抽頭組合沒有一個(gè)三項(xiàng)式的全得用五項(xiàng)式比如 x^8x^4x^3x^21、x^8x^6x^5x^41 這類。這里我要提醒一句網(wǎng)上流傳的本原多項(xiàng)式表質(zhì)量參差不齊我遇到過至少兩次抄錯(cuò)系數(shù)的情況。有的是印刷錯(cuò)誤有的是把不可約當(dāng)成本原列進(jìn)去了。所以我的習(xí)慣是候選多項(xiàng)式一律先用代碼驗(yàn)一遍不可約和本原兩個(gè)性質(zhì)驗(yàn)過了再往 RTL 里寫?；ㄎ宸昼婒?yàn)證比在板子上調(diào)三天強(qiáng)得多。還有一個(gè)容易被忽略的取舍項(xiàng)數(shù)少不等于性能好。在軟件實(shí)現(xiàn)里非零項(xiàng)的分布位置會(huì)影響緩存和指令流水有時(shí)候一個(gè)五項(xiàng)式的實(shí)際跑分反而比三項(xiàng)式更穩(wěn)。這個(gè)只能實(shí)測別光看公式。4. 從零寫代碼驗(yàn)證不查表也能自己算4.1 GF(2) 多項(xiàng)式運(yùn)算的位運(yùn)算實(shí)現(xiàn)前面全在紙上推現(xiàn)在把它工程化。GF(2) 上的多項(xiàng)式有個(gè)天然的好處系數(shù)只有 0 和 1可以用一個(gè)整數(shù)的二進(jìn)制位直接表示。比如 0b1011 表示 x^3x1bit i 對應(yīng) x^i 的系數(shù)。加法和減法在 GF(2) 上都是異或乘法和取模也都是位運(yùn)算寫起來非常短。先把基礎(chǔ)函數(shù)搭起來# GF(2) 多項(xiàng)式用整數(shù)位掩碼表示bit i x^i 的系數(shù) # 例如 0b1011 表示 x^3 x 1 def deg(a): return a.bit_length() - 1 def poly_mod(a, m): 在 GF(2) 上求 a mod m加減統(tǒng)一用異或 dm deg(m) while a and deg(a) dm: a ^ m (deg(a) - dm) return a def poly_mul(a, b, mNone): 多項(xiàng)式乘法給了 m 就在商環(huán)里做 r 0 while b: if b 1: r ^ a b 1 a 1 return r if m is None else poly_mod(r, m) def poly_gcd(a, b): 歐幾里得算法求最大公因式 while b: a, b b, poly_mod(a, b) return apoly_mod用的是長除法只要被除式的次數(shù)不低于除式次數(shù)就把除式左移相應(yīng)位數(shù)再異或回去。這里能直接用異或代替減法是因?yàn)?GF(2) 上 1-10 和 110 完全一樣。這個(gè)特性也解釋了為什么代碼這么短。poly_mul是標(biāo)準(zhǔn)的俄羅斯農(nóng)民乘法乘數(shù)逐位右移被乘數(shù)逐位左移遇到 1 就累加。注意這里我用的是邊乘邊不進(jìn)模最后統(tǒng)一取模對小次數(shù)完全夠用。如果要做 32 次以上的多項(xiàng)式建議改成邊乘邊取模否則中間結(jié)果會(huì)膨脹得很大。再補(bǔ)一個(gè)快速冪Rabin 判定和階的計(jì)算都要用def poly_powmod(base, e, m): base^e mod m快速冪 r 1 base poly_mod(base, m) while e: if e 1: r poly_mul(r, base, m) base poly_mul(base, base, m) e 1 return r4.2 枚舉所有 n 次不可約多項(xiàng)式并與公式對照有了基礎(chǔ)運(yùn)算不可約判定可以先寫個(gè)樸素版把所有次數(shù)不超過 n/2 的首一多項(xiàng)式都拿來試除一遍。邏輯上無腦但勝在正確性一目了然。def is_irreducible(f): 樸素試除法用所有次數(shù) deg(f)/2 的首一多項(xiàng)式試除 n deg(f) if n 0: return False for d in range(1, n // 2 1): for g in range(1 d, 1 (d 1)): # d 次首一多項(xiàng)式全集 if poly_mod(f, g) 0: return False return Truerange(1 d, 1 (d1))這個(gè)寫法值得說一下。所有次數(shù)恰好為 d 的首一多項(xiàng)式最高位一定是 1所以最低的值是 1d最高是 1(d1)-1正好是這么個(gè)左閉右開區(qū)間。這個(gè)技巧在后面枚舉時(shí)反復(fù)用到。跑一遍枚舉把所有 n 次不可約多項(xiàng)式列出來for n in range(1, 13): irr [f for f in range(1 n, 1 (n 1)) if is_irreducible(f)] print(n, len(irr), [bin(f) for f in irr])n4 時(shí)會(huì)輸出 3 個(gè)0b10011 (x^4x1)、0b11011 (x^4x^31)、0b11111 (x^4x^3x^2x1)。跟我前面手算的完全一致。n6 時(shí)會(huì)輸出 9 個(gè)。n8 時(shí)會(huì)輸出 30 個(gè)。這些數(shù)字跟公式 N_2(n) 算出來的就一一對上了這也是驗(yàn)證代碼有沒有寫錯(cuò)的最好方式。順便說一句性能。這個(gè)樸素版本枚舉 12 次多項(xiàng)式時(shí)每個(gè)候選要試除大約 Σ(2^d) ≈ 2^(n/21) 個(gè)除式總計(jì)算量對 n≤16 完全能接受跑起來就是幾秒鐘。真要上 20 次以上就得換成 Rabin 或者 Berlekamp別硬扛。4.3 用 Rabin 和階來判本原性不可約判完了接著判本原。先把 Rabin 實(shí)現(xiàn)出來它比試除法快得多def prime_factors(n): fs, d set(), 2 while d * d n: while n % d 0: fs.add(d) n // d d 1 if n 1: fs.add(n) return fs def rabin_irreducible(f): Rabin 不可約判定僅針對 GF(2) n deg(f) if n 1: return False # 條件一x^(2^n) ≡ x (mod f) if poly_powmod(2, 1 n, f) ! poly_mod(2, f): return False # 條件二對每個(gè)素因子 dgcd(x^(2^(n/d)) x, f) 1 for d in prime_factors(n): h poly_powmod(2, 1 (n // d), f) ^ 2 # 異或 2 就是減 x if poly_gcd(poly_mod(h, f), f) ! 1: return False return True這里有個(gè)實(shí)現(xiàn)細(xì)節(jié)要注意條件二里的減 x在 GF(2) 上就是異或 2因?yàn)?x 的位掩碼是 0b10。寫別的域的時(shí)候要老老實(shí)實(shí)用減法GF(2) 才能這么省事。再看階的計(jì)算這是判本原的核心def poly_order(f): 求 x 在 GF(2)[x]/(f) 里的階返回 None 表示 f 不可約性有問題 n deg(f) cur, k 1, 0 while True: cur poly_mul(cur, 2, f) # 每次乘一個(gè) x k 1 if cur 1: return k if k (1 n): return None def is_primitive(f): n deg(f) return is_irreducible(f) and poly_order(f) (1 n) - 1最后把兩者串起來把前面那張表跑出來for n in range(1, 13): irr [f for f in range(1 n, 1 (n 1)) if is_irreducible(f)] pri [f for f in irr if poly_order(f) (1 n) - 1] print(fn{n:2d} 不可約{len(irr):3d} 本原{len(pri):3d})輸出會(huì)是 1:2/1、2:1/1、3:2/2、4:3/2、5:6/6、6:9/6、7:18/18、8:30/16、9:56/48、10:99/60、11:186/176、12:335/144跟第 1.3 節(jié)那張表一字不差。到這一步你已經(jīng)有了一個(gè)完全可以自證的驗(yàn)證工具以后不管誰給你一個(gè)多項(xiàng)式三十行代碼就能驗(yàn)完再也不用求人。有個(gè)小優(yōu)化值得提一句。poly_order是老老實(shí)實(shí)一次乘一個(gè) x對 n16 要循環(huán) 65535 次還行n32 就是 40 億次跑不動(dòng)了。真要做大次數(shù)應(yīng)該改成先算 x^(2^n-1) 確認(rèn)是 1再對 2^n-1 的每個(gè)素因子 p 驗(yàn)證 x^((2^n-1)/p)≠1這樣只需 O(log n × 素因子個(gè)數(shù)) 次快速冪。這是把前面 3.1 節(jié)的理論直接用上了。4.4 用現(xiàn)成庫交叉驗(yàn)證別只信自己的代碼自己寫實(shí)現(xiàn)最大的風(fēng)險(xiǎn)是錯(cuò)得一致——邏輯本身有 bug但輸出內(nèi)部自洽你反而更放心。所以我一定會(huì)拿現(xiàn)成庫對一遍。用 sympy 驗(yàn)不可約性最省事from sympy import Poly, GF, symbols x symbols(x) f Poly(x**8 x**4 x**3 x**2 1, x, domainGF(2)) print(f.is_irreducible) # True用 galois 庫可以直接把不可約和本原的列表一起拉出來import galois print(galois.irreducible_polys(2, 8, reverseTrue)) print(galois.primitive_polys(2, 8, reverseTrue))如果你有 Sage 環(huán)境那更簡單一行搞定R.x PolynomialRing(GF(2)) f x^8 x^4 x^3 x^2 1 print(f.is_irreducible(), f.is_primitive())我習(xí)慣的做法是用自己寫的代碼生成一份列表用庫再生成一份兩邊取集合做差。只要差集為空就說明實(shí)現(xiàn)沒問題。這個(gè)方法幫我抓出過兩次 bug一次是poly_mod里忘了處理 a 歸零的情況導(dǎo)致死循環(huán)一次是階的循環(huán)上限設(shè)成了 2^n 而不是 2^n-1邊界上多算了一輪。這種錯(cuò)誤光靠看代碼很難發(fā)現(xiàn)必須交叉驗(yàn)證。提示不同庫的版本 API 可能略有差異尤其是 galois 的返回類型和參數(shù)名。以上代碼以常見版本為準(zhǔn)跑之前建議先確認(rèn)一下自己環(huán)境里的函數(shù)簽名。5. 踩坑記錄與速查表5.1 五個(gè)最容易翻車的點(diǎn)第一個(gè)把無根當(dāng)成不可約。前面反復(fù)強(qiáng)調(diào)過了次數(shù) ≥4 時(shí)這個(gè)等價(jià)關(guān)系不成立。典型的反例 x^4x^21(x^2x1)^2。我現(xiàn)在看新人代碼的習(xí)慣動(dòng)作就是搜一遍有沒有只判根就返回不可約的實(shí)現(xiàn)十個(gè)里面能抓到三個(gè)。第二個(gè)階算錯(cuò)。最常見的兩種錯(cuò)法一種是查到 x^k1 就收工沒確認(rèn) k 是不是最小的另一種是循環(huán)邊界寫錯(cuò)把 q^n-1 寫成 q^n 或者 q^n-2。這兩種錯(cuò)誤都不會(huì)報(bào)異常只會(huì)讓結(jié)論靜悄悄地錯(cuò)掉。我的做法是在代碼里加一條斷言算出來的階必須整除 q^n-1不整除就說明實(shí)現(xiàn)有問題。第三個(gè)特征多項(xiàng)式選成了不可約但非本原的。這個(gè)坑最隱蔽因?yàn)榉抡媾芷饋硪磺卸颊Ｖ皇侵芷诒阮A(yù)期短。判斷辦法很簡單如果 LFSR 的周期不是 2^n-1先懷疑多項(xiàng)式的階。第四個(gè)混淆 p 和 n。GF(p^n) 里 p 是特征是模的素?cái)?shù)n 是擴(kuò)張次數(shù)是多項(xiàng)式的次數(shù)。這兩個(gè)量在很多公式里同時(shí)出現(xiàn)抄公式的時(shí)候特別容易串位。我一般會(huì)在草稿上把每個(gè)符號的含義寫一遍再代入。第五個(gè)跨域使用結(jié)論。GF(2) 上的表不能直接搬到 GF(3) 或者 GF(2^8) 上用。比如判別式是不是平方數(shù)這個(gè)判據(jù)只對奇素?cái)?shù) p 的 2 次多項(xiàng)式成立在 GF(2) 上根本不適用因?yàn)?2 是偶素?cái)?shù)判別式公式退化。換域就得重算沒有捷徑。5.2 癥狀—原因—處理速查表現(xiàn)象可能原因處理方式有限域乘法求逆失敗或結(jié)果異常模多項(xiàng)式可約商環(huán)不是域用 Rabin 或試除確認(rèn)不可約LFSR 周期遠(yuǎn)小于 2^n-1特征多項(xiàng)式不可約但非本原計(jì)算 x 的階換成本原多項(xiàng)式代碼判不可約但試除能拆開只做了試根漏了高次因子補(bǔ)上 d≤n/2 的完整試除階算出來不整除 q^n-1循環(huán)邊界或關(guān)系式化簡寫錯(cuò)加整除斷言重查 poly_mod同一多項(xiàng)式在不同資料里結(jié)論沖突一份資料把不可約當(dāng)本原了自己跑一遍代碼以計(jì)算結(jié)果為準(zhǔn)8 次找不到三項(xiàng)式該次數(shù)確實(shí)不存在不可約三項(xiàng)式改用五項(xiàng)式如 x^8x^4x^3x^21換了特征多項(xiàng)式后 CRC/S 盒全錯(cuò)換多項(xiàng)式等于換了整個(gè)對數(shù)表所有派生表全部重新生成這張表基本覆蓋了我自己遇到過的所有情況。最后一條尤其值得強(qiáng)調(diào)模多項(xiàng)式和它派生出來的表是強(qiáng)綁定的改一個(gè)系數(shù)整張表就全變了不存在改一點(diǎn)點(diǎn)、影響一點(diǎn)點(diǎn)的情況。5.3 我自己用的驗(yàn)證流程跑過這么多項(xiàng)目之后我形成了一個(gè)固定動(dòng)作幾乎每次都按這個(gè)順序走一遍。第一步拿到候選多項(xiàng)式先轉(zhuǎn)成位掩碼跑is_irreducible。這一步過濾掉最基礎(chǔ)的錯(cuò)誤。第二步跑poly_order拿到 x 的階跟 2^n-1 比。相等才算過。第三步用庫交叉驗(yàn)證一遍確認(rèn)自己的代碼沒寫歪。第四步如果這個(gè)多項(xiàng)式要用在硬件上再檢查一下非零項(xiàng)的位置和數(shù)量評估異或門的開銷。第五步如果它要派生 S 盒、CRC 表或者對數(shù)表生成完之后再做一次一致性自測比如驗(yàn)證任意元素乘它的逆等于 1。這五步加起來可能要多花二十分鐘但相比在板子上調(diào)三天的成本完全值。我印象最深的一次是做一個(gè) 16 位 CRC掐著時(shí)間上線多項(xiàng)式是從一份老文檔里直接抄的。結(jié)果 CRC 的檢錯(cuò)能力明顯不達(dá)標(biāo)突發(fā)錯(cuò)誤測試通過率異常最后發(fā)現(xiàn)那個(gè)多項(xiàng)式壓根就是可約的。從那以后我再也沒跳過第一步。最后分享一個(gè)小習(xí)慣我會(huì)把每次項(xiàng)目里用到的本原多項(xiàng)式、它的階、驗(yàn)證時(shí)間記在一個(gè)自己的小本子上同時(shí)把對應(yīng)的枚舉代碼段一起存下來。用的時(shí)候直接拿出來對一遍比重新推一遍快得多也比查網(wǎng)上的表放心得多。次數(shù)多了之后你會(huì)發(fā)現(xiàn)常用的就那么幾十個(gè)比如 4 次用 x^4x1、8 次用 x^8x^4x^3x^21、16 次用 x^16x^12x^3x1 這類手熟了之后看一眼系數(shù)就知道是不是三項(xiàng)式、奇偶性對不對直覺會(huì)變得很準(zhǔn)。