信息安全數(shù)學(xué)基礎(chǔ)1課件

1、信息安全數(shù)學(xué)基礎(chǔ)張 立 江2022/8/61計算機科學(xué)與技術(shù)學(xué)院信息安全數(shù)學(xué)(數(shù)論、代數(shù)和橢圓曲線理論)身份識別技術(shù)、防火墻技術(shù)、入侵檢測技術(shù)等2022/8/62計算機科學(xué)與技術(shù)學(xué)院課程內(nèi)容數(shù)論代數(shù)(群、環(huán)、域)-新第8章(第8,9,10,11,12章)橢圓曲線-新第9章(第13章)同余式(第3章)二次同余式與平方剩余(第4章)原根與指標(biāo)(第5章)素性檢測(第6+14章)連分數(shù)(第7章)不定方程與同余(第2章)整數(shù)的可除性(第1章)2022/8/63計算機科學(xué)與技術(shù)學(xué)院選用教材：信息安全數(shù)學(xué)基礎(chǔ)陳恭亮 著參考書目： 初等數(shù)論 潘承洞 潘承彪 著代數(shù)學(xué)引論 第2版 聶靈沼 丁石孫 著“Commu

2、tative Algebra”第1、2卷 O. Zariski & P. Samuel 著“Primality and Cryptography”E. Kranakis 著橢圓曲線密碼學(xué)導(dǎo)論張煥國 等譯2022/8/64計算機科學(xué)與技術(shù)學(xué)院課件郵箱 郵箱： 密碼：1234562022/8/65計算機科學(xué)與技術(shù)學(xué)院信息安全數(shù)學(xué)基礎(chǔ)第1章：整數(shù)的可除性2022/8/66計算機科學(xué)與技術(shù)學(xué)院數(shù)的集合：，-3，-2，-1，0，1，2，3， 在數(shù)學(xué)中有一門稱為“整數(shù)論”的分支早在公元前50年左右，在我國第一部數(shù)學(xué)專著九章算術(shù)(作者不詳)的第一章中就開始討論整數(shù)，介紹了輾轉(zhuǎn)相除法它與公元前三世紀(jì)歐幾里德所

3、著幾何原本中介紹的輾轉(zhuǎn)相除法是各自獨立地總結(jié)出來的五世紀(jì)時，在我國的孫子算經(jīng)中更有聞名于世的中國剩余定理(即孫子定理)，也對整數(shù)做了研究整數(shù)論是研究整數(shù)的學(xué)科整數(shù)什么叫整數(shù)？整數(shù)的一部分最簡單的數(shù)學(xué)模型就是自然數(shù)自然數(shù)的嚴(yán)格定義是在集合論的基礎(chǔ)上，由Peano(皮亞諾)給出了自然數(shù)公理如果有一些對象(可數(shù)集)，除了它們的數(shù)目之外其它性質(zhì)我們不予考慮的話，我們就可以用自然數(shù)來數(shù)它們無窮大總有一些數(shù)目由于太大而沒有名稱。這種現(xiàn)象或許就是人們第一次碰到無窮大這在古代就已經(jīng)導(dǎo)致這種嚴(yán)肅的問題：有沒有大得不能數(shù)的數(shù)？阿基米德在一本題為數(shù)沙器(公元前200年)的書中回答了他列舉了一系列增長很快的數(shù)目，并且

4、通過體積的估計而證明：這些數(shù)目當(dāng)中有些數(shù)目比地球上甚至比太陽系中的沙粒的數(shù)目還大素數(shù)的數(shù)目是有限多還是無窮多？有了研究的對象集合，再建立對象集合上的運算。一些乘法的經(jīng)驗表明，有些數(shù)是一些比1大的其它數(shù)的乘積而有些數(shù)，就沒有這種性質(zhì)-質(zhì)數(shù)(素數(shù))在歐幾里德的原本中，已經(jīng)有一個簡單而巧妙的推理能夠得出結(jié)論：質(zhì)數(shù)無窮多計算機只能處理有限數(shù)和有限個數(shù)，計算機的計算模型，硬件體系結(jié)構(gòu)的設(shè)計與實現(xiàn)，代數(shù)編碼，軟件設(shè)計與實現(xiàn)，計算機通信及密碼學(xué)等，都廣泛使用了整數(shù)理論而數(shù)學(xué)可以處理無窮大數(shù)論特點任意兩個整數(shù)可以相加，相減，相乘，結(jié)果仍是整數(shù)但兩個整數(shù)不一定能在整數(shù)的范圍內(nèi)相除，這是整數(shù)系統(tǒng)的特點研究整數(shù)就針

5、對這一特點加以分析實際上，研究整數(shù)的性質(zhì)基本上就是要研究整除性和因數(shù)分解等問題以及其它一些有關(guān)的問題數(shù)論內(nèi)容介紹數(shù)論中一些最基本的事實介紹整數(shù)的一些最基本的性質(zhì)有時似乎在敘述或證明一些盡人皆知非常明顯的事實。實則并非如此有些事情，我們習(xí)而不察，知其然而不知其所以然。有些事情，雖然知道，卻知道的不確切若未特別指明，凡出現(xiàn)的數(shù)都是指整數(shù)本章主要內(nèi)容：整除的概念歐幾里得算法(*)整數(shù)的表示最大公因子與廣義歐幾里得算法(*)最小公倍數(shù)素數(shù)與算數(shù)基本定理(*)素數(shù)定理2022/8/613計算機科學(xué)與技術(shù)學(xué)院1.1 整除的概念 歐幾里得除法一、整除基本概念及性質(zhì) 14152022/8/616計算機科學(xué)與技

6、術(shù)學(xué)院1718192021練習(xí)：1. 設(shè)a，b是兩個給定的非零整數(shù)，且有整數(shù)x，y使得ax+by=1.證明：若a|n且b|n，則ab|n2. 設(shè) 是整系數(shù)多項式。若d|b-c，則d|2022/8/622計算機科學(xué)與技術(shù)學(xué)院解答：1.證明：由n=n(ax+by)=(na)x+(nb)y,及ab|na，ab|nb 得證。2.證明： 又 得證。 2022/8/623計算機科學(xué)與技術(shù)學(xué)院二、素數(shù)(質(zhì)數(shù))及其判別法24252627282930三、歐幾里得除法(帶余除法)313233342022/8/635計算機科學(xué)與技術(shù)學(xué)院2022/8/636計算機科學(xué)與技術(shù)學(xué)院373839402022/8/641計算

7、機科學(xué)與技術(shù)學(xué)院2022/8/642計算機科學(xué)與技術(shù)學(xué)院思考題作業(yè)431.2 整數(shù)的表示4445464748例1 表示整數(shù)642為二進制因為：491111F150111771110E140110661101D130101551100C120100441011B110011331010A10001022100199000111100088000000二進制十六進制十進制二進制十六進制十進制二進制,十進制和十六進制換算表50 一般地,將十進制轉(zhuǎn)換為二進制比轉(zhuǎn)換為十六進制要容易些.因此要將十進制轉(zhuǎn)換為十六進制,可先將十進制轉(zhuǎn)換為二進制,再將二進制轉(zhuǎn)換為十六進制.(四位二進制數(shù)對應(yīng)一個十六進制數(shù))51

8、1.3 最大公因數(shù)與廣義歐幾里得除法一、最大公因數(shù)5253545556如何才能計算出兩個整數(shù)的最大公因數(shù)哪？(*)方法1：直接分解兩個整數(shù)但當(dāng)整數(shù)很大時不可行(后面我們會講到大整數(shù)分解是很困難的事情)方法2：廣義歐幾里得算法/輾轉(zhuǎn)相除法2022/8/657計算機科學(xué)與技術(shù)學(xué)院58二、廣義歐幾里得除法5960求最大公因數(shù)的步驟(*)：2022/8/661計算機科學(xué)與技術(shù)學(xué)院6263646566676869707172ja(r0)b(r1)101100123n7374j 01234567576是否也有(a，d)=1和(b，c)=1？2022/8/677計算機科學(xué)與技術(shù)學(xué)院787980818283歐

9、幾里得除法的應(yīng)用：2022/8/684計算機科學(xué)與技術(shù)學(xué)院85868788891.4 整除的進一步性質(zhì)及最小公倍數(shù)一、整除的性質(zhì)9091922022/8/693計算機科學(xué)與技術(shù)學(xué)院94練習(xí)：設(shè)k是正整數(shù)，證明： (1)(ak, bk)=(a, b)k (2)設(shè)a，b是正整數(shù)，若(a，b)=1，ab=ck，則a=(a, c)k，b=(b, c)k提示： (a, b)=1(ak-1, b)=1 a=a(ak-1, b)=(ak, ab)=(ak, ck)2022/8/695計算機科學(xué)與技術(shù)學(xué)院二、最小公倍數(shù)969798991001011021031041.5 素數(shù) 算術(shù)基本定理1051061071

10、082022/8/6109計算機科學(xué)與技術(shù)學(xué)院110111112113114115116117118119每個正整數(shù)可表示成素數(shù)冪的乘積素數(shù)是否有無窮多個？如果有無窮多個，那么作為無窮大量，素數(shù)個數(shù)具有怎樣的形狀？對正實數(shù)x，以(x)表示不超過x的素數(shù)個數(shù)例如：(15) = 6，(10.4) = 4，(50) = 152022/8/6120計算機科學(xué)與技術(shù)學(xué)院定理1 素數(shù)有無限多個 2022/8/6121計算機科學(xué)與技術(shù)學(xué)院2022/8/6122計算機科學(xué)與技術(shù)學(xué)院2022/8/6123計算機科學(xué)與技術(shù)學(xué)院費爾馬-業(yè)余數(shù)學(xué)家之王費爾馬(Pierre de Fermat，16011665)法國著

11、名數(shù)學(xué)家1601.8.17出生于法國圖盧茲。父親開了一家大皮革商店，擁有相當(dāng)豐厚的產(chǎn)業(yè)小時候受教于他的叔叔14歲時，才進入博蒙德洛馬涅公學(xué)，畢業(yè)后先后在奧爾良大學(xué)和圖盧茲大學(xué)學(xué)習(xí)法律還沒大學(xué)畢業(yè)，便買好了“律師”和“參議員”的職位。 1631年畢業(yè)返回家鄉(xiāng)以后，便成為圖盧茲議會的議員直到去世都沒失去官職，而且逐年得到提升1646年，費馬升任議會首席發(fā)言人，還當(dāng)過天主教聯(lián)盟的主席等職。費馬的官場生涯沒有突出政績費馬生有三女二男，長子整理了費馬的數(shù)學(xué)論著并積極出版費馬的數(shù)學(xué)論著數(shù)學(xué)論集2022/8/6124計算機科學(xué)與技術(shù)學(xué)院對數(shù)論的貢獻主要有：費馬大定理：n2的整數(shù)，則方程xn+yn=zn沒有滿

12、足xyz0的整數(shù)解。由英國數(shù)學(xué)家懷爾斯證明(1995年)，證明過程是相當(dāng)艱深的！費馬小定理：ap-a0(mod p)，其中p是素數(shù)，a是正整數(shù)，證明比較簡單錯誤貢獻1640年，費馬說他發(fā)現(xiàn)形如Fn=2(2n)+1的數(shù)全是素數(shù)，比如當(dāng)n=04時，3，5，17，257，65537都是素數(shù)，不過從第五個數(shù)開始由于數(shù)字過大，費馬并沒有進行驗算。但后來在1732年時，大數(shù)學(xué)家歐拉發(fā)現(xiàn)，n=5時，641*6700417=4294967297卻是個合數(shù)。并且以后被發(fā)現(xiàn)的數(shù)都是合數(shù)，最大的是n=1495時的Fn2022/8/6125計算機科學(xué)與技術(shù)學(xué)院1261272022/8/6128計算機科學(xué)與技術(shù)學(xué)院2022/8/6129計算機科學(xué)與技術(shù)學(xué)院證明可參考： 素數(shù)定理的初等證明 潘承洞 潘成彪 著2022/8/6130計算機科學(xué)與技術(shù)學(xué)院2022/8/6131計算機科學(xué)與技術(shù)學(xué)院問題：當(dāng)n為素數(shù)時，2n-1一定是素數(shù)嗎？211-1=2047=23*892022/8/6132計算機科學(xué)與技術(shù)學(xué)院2022/8/6133計算機科學(xué)與技術(shù)學(xué)院2022/8/6134計算機科學(xué)與技術(shù)學(xué)院高斯函數(shù)x和