你的進度
0/ 32 節已標記完成
下一節: 距離、線性碼與伴隨式
完成記錄儲存在此瀏覽器中。
這門課在網上
MATH4260 筆記裏的內容
- 定理卡
- 82
- 定義
- 48
- 反例
- 34
- 概念視角
- 22
- 思想史
- 6
- 證明透視
- 32
有思想史的節
- 重量枚舉多項式與 MacWilliams 對偶1.4
- 熵與二元前綴碼3.1
- ElGamal 加密與條件保密性證明4.2
- Schnorr 身份識別與隨機數重用4.4
- 矩陣密碼、週期密鑰與資訊洩露5.2
- 多項式求值、插值與最優距離16.1
這些思想史還沒有放上時間線。
這門課的概念視角還沒有記錄到網上。
數字只算這門課 32 節公開筆記裏寫了甚麼,不是網上已記錄的關係。目前其中 0 節已細緻地記錄到網上。
在網上定理卡 82 · 定義 48 · 反例 34 · 概念視角 22 · 思想史 6 · 證明透視 32
第 1 章 · 4 節
線性碼
二元域上的距離、糾錯與伴隨式。
- 1.1
距離、線性碼與伴隨式
推導糾錯保證、二元線性碼和伴隨式解碼。
- 1.2
擴展漢明碼與單錯糾正、雙錯檢測
推導擴展漢明碼的伴隨式解碼器、單錯糾正與雙錯檢測保證,以及保證不成立時的限制。
- 1.3
填充、覆蓋與碼大小的極限
證明有限與漸近形式的 Hamming、Gilbert–Varshamov 與 Plotkin 界,並區分存在性、線性性與有效構造。
- 1.4
重量枚舉多項式與 MacWilliams 對偶
利用加法特徵標的正交性推導對偶重量變換,得出精確的係數約束與矩約束,並檢驗候選碼的重量分佈。
第 2 章 · 2 節
2. 循環碼
連續根與有限伴隨式解碼器。
- 2.1
連續根與循環碼解碼
證明連續根距離下界,並為二元長度七循環碼解碼。
- 2.2
作為多項式理想的循環碼
將循環移位與模 x^n−1 的乘法聯繫起來,構造二元循環碼。
第 3 章 · 4 節
3. 資訊理論
有限信源的熵與二元前綴碼。
- 3.1
熵與二元前綴碼
推導熵下界,並為有限信源構造前綴碼。
- 3.2
Huffman 編碼與無損分塊信源碼率
證明貪心前綴碼算法及其精確的代價證書與熵界,然後說明獨立分塊如何逼近信源熵。
- 3.3
噪聲通道、互資訊與解碼逆定理
量度有限通道所保留的資訊,並證明可靠二元通訊的一個必要碼率界。
- 3.4
有限無記憶通道的編碼定理
透過資訊密度閾值解碼證明容量可達性,並對任意輸入相關性證明弱逆定理。
第 4 章 · 4 節
4. 公鑰算術
RSA 正確性與教材算術的安全界限。
- 4.1
RSA:模運算與公鑰加密
證明 RSA 在所有剩餘類上的正確性,並區分教材算術與安全加密。
- 4.2
ElGamal 加密與條件保密性證明
在判定性 Diffie–Hellman 假設下證明正確性與選擇明文安全性,說明有界公平位元取樣的誤差,並展示可延展性。
- 4.3
RSA 簽名與全域雜湊
定義選擇訊息偽造,展示教科書式 RSA 的攻擊,並在隨機預言機模型中證明一個條件性的全域雜湊定理。
- 4.4
Schnorr 身份識別與隨機數重用
證明離散對數身份識別協議的正確性、提取性與誠實驗證者模擬,然後考察其簽名變換與隨機數(nonce)失效。
第 5 章 · 2 節
5. 古典密碼
仿射代換與精確資訊洩漏。
- 5.1
古典密碼:仿射密碼及其保留的資訊
推導仿射解密公式,從已知觀察恢復密鑰,並區分精確的資訊洩漏與統計頻率分析。
- 5.2
矩陣密碼、週期密鑰與資訊洩露
用模線性代數、已知明文與精確的保密性障礙來分析 Hill 密碼與 Vigenère 密碼。
第 6 章 · 1 節
6. 信源壓縮
構造最優有限二元前綴碼。
- 6.1
Huffman 編碼與最優前綴樹
證明貪心構造對有限信源的期望前綴碼長度最小。
第 7 章 · 1 節
7. 噪聲通道
研究二元對稱通道的資訊與糾錯。
- 7.1
二元對稱通道與重複碼
計算單次使用通道的互資訊,並在明確的噪聲模型下研究有限重複碼。
第 8 章 · 1 節
8. 秘密分享
證明門檻重建及資訊論保密性。
- 8.1
多項式門檻秘密分享
證明有限域門檻方案的重建性及完全保密性。
第 9 章 · 1 節
9. 多項式求值碼
研究求值碼的距離、錯誤與擦除。
- 9.1
求值碼、錯誤與擦除
推導多項式求值碼的距離和錯誤與擦除保證。
第 10 章 · 2 節
10. 密鑰協商
研究模運算密鑰協商及其安全假設。
- 10.1
Diffie–Hellman 密鑰協商
推導模運算密鑰協商,區分其算術、身份認證和安全性。
- 10.2
Diffie–Hellman 安全實驗
比較被動安全實驗、計算假設與主動替換。
第 11 章 · 1 節
11. 訊息認證
研究一次性認證實驗及其限制。
- 11.1
一次性認證實驗
證明一次性仿射標籤的替換機率,並研究密鑰重用。
第 12 章 · 1 節
12. 譯碼限制
連結有限字母表的估計錯誤與條件熵。
- 12.1
錯誤機率與條件熵
證明有限字母表的 Fano 界並解釋其限制。
第 13 章 · 1 節
13. 編碼界
比較貪心存在性界與漢明裝箱界。
- 13.1
貪心碼與漢明界
以貪心法構造有限碼,比較存在性與裝箱界。
第 14 章 · 3 節
有限域
有限域的構造、結構與離散對數。
- 14.1
有限域為何存在,以及其子域如何互相嵌套
由不可約多項式構造有限域,並證明其元素個數為質數冪、非零元乘法群是循環群、Frobenius 映射的週期以及子域的分類。
- 14.2
以可驗證的檢驗來計算並構造有限域
實現多項式剩餘類算術,證明一個不可約性檢驗,並給出帶明確失敗概率、隨機性有界的有限域構造。
- 14.3
元素的階、單位根與離散對數
構造指定階的單位根,並在明確的成本假設下證明小步大步算法與質數冪離散對數算法。
第 15 章 · 2 節
BCH 碼
BCH 碼的設計距離與伴隨式解碼。
- 15.1
連續根與 BCH 距離保證
由擴域中的根構造循環碼,證明范德蒙距離界,並構造一個長度為十五的二元碼。
- 15.2
由 BCH 伴隨式定位兩個位元錯誤
為二元長度十五的 BCH 碼推導完整的二錯解碼器,並區分有保證的糾正與錯誤半徑之外的行為。
第 16 章 · 2 節
求值碼
Reed-Solomon 碼與 Berlekamp-Welch 解碼。
- 16.1
多項式求值、插值與最優距離
構造 Reed–Solomon 碼,證明其參數與擦除恢復,並由插值推導校驗關係。
- 16.2
未知錯誤化為線性方程組
利用首一錯誤定位多項式證明 Reed–Solomon 碼的多項式時間唯一解碼,包括失敗證書與未用完的錯誤預算。