该文章PDF文件过多，服务器拥堵，请耐心等待以防止页面卡死

写在前面

信息安全数学基础主要分为两个部分，数论部分与近世代数部分。一般而言，学校应该设置两个学期的课程，其主要是应用在密码学的方向上。首先要明确，数论也好，近世代数也好，是利用其设计更安全且效率更高的算法与协议，这是和数学系学的数论和近世代数的区别。但个人觉得，密码学给人带来的优美是最接近纯数学美妙的分支学科了。

对于数论部分，主要是这样几个模块：

  1. 整除与带余除法：Euclid带余除法（可以延伸到素数判别算法），进制问题（包括计算复杂度相关内容，以及Lucas定理，可以延伸到快速幂算法），Bezout定理（包括反向构造Bezout等式），最大公约数以及最小公倍数（相关性的恒等式），算数基本定理

  2. 同余问题：完全剩余系与简化剩余系（二者的区别与联系，数域的不同），几大定理（Fermat小定理，Euler定理，Wilson定理），模平方算法

  3. 同余方程：中国剩余定理（证明包括存在性和唯一性，应用（联合Bezout定理以及Lucas定理），算法的优化），高次同余方程，素数模的同余式

  4. 二次剩余：二次剩余的判别法（Euler判别法），Legendre符号与Jacobi符号及运算（分清区别），二次互反律（会运用），模平方根 ，(modp，modp2，modm2)，4k+3性特殊素数的的平方剩余解

  5. 指数与原根： 如何判断modp的原根， 如何构造modpα 的原根

  6. 不定方程：勾股方程，Pell方程，几类特殊的不定方程（包括Fermat圣诞树方程）

  7. 连分数：渐进分数，最佳逼近（列表求解），求展开式

  8. 素数分布：素数定理（渐进公式），艾森斯坦因筛法，Чебышев不等式（给出 π(x)的上下界），Betrand假设

  9. 数论函数：常见的数论函数，积性函数及判断的充要条件，麦比乌斯变换和反转公式，数论函数均值的渐进公式，狄里克莱特征及判定方法。

以及还要学习一些计算数论的内容：

  1. 素性检验：https://zhuanlan.zhihu.com/p/105902706

  2. 因子分解算法：Legendre同余，连分数，二次筛法和数域筛法，两类特殊的（Pollard的rho算法和p-1算法）

  3. 离散对数问题：Shanks小步大步算法，SPH算法

对于近世代数部分，主要分为以下模块：

  1. 群：群的定义（结合律，单位元，逆元），子群，陪集（拉格朗日定理），正规子群，商群，循环群（循环子群），置换群，群同态，同态分解定理

  2. 环：环的定义（加法交换律+乘法结合律/分配律），几种特殊的环（交换环（满足交换律），零因子环（有零因子），单位元环（有单位元），整环（有单位元，没零因子）），环同态，素域，分式域，理想（定义，与子群的区别和相同，主理想，主理想环，素理想，极大理想），多项式环（多项式整环，多项式理想，本原多项式，本原多项式的两种构造方法）

  3. 域：域的扩张（代数数，代数整数），Galois理论，可分域，闭包，有限域（构造有限域的几种方法，判断生成元），Frobenius映射（定义构造和具体构造），正规基

  4. 椭圆曲线： Fp,Fpn上的椭圆曲线计算，椭圆曲线的阶

剩下的就是对几个困难问题的使用，包括基于Trapdoor OWP的RSA假设和factoring假设，DH假设族的ELGamal问题以及DCR假设Pailliar问题。以及一些常用的数学手段包括双线性映射等的使用。

这些基本就是信息安全数学基础的大概框架。

内容参考：https://www.zhihu.com/question/56701402/answer/151163570

作者：沙金锐

此文章使用了较多的内嵌PDF阅读器，使用移动端访问会导致无法正常显示，请知悉

数论部分

数论部分建议不要去网上找资源，好好啃课本，讲的都很详细

如果实在想看网课，推荐 B站无尽沙砾

第一章 整数的可除性

知识点

习题

P48.习题 (6),(11),(17),(18),(32),(33)

第二章 同余

知识点

习题

P88.习题(1), (5), (6), (17)

P89.习题(16), (19), (23), (24)

第三章 同余式

知识点

习题

P121-123.习题(1), (3), (7), (17)

P123.习题 (16), (18), (23), (24)

第四章 二次同余式与平方剩余

知识点

习题

P163.习题(1),(2),(9),(13),(20)

P164-165.习题(22),(26),(35),(37)

模平方根没学太明白，就不误导人了。

第五章 原根与指标

原根一定要与模 m 互素。在数论中，一个整数 a 是模 m 的原根，意味着 a 的幂可以生成模 m 的所有剩余类。具体而言，如果 a 是模 m 的原根，那么对于所有与 m 互素的正整数 x，都存在一个整数 k，使得 ak≡x (modm) 。为了确保 a 是模 m 的原根，a 和 m 必须是互素的。如果它们有共同的因子，那么 a 的幂就不能覆盖整个剩余类。因此，a 和 m 互素是原根存在的必要条件。

知识点

习题

P196-197.习题 (1), (3), (7), (11), (13), (16)

第六章 素性检验

知识点

习题

P211.习题页(1),(5),(9),(14),(17),(19)

第七章 连分数

不做考察，大致了解一下即可

知识点

习题

无

近世代数部分

近世代数部分建议不要看着课本学习，课本中该部分错误很多，讲的也很一般

网络上近世代数的资源相对数论就比较丰富了，读者可自行查找，并且在信安数基的授课体系中其实不要求学生很会近世代数，大致学学差不多就可以了

第八章 发展史

在学习近视代数的理论知识之前，推荐先了解一下其背后的发展故事，意识到自己学的东西是在怎样的背景下诞生的，被拿来解决什么问题，会对近世代数的学习起到意想不到的帮助。

  • 简短的视频介绍

  • 详细且有趣的PPT介绍

第九章 群

素数阶的群必为循环群，这个性质很重要，尤其是在密码学中，我们总是引入素数阶的群，这个性质保证了我们引入的群具有循环群的一切特征，包括交换性、具有生成元。

第十章 环

第十一章 域

环里顺带说了一丢丢丢丢丢，这部分内容等假期有时间再补齐吧

知识框架

写在后面

非数理精通者，如看天书。匆匆一暼，尽皆术语，让人汗流浃背。数学之涩，易理之难。其行也远, 其路也艰, 虽千万里, 吾往矣。

信安数基的学习终于是告一段落，从零开始共花了十天时间，尽管取得了一些进展，但对于某些复杂的概念和定理，仍感到力有未逮，可惜期末周时间紧迫，悔之晚矣。其中数论学的比较细致，大概花了8天时间，近世代数就有点潦草了，只用两天不到就速成完毕了（古代数学天才一辈子研究的东西，用两天就搞完了，我>>天才🤪），对这门科目的整体掌握虽然称不上牛逼，但应付期末考试，也算是绰绰有余了。在数基的学习过程中，屡次沉醉于数学辽阔的天地，深深为其广博无垠所折服，这是在高数、线代、离散数学等其他学科上不曾有的。

这么难的一门学科，为什么要拖到期末考试前十天才开始学习？我本身其实是十分抵触这种需要一大段一大段证明定理、每个定理跟每个定理环环相扣、只要一个定理没看懂可能紧跟着下一个定理的证明也就看不懂的极其抽象的数学学科。也跟自己从小到大学习理科的习惯有关，即使一个定理有着很严谨的证明，逻辑十分的清晰明了，自己也懂，但都要在脑子里什么也不推理，纯看这个定理的最终公式，给出其的一个能够说服自己他为什么长这样的理由。举个例子：

对于这个公式，书上有着非常严谨合理的证明，自己也懂，但就是会在证明过后，又跳到这个公式页，重新在脑海中说服自己他为什么是这样（e可以使所有项都成立，所以它最差也是个欧拉(m)-1，这样要是所有的成立，那么每个起码都要先满足自己的指数等于1，等于1以后再多次也就一直都是1了，这样求出它们的最小公倍数，就每个都满足了，然后这时为什么存在一个a呢？巴拉巴拉...），就好像严谨的证明是说给表面的自己听的，脑子里的胡乱想是说给背后的自己听的😥。这样有好处也有坏处，对于以前简单的学习，每个定理都不会套太多层，都能重新这样想明白，让自己彻底把这些公式变成自己的东西，牢牢地记住、很好的理解，我觉的这算是自己将抽象的东西在脑海中进行了一次具象等价吧。但是一旦难度上来了，几页几页的证明，多个定理嵌套，互相引用，自己就想不明白了，无法将抽象的东西转化为自己所能理解的具象模拟并吸收，即使能证明明白，也记不住。根深蒂固的思维方式，是原因之一。再者，老师授课时不注重证明，更多的是念公式式的知识灌输而不是带着同学去理解，也就导致了大家都知其然不知其所以然。高数线代概率论等等之前的学科，更多注重的是计算，公式定理其实很少，理解起来没有什么太大问题。与数论类似的离散数学，虽然也抽象，但就好像是小学的思维拓展题，远没到难理解的程度。所以对其的学习就一直拖着，没想到一拖就到了期末，火烧眉毛，强迫自己看书，没想到也学了个八九不离十。期间无数次想给半年前的自己一个大嘴巴子，这么多奇妙的数学理论，要是跟着进度慢慢学，大把的时间供自己好好研究，建立一个清晰的知识体系，多么好的一件事，可惜时间不可逆转，下学期不这样了，这种期末考试窒息的感觉这辈子不想体验第二次了😭。

学完以后，我的所思所想。短短十天学习，好像给我的思维来了一次大升级，自己慢慢的可以接受一些极其抽象的理论，不在脑海中用自己具象的方式推理他，而是转而去想对其严谨的证明步骤，虽然还有点固性思维，但是一个好的开端。更重要的是，意识到自己的脑子不太适合做一些特别需要严谨思考的东西，以后尽量避开点🤣。数基学习中由于时间原因还留下好多遗憾，包括RSA加密、域的探究等等，假期我会再做一次更新总结，把没时间研究的都给解决了，画一个圆满的句号。

最后的最后，非常感谢你看到这里。如果你发现这篇文章有错误，请联系我（反正我也不会改）；如果你对内容有疑问，请联系我（反正我也没学明白）；如果你有相关问题想与我一起探讨，也请联系我（骗你的其实我学明白了🤪）。