不可約多項(xiàng)式和本原多項(xiàng)式這兩個(gè)詞第一次撞見基本都在有限域、糾錯(cuò)編碼或者 LFSR 的教材里公式一擺、符號(hào)一多人就開始飄。我第一次做 GF(2^8) 上的乘法器時(shí)隨手從網(wǎng)上抄了個(gè)八次多項(xiàng)式當(dāng)模仿真跑起來(lái)乘法逆元全錯(cuò)寄存器值滿屏亂飛查了大半天才發(fā)現(xiàn)那個(gè)多項(xiàng)式是可約的——它連一個(gè)有限域都撐不起來(lái)談何求逆。從那以后我養(yǎng)成一個(gè)習(xí)慣凡是涉及不可約多項(xiàng)式、本原多項(xiàng)式的選型一律自己算一遍、跑一遍代碼再往工程里填絕不信手里的表。這篇內(nèi)容就是把這件事說(shuō)透。我會(huì)先把不可約和本原這兩個(gè)概念釘死再用大量手算例子把判定過(guò)程走一遍包括 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ì)算過(guò)程我都寫全了你可以拿紙筆跟著對(duì)一遍。1. 先把概念釘死不可約多項(xiàng)式到底不可約在哪1.1 從沒(méi)有實(shí)根這個(gè)直覺說(shuō)起不可約多項(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)直接決定了后面所有的坑。先說(shuō)在哪個(gè)域上。x^21 在實(shí)數(shù)域上不可約因?yàn)闆](méi)有任何實(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è)相對(duì)概念離開域的定義談不可約是沒(méi)有意義的。我們后面討論的域主要是有限域 GF(p) 和 GF(p^n)其中最常用的是 GF(2)。再說(shuō)次數(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ù)是單位元不是真正的因子。我見過(guò)最常見的誤判就是有人把在 GF(2) 上沒(méi)有根直接等同于不可約。這個(gè)等價(jià)關(guān)系只在次數(shù)不超過(guò) 3 的時(shí)候成立。到了 4 次及以上就開始失效因?yàn)?4 次多項(xiàng)式可以拆成兩個(gè) 2 次的乘積而這兩個(gè) 2 次因子各自都沒(méi)有一次因子所以整個(gè) 4 次多項(xiàng)式在 GF(2) 上照樣沒(méi)有根卻明明是可約的。最經(jīng)典的例子就是 f(x) x^4 x^2 1。代 x0 進(jìn)去得到 1代 x1 進(jìn)去得到 1111兩個(gè)取值都不是 0所以在 GF(2) 上沒(méi)有根。但它實(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 次可約、卻無(wú)根的例子。類似的還有 x^41在 GF(2) 上它等于 (x1)^4因?yàn)?(x1)^2 x^21再平方就是 x^41。這兩個(gè)例子建議你記牢面試和排錯(cuò)都用得上。提示判斷無(wú)根只是排除了一次因子可約還包含兩個(gè)高次因子相乘的情況。次數(shù)大于 3 時(shí)無(wú)根是最低門檻不是充分條件。1.2 本原多項(xiàng)式是不可約多項(xiàng)式里的優(yōu)選生不可約多項(xiàng)式只是分不開的多項(xiàng)式而本原多項(xiàng)式是在此基礎(chǔ)上再挑一層出來(lái)它不僅不可約而且它的某個(gè)根還是擴(kuò)域乘法群的生成元。具體說(shuō)設(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也就是說(shuō) α 的冪能遍歷所有非零元素那么 α 就是一個(gè)本原元f(x) 就叫做 GF(q) 上的 n 次本原多項(xiàng)式。反過(guò)來(lái)說(shuō)不可約多項(xiàng)式的根 α 的階一定是 q^n - 1 的因子但不一定等于它。只有當(dāng)這個(gè)階剛好頂滿 q^n - 1 時(shí)才升級(jí)為本原多項(xiàng)式。所以本原多項(xiàng)式一定不可約不可約多項(xiàng)式的卻不一定本原。這個(gè)方向千萬(wàn)不能記反。舉一個(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á)到最大長(zhǎng)度 2^n-1如果只保證不可約周期可能只有 2^n-1 的某個(gè)因子序列會(huì)提前重復(fù)隨機(jī)性和統(tǒng)計(jì)特性直接崩掉。反過(guò)來(lái)做有限域乘法的時(shí)候只要不可約就夠了因?yàn)槌朔嬖拇嬖谛灾灰蕾囉蚪Y(jié)構(gòu)不依賴是不是本原。所以選型之前先問(wèn)自己一句我要的是能構(gòu)成域還是要有滿周期這個(gè)問(wèn)題的答案決定了你得驗(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ù)的效果看起來(lái)很整齊一旦到了 n82^8-12553×5×17 有多個(gè)因子情況立刻復(fù)雜起來(lái)。拿 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)式有超過(guò)一半的概率拿到的是非本原的周期直接腰斬甚至只有原來(lái)的十幾分之一。2. GF(p)上判定不可約的三條實(shí)用路線2.1 低次2 次、3 次直接試根就夠次數(shù)是 2 或 3 的時(shí)候判定邏輯最簡(jiǎn)單把域里所有元素代進(jìn)去只要有一個(gè)取值為 0就說(shuō)明有一次因子可約如果全都不為 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 完全對(duì)得上。3 次在 GF(2) 上有 8 個(gè)首一多項(xiàng)式其中能分解的占 6 個(gè)剩下 2 個(gè)不可約x^3x1 和 x^3x^21。這兩個(gè)互為反序多項(xiàng)式系數(shù)順序倒過(guò)來(lái)在 GF(2) 上這種配對(duì)很常見后面枚舉時(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è)小技巧值得說(shuō)在 GF(p) 上用試根法時(shí)與其老老實(shí)實(shí)代 p 個(gè)值不如先算一下判別式。對(duì) 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ù)只對(duì) 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)。具體說(shuō)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。因式分解出來(lái)是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說(shuō)明除了那個(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說(shuō)明除了 (x1) 之外剩下 6 次的部分 x^6x^5x^4x^3x^2x1 會(huì)拆成兩個(gè) 3 次不可約多項(xiàng)式。實(shí)際拆出來(lái)是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說(shuō)明 Φ_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說(shuō)明 Φ_21 會(huì)拆成兩個(gè) 6 次不可約多項(xiàng)式。這兩只的根階都是 21。所以 6 次不可約多項(xiàng)式一共有三組來(lái)源兩組來(lái)自 Φ_21階 21一個(gè)來(lái)自 Φ_9階 9再加上本原的那 6 個(gè)階 63正好湊出 N_2(6)2169。這個(gè)分解思路在做枚舉驗(yàn)證時(shí)非常有用可以拿它當(dāng)標(biāo)準(zhǔn)答案去對(duì)代碼輸出。2.3 Rabin 判定法一條公式管到底附手算全過(guò)程分圓法靠的是恰好能對(duì)上 x^m-1這個(gè)條件遇到不對(duì)應(yīng)的多項(xiàng)式就不好使了。要一個(gè)普適的判定得請(qǐng)出 Rabin 不可約性測(cè)試。定理是這么說(shuō)的設(shè) f 是 GF(q) 上次數(shù)為 n 的多項(xiàng)式f 不可約當(dāng)且僅當(dāng)下面兩條同時(shí)成立一是 x^(q^n) ≡ x (mod f) 二是對(duì) n 的每個(gè)素因子 d都有 gcd(x^(q^(n/d)) - x, f) 1。第一條保證 f 的根都在 GF(q^n) 里第二條保證根不會(huì)掉進(jìn)任何一個(gè)真子域 GF(q^(n/d)) 里。兩條合起來(lái)說(shuō)明 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 沒(méi)有一次因子前面試根已經(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è)對(duì)比很有意思本原與否會(huì)影響 x 的階但可約與否會(huì)直接讓 x^(q^n) ≡ x 這個(gè)整體條件失效。注意 x^16 ≡ x 這一條本質(zhì)上是要求f 的所有根都落在 GF(q^n) 里對(duì)可約多項(xiàng)式來(lái)說(shuō)只要有一個(gè)因子的次數(shù)不整除 n這個(gè)條件就崩。而 gcd 那一條是專門用來(lái)排除根的次數(shù)是 n 的真因子這種情況的。舉個(gè)需要靠第二條才能抓住的例子。取 f (x^2x1)(x^2x1)不行剛用過(guò)。換 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……那不可能。真正的場(chǎng)景是 f 不可約且次數(shù)為真因子。比如取 f x^2x12 次不可約如果我們錯(cuò)把它當(dāng)成 4 次來(lái)測(cè)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 化簡(jiǎn)。另一個(gè)是 gcd 那一步別真的去展開 x^(q^(n/d)) 這個(gè)多項(xiàng)式直接在商環(huán)里算出它的化簡(jiǎn)結(jié)果再求 gcd因?yàn)?gcd 只跟化簡(jiǎn)結(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(shuō)這個(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 代替 α 來(lái)算是因?yàn)?α 就是 x 在商環(huán)里的像兩者階完全一致。有個(gè)細(xì)節(jié)我踩過(guò)坑判斷 x^k 是不是 1 的時(shí)候別忘了 k 要最小的那個(gè)。有人算到 x^151 就宣布本原完全沒(méi)檢查 x^3、x^5 是不是也等于 1。萬(wàn)一是 x^51那階就是 5 而不是 15結(jié)論直接反了。正確的做法是先確認(rèn) x^(q^n-1)1再對(duì) q^n-1 的每個(gè)素因子 p驗(yàn)證 x^((q^n-1)/p) ≠ 1。全部通過(guò)階才等于 q^n-1。3.2 手算階的完整流程以 x^4x^31 為例光說(shuō)流程太干直接上完整的冪表。取 f x^4x^31在 GF(2) 上n4目標(biāo)階是 2^4-115。關(guān)系式x^4 x^31。逐次往上推kx^k 的化簡(jiǎn)結(jié)果說(shuō)明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而且從表里能直接看出來(lái)1 到 14 次冪沒(méi)有任何一個(gè)等于 1。所以階就是 15等于 2^4-1f 是本原多項(xiàng)式。再看一個(gè)反面例子f x^4x^3x^2x1。前面已經(jīng)算過(guò) x^4 x^3x^2x1一步就得到 x^5 1。所以階是 5而 2^4-1155≠15不是本原的。這個(gè)多項(xiàng)式在 LFSR 里用起來(lái)周期只有 5序列短得可憐。順手把另一個(gè)本原的 4 次多項(xiàng)式 x^4x1 的冪表也貼出來(lái)方便你對(duì)照kx^k 化簡(jiǎn)結(jié)果011x2x^23x^34x15x^2x6x^3x^27x^3x18x^219x^3x10x^2x111x^3x^2x12x^3x^2x113x^3x^2114x^31151兩張表對(duì)比著看你會(huì)發(fā)現(xiàn) x^7 和 x^7 就不一樣了在 x^4x1 里 x^7x^3x1在 x^4x^31 里 x^7x^2x1。這說(shuō)明兩個(gè)本原多項(xiàng)式雖然都撐起 GF(16) 的乘法群但元素的編號(hào)也就是離散對(duì)數(shù)表是不同的。所以工程里換多項(xiàng)式就等價(jià)于換了一套對(duì)數(shù)表S 盒、CRC 表全得重算。這也是為什么我在項(xiàng)目里從不輕易改特征多項(xiàng)式。三個(gè)階段性的檢查點(diǎn)總結(jié)一下先看 x^(q^n-1) 是否等于 1再對(duì) q^n-1 的每個(gè)素因子 p 檢查 x^((q^n-1)/p) 是否不等于 1兩條都過(guò)階就是滿的。以 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通過(guò)。3.3 6 次不可約多項(xiàng)式的分歧63、21、9 三種階前面用分圓法算過(guò)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è)來(lái)自 Φ_21 的分解它們的冪次只會(huì)落在 21 個(gè)值上永遠(yuǎn)到不了 63。這兩個(gè)多項(xiàng)式具體是什么不重要重要的是這個(gè)事實(shí)同樣是 6 次不可約多項(xiàng)式用它們做 LFSR周期會(huì)從 63 掉到 21 或 9掉了三分之二還多。我在實(shí)際項(xiàng)目里見過(guò)更慘的有人用了一個(gè) 16 次的多項(xiàng)式做流密碼的驅(qū)動(dòng)序列2^16-1655353×5×17×257階的因子很多。他挑的那個(gè)多項(xiàng)式的階只有 255周期短了兩個(gè)數(shù)量級(jí)測(cè)試時(shí)看著隨機(jī)性還行實(shí)際在長(zhǎng)時(shí)間抓包下序列重復(fù)得非常明顯。這類問(wèn)題在短測(cè)試?yán)锔颈┞恫怀鰜?lái)只能靠提前把階算清楚。所以我的建議是任何人讓你用一個(gè)特征多項(xiàng)式先問(wèn)一句話它的階是多少答不上來(lái)的就用代碼跑一遍再談。3.4 三項(xiàng)式、五項(xiàng)式怎么選以及 8 次為什么沒(méi)有三項(xiàng)式選本原多項(xiàng)式的時(shí)候工程上有兩個(gè)偏好項(xiàng)數(shù)越少越好最高次項(xiàng)系數(shù)固定為 1中間只有少量非零系數(shù)。原因是硬件上每個(gè)非零系數(shù)對(duì)應(yīng)一個(gè)異或門或者一個(gè)抽頭項(xiàng)數(shù)越少LFSR 的反饋邏輯越省資源軟件上計(jì)算也越快。系數(shù)只有三項(xiàng)的形如 x^n x^k 1叫三項(xiàng)式是最理想的形態(tài)。但三項(xiàng)式不存在萬(wàn)能的情況。一個(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í)候市面上流傳的抽頭組合沒(méi)有一個(gè)三項(xiàng)式的全得用五項(xiàng)式比如 x^8x^4x^3x^21、x^8x^6x^5x^41 這類。這里我要提醒一句網(wǎng)上流傳的本原多項(xiàng)式表質(zhì)量參差不齊我遇到過(guò)至少兩次抄錯(cuò)系數(shù)的情況。有的是印刷錯(cuò)誤有的是把不可約當(dāng)成本原列進(jìn)去了。所以我的習(xí)慣是候選多項(xiàng)式一律先用代碼驗(yàn)一遍不可約和本原兩個(gè)性質(zhì)驗(yàn)過(guò)了再往 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í)測(cè)別光看公式。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 對(duì)應(yīng) x^i 的系數(shù)。加法和減法在 GF(2) 上都是異或乘法和取模也都是位運(yùn)算寫起來(lái)非常短。先把基礎(chǔ)函數(shù)搭起來(lái)# 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用的是長(zhǎng)除法只要被除式的次數(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)一取模對(duì)小次數(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)式并與公式對(duì)照有了基礎(chǔ)運(yùn)算不可約判定可以先寫個(gè)樸素版把所有次數(shù)不超過(guò) n/2 的首一多項(xiàng)式都拿來(lái)試除一遍。邏輯上無(wú)腦但勝在正確性一目了然。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è)寫法值得說(shuō)一下。所有次數(shù)恰好為 d 的首一多項(xiàng)式最高位一定是 1所以最低的值是 1d最高是 1(d1)-1正好是這么個(gè)左閉右開區(qū)間。這個(gè)技巧在后面枚舉時(shí)反復(fù)用到。跑一遍枚舉把所有 n 次不可約多項(xiàng)式列出來(lái)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) 算出來(lái)的就一一對(duì)上了這也是驗(yàn)證代碼有沒(méi)有寫錯(cuò)的最好方式。順便說(shuō)一句性能。這個(gè)樸素版本枚舉 12 次多項(xiàng)式時(shí)每個(gè)候選要試除大約 Σ(2^d) ≈ 2^(n/21) 個(gè)除式總計(jì)算量對(duì) n≤16 完全能接受跑起來(lái)就是幾秒鐘。真要上 20 次以上就得換成 Rabin 或者 Berlekamp別硬扛。4.3 用 Rabin 和階來(lái)判本原性不可約判完了接著判本原。先把 Rabin 實(shí)現(xiàn)出來(lái)它比試除法快得多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 不可約判定僅針對(duì) 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 # 條件二對(duì)每個(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 不可約性有問(wèn)題 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最后把兩者串起來(lái)把前面那張表跑出來(lái)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)證工具以后不管誰(shuí)給你一個(gè)多項(xiàng)式三十行代碼就能驗(yàn)完再也不用求人。有個(gè)小優(yōu)化值得提一句。poly_order是老老實(shí)實(shí)一次乘一個(gè) x對(duì) n16 要循環(huán) 65535 次還行n32 就是 40 億次跑不動(dòng)了。真要做大次數(shù)應(yīng)該改成先算 x^(2^n-1) 確認(rèn)是 1再對(duì) 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)成庫(kù)交叉驗(yàn)證別只信自己的代碼自己寫實(shí)現(xiàn)最大的風(fēng)險(xiǎn)是錯(cuò)得一致——邏輯本身有 bug但輸出內(nèi)部自洽你反而更放心。所以我一定會(huì)拿現(xiàn)成庫(kù)對(duì)一遍。用 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 庫(kù)可以直接把不可約和本原的列表一起拉出來(lái)import galois print(galois.irreducible_polys(2, 8, reverseTrue)) print(galois.primitive_polys(2, 8, reverseTrue))如果你有 Sage 環(huán)境那更簡(jiǎn)單一行搞定R.x PolynomialRing(GF(2)) f x^8 x^4 x^3 x^2 1 print(f.is_irreducible(), f.is_primitive())我習(xí)慣的做法是用自己寫的代碼生成一份列表用庫(kù)再生成一份兩邊取集合做差。只要差集為空就說(shuō)明實(shí)現(xiàn)沒(méi)問(wèn)題。這個(gè)方法幫我抓出過(guò)兩次 bug一次是poly_mod里忘了處理 a 歸零的情況導(dǎo)致死循環(huán)一次是階的循環(huán)上限設(shè)成了 2^n 而不是 2^n-1邊界上多算了一輪。這種錯(cuò)誤光靠看代碼很難發(fā)現(xiàn)必須交叉驗(yàn)證。提示不同庫(kù)的版本 API 可能略有差異尤其是 galois 的返回類型和參數(shù)名。以上代碼以常見版本為準(zhǔn)跑之前建議先確認(rèn)一下自己環(huán)境里的函數(shù)簽名。5. 踩坑記錄與速查表5.1 五個(gè)最容易翻車的點(diǎn)第一個(gè)把無(wú)根當(dāng)成不可約。前面反復(fù)強(qiáng)調(diào)過(guò)了次數(shù) ≥4 時(shí)這個(gè)等價(jià)關(guān)系不成立。典型的反例 x^4x^21(x^2x1)^2。我現(xiàn)在看新人代碼的習(xí)慣動(dòng)作就是搜一遍有沒(méi)有只判根就返回不可約的實(shí)現(xiàn)十個(gè)里面能抓到三個(gè)。第二個(gè)階算錯(cuò)。最常見的兩種錯(cuò)法一種是查到 x^k1 就收工沒(méi)確認(rèn) k 是不是最小的另一種是循環(huán)邊界寫錯(cuò)把 q^n-1 寫成 q^n 或者 q^n-2。這兩種錯(cuò)誤都不會(huì)報(bào)異常只會(huì)讓結(jié)論靜悄悄地錯(cuò)掉。我的做法是在代碼里加一條斷言算出來(lái)的階必須整除 q^n-1不整除就說(shuō)明實(shí)現(xiàn)有問(wèn)題。第三個(gè)特征多項(xiàng)式選成了不可約但非本原的。這個(gè)坑最隱蔽因?yàn)榉抡媾芷饋?lái)一切都正常只是周期比預(yù)期短。判斷辦法很簡(jiǎn)單如果 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è)符號(hào)的含義寫一遍再代入。第五個(gè)跨域使用結(jié)論。GF(2) 上的表不能直接搬到 GF(3) 或者 GF(2^8) 上用。比如判別式是不是平方數(shù)這個(gè)判據(jù)只對(duì)奇素?cái)?shù) p 的 2 次多項(xiàng)式成立在 GF(2) 上根本不適用因?yàn)?2 是偶素?cái)?shù)判別式公式退化。換域就得重算沒(méi)有捷徑。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 的完整試除階算出來(lái)不整除 q^n-1循環(huán)邊界或關(guān)系式化簡(jiǎ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è)對(duì)數(shù)表所有派生表全部重新生成這張表基本覆蓋了我自己遇到過(guò)的所有情況。最后一條尤其值得強(qiáng)調(diào)模多項(xiàng)式和它派生出來(lái)的表是強(qiáng)綁定的改一個(gè)系數(shù)整張表就全變了不存在改一點(diǎn)點(diǎn)、影響一點(diǎn)點(diǎn)的情況。5.3 我自己用的驗(yàn)證流程跑過(guò)這么多項(xiàng)目之后我形成了一個(gè)固定動(dòng)作幾乎每次都按這個(gè)順序走一遍。第一步拿到候選多項(xiàng)式先轉(zhuǎn)成位掩碼跑is_irreducible。這一步過(guò)濾掉最基礎(chǔ)的錯(cuò)誤。第二步跑poly_order拿到 x 的階跟 2^n-1 比。相等才算過(guò)。第三步用庫(kù)交叉驗(yàn)證一遍確認(rèn)自己的代碼沒(méi)寫歪。第四步如果這個(gè)多項(xiàng)式要用在硬件上再檢查一下非零項(xiàng)的位置和數(shù)量評(píng)估異或門的開銷。第五步如果它要派生 S 盒、CRC 表或者對(duì)數(shù)表生成完之后再做一次一致性自測(cè)比如驗(yàn)證任意元素乘它的逆等于 1。這五步加起來(lái)可能要多花二十分鐘但相比在板子上調(diào)三天的成本完全值。我印象最深的一次是做一個(gè) 16 位 CRC掐著時(shí)間上線多項(xiàng)式是從一份老文檔里直接抄的。結(jié)果 CRC 的檢錯(cuò)能力明顯不達(dá)標(biāo)突發(fā)錯(cuò)誤測(cè)試通過(guò)率異常最后發(fā)現(xiàn)那個(gè)多項(xiàng)式壓根就是可約的。從那以后我再也沒(méi)跳過(guò)第一步。最后分享一個(gè)小習(xí)慣我會(huì)把每次項(xiàng)目里用到的本原多項(xiàng)式、它的階、驗(yàn)證時(shí)間記在一個(gè)自己的小本子上同時(shí)把對(duì)應(yīng)的枚舉代碼段一起存下來(lái)。用的時(shí)候直接拿出來(lái)對(duì)一遍比重新推一遍快得多也比查網(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)式、奇偶性對(duì)不對(duì)直覺會(huì)變得很準(zhǔn)。