信息安全的数学基础

在信息时代，信息是时间也是财富，这已是不争的事实。所以如何保护信息的安全，已经提到日程上来了。但研究信息安全涉及众多的数学基础，本书的目的也就是为研究信息安全提供必要的数学内容，主要内容包括数论、群论、组合论、素数的判定法、椭圆曲线、信息论等。

目录
第1章数论1
1.1整数1
1.2素数2
1.3最大公约数与欧几里得算法3
1.4欧几里得算法复杂性讨论5
1.5大数的因数分解6
1.6同余式7
1.7中国剩余定理10
1.8Gauss算法11
1.9古典密码举例之一: Kaiser密码12
1.10古典密码举例之二: 单表置换13
1.11古典密码举例之三: Vigenere密码17
1.12Wilson定理与Fermat定理20
1.13Euler定理21
1.14Euler定理帮助人们完成了一场密码学的革命22
1.15数字签名24
1.16KaratsubaOffman算法及中国剩余定理在解密过程中的应用24
1.17指数和原根25
1.18指标(离散对数)27
1.19Miller素数判定法28
1.20ElGamal公钥密码29
1.21平方剩余与非平方剩余，Legender符号31
1.22互倒定理33
1.23Jacobi符号37
习题41

第2章群论与有限域理论简介45
2.1群论45
2.2有限域51
习题57

第3章大数分解58
3.1Pollard p-1因数分解法58
3.2连分数因数分解法59
3.3Pollard ρ法64
3.4Dixon随机平方因数分解法65
习题66

第4章线性反馈移位寄存器67
4.1流码67
4.2线性反馈移位寄存器67
4.3Golomb随机性概念70
4.4非线性移位寄存器举例71
4.5LFSR的密码反馈75
习题76

第5章判定素数的算法77
5.1数学准备77
5.2概率算法79
5.3随机数的发生器80
5.4MillerRabin测试法82
5.5MillerRabin算法的有关定理83
5.6附录AKS确定型判定素数的多项式算法83
5.7符号与准备84
5.8AKS算法85
5.9正确性证明85
5.10复杂性分析88
5.11改进意见88
5.122002年的AKS算法88
习题89

第6章零知识证明简介90
6.1概念90
6.2身份的零知识证明91
6.3FiatShamir协议适于网上身份验证92
6.4Schnorr身份验证92
6.5FeigeFiatShamir身份验证协议92
6.6FeigeFiatShamir身份验证93
习题94

第7章大数快速算法与求离散对数95
7.1数的m进制表示95
7.2多位数的运算96
7.3离散对数106
7.4求离散的BabyStep giantstep算法107
7.5PohligHellman算法108
7.6Shank法109
7.7数指标的算法111
习题114

第8章椭圆曲线115
8.1Weierstrass方程115
8.2判别式与结式116
8.3椭圆曲线上的加法法则118
8.4椭圆曲线上的无穷远点及有限域上的椭圆曲线122
8.5GF(2k)上的椭圆曲线125
8.6P+(Q+R)=(P+Q)+R125
8.7椭圆曲线的密码127
8.8若干算法129
8.9复合域G((2n)m)简介130
习题132

第9章Lenstra因数分解法133
9.1mod n的椭圆曲线133
9.2算法的补充139
习题142

第10章信息论及编码143
10.1导论143
10.2Hamming距离143
10.3码字144
10.4熵的概念145
10.5熵的性质147
10.6条件熵148
10.7信道容量155
10.8无噪声信道158
10.9无噪声无记忆的编码理论160
10.10Huffman码161
10.11变长度码的译码方法163
10.12分组码，Hamming码164
10.13BCH码166
习题168

参考文献170
第6章零知识证明简介90
6.1概念90
6.2身份的零知识证明91
6.3FiatShamir协议适于网上身份验证92
6.4Schnorr身份验证92
6.5FeigeFiatShamir身份验证协议92第7章大数快速算法与求离散对数95
7.1数的m进制表示95
7.2多位数的运算96
习题106
7.3离散对数106
7.4求离散的BabyStep giantstep算法107
7.5PohligHellman算法108
7.6Shank法109
7.7数指标的算法111第8章椭圆曲线115
8.1Weierstrass方程115
8.2判别式与结式116
8.3椭圆曲线上的加法法则118
8.4椭圆曲线上的无穷远点及有限域上的椭圆曲线122
8.5GF(2k)上的椭圆曲线125
8.6P+(Q+R)=(P+Q)+R125
8.7椭圆曲线的密码127
8.8若干算法129
8.9复合域G((2n)m)简介130
习题132第9章Lenstra因数分解法133
9.1modn的椭圆曲线133
9.2算法的补充139
习题142第10章信息论及编码143
10.1导论143
10.2Hamming距离143
10.3码字144
10.4熵的概念145
10.5熵的性质147
10.6条件熵148
10.7信道容量155
10.8无噪声信道158
10.9无噪声无记忆的编码理论160
10.10Huffman码161
10.11变长度码的译码方法164
10.12分组码，Hamming码164
10.13BCH码167
习题168参考文献170第Ⅰ部分加法规则、乘法规则与排列组合1第Ⅱ部分序列、递推关系与母函数、Fibonacci数、Catalan数137第Ⅲ部分容斥原理、鸽巢原理与Ramsey数、Stirling数232第Ⅳ部分Polya定理307参考文献344