動機
知道含 個符號的域存在,並沒有指明它的算術。具體計算需要選定一個不可約多項式、一種係數表示,以及乘法和除法的算法。反過來,若不加檢驗就把隨機的模多項式當作不可約的,則可能產生零因子,使後續所有解碼方程失效。
我們把存在性定理與一個有限的過程聯繫起來。首先在給定的多項式商中計算。然後用 Frobenius 冪和多項式最大公因式檢驗該商是否為域。最後,利用已證明的不可約多項式的密度,以規定的成功概率和有界的隨機性進行搜尋。搜尋不成功時報告失敗;它絕不會把未經驗證的環標為域。
最後一步還區分了不可約模多項式與本原乘法元素。BCH 碼需要特定階的根,這是一個額外條件,而不是表示該域後的自動結果。
定義
取給定的質數 和首一 次多項式 ,其中 。每個剩餘類用其係數列表 表示,意為 ,其中 。常數嵌入素域。若模多項式經驗證不可約,則商是大小為 的域 。
本章中的多項式除法和最大公因式計算在已知的係數域 上進行。它們並不假設所給的商是域。定義餘式
於是 是 的餘式。對 也作約化,可使公式對一次模多項式仍然正確。
一個域符號的算術表示使用變量 。訊息或循環碼字多項式可以使用另一個變量 ,以域元素為係數。把一個符號對 取模,與把一個循環碼字對 取模,是不同多項式環中的不同運算。
定理/命題
定理 14.2.1
(已驗證的商中的算術與逆元)
剩餘類的加法按係數模 進行。乘法則將代表元相乘後再對 取模。由 代表的剩餘類是單位,當且僅當 ;Bézout 恆等式 給出其逆元 。特別地,若 不可約,則每個非零剩餘類都有這樣的逆元。
定理 14.2.2
(有限的不可約性檢驗)
首一 次多項式 不可約,當且僅當
當 時,質因數列表為空。使用普通的精確多項式與模整數算術,該檢驗的代價關於 和 是多項式的。
定理 14.2.3
(失敗概率與運行時間有界的構造)
給定 和有理數 ,存在一個隨機算法,其運行時間關於 、 和 的編碼長度是多項式的(特別地,當 時,關於 是多項式的),它以至少 的概率返回一個不可約的 次模多項式,否則報告失敗。每個返回的模多項式都經確定性檢驗驗證;隨機性只影響發現過程,不影響所聲稱的域的正確性。
證明思路或證明
算術就是多項式算術再取餘
證明
(餘式保持環運算)
除以首一多項式 ,在每個剩餘類中給出一個次數小於 的代表元。先對這些代表元作加法和乘法再約化,保持環運算,因為 的倍數構成理想。若 ,約化後得 ,這就證明了逆元公式。反之,模 的逆元會給出這樣的恆等式,因此不可能存在非常數的公因式。
即使模多項式可約,這些論述仍然有效,只是某些非零剩餘類可能沒有逆元。例如,若 ,且兩個因式的次數都更小且為正,則 的非零剩餘類相乘為零。多項式最大公因式的計算會檢測出這一障礙,而不是試圖除以零因子。
對於已驗證的域,普通多項式乘法後接長除法,其代價是素域運算次數的多項式。隨著次數下降,擴展 Euclid 算法的代價也是多項式的。以二進制整數為指數的冪運算採用反覆平方。這些過程作用於由 個模 的剩餘組成的列表,沒有浮點捨入。打包的整數標記只是一種儲存約定,並不允許用模 的算術代替。
Frobenius 映射區分各種可能的因式次數
證明
(Frobenius 整除性與質數下標的最大公因式)
前面關於存在性的一章證明了:次數為 的首一不可約多項式 整除 ,當且僅當 。它還證明了該多項式無平方因式,因為其導數為負一。
若 是 次不可約多項式,則它整除 ,所以 。它不整除下標 處的任何更小的多項式,所以每個所示的最大公因式都為一。
反之,假設檢驗通過。第一個條件使 成為無平方因式的多項式 的因式。因此它的不可約因式互不相同,且次數 整除 。若有某個 ,取質數 整除 。則 ,於是該因式會同時整除 和 ,與其最大公因式檢驗矛盾。因此每個因式的次數都是 ,而 的次數只允許恰有一個這樣的因式。這就在不假設所給商已是域的前提下證明了不可約性。
巨大的指數 不必寫成多項式次數。迭代 使每個中間代表元的次數都低於 ;每一步使用 次商環乘法。共有 步,隨後是多項式最大公因式。整數次數 的質因數可以用試除法求得,其代價關於 是多項式的,而 本來就是顯式多項式輸入規模的一部分。該域檢驗不需要對 作因數分解。
證明透視
兩個條件如何分工
最後的條件 表示 ;由存在性一章,這把 的每個不可約因式的次數限制為 的因數。最大公因式條件再排除各個真因數,而且只需檢查少數幾個: 的每個真因數 都整除某個極大真因數 ( 為質數),所以對 的每個質因數做一次最大公因式檢驗,就涵蓋了全部真因數。兩步之後,每個不可約因式的次數都是 ,而 只容得下一個; 無平方因式固然方便,但這個計數並不需要它。所有除法都在係數域已知的 中進行,從不用到受檢商環中的逆元,所以論證不是循環的。
檢驗的兩半各自都不可缺少。
反例模式
單有最大公因式條件不能認證域
在 上取 ,次數為質數 。 的質因數只有它本身,所以檢驗的最大公因式部分只要求 ,即 在 中沒有根。確實 、。然而 是可約的。最後的條件能發現這一點: 整除 ,而它整除 僅當 ,所以 。反方向上,例題中的四次式 通過最後的條件,卻不通過一個最大公因式檢驗。正如定理所述,只有兩個條件合起來才刻畫不可約性。
不可約多項式足夠多,短搜尋即可
證明
(不可約多項式的計數與固定的候選預算)
令 為 次首一不可約多項式的個數。此前的計數恆等式給出 。對 ,真因數的貢獻為 。對 ,真因數的幾何級數上界小於 。因此對每個 ,都有 ;而當 時每個首一一次多項式都不可約,同樣的下界成立。
因此,均勻隨機選取的首一 次多項式通過檢驗的概率至少為 。取正整數 使 ,並嘗試 個獨立候選。在理想的係數均勻實驗中,所有候選都可約的概率至多為
對每個候選作確定性檢驗,返回第一個通過者。這一理想分析已經給出固定的候選預算;剩下的問題是如何用有界數量的公平位元抽取其係數。
明確核算係數抽樣
證明
(有上限的係數抽樣與耦合)
要在 中抽取一個係數,抽取 個公平位元,若所得整數小於 則接受。一次嘗試成功的概率為 ,且被接受的整數在 種選擇中是均勻的。每次係數調用至多嘗試 次,其中 。這類調用至多有 次,所以某次達到上限而失敗的概率至多為 。
為嚴格起見,把有上限的算法與使用相同新鮮嘗試位元的理想無上限係數抽取作比較。在出現上限失敗之前,它們產生相同的候選。並集界控制了第一次分歧,而無需以所有調用均成功為條件來討論整個搜尋。合併兩個失敗事件,得到至多 。所有計數器和位元預算都在執行前就有界,且不可約性檢驗是多項式的。合適的 透過對有理輸入作二的冪次整數比較而算出,因此不需要隱藏的數值捨入。
該算法以所述概率和資源界認證一個模多項式。它並不選出各實現共同使用的標準模多項式;所選多項式和基仍須作為約定表示的一部分被傳達或固定。
概念視角代數
兩個模多項式,同一個域的不同座標
不同的 次不可約模多項式給出同構的域,而同構由一個根給出。若 與 都是 次不可約多項式, 是 在 中的根,則 定義一個從 出發的環映射;由於來源是域,它是單射,再由計數知它是雙射。對 上的 與 ,記 ,由 得 ,所以 是 的根。
單獨檢驗乘法階
假設域已驗證,並且給出了 的因數分解。非零元素 生成其乘法群,當且僅當
證明
(階整除 )
事實上,它的階整除 。若階是真因數,則整除商的某個質數會使所示的某個冪等於一。反之,階為 的元素通過每個檢驗。對於 ,質數列表為空,唯一的非零元素生成平凡群。
在給定該整數分解的前提下,階的檢驗是高效的;這並不是說對每個 作因數分解都高效。若已知本原元 且 ,則由冪的階公式, 的階恰為 。這解釋了在 BCH 構造中得到單位根假設的一條標準途徑,同時使其前提條件清晰可見。
例題詳解
例題 14.2.4
(八符號字母表中的顯式逆元)
在 上, 沒有根,因此不可約。記 。兩個一次項和兩個常數項抵消後,乘法給出 。對於除法,注意如下精確的 Bézout 恆等式
因此 。在基 下,向量 與 相乘得 。若把它們的打包整數標記模八相乘,則是在有零因子的環中進行的另一種計算。
例題 14.2.5
(三元域中的符號)
取 。該模多項式在 中沒有根,所以商是九元域,且 。我們有 ,其在素域中的逆元是二。因此 ;直接相乘得 。
該域的特徵為三:三個 相加為零。它不是模九的整數算術。另外 的階是四而不是八,這說明了為甚麼不可約模多項式並不自動使其剩餘變量成為本原元。
例題 14.2.6
(通過檢驗的四次式,以及一個錯誤的捷徑)
對 上的 ,相繼的餘式為 ,, 和 。四的唯一質因數是二,且 ,所以最大公因式為一,檢驗證明其不可約。
相比之下, 能通過最後的 Frobenius 檢驗:在其商中 ,所以 。但較小的檢驗中 ,最大公因式為 而不是一。該模多項式可約,其非零剩餘類 與 相乘為零。僅憑最後的 Frobenius 等式無法區分域與這個環。
常見錯誤
常見錯誤
(把兩個多項式變量分開)
在 上的碼中, 描述單個符號的內部。碼字多項式 以許多這樣的符號為係數。對其 分量取模 ,並不意味著把碼字多項式 對同一個多項式取模。循環碼字的約化改用 ,而求值則是把一個域元素代入 。
常見錯誤
(壓縮標籤不是模 的整數)
在 中,以整數 作為 的標籤。於是 的標籤是 , 的標籤是 ,而第一個例題表明兩者之積為 。把標籤模 相乘卻得到 ,即 的標籤。更糟的是 ,但 。標籤只是儲存方式;算術必須作用於係數列表。
常見錯誤
(找不到模多項式並不是錯誤的證明)
隨機搜尋總會檢驗其結果。它可能在預算內找不到模多項式,但絕不可能把可約的候選作為已認證的域返回。增大預算會改變失敗概率的上界,而有效性的判據始終是確定性的。反過來,存在性證明或看似合理的乘法表都不是不可約性的證明。
總結
多項式餘式給出精確的符號算術,素域上的 Euclid 算法給出逆元。Frobenius 餘式與選定的最大公因式在多項式時間內證明不可約性。不可約多項式的密度進而給出帶明確失敗預算、隨機性有界的構造。乘法階的驗證是單獨的一步,其對因數分解的前提必須說明。
練習
快速檢查
(為甚麼 要對 取模,而不總是存為字面上的多項式 ?)
考慮一次的模多項式。
解答
對一次模多項式, 已經約化為一個常數。統一的公式將 與同一個剩餘類 比較。若把常數餘式與未約化的一次表達式比較,會錯誤地拒絕有效的一次模多項式。
快速檢查
(六次不可約性檢驗中,哪些更小的 Frobenius 下標已足夠?)
列出 的質因數。
解答
六的質因數是二和三,所以下標 和 已足夠,再加上最後的下標六。任何整除六的真因式次數至少整除這兩個較小下標之一,因而被某個最大公因式檢驗排除。
快速檢查
(在八元域中,為甚麼每個異於一的非零元素都是本原元?)
求乘法群的階。
解答
其乘法群是七階循環群,七為質數。異於乘法單位元的非零元素的階整除七且不為一,所以是七。這一特殊情形不能推廣到所有域的大小,九元域的例子就說明了這一點。
快速檢查
(為甚麼生成算法的正確性不依賴於隨機候選很可能不可約這一統計性保證?)
把「返回甚麼」與「多常返回」分開考慮。
解答
每個返回的候選都通過精確的充要檢驗。密度下界只控制有界搜尋返回候選而不是報告失敗的機會。偶然出現的一連串可約樣本會耗盡預算,但絕不會產生虛假的域證明。