密码学中的数学基础（一）

缺乏、安全感 2022-05-13 13:14 393阅读 0赞

学习了一门课《信息安全数学基础》，这门课主要讲述的是关于密码学的数学基础，这门课本质就是“初等数论 + 抽象代数”。我更愿意概括为“质数 + 代数系统”。本文的目的在于将这一门课用“质数 + 代数系统”两个部分以及“素数在基本代数系统的应用”一共三个部分总结起来，希望能够加深自己的印象。

第一部分：素数（亦称质数）

**素数的来源**

个人感觉是现在的基础数学系统还有很多不完备的地方，例如素数相关的理论，到现在都还没有定论，例如“黎曼猜想”，2018.9.24 日英国阿迪亚爵士宣称自己证明了“黎曼猜想”，但是他的报告，就像网友评论的“让物理学家尴尬，让数学家沉默”。素数现阶段还是让人们为之着迷的一个领域，就像杨老师曾说过，素数是数学皇冠上的明珠，是信息安全的“保护神”，大概就是如此吧。

**概念**

素数的概念并不陌生，小学时还曾经背诵过1~100以内的所有素数，事实表明这还是有用的，其中素数的定义就不在赘述。

**素数的相关定理**

素数看起来并不是像其他普通数字理论那样多么有连续性，素数似乎是以一种“离散”的方式，散落在整个数轴上，所以和它相关的理论似乎以也是挺独立的，并且在初等数论中，素数相关理论讨论的更是一些比较具体的场景。

**从素数的数量上看：**以下定理基本描述了素数的个数的基本问题。

定理1-1 素数有无穷多个。

定理1-2 素数在不超过x 的范围的个数。

定理1-3 欧拉定理

定理1-4 费马定理。

定理1-5 Wilson定理。

**第二部分：代数系统（模运算）**

在第二部分，我们只讨论一种运算----模运算，它广泛的存在于我们平时的数学运算中，其中10进制下的加减乘除运算，个人其实觉得也可以当作是一种“模10的运算”。

一个整数有几种表示方式：

第一种，欧几里得除法。

使用欧几里得除法，我们可以将任何一个整数表示成这种形式，其中我们最为感兴趣的就是余数，所以就有了同余的内容。

第二种，算术基本定理。

任意一个整数n>1都可以表示成素数的乘积，且在不考虑乘积顺序的情况下，该表达式是唯一的，推广的来说，可以表示成一些素数次方的乘积，并且不考虑素数的情况下也是唯一的。

数的表示方法还有很多，例如哥德尔数，多进制等在此不再继续讨论。

**基本的运算工具：**

最大公因数，最小公倍数这两个运算在模运算种非常重要，最大公因数描述了模运算的最大下界运算界限，当(a,b)=1时，自然不存在最大公因数了，换个角度来说对于这两个对象的有效模运算也进行到头了。同时最小公倍数描述了模运算的最小上界，倍数一定是最小公倍数的倍数。其中这里有一个最为重要的运算就是“**辗转相除求最大公因数**”,具体算法这里不再赘述（信息安全p22）。

定理2-1 整数a,b 互素的充分必要条件是存在整数s,t使得：

Sa + tb = 1 （这也是一个求逆元的方法）

**同余**：

同余顾名思义，就是有相同的余数的意思。

同余的定义：    a 模m同余b等同于m|a-b。

同于式的定义：  f(x)模m 同余b。只不过是换成了多项式。

二次同余的定义：x2模m 同余b。只不过换成了平方项。

**模同余具有的性质：**

1.首先这是一种等价关系，具有自反，对称，传递性。

2.满足加法和乘法。（在同余式运算种可以直接加，乘）

3.两个同余使用加法和乘法的组合也是同余的。（可计算性）

4.（d,m）= 1 模同余两边才可以约数。