信息安全数学基础 – Sigma的学海

作者：贾春福

第三章同余

同余式中除法的性质：
1.一般的，若ac≡bc(mod m),且(c,m)=d,则a≡b(mod m/d)
2.当c|m，(c,m)=c,ac≡bc(mod m)→a≡b(mod m/c)
3.当(c,m)=1,ac≡bc(mod m)→a≡b(mod m)

[剩余类和剩余系]
剩余类：假设给定一个整数M，我们知道mod M的结果是 0到M-1，假如设定一个整数R，那么所有mod M之后等于R的整数构成一个集合，这个集合叫做模M的一个剩余类记为C_R，剩余类是有限的。以M=5为例子，他就有C0,C1,C2,C3,C4，在每一个剩余类中任意一个整数可以叫做代表元，比如C1就可以用6做代表元

还是以M=5为例子，从C0到C4分别找一个代表元，这些代表元组成一个集合，叫做模M的一个完全剩余系（完系），注意，完系中的元素两两模M不同余

[欧拉定理和费马小定理]
欧拉函数：一个整数M，M的所有剩余类中与M互素的剩余类的个数。
以M=6作为例子，在模6的剩余类我取 {0，1，2，3，4，5}，可以看到1，5跟6互素，所以6的欧拉函数是2.
对于素数的欧拉函数，是素数-1.比如M=7，7的欧拉函数=（7-1）=6
记得0跟任何数不互素，1的欧拉函数是1，2的欧拉函数是1，3的欧拉函数是2

[缩系/简化剩余系]：在与M互素的剩余类中找代表元组成的集合（元素个数是M的欧拉函数）
比如模6的缩系是{1，5}

[欧拉定理]：M>1,(a,m)=1,有 a^φ(M)≡1 mod M

[费马小定理]：P是素数，对任意整数a，有 a^P≡a mod P

φ(m₁,m₂)= φ (m₁) φ (m₂) //当m1,m2互素

φ (m)=m·(1-1/p_i) //如 φ (240)= φ (2⁴·3·5)=240·(1-1/2)(1-1/3)(1-1/5)=64

[扩展欧几里得]：用来求乘法逆元的，比如一份a要摸m得到1，即求a的乘法逆元a^-1
a^-1a≡1 mod m
方法如下图

【例】a=4，m=9
ri qi si ti
9 – 1 0
4 2 0 1
1 4 1 -2
0
∵(r₀,r₁)=s_nr₀+t_nr₁=9×1+4×(-2)=1
∴4^–≡7 mod 9
【n为ri=0的上一个i】

[威尔逊定理]：P是一个素数，则(p-1)!≡-1 mod P

[线性同余方程]：f(x)≡0 mod m
若f(x₀)≡0 mod m 则x≡x₀ mod m，x₀称为解
求解时，依次把数字(0至m-1)带入，如果算出的结果mod m 之后为0，就有解否则无解。

求解同余方程：

若m>1,(a,m)=d>1,d|b是同余方程ax≡b mod m的充要条件，如果有解，解的个数是d，
如果x≡x₀ mod m，是特解，那么它的d个解为：x≡x₀+(m/d)t mod m,t=0,1….d-1

[例题]：

[中国剩余定理]：

以上图为例子
1.先计算m
m=m1+m2+m3+m4
2.再计算出M1,M2,M3,M4,M5,M6
Mi=m/m_i //如M1=m/m1
3.然后计算M’,注意M·M’≡1 mod m_i
4.计算方程组的解：x≡M1M’1b1+M2M’2b2+…+M4M’4b4 mod m

[同余方程组]：

解题思路是：
1.求d=(m1,m2)
2.求b1-b2
3.若d|b1-b2,有解且解模数为 [m1,m2]
4.后续计算如例子：
假设方程组为
x≡5 mod 12
x≡11 mod 18
d=(12,18)=6,b1-b2=5-11=-6,6|-6,所以有解，模数为[12,18]=36
令x=5+12k，然后带入x≡11 mod 18中得
5+12k≡11 mod 18
12k≡6 mod 18 //可以两边除去6得
2k≡1 mod 3 //求出k为2
K=2+3k //把新求出的K带入x≡5 mod 12k 中得
x≡5+12(2+3k) //化简后得
x≡29+36k mod 36
x≡26 mod 36 //此为方程组的解，若下面还有式子，用本条继续使用同样的方法算。

下面一个例子：

第四章原根与指数

[次数]：因为a^φ(m)≡1 mod m，当a得l次幂≡1 mod m，l< ^φ(m) ,就说l是a对模m得次数

记作ord_m(a)

找次数就可以一个个试，从i=1试到i=m-1，如下图

当存在一个整数n是ord_m(a)得整数倍，即 ord_m(a) |n，有aⁿ≡1 mod m

次数的一些性质，如下图

由于次数有以上性质，所以计算的时候可以简化，例子如下：

信安数学得知识虽然底层但是十分重要，之前学了怎么求同余方程，下面的知识点，在求指数上派上用场

下面是求aⁿ模m得次数求法，是之前学过的推广，如下图

下面是一些性质，重要

【原根】：

要判断原根的方法：

下面是很重要的知识点，如果一个数有原根，那么原根数量是知道的，如下图

怎么判断一个数有没有原根呢？如下图：

找原根的方法，如下图：

从2开始试，直到找到所有g不恒等1的元素，他们就是原根，举例子：

找到一个最小的原根了，下面是要把所有的原根找出来，方法是找到φ(m)=40的缩系，然后把里面的元素挨个放到6头上算，就能得到所有原根，如下图：

[指数与高次剩余]

也就是用到4.1.3的知识，注意涉及指数，会频繁使用mod φ(m)，比如下面的定理

与一般的指数，对数思路一样，可以得到一些性质方便计算，如下：

下面是几个重要的定理，用于计算：

下面是求n次剩余

下面求二次剩余

下面是求同余方程的例子：

第五章二次剩余

定义如下图

求解二次同余方程的例子：

梳理一下解题思路：
1.首先求d，也就是用中学的判定条件来算，d=b²-4ac //在这里是(-6)²-4×5×2=-4
2.然后设 y²≡d mod m //这里是y²≡-4，而-4≡9 mod 13，所以y²≡-4≡9 mod 13
3.根据上面的式子求出y的解，y₁，y₂ //这里是解出y的解是3，10，因为3×3=9，模13是9，10×10=100，模13是9
4.列出2ax≡y-b mod m的式子 // 这里是2×5=10，y的解是3和10，所以y-b是3-(-6)=9,10-(-6)=16
即 10x≡9 mod 13 ； 10x≡16 mod 13
5.根据x≡x₀=(2a)^-1·（y-b）算出解 //这里2a是10，所以算出10模13的乘法逆元是4，因为4×10=40，40≡1 mod 13，y-b是9和16，x的解是4×9=36≡10 mod 13；4×16=64≡12 mod 13

也相当于对m素因数分解，x²≡a(mod p_i),p_i是m的素因数

判断二次剩余和二次非剩余的方法：
【欧拉判别条件】：如下图

对于模p的二次剩余以及二次非剩余的个数，可以用下面定理求出，如下图：

[勒让德符号]：便于我们计算二次剩余判别式

下面是勒让德符号的一些性质：

下面写一道例题，如下图：

把-46拆成-1×46，因为17 mod 4 为1，所以(-1/17)=1;然后算(46/17)，46≡12 mod 17，再把12分解成3×4，因为4可以写成2²，而平方数的勒让德符号肯定为1，结果化简为(3/17),根据判别式得出结果

下面是常用的结论：

也可以写成
1 p=8m±1
-1 p=8m±3

当a=奇数的时候

下面算一个例子：计算（6/53）
因为6可以写成2×3所以原式子改成(2/53)(3/53),因为53=8×7-3，所以原式子写成-(3/53),因为此时a=3是奇数，用定理5.2.6，计算出（53-1）/2=26,即计算(ak)/p,k从1取到26.注意到没必要全部算完，(ak)/p是要向下取整的，知a=3时，3×17=53，所以当1<=k<=17的时候，结果是0
当18<=k<=35(因为3×35是53的两倍)的时候，结果是1.对于这个题相当于从k=18开始到k=26一共是9个1相加，因此算的这一串结果是1，所以原式子变成(-1)(-1)=1

下面是一个推论，整数a，b都与p互素，那么有

[高斯引理]:

对于a是奇数时运算太复杂，此时我们可以用二次互反律来求解，如下图

【雅可比符号】对勒让德符号的展开

使用雅可比符号，m要是正奇数（不是奇素数）注意，雅可比符号的一些性质：

类似勒让德符号运算，雅可比符号有：

雅可比符号二次互反律跟勒让德符号计算一样：

记住，勒让德符号p、q都是奇素数，雅可比符号m是正奇数。

归纳一下如何计算勒让德符号：
1.首先看p、q都是奇素数
2.当q超过p的一般，考虑取q-p作为新的q，此时q是负数
3.将（-1/p)提出来，根据5.2.3，判断(p-1)/2
4.将q分解成a×b，如果a或者b是2，根据5.2.5判断(p²-1)/8
5.若a或者b是奇数，利用二次互反律求出
6.得出结果，注意细心检查

下面是两道例题：

好难，我跳过，进行第六章的学

第六章：群

【半群】

当班群满足一些条件，他就是群

需要记忆的一些集合！

下面是一些定理：

下面是判断群的阶

下面是阿贝尔群的定义

————–注意，之后用“1”表示群的单位元，用a^-1表示a的逆元 ————-

因为存在唯一的逆元，所以当对式子ax=b等号两边同时乘上a^-1，x=a^-1b，因此是唯一的

下面是群中元素的性质：

下面是关于阶的定义

下面是例子

定理：

[子群]：

{1}和G本身，是G的平凡子群

下面是一个定理：

[正规子群]：

下面是定理：

[循环子群]：

[循环群]：

与讨论原根相似，通过一些条件可以判断生成元，如下：

6.3.2也就是说当找到这个k的时候，G就可以表示成G=<a^k>即G=<1,(a^k),(a^k)²…(a^k)^n-1>如果有生成元，数量也是知道的，如下

下面是一些定理：

云里雾里，书本写到了由给定子群构造新的子群

下面是研究如何从给定的子集推出子群

下面是定义

引申的定理

实在是顶不住了，这本书里面的知识点太难懂，我去b站看视频学
【循环群】：群G中每个元都能表示成一个 a的方幂，那么G就是由a生成的循环群，记G=<a>,a是生成元。
【培集与商群】：群和子群是有很多关系的
[左培集]：

aH是一个集合，里面的元素是G中任何元素a跟

[左培集关系]

【拉格朗日定理】

[商集和指标的概念]

下面是几个定理：

商群：

【同态和同构】

解释上图，“·”和“*”都是表示乘法，映射是x中每一个都能在y找到对应的结果，可以多个x对应一个y，但是不能一个x对应多个y。从b站视频学习到其中需要保持乘法
简单地说就是f(x1·x2)的结果在y里能找到，f(x1)*f(x2)的结果也能在y找到，并且这两个结果一样

回忆单射满射：
单射，x与y一一对应
满射，y中所有都被映射
双射，即单射又满射

下面是定理：

下面是同态的核跟像的概念，看下面截图

解释上图，首先f(a),表示在G中找到了S的映射。那么所谓的核，指的是先从G找到G的单位元，然后在S中找到是哪个元素映射出的，这个来自S的元素就是ker f，核
像，就是在G中找到每个S映射过来对应的元素。

下面是一些定理：

下面是一些重要定理，需要用到6.2.3正规子群的概念，如下

[同态基本定理]

第七章环

环，是具有两种运算的代数结构

子环的概念：

零因子概念：

下面是一些定义：

如上图，后面默认环都是交换幺环。注意，因为是半群，有了幺元不能有逆元，否则就变成群了。阿贝尔群就是交换群的意思。

下面是一些性质：

下面是运算时的一些定理

下面是一些定义

[环上多项式]

【常多项式】：只含有常数项的多项式的集合该集合里的元素被称为常多项式

【理想和商环】

通俗来说就是找一个比R小的环I，RI包含于R，从R和I中找r和i，ri∈I

理想类似群的培集

死记硬背！

这道题，首先构造4个元素，死记硬背“0”、“1”、“x”、“x+1”
不可约多项式，死记硬背x²+x+1，并且Z₂表示结果mod 2，所以加法出现2就会被mod 掉消失。而在乘法中，不能出现x²，当出现时要“-”不可约多项式 x²+x+1 ，比如x×x=x²，此时减去不可约多项式之后mod 2 为x+1.

如果构造9个元素， 0，1，2，x，x+1，x+2，2x，2x+1，2x+2,其中不可约多项式是x+1

看不下去了，下面直接第八章

第八章域

【域上多项式】