信息安全數(shù)學(xué)基礎(chǔ) 第2版 課件 第3、4章 同余方程、原根與指數(shù)

第3章同余方程《信息安全數(shù)學(xué)基礎(chǔ)（第2版）》1主要內(nèi)容本章主要介紹同余方程和線性同余方程的基本概念和性質(zhì)。然后討論如何使用中國剩余定理求解線性同余方程組。接下去討論二次同余方程的解法——二次剩余理論，并引入與二次剩余相關(guān)的運(yùn)算函數(shù)，即勒讓德符號與雅可比符號。最后討論高次同余方程的解法。學(xué)習(xí)要求：掌握線性同余方程、線性同余方程組和中國剩余定理的概念與性質(zhì)，以及相應(yīng)的求解方法；掌握二次剩余的概念與性質(zhì)，以及相關(guān)的計(jì)算方法和應(yīng)用；掌握勒讓德符號和雅可比符號的概念和性質(zhì)，以及其相關(guān)的應(yīng)用；了解高次同余方程的概念和性質(zhì)，以及方程的求解方法.同余方程2CONTENTS目錄同余方程線性同余方程1線性同余方程組與中國剩余定理2二次剩余3勒讓德符號與二次互反律4雅可比符號5高次同余方程63第1節(jié)線性同余方程線性同余方程4線性同余方程5主要內(nèi)容本節(jié)首先介紹同余方程和次數(shù)的定義，隨后介紹同余方程的性質(zhì)，作為后續(xù)內(nèi)容的背景知識。所涉及內(nèi)容總結(jié)如下：同余方程和次數(shù)的定義；同余方程的性質(zhì)。

線性同余方程6

線性同余方程7線性同余方程組與中國剩余定理第2節(jié)線性同余方程組與中國剩余定理8線性同余方程組與中國剩余定理9主要內(nèi)容本節(jié)首先介紹同余方程和次數(shù)的定義，隨后介紹同余方程的性質(zhì)，作為后續(xù)內(nèi)容的背景知識。所涉及內(nèi)容總結(jié)如下：同余方程和次數(shù)的定義；同余方程的性質(zhì)；

線性同余方程組與中國剩余定理10

線性同余方程組與中國剩余定理11

線性同余方程組與中國剩余定理12

線性同余方程組與中國剩余定理13

線性同余方程組與中國剩余定理14二次剩余第3節(jié)二次剩余15二次剩余16

二次剩余17

二次剩余18

二次剩余19勒讓德符號與二次互反律第4節(jié)勒讓德符號與二次互反律20勒讓德符號與二次互反律21

勒讓德符號與二次互反律22

勒讓德符號與二次互反律23

勒讓德符號與二次互反律24

勒讓德符號與二次互反律25雅可比符號第5節(jié)雅可比符號26雅可比符號27

雅可比符號28

雅可比符號29

雅可比符號30

雅可比符號31

雅可比符號32

雅可比符號33本章小結(jié)求解同余方程的各種方法對許多密碼算法的設(shè)計(jì)和分析具有重要作用。本章我們首先介紹同余方程和線性同余方程的基本概念和性質(zhì)。并且討論了如何使用中國剩余定理求解線性同余方程組以及二次同余方程的解法——二次剩余理論，并引入與二次剩余相關(guān)的運(yùn)算函數(shù)，即勒讓德符號與雅可比符號。進(jìn)一步地，我們介紹了如何求解高次同余方程。同余方程34第4章原根與指數(shù)《信息安全數(shù)學(xué)基礎(chǔ)（第2版）》35原根與指數(shù)主要內(nèi)容本章將主要介紹原根以及預(yù)期相關(guān)的基本知識。原根和指數(shù)是數(shù)論及其應(yīng)用中一個重要的概念，在ElGamal密碼算法、Diffie-Hellman密鑰交換協(xié)議（簡記DH）、橢圓曲線密碼學(xué)和數(shù)字簽名理論中有廣泛的應(yīng)用。學(xué)習(xí)要求掌握次數(shù)和原根的概念和性質(zhì)，以及相關(guān)的計(jì)算方法和應(yīng)用；掌握指數(shù)和高次剩余的概念與性質(zhì)，以及相關(guān)的計(jì)算方法和應(yīng)用。36CONTENTS目錄原根與指數(shù)次數(shù)1指數(shù)與高次剩余3原根

237原根與指數(shù)第1節(jié)次數(shù)38原根與指數(shù)39

原根與指數(shù)40

原根與指數(shù)

41

原根與指數(shù)42

原根與指數(shù)43原根與指數(shù)第2節(jié)原根44原根與指數(shù)45

原根與指數(shù)46

原根與指數(shù)47

原根與指數(shù)證明：（思路）

存在整數(shù)u,v滿足u|ordm(a),v|ordm(b),并使得(u,v)=1,uv=[ordm(a),ordm(b)].

xu48

原根與指數(shù)證明：（思路）

數(shù)學(xué)歸納法，假設(shè)定理對l（l≥2）成立49

原根與指數(shù)50

原根與指數(shù)51指數(shù)與高次剩余第3節(jié)指數(shù)與高次剩余52指數(shù)與高次剩余53

指數(shù)與高次剩余54

指數(shù)與高次剩余55

指數(shù)與高次剩余56

指數(shù)與高次剩余57本章小結(jié)本章小結(jié)本章主要介紹原根以及與其相關(guān)的基本知識。

原根和指數(shù)是數(shù)論及其應(yīng)用中一個重要的概念，是后續(xù)相關(guān)問題的