《密码学——加密演算法》-第3章 基础数论

《《密码学——加密演算法》-第3章 基础数论》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、返回总目录第3章基础数论教学目的了解模运算及辗转相除法了解中国余式子定律了解Lagrange定理与费马小定理了解原根、二次剩余、Galois域等概念了解质数理论和连分数了解密码安全伪随机数字生成器模运算与辗转相除法本章内容中国余式子定律Lagrange定理与费马小定理原根二次剩余Galois域连分数质数理论密码安全伪随机数字生成器模运算与辗转相除法3.1模运算与辗转相除法假设今天是星期五，请问10000天后是星期几？（即5+10000除以7的余数）即：10000天后是星期二同余定义（同余，Congruence）：令。令为两整数，称a同余b模n，记为，当n

2、整除b-a。而所有与a同余的整数所组成的集合，即称为a的同余类。所有同余类所形成的集合同余类同余类满足的性质：（1）（反身性，Reflexivity）（2）（对称性，Symmetry）若则（3）（迁移性，Transitivity）若则例：令则模运算加法：（1）封闭性：若同余类则（2）交换律：若同余类则（3）结合律：若同余类则（4）存在加法单位素：存在，使得（5）存在加法反元素：对任一存在使得减法：乘法：交换群定义（交换群）考虑，其中G为集合，而*为运算。令公理：（1）封闭性：则；（2）交换律：则；（3）结合律：则；（4）存在单位素：，，使得（5）存在反元素：，，使得若公理1

3、、3、4、5成立，称为群(Group)；若以上公理1～5都成立，称为交换群。交换环此时除了为交换群以外，另外针对乘法运算也满足封闭性、交换律、结合律以及存在乘法单位素（即）等性质，但并非所有非零元素都有乘法反元素，另外乘法对加法有分配律，即：若则此时，以代数的术语，称为交换环（CommutativeRing）。考虑辗转相除法例：求7812及6084的最大公因子被除数=商×除数+余数，gcd（被除数，除数）=gcd（除数，余数）辗转相除法就是利用此性质，反复以（除数/余数）取代（被除数/除数）k01234567rk78126048172890082872360qk131111

4、2其中：所以gcd(7812,6084)=36辗转相除法定理3.1整数线性方程有整数解证明：若则：为一整数解若有整数解因：且所以借助广义辗转相除法，存在整数，使得对模乘法例：令n为自然数，则对模乘法为交换群证明：根据交换群封闭性则因，故存在乘法反元素、使得且，而故为的乘法反元素。模运算与辗转相除法3.2中国余式子定理（ChineseRemainderTheorem）定理：令为两两互质的正整数，令则同余联立方程组在集合有惟一解，其解为其中，而余式定理应用其中，为n的质因数，性质1：存在群同构（GroupIsomorphism）定义：当为正整数时，定义Euler-Phi函数为性

5、质2：Lagrange定理与费马小定理3.3Lagrange定理与费马小定理令为群，若为子集，且在相同的运算*形成群则称（或H）为G的子群（Subgroup）。子群(Subgroup)Lagrange定理定理（Lagrange定理）若G为有限群，H为G中之子群，则证明：H为G的子群，为方便起见，假设为乘法群。可定等价关系如下：若如此定义出的等价关系可将分割成若干个等价类，即每个等价类都有#H个元素（考虑为1－1对应）。因此#H整除#G费马小定理定理（费马小定理）令为p质数、a为与p互质的整数，则证明：考虑乘法群，为其子群，根据Lagrange定理所以其中因此：原根考虑2的次

6、方（mod11）：3.4原根可以发现乘法群中的同余类均可表示为[2]的若干次方此时称2为乘法群的原根（PrimitiveRoot）当时，则10必整除x；此时称10为2在（mod11）（或在乘法群）的秩（Order）秩定义：令G为乘法群，而g∈G为其中一元素，则元素g的秩（Order）定义为也可能不存在x∈N使得，此时定义。若G为有限群，则为G的子群，有，根据Lagrange定理，子群的元素个数必整除母群G的元素个数，故原根定理定理：令g为质数p上的原根，则（1）若x为整数，则（2）若i、j为整数，则证明：（1）若欲证假设不成立，可写得：但：…...所以：有r个元素，这与p为

7、原根的假设矛盾。（2）假设i>j，将同余式两边同乘以得：利用已证明的性质1，此等价于：子群与循环群令G为任一乘法群，为任一元素，则为G中的子群（封闭性与反元素的存在性自然成立）。此子群称为由元素g所生成的子群。定义：子群定义：循环群（CyclicGroup）若存在使得，则称G为循环群（CyclicGroup），而g为原根或生成元（Generator）。二次剩余3.5二次剩余QuadraticResidue定义：同余式a与n为互质整数若有整数解，称a为（modn）的二次剩余（QuadraticResidue）若