信息安全數(shù)學基礎1ppt課件

2020/4/26,.,1,信息安全數(shù)學基礎,張立江cheungcumt,2020/4/26,.,2,信息安全,2020/4/26,.,3,課程內(nèi)容,數(shù)論,代數(shù)(群、環(huán)、域)-新第8章(第8,9,10,11,12章),橢圓曲線-新第9章(第13章),2020/4/26,.,4,選用教材：信息安全數(shù)學基礎陳恭亮著參考書目：初等數(shù)論潘承洞潘承彪著代數(shù)學引論第2版聶靈沼丁石孫著“CommutativeAlgebra”第1、2卷O.Zariski&P.Samuel著“PrimalityandCryptography”E.Kranakis著橢圓曲線密碼學導論張煥國等譯,2020/4/26,.,5,課件郵箱,郵箱：infosecmath密碼：123456,2020/4/26,.,6,信息安全數(shù)學基礎第1章：整數(shù)的可除性,數(shù)的集合：，-3，-2，-1，0，1，2，3，在數(shù)學中有一門稱為“整數(shù)論”的分支早在公元前50年左右，在我國第一部數(shù)學專著九章算術(作者不詳)的第一章中就開始討論整數(shù)，介紹了輾轉(zhuǎn)相除法它與公元前三世紀歐幾里德所著幾何原本中介紹的輾轉(zhuǎn)相除法是各自獨立地總結出來的五世紀時，在我國的孫子算經(jīng)中更有聞名于世的中國剩余定理(即孫子定理)，也對整數(shù)做了研究,整數(shù)論是研究整數(shù)的學科,整數(shù),什么叫整數(shù)？整數(shù)的一部分最簡單的數(shù)學模型就是自然數(shù)自然數(shù)的嚴格定義是在集合論的基礎上，由Peano(皮亞諾)給出了自然數(shù)公理如果有一些對象(可數(shù)集)，除了它們的數(shù)目之外其它性質(zhì)我們不予考慮的話，我們就可以用自然數(shù)來數(shù)它們,無窮大,總有一些數(shù)目由于太大而沒有名稱。這種現(xiàn)象或許就是人們第一次碰到無窮大這在古代就已經(jīng)導致這種嚴肅的問題：有沒有大得不能數(shù)的數(shù)？阿基米德在一本題為數(shù)沙器(公元前200年)的書中回答了他列舉了一系列增長很快的數(shù)目，并且通過體積的估計而證明：這些數(shù)目當中有些數(shù)目比地球上甚至比太陽系中的沙粒的數(shù)目還大,素數(shù)的數(shù)目是有限多還是無窮多？,有了研究的對象集合，再建立對象集合上的運算。一些乘法的經(jīng)驗表明，有些數(shù)是一些比1大的其它數(shù)的乘積而有些數(shù)，就沒有這種性質(zhì)-質(zhì)數(shù)(素數(shù))在歐幾里德的原本中，已經(jīng)有一個簡單而巧妙的推理能夠得出結論：質(zhì)數(shù)無窮多計算機只能處理有限數(shù)和有限個數(shù)，計算機的計算模型，硬件體系結構的設計與實現(xiàn)，代數(shù)編碼，軟件設計與實現(xiàn)，計算機通信及密碼學等，都廣泛使用了整數(shù)理論而數(shù)學可以處理無窮大,數(shù)論特點,任意兩個整數(shù)可以相加，相減，相乘，結果仍是整數(shù)但兩個整數(shù)不一定能在整數(shù)的范圍內(nèi)相除，這是整數(shù)系統(tǒng)的特點研究整數(shù)就針對這一特點加以分析實際上，研究整數(shù)的性質(zhì)基本上就是要研究整除性和因數(shù)分解等問題以及其它一些有關的問題,數(shù)論內(nèi)容,介紹數(shù)論中一些最基本的事實介紹整數(shù)的一些最基本的性質(zhì)有時似乎在敘述或證明一些盡人皆知非常明顯的事實。實則并非如此有些事情，我們習而不察，知其然而不知其所以然。有些事情，雖然知道，卻知道的不確切若未特別指明，凡出現(xiàn)的數(shù)都是指整數(shù),2020/4/26,.,13,本章主要內(nèi)容：,整除的概念歐幾里得算法(*)整數(shù)的表示最大公因子與廣義歐幾里得算法(*)最小公倍數(shù)素數(shù)與算數(shù)基本定理(*)素數(shù)定理,14,1.1整除的概念歐幾里得除法,一、整除基本概念及性質(zhì),15,2020/4/26,.,16,17,18,19,20,21,2020/4/26,.,22,練習：,1.設a，b是兩個給定的非零整數(shù)，且有整數(shù)x，y使得ax+by=1.證明：若a|n且b|n，則ab|n2.設是整系數(shù)多項式。若d|b-c，則d|,2020/4/26,.,23,解答：,1.證明：由n=n(ax+by)=(na)x+(nb)y,及ab|na，ab|nb得證。2.證明：又得證。,24,二、素數(shù)(質(zhì)數(shù))及其判別法,25,26,27,28,29,30,31,三、歐幾里得除法(帶余除法),32,33,34,2020/4/26,.,35,2020/4/26,.,36,37,38,39,40,2020/4/26,.,41,2020/4/26,.,42,43,思考題,作業(yè),44,1.2整數(shù)的表示,45,46,47,48,49,例1表示整數(shù)642為二進制,因為：,50,二進制,十進制和十六進制換算表,51,一般地,將十進制轉(zhuǎn)換為二進制比轉(zhuǎn)換為十六進制要容易些.因此要將十進制轉(zhuǎn)換為十六進制,可先將十進制轉(zhuǎn)換為二進制,再將二進制轉(zhuǎn)換為十六進制.(四位二進制數(shù)對應一個十六進制數(shù)),52,1.3最大公因數(shù)與廣義歐幾里得除法,一、最大公因數(shù),53,54,55,56,2020/4/26,.,57,如何才能計算出兩個整數(shù)的最大公因數(shù)哪？(*),方法1：直接分解兩個整數(shù)但當整數(shù)很大時不可行(后面我們會講到大整數(shù)分解是很困難的事情)方法2：廣義歐幾里得算法/輾轉(zhuǎn)相除法,58,59,二、廣義歐幾里得除法,60,2020/4/26,.,61,求最大公因數(shù)的步驟(*)：,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,2020/4/26,.,77,是否也有(a，d)=1和(b，c)=1？,78,79,80,81,82,83,2020/4/26,.,84,歐幾里得除法的應用：,85,86,87,88,89,90,1.4整除的進一步性質(zhì)及最小公倍數(shù),一、整除的性質(zhì),91,92,2020/4/26,.,93,94,2020/4/26,.,95,練習：,設k是正整數(shù)，證明：(1)(ak,bk)=(a,b)k(2)設a，b是正整數(shù)，若(a，b)=1，ab=ck，則a=(a,c)k，b=(b,c)k提示：(a,b)=1(ak-1,b)=1a=a(ak-1,b)=(ak,ab)=(ak,ck),96,二、最小公倍數(shù),97,98,99,100,101,102,103,104,105,1.5素數(shù)算術基本定理,106,107,108,2020/4/26,.,109,110,111,112,113,114,115,116,117,118,119,2020/4/26,.,120,每個正整數(shù)可表示成素數(shù)冪的乘積素數(shù)是否有無窮多個？如果有無窮多個，那么作為無窮大量，素數(shù)個數(shù)具有怎樣的形狀？對正實數(shù)x，以(x)表示不超過x的素數(shù)個數(shù)例如：(15)=6，(10.4)=4，(50)=15,2020/4/26,.,121,定理1素數(shù)有無限多個,2020/4/26,.,122,2020/4/26,.,123,2020/4/26,.,124,費爾馬-業(yè)余數(shù)學家之王,費爾馬(PierredeFermat，16011665)法國著名數(shù)學家1601.8.17出生于法國圖盧茲。父親開了一家大皮革商店，擁有相當豐厚的產(chǎn)業(yè)小時候受教于他的叔叔14歲時，才進入博蒙德洛馬涅公學，畢業(yè)后先后在奧爾良大學和圖盧茲大學學習法律還沒大學畢業(yè)，便買好了“律師”和“參議員”的職位。1631年畢業(yè)返回家鄉(xiāng)以后，便成為圖盧茲議會的議員直到去世都沒失去官職，而且逐年得到提升1646年，費馬升任議會首席發(fā)言人，還當過天主教聯(lián)盟的主席等職。費馬的官場生涯沒有突出政績費馬生有三女二男，長子整理了費馬的數(shù)學論著并積極出版費馬的數(shù)學論著數(shù)學論集,2020/4/26,.,125,對數(shù)論的貢獻主要有：費馬大定理：n2的整數(shù)，則方程xn+yn=zn沒有滿足xyz0的整數(shù)解。由英國數(shù)學家懷爾斯證明(1995年)，證明過程是相當艱深的！費馬小定理：ap-a0(modp)，其中p是素數(shù)，a是正整數(shù)，證明比較簡單錯誤貢獻1640年，費馬說他發(fā)現(xiàn)形如Fn=2(2n)+1的數(shù)全是素數(shù)，比如當n=04時，3，5，17，257，65537都是素數(shù)，不過從第五個數(shù)開始由于數(shù)字過大，費馬并沒有進行驗算。但后來在1732年時，大數(shù)學家歐拉發(fā)現(xiàn)，n=5時，641*6700417=4294967297卻是個合數(shù)。并且以后被發(fā)現(xiàn)的數(shù)都是合數(shù)，最大的是n=1495時的Fn,126,127,2020/4/26,.,128,2020/4/26,.,129,2020/4/26,.,130,證明可參考：素數(shù)定理的初等證明潘承洞潘成彪著,2020/4/26,.,131,2020/4/26,.,132,問題：當n為素數(shù)時，2n-1一定是素數(shù)嗎？,211-1=2047=23*89,2020/4/26,.,133,2020/4/26,.,134,135,高斯函數(shù)x和x的定義及其性質(zhì),136,137