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

1、信息安全數(shù)學(xué)基礎(chǔ)張 立 江2022/8/61計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院信息安全數(shù)學(xué)(數(shù)論、代數(shù)和橢圓曲線理論)身份識(shí)別技術(shù)、防火墻技術(shù)、入侵檢測(cè)技術(shù)等2022/8/62計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院課程內(nèi)容數(shù)論代數(shù)(群、環(huán)、域)-新第8章(第8,9,10,11,12章)橢圓曲線-新第9章(第13章)同余式(第3章)二次同余式與平方剩余(第4章)原根與指標(biāo)(第5章)素性檢測(cè)(第6+14章)連分?jǐn)?shù)(第7章)不定方程與同余(第2章)整數(shù)的可除性(第1章)2022/8/63計(jì)算機(jī)科學(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計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院課件郵箱 郵箱： 密碼：1234562022/8/65計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院信息安全數(shù)學(xué)基礎(chǔ)第1章：整數(shù)的可除性2022/8/66計(jì)算機(jī)科學(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)相除法是各自獨(dú)立地總結(jié)出來的五世紀(jì)時(shí)，在我國的孫子算經(jīng)中更有聞名于世的中國剩余定理(即孫子定理)，也對(duì)整數(shù)做了研究整數(shù)論是研究整數(shù)的學(xué)科整數(shù)什么叫整數(shù)？整數(shù)的一部分最簡單的數(shù)學(xué)模型就是自然數(shù)自然數(shù)的嚴(yán)格定義是在集合論的基礎(chǔ)上，由Peano(皮亞諾)給出了自然數(shù)公理如果有一些對(duì)象(可數(shù)集)，除了它們的數(shù)目之外其它性質(zhì)我們不予考慮的話，我們就可以用自然數(shù)來數(shù)它們無窮大總有一些數(shù)目由于太大而沒有名稱。這種現(xiàn)象或許就是人們第一次碰到無窮大這在古代就已經(jīng)導(dǎo)致這種嚴(yán)肅的問題：有沒有大得不能數(shù)的數(shù)？阿基米德在一本題為數(shù)沙器(公元前200年)的書中回答了他列舉了一系列增長很快的數(shù)目，并且

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

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

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

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

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

9、幾里得除法的應(yīng)用：2022/8/684計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院85868788891.4 整除的進(jìn)一步性質(zhì)及最小公倍數(shù)一、整除的性質(zhì)9091922022/8/693計(jì)算機(jī)科學(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計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院二、最小公倍數(shù)969798991001011021031041.5 素?cái)?shù) 算術(shù)基本定理1051061071

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

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

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