你的进度
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 码的多项式时间唯一译码,包括失败证书与未用完的错误预算。