版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
信息安全數(shù)學基礎(chǔ)信息安全工程大學第1章整數(shù)的可除性1.1整除
整除的一些基本性質(zhì)
整除的一些基本性質(zhì)
素數(shù)
素數(shù)
埃拉托色尼斯篩法
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950【人物傳記】埃拉托色尼斯埃拉托色尼斯(公元前276-194),出生于希臘屬地埃及西部的Cyrene,他在雅典的柏拉圖學習了一段時間.托勒密二世(PtolemyII)邀請他到亞歷山大教他的兒子.后來成為著名的亞歷山大圖書館館長.他著有數(shù)學、地理、天文、歷史、哲學和文學方面的書.除了數(shù)學方面的工作,他還以古代編年史和地理測量聞名.素數(shù)的性質(zhì)
素數(shù)個數(shù)定理
1,0001681451.16100,000959286861.1010,000,0006645796202411.071,000,000,00050847478482549421.05【人物傳記】克里斯汀·歌德巴赫
克里斯汀·歌德巴赫(1690-1764)生于普魯士哥尼斯堡(這個城市因七橋問題而在數(shù)學界很有名).1725年成為圣彼得堡皇家學院的數(shù)學教授.1728年到莫斯科成為沙皇彼得二世的老師.1742年任職于俄國外交部.除了“每個大于2的偶數(shù)都能寫為兩個素數(shù)的和以及每個大于5的奇數(shù)能寫為3個素數(shù)的和”的猜想外,在數(shù)學分析方面也做出了令人矚目的貢獻.【人物傳記】陳景潤陳景潤(1933-1996)取得了關(guān)于孿生素數(shù)和歌德巴赫猜想的重要結(jié)果.1966年發(fā)表《Ontherepresentationofalargeevenintegerasthesumofaprimeandtheproductofatmosttwoprimes》(《大偶數(shù)表為一個素數(shù)及一個不超過二個素數(shù)的乘積之和》,簡稱“1+2”),成為哥德巴赫猜想研究上的里程碑.而他所發(fā)表的成果也被稱之為陳氏定理.【人物傳記】張益唐美籍華裔數(shù)學家張益唐(1955-)于1978年進入北京大學數(shù)學科學學院攻讀本科,1982年讀碩士,師從潘承彪,1985年入讀普渡大學,導師為莫宗堅.2013年由于在研究孿生素數(shù)猜想上取得了重大突破,于第六屆世界華人數(shù)學家大會中榮獲晨興數(shù)學卓越成就獎,后來他也獲頒Ostrowski獎和RolfSchock獎.2014年,美國數(shù)學學會更將崇高的柯爾數(shù)論獎授予張益唐.同年7月4日,張益唐當選為中央研究院第30屆數(shù)理科學組院士.同年9月,張益唐獲得了該年度的麥克阿瑟獎(俗稱“天才”獎).1.2.1帶余除法
帶余除法一般形式
帶余除法-舉例
1.2.2最大公因數(shù)
最大公因數(shù)-舉例
故168和99的最大公因數(shù)為(168,90)=2×3=6.最大公因數(shù)的基本性質(zhì)
最大公因數(shù)的基本性質(zhì)
【例1.2.3】計算最大公因數(shù)(120,150,210,35).解:(120,150)=30,(30,210)=30,(30,35)=5,故(120,150,210,35)=5或(120,150,210,35)=((120,150),(210,35))=(30,35)=5最大公因數(shù)的基本性質(zhì)
【人物傳記】歐幾里德【人物傳記】歐幾里德(Euclid,前325年—前265年),古希臘數(shù)學家,他最著名的著作《幾何原本》被廣泛的認為是歷史上最成功的教科書,從古至今已經(jīng)有了上千種版本,這本書介紹了從平面到剛體幾何以及數(shù)論的知識.人們關(guān)于歐幾里德的生平所知很少,現(xiàn)存的歐幾里德畫像都是出于畫家的想像.當兩個數(shù)很大且共同的素因數(shù)也很大時,短除法用起來就不方便了.例如,求46480和39423的最大公因數(shù).這里介紹另外一種求最大公因數(shù)的方法─歐幾里德算法,該方法有較高的效率,而且易于程序?qū)崿F(xiàn).歐幾里德算法,中文通常稱為輾轉(zhuǎn)相除法,主要用于求兩個整數(shù)的最大公因數(shù),從而為求解一次同余方程及一次同余方程組做鋪墊.1.2.3歐幾里德算法
歐幾里德算法
歐幾里德算法
歐幾里德算法-舉例【例1.2.6】利用歐幾里德算法求(172,46).172=46×3+34(172,46)=(46,34)46=34+12(46,34)=(34,12)34=12×2+10(34,12)=(12,10)12=10+2(12,10)=(10,2)10=5×2(10,2)=(2,0)=2歐幾里德算法-舉例也可以這樣求解:172=46×4+(-12)(172,46)=(46,-12)46=(-12)×(-4)+(-2)(46,-12)=(-12,-2)-12=6×(-2)(-12,-2)=(-2,0)=2C語言的一種程序?qū)崿F(xiàn)方法下面給出C語言的一種程序?qū)崿F(xiàn)方法.intgcd(inta,intb){while(b!=0){intr=b;b=a%b;a=r;}returna;}
裴蜀等式
裴蜀等式-舉例
計算過程備注172=46×3+34(172,46)=(46,34)46=34+12(46,34)=(34,12)34=12×2+10(34,12)=(12,10)12=10+2(12,10)=(10,2)10=5×2(10,2)=(2,0)=2裴蜀等式-舉例計算過程備注2=12-10(12,10)=(10,2)=12-(34-12×2)=12×3-34(34,12)=(12,10)=(46-34)×3-34=46×3-34×4(46,34)=(34,12)=46×3-(172-46×3)×4=46×15-172×4(172,46)=(46,34)故:2=46×15+172×(-4)
裴蜀等式-特例
裴蜀等式-舉例
voidEuclid(unsignedintnum1,unsignedintnum2){ inta[32],b[32]; intinv_a,inv_b,tmp; inti=0,j=0; a[0]=num1; b[0]=num2;while(a[i]%b[j]!=0) { printf("%d=%d×%d+%d\n",a[i],a[i]/b[j],b[j],a[i]%b[j]); i++; j++; a[i]=b[j-1]; b[j]=a[i-1]%b[j-1]; }printf("%d=%d*%d+%d\n\n",a[i],a[i]/b[j],b[j],a[i]%b[j]);////////////回代過程///////////////////////////////////
i--;j--; inv_a=1; inv_b=-a[i]/b[j]; printf("%d\n",a[i]%b[j]); for(;i>=0,j>=0;i--,j--) { printf("=%d×(%d)+%d×(%d)\n",a[i],inv_a,b[j],inv_b); tmp=inv_a; inv_a=inv_b; inv_b=tmp-a[i-1]/b[j-1]*inv_b; }}下面給出程序的一個運行結(jié)果:209=3×59+3259=1×32+2732=1×27+527=5×5+25=2×2+12=2*1+0
1=5×(1)+2×(-2)=27×(-2)+5×(11)=32×(11)+27×(-13)=59×(-13)+32×(24)=209×(24)+59×(-85)
作業(yè)11、設(shè)a為自己的學號,b=210,求整數(shù)s,t,使得as+tb=(a,b)1.3最小公倍數(shù)
【例1.3.1】求最小公倍數(shù)[168,90].解:前面用短除法得到了(168,90).求解過程如下.故168和99的最小公倍數(shù)[168,90]=2×3×28×15=2520.最小公倍數(shù)的性質(zhì)
最小公倍數(shù)的性質(zhì)
最小公倍數(shù)的性質(zhì)
最小公倍數(shù)的性質(zhì)
1.4算術(shù)基本定理
標準分解式
最大公因數(shù)和最小公倍數(shù)
最大公因數(shù)和最小公倍數(shù)【例1.4.3】
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
- 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025年小學四班語文教學工作計劃范文
- 習作《二十年后的家鄉(xiāng)》說課稿-2024-2025學年五年級上冊語文統(tǒng)編版
- 2025年村計劃生育工作計劃范例
- 2025年小學生寒假計劃
- 2025年度轄區(qū)清潔生產(chǎn)審核工作計劃
- 2025幼兒園中班保育員工作計劃范本
- Unit5第1課時Section A(1a-Pronunciation)說課稿 2024-2025學年人教版英語七年級上冊
- 2025年科教興區(qū)年度工作計劃范文
- 2025年市場推廣工作計劃模板市場推廣工作計劃范文
- 2025扶貧工作隊工作計劃
- 浙江省嘉興市2023-2024學年七年級上學期語文期末試卷(含答案)
- 《鴻蒙智能互聯(lián)設(shè)備開發(fā)(微課版)》全套教學課件
- 場地平整施工組織設(shè)計-(3)模板
- 交通設(shè)施設(shè)備供貨及技術(shù)支持方案
- 山西省晉中市2023-2024學年高一上學期期末考試 物理 含解析
- 項目工程師年終總結(jié)課件
- 一年級口算練習題大全(可直接打印A4)
- 安全與急救學習通超星期末考試答案章節(jié)答案2024年
- 人力資源戰(zhàn)略規(guī)劃地圖
- 2024電力安全工器具及小型施工機具預防性試驗規(guī)程
- 基于單片機的2.4G無線通信系統(tǒng)
評論
0/150
提交評論