數(shù)論與代數(shù)知識(shí)初步上課件

第二講數(shù)論與代數(shù)知識(shí)初步(上)第二講數(shù)論與代數(shù)知識(shí)初步(上)1現(xiàn)代密碼系統(tǒng)中，消息都是事先轉(zhuǎn)換成數(shù)值進(jìn)行加密傳輸。密碼過(guò)程是一些輸入輸出都是數(shù)值的數(shù)學(xué)操作，建立，分析，攻擊這些算法需要數(shù)學(xué)工具。其中在實(shí)踐中應(yīng)用最為成功的數(shù)學(xué)理論當(dāng)然是數(shù)論和代數(shù)，特別是同余理論?，F(xiàn)代密碼系統(tǒng)中，消息都是事先轉(zhuǎn)換成數(shù)值進(jìn)行加密傳輸。密2本講提要基本概念同余本講提要基本概念31基本概念1.1整除性1基本概念1.1整除性41.1整除性(續(xù))1.1整除性(續(xù))51.2素?cái)?shù)1.2素?cái)?shù)61.2素?cái)?shù)(續(xù))200以內(nèi)的素?cái)?shù)：

2357111317192329313741434753596167717379838997101103107109113127131137139149151157163167173179181191193197199

1.2素?cái)?shù)(續(xù))200以內(nèi)的素?cái)?shù)：71.2素?cái)?shù)(續(xù))1.2素?cái)?shù)(續(xù))81.3最大公約數(shù)1.3最大公約數(shù)91.3最大公約數(shù)(續(xù))1.3最大公約數(shù)(續(xù))101.3最大公約數(shù)(續(xù))1.3最大公約數(shù)(續(xù))111.3最大公約數(shù)(續(xù))1.3最大公約數(shù)(續(xù))121.3最大公約數(shù)(續(xù))1.3最大公約數(shù)(續(xù))131.4最小公倍數(shù)1.4最小公倍數(shù)141.4最小公倍數(shù)(續(xù))1.4最小公倍數(shù)(續(xù))151.4整數(shù)唯一分解定理1.4整數(shù)唯一分解定理161.4整數(shù)唯一分解定理(續(xù))1.4整數(shù)唯一分解定理(續(xù))171.4整數(shù)唯一分解定理(續(xù))1.4整數(shù)唯一分解定理(續(xù))181.5一次不定方程1.5一次不定方程192同余2.1同余定義與概念2同余2.1同余定義與概念202.1同余定義與概念(續(xù))2.1同余定義與概念(續(xù))212.2剩余類和完全剩余類2.2剩余類和完全剩余類222.2剩余類和完全剩余類(續(xù)）2.2剩余類和完全剩余類(續(xù)）232.3縮系2.3縮系242.3縮系(續(xù))2.3縮系(續(xù))252.3縮系(續(xù))2.3縮系(續(xù))262.4一次同余式2.4一次同余式272.4一次同余式(續(xù))2.4一次同余式(續(xù))282.5模是素?cái)?shù)的同余式2.5模是素?cái)?shù)的同余式292.6中國(guó)剩余定理(CRT)2.6中國(guó)剩余定理(CRT)302.6中國(guó)剩余定理(CRT)(續(xù))2.6中國(guó)剩余定理(CRT)(續(xù))31謝謝！謝謝！32第二講數(shù)論與代數(shù)知識(shí)初步(上)第二講數(shù)論與代數(shù)知識(shí)初步(上)33現(xiàn)代密碼系統(tǒng)中，消息都是事先轉(zhuǎn)換成數(shù)值進(jìn)行加密傳輸。密碼過(guò)程是一些輸入輸出都是數(shù)值的數(shù)學(xué)操作，建立，分析，攻擊這些算法需要數(shù)學(xué)工具。其中在實(shí)踐中應(yīng)用最為成功的數(shù)學(xué)理論當(dāng)然是數(shù)論和代數(shù)，特別是同余理論?，F(xiàn)代密碼系統(tǒng)中，消息都是事先轉(zhuǎn)換成數(shù)值進(jìn)行加密傳輸。密34本講提要基本概念同余本講提要基本概念351基本概念1.1整除性1基本概念1.1整除性361.1整除性(續(xù))1.1整除性(續(xù))371.2素?cái)?shù)1.2素?cái)?shù)381.2素?cái)?shù)(續(xù))200以內(nèi)的素?cái)?shù)：

2357111317192329313741434753596167717379838997101103107109113127131137139149151157163167173179181191193197199

1.2素?cái)?shù)(續(xù))200以內(nèi)的素?cái)?shù)：391.2素?cái)?shù)(續(xù))1.2素?cái)?shù)(續(xù))401.3最大公約數(shù)1.3最大公約數(shù)411.3最大公約數(shù)(續(xù))1.3最大公約數(shù)(續(xù))421.3最大公約數(shù)(續(xù))1.3最大公約數(shù)(續(xù))431.3最大公約數(shù)(續(xù))1.3最大公約數(shù)(續(xù))441.3最大公約數(shù)(續(xù))1.3最大公約數(shù)(續(xù))451.4最小公倍數(shù)1.4最小公倍數(shù)461.4最小公倍數(shù)(續(xù))1.4最小公倍數(shù)(續(xù))471.4整數(shù)唯一分解定理1.4整數(shù)唯一分解定理481.4整數(shù)唯一分解定理(續(xù))1.4整數(shù)唯一分解定理(續(xù))491.4整數(shù)唯一分解定理(續(xù))1.4整數(shù)唯一分解定理(續(xù))501.5一次不定方程1.5一次不定方程512同余2.1同余定義與概念2同余2.1同余定義與概念522.1同余定義與概念(續(xù))2.1同余定義與概念(續(xù))532.2剩余類和完全剩余類2.2剩余類和完全剩余類542.2剩余類和完全剩余類(續(xù)）2.2剩余類和完全剩余類(續(xù)）552.3縮系2.3縮系562.3縮系(續(xù))2.3縮系(續(xù))572.3縮系(續(xù))2.3縮系(續(xù))582.4一次同余式2.4一次同余式592.4一次同余式(續(xù))2.4一次同余式(續(xù))602.