動機
BCH 構造需要一個具有指定乘法階的元素。密碼學構造則關心某個指數是否仍然難以恢復。這是兩類不同的計算問題。找到合適的單位根可能很容易,而在它所在的循環群中恢復指數卻可能代價高得多。
我們先構造所需的單位根,再用兩種一般方法求解離散對數。小步大步算法以儲存空間換取平方根量級的搜尋。質數冪數位恢復則利用群的階的分解,把任務拆成若干較小的對數問題。兩者合起來說明:起決定作用的是階及其質因子,而不僅僅是域的大小。
這裏給出的是算法與上界,而不是密碼學困難性的證明。一個對階的二進制長度呈指數級的算法,並不能推翻多項式時間困難性假設;反過來,域很大本身也不能確立該假設。我們的計算使用前面各單元已經驗證過的域的表示。
定義
設 是含 個元素的域,其乘法群是大小為 的循環群。固定整除 的 ,並假定已給出 的質因子分解。對於帶有顯式長度為 的碼字的編碼應用,透過試除獲得該分解的成本對 是多項式的;我們並不聲稱對任意數的分解在 下具有多項式成本。
定義 14.3.1
(階與離散對數)
若 且沒有更小的正整數冪等於 ,則稱元素 的階為 。它的各次冪構成子群 。對 ,其離散對數是滿足 的唯一剩餘類 。零不是乘法群中的元素。
對於階為 的元素 , 的階是 :方程 等價於 ,其最小正解就是該商。我們使用精確的域乘法、求逆與取冪,並用規範的係數列表編碼來比較元素。
定理/命題
定理 14.3.2
(構造所要求階的單位根)
給定 的質因子分解以及有理數 ,可以在精確域運算下,以至少 的概率找到階恰為 的元素,否則報告失敗;所用時間關於 、 以及 的編碼長度是多項式的。每個返回的元素都經過確定性驗證。該過程既不要求分解 ,也不要求求解離散對數。
定理 14.3.3
(小步大步算法)
給定已知階為 的元素 與非零目標 ,可以判定 是否屬於 ,並在屬於時用 次群運算與 個儲存元素恢復其對數。確定性的表排序與查找另外需要 次編碼比較。
定理 14.3.4
(質數冪數位恢復)
若 已經分解,則對每個因子求解階為 的群中的 個對數,再用中國剩餘定理合併答案,即可恢復對數。若這些小對數用小步大步算法求解,則群運算的成本為
此外還有表比較以及已給定的整數/域運算。分解本身的成本被明確排除在外。
證明思路或證明
把均勻元素投影到目標子群
證明
(投影、精確的階檢驗與固定的失敗預算)
映射 從 出發,其像是唯一的階為 的子群。為看出這一點,把元素寫成該循環群某個抽象生成元的冪。指數乘以 後,恰好得到模 的 的所有倍數,每個值有 個原像。因此,均勻的非零域元素被映到該子群中的均勻元素,儘管算法並不知道那個抽象生成元。
候選元素 的階恰為 ,當且僅當 ,且對 的每個質因子 都有 。若其階是 的真因子,則商的某個質因子會使其中一個檢驗失敗。投影已經保證了第一個條件,但再驗證一次也無妨。
由冪的階公式,階為 的循環群中有 個生成元。對質數作容斥原理,得 。把不同質數按遞增順序排列,有 ,故該乘積至少為 。由於 ,對 ,它至少為 。
取整數 使 ,並嘗試 個相互獨立的投影候選。在理想的均勻非零抽樣下,全部失敗的概率至多為 。返回第一個通過精確階檢驗的候選。
為實現非零抽樣,用 個公平位元生成整數標號,並接受 到 之間的標號。把被接受的標號解釋為以 為基的係數列表,這是到非零域元素的雙射。每次嘗試成功的概率至少為 。把每次抽樣限制在 次嘗試之內,其中 。在相同位元上與不設上限的抽樣耦合,可知任何上限改變搜尋結果的概率至多為 。總失敗概率至多為 ,且所有預算都是固定的多項式量。標號只用於抽樣,絕不取代域運算。
階檢驗必須在 的每個質因子處進行;只做一個檢驗並不足夠。
反例模式
只檢驗一個質因子會接受錯誤的階
斷言:若 ,且對 的最大質因子 有 ,則 的階為 。取 、,其最大質因子為三,並取 。則
該候選通過在三處的檢驗,但其階是三而不是六;在二處的檢驗會發現這一點。修正後的命題就是上面所用的: 的階為 ,當且僅當 ,且對 的每個質因子 都有 。
讓一個小步與一個大步相匹配
證明
(碰撞搜尋及其成本)
成員判定首先有一個簡單而精確的檢驗: 當且僅當 。該子群已經包含 的 個不同的根,域上的根數界不容許再有其他根。零以及任何未通過成員檢驗的元素都應被拒絕。
令 。對 儲存小步 。對 計算大步 ,直到某個值與已存值相等。一次碰撞給出 ,於是返回模 約化後的該指數並加以驗證。
由於 ,每個指數 都有分解 ,其中 。因此對有效目標必然發生碰撞。相鄰的小步用乘以 得到;相鄰的大步用乘以 得到,所以次數為 。負冪使用域中的逆元,而不是離散對數的計算。對規範編碼排序並作二分查找,即得所述的確定性比較成本與儲存界。
群運算的次數並不是全部的位元成本。用 個素域係數表示的元素佔用 位元,所以除了下標之外,小步表佔用 位元。前面的算術算法使每次群運算的位元成本關於 是多項式的。比較兩個規範係數列表的最壞成本也與其長度成正比。
對這些列表排序僅僅是為精確編碼建立索引;它並沒有在元素上賦予與域相容的數值序。編碼標號可以按字典序比較,儘管域本身並不是有序域。雜湊表實現可以給出不同的期望查找界,但需要自己的數據結構假設。上述確定性的排序加搜尋估計避免了對該期望的依賴。最後,由於 可能超過 ,匹配的指數可能大於 。將其模 約化既不改變群中的值,也不改變唯一的對數剩餘類,而最後的等式檢驗使返回的答案可以直接驗證。
該表把對 個指數的窮舉搜尋改進為約 次群運算。若 約為 ,這仍然約為 次運算,對位元參數是指數級的:算法提供的是上界,並沒有相應的困難性定理。
由低位到高位恢復質數冪的數位
證明
(數位歸納與中國剩餘定理的合併)
對因子 ,投影到 與 。 的階為 ,未知指數是 。令 ,其階為 。
假設前 個數位已給出 ,用 到 之間的代表表示。寫 。則
更高的數位消失了,因為它們的指數是 的倍數。求解這個階為 的對數,令 ,並重複直到 。以 起步即完成歸納,並恢復整個質數冪剩餘類。
模數 兩兩互質。令 ,並由 Bézout 選取 使 。則 具有所有已恢復的剩餘。兩個解之差是每個互質的 的倍數,因而是它們乘積 的倍數,由此證明唯一性。
每個數位使用普通取冪,需 次群運算,外加一次階為 的小步大步搜尋。依次處理各質數冪可以重用儲存。因此,即使階很大,只要它只含小質因子,其對數就可能很容易求得。該定理並不假設分解總能被高效找到。
證明透視
哪個指數消去哪些數位
三個假設分別在不同地方進入。投影 用到 的階恰為 :只有這樣, 的階才恰為 , 的階才恰為 。若真正的階較小, 可能等於一,每個數位看起來都會是零。
關鍵的一步是兩邊同時消去。乘以 去掉已知的數位;取 次冪則把未知的高位部分 變成 的倍數而消失,當前數位則以 的形式保留。由於 而 的階為 ,這個小對數唯一確定 ,所以由 開始的歸納在 步後完成。模 的唯一性則來自中國剩餘定理一步中各 兩兩互質,而不是來自數位恢復本身。
例題詳解
例題 14.3.5
(十六元域中的五元單位根子群)
在 中,元素 的階為十五:僅有的質因子檢驗是 與 ,兩者都由不可約四次關係得出。因此 的階為五。它的五個冪是 的互不相同的根,適用於長度為五的循環構造。
隨機化投影可以從任意均勻的非零元素出發,不必是這個已知的本原元。立方把十五個元素均勻地映到那個五元子群上,每個輸出有三個原像。該五個元素中有四個是生成元,所以一次投影試驗成功的概率為 。
例題 14.3.6
(一次小步大步碰撞)
在模二十三下, 的階為十一。設 ,。小步為 。大步乘子的逆為 。第一個大步值是十三,不在表中;下一個是 ,與小步指數三匹配。故 ,且 驗證了結果。該表並不需要整數四模十一的逆;它用的是 的群逆元。
例題 14.3.7
(光滑階對數的四個二進制數位)
在模十七下,由於 , 的階為十六。取 ,。在 時,,所以第一個數位為一,。在 時,餘項為 ,其四次方為十六;下一個數位為一,。
在 時,餘項為 ,其平方為一,得數位零。在 時,餘項仍為十六,不需要再取冪,得數位一。因此 。直接相乘得 。每個小對數只有兩種可能;由於階是二的冪,不需要對大階作搜尋。
概念視角結構
對數是到剩餘類的同構
由於 的階為 ,映射 , 是群同構,而離散對數正是它的逆:它把 中的乘法變成剩餘類的加法。數位恢復就是透過中國剩餘定理來看這個同構。在 之下,升到 次冪把 映到其 階子群上,並把 送到 ,而後者恰好記錄 。因此成本界由最大的質數 主導。
常見錯誤
常見錯誤
(滿足 的元素不一定階為 )
單位元對每個 都滿足該方程。因此,投影到階為 的子群後,必須先通過生成元檢驗,其輸出才能充當所要求的元素。在 處的檢驗排除了每一個真階,而不是僅僅檢驗某個方便的指數。
常見錯誤
(高效的構造不是困難性的證明)
已驗證的域或本原元都不能證明某個密碼學假設。離散對數求解器在熟知的容易方向上給出共享密鑰求解器與判定檢驗,但困難性的逆命題需要另行論證。這裏的算法只展示了在所選群上假設可能失效的特定方式;它們並不證明能抵抗這些特定方法的群就是安全的。
總結
投影與經驗證的階檢驗,可以在顯式有界的失敗預算下構造循環碼所需的單位根。小步大步算法以平方根量級的儲存與群運算恢復子群中的任意對數。階已分解的群容許進行質數冪數位恢復與中國剩餘定理合併,這凸顯了小因子的重要性,同時明確保留了關於分解的假設。
練習
快速檢查
(為甚麼只靠 次冪投影而不作最後的階檢驗是不夠的?)
想一想投影後的元素可能落在哪些子群中。
解答 · 答案
投影落在正確的子群中,但也可能落在某個真子群中,包括其單位元。這些檢驗排除了 的所有真因子,從而保證了得到各座標冪互不相同所需的精確階。
快速檢查
(為甚麼 刻劃了由階為 的域元素生成的子群的成員資格?)
數一數該子群中已有多少個 的根。
解答 · 答案
該子群包含 的 個不同的根。域上的 次多項式不會有更多的根。因此非零成員檢驗恰好識別出這些冪。
快速檢查
(在數位恢復中,為甚麼所選的指數能消去未知的更高數位?)
追蹤未知餘項的指數被 的多少次冪整除。
解答
未知餘項的指數可被 整除。乘以 後,它可被 整除,而 正是投影後的生成元的階。當前數位則作為階為 的元素 的冪保留下來。
快速檢查
(為甚麼質數冪算法並不證明存在分解任意群的階的多項式時間算法?)
檢查算法接收的輸入是甚麼。
解答
它的質數冪分解在一開始就已給定。高效地利用已知的分解並不等於計算這個分解。試除對顯式的編碼長度 是多項式的,但對密碼學複雜度中使用的二進制長度 可能是指數級的。
快速檢查
(投影後的對數給出 與 。求 。)
用 與 代入中國剩餘定理公式。
解答
中國剩餘定理公式使用 與 。得 。直接驗證,七模三餘一、模五餘二,並且這些剩餘唯一確定它模十五的值。