信息安全数学基础 第2版 课件 第3、4章 同余方程、原根与指数

第3章同余方程《信息安全数学基础（第2版）》1主要内容本章主要介绍同余方程和线性同余方程的基本概念和性质。然后讨论如何使用中国剩余定理求解线性同余方程组。接下去讨论二次同余方程的解法——二次剩余理论，并引入与二次剩余相关的运算函数，即勒让德符号与雅可比符号。最后讨论高次同余方程的解法。学习要求：掌握线性同余方程、线性同余方程组和中国剩余定理的概念与性质，以及相应的求解方法；掌握二次剩余的概念与性质，以及相关的计算方法和应用；掌握勒让德符号和雅可比符号的概念和性质，以及其相关的应用；了解高次同余方程的概念和性质，以及方程的求解方法.同余方程2CONTENTS目录同余方程线性同余方程1线性同余方程组与中国剩余定理2二次剩余3勒让德符号与二次互反律4雅可比符号5高次同余方程63第1节线性同余方程线性同余方程4线性同余方程5主要内容本节首先介绍同余方程和次数的定义，随后介绍同余方程的性质，作为后续内容的背景知识。所涉及内容总结如下：同余方程和次数的定义；同余方程的性质。

线性同余方程6

线性同余方程7线性同余方程组与中国剩余定理第2节线性同余方程组与中国剩余定理8线性同余方程组与中国剩余定理9主要内容本节首先介绍同余方程和次数的定义，随后介绍同余方程的性质，作为后续内容的背景知识。所涉及内容总结如下：同余方程和次数的定义；同余方程的性质；

线性同余方程组与中国剩余定理10

线性同余方程组与中国剩余定理11

线性同余方程组与中国剩余定理12

线性同余方程组与中国剩余定理13

线性同余方程组与中国剩余定理14二次剩余第3节二次剩余15二次剩余16

二次剩余17

二次剩余18

二次剩余19勒让德符号与二次互反律第4节勒让德符号与二次互反律20勒让德符号与二次互反律21

勒让德符号与二次互反律22

勒让德符号与二次互反律23

勒让德符号与二次互反律24

勒让德符号与二次互反律25雅可比符号第5节雅可比符号26雅可比符号27

雅可比符号28

雅可比符号29

雅可比符号30

雅可比符号31

雅可比符号32

雅可比符号33本章小结求解同余方程的各种方法对许多密码算法的设计和分析具有重要作用。本章我们首先介绍同余方程和线性同余方程的基本概念和性质。并且讨论了如何使用中国剩余定理求解线性同余方程组以及二次同余方程的解法——二次剩余理论，并引入与二次剩余相关的运算函数，即勒让德符号与雅可比符号。进一步地，我们介绍了如何求解高次同余方程。同余方程34第4章原根与指数《信息安全数学基础（第2版）》35原根与指数主要内容本章将主要介绍原根以及预期相关的基本知识。原根和指数是数论及其应用中一个重要的概念，在ElGamal密码算法、Diffie-Hellman密钥交换协议（简记DH）、椭圆曲线密码学和数字签名理论中有广泛的应用。学习要求掌握次数和原根的概念和性质，以及相关的计算方法和应用；掌握指数和高次剩余的概念与性质，以及相关的计算方法和应用。36CONTENTS目录原根与指数次数1指数与高次剩余3原根

237原根与指数第1节次数38原根与指数39

原根与指数40

原根与指数

41

原根与指数42

原根与指数43原根与指数第2节原根44原根与指数45

原根与指数46

原根与指数47

原根与指数证明：（思路）

存在整数u,v满足u|ordm(a),v|ordm(b),并使得(u,v)=1,uv=[ordm(a),ordm(b)].

xu48

原根与指数证明：（思路）

数学归纳法，假设定理对l（l≥2）成立49

原根与指数50

原根与指数51指数与高次剩余第3节指数与高次剩余52指数与高次剩余53

指数与高次剩余54

指数与高次剩余55

指数与高次剩余56

指数与高次剩余57本章小结本章小结本章主要介绍原根以及与其相关的基本知识。

原根和指数是数论及其应用中一个重要的概念，是后续相关问题的