《信息安全數(shù)學(xué)基礎(chǔ)》課件第1章 整數(shù)的可除性

信息安全數(shù)學(xué)基礎(chǔ)信息安全工程大學(xué)第1章整數(shù)的可除性1.1整除

整除的一些基本性質(zhì)

整除的一些基本性質(zhì)

素?cái)?shù)

素?cái)?shù)

埃拉托色尼斯篩法

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950【人物傳記】埃拉托色尼斯埃拉托色尼斯（公元前276-194）,出生于希臘屬地埃及西部的Cyrene,他在雅典的柏拉圖學(xué)習(xí)了一段時(shí)間.托勒密二世（PtolemyII）邀請(qǐng)他到亞歷山大教他的兒子.后來(lái)成為著名的亞歷山大圖書館館長(zhǎng).他著有數(shù)學(xué)、地理、天文、歷史、哲學(xué)和文學(xué)方面的書.除了數(shù)學(xué)方面的工作,他還以古代編年史和地理測(cè)量聞名.素?cái)?shù)的性質(zhì)

素?cái)?shù)個(gè)數(shù)定理

1,0001681451.16100,000959286861.1010,000,0006645796202411.071,000,000,00050847478482549421.05【人物傳記】克里斯汀·歌德巴赫

克里斯汀·歌德巴赫（1690-1764）生于普魯士哥尼斯堡（這個(gè)城市因七橋問(wèn)題而在數(shù)學(xué)界很有名）.1725年成為圣彼得堡皇家學(xué)院的數(shù)學(xué)教授.1728年到莫斯科成為沙皇彼得二世的老師.1742年任職于俄國(guó)外交部.除了“每個(gè)大于2的偶數(shù)都能寫為兩個(gè)素?cái)?shù)的和以及每個(gè)大于5的奇數(shù)能寫為3個(gè)素?cái)?shù)的和”的猜想外,在數(shù)學(xué)分析方面也做出了令人矚目的貢獻(xiàn).【人物傳記】陳景潤(rùn)陳景潤(rùn)（1933-1996）取得了關(guān)于孿生素?cái)?shù)和歌德巴赫猜想的重要結(jié)果.1966年發(fā)表《Ontherepresentationofalargeevenintegerasthesumofaprimeandtheproductofatmosttwoprimes》（《大偶數(shù)表為一個(gè)素?cái)?shù)及一個(gè)不超過(guò)二個(gè)素?cái)?shù)的乘積之和》,簡(jiǎn)稱“1+2”）,成為哥德巴赫猜想研究上的里程碑.而他所發(fā)表的成果也被稱之為陳氏定理.【人物傳記】張益唐美籍華裔數(shù)學(xué)家張益唐（1955-）于1978年進(jìn)入北京大學(xué)數(shù)學(xué)科學(xué)學(xué)院攻讀本科,1982年讀碩士,師從潘承彪,1985年入讀普渡大學(xué),導(dǎo)師為莫宗堅(jiān).2013年由于在研究孿生素?cái)?shù)猜想上取得了重大突破,于第六屆世界華人數(shù)學(xué)家大會(huì)中榮獲晨興數(shù)學(xué)卓越成就獎(jiǎng),后來(lái)他也獲頒Ostrowski獎(jiǎng)和RolfSchock獎(jiǎng).2014年,美國(guó)數(shù)學(xué)學(xué)會(huì)更將崇高的柯?tīng)枖?shù)論獎(jiǎng)授予張益唐.同年7月4日,張益唐當(dāng)選為中央研究院第30屆數(shù)理科學(xué)組院士.同年9月,張益唐獲得了該年度的麥克阿瑟獎(jiǎng)（俗稱“天才”獎(jiǎng)）.1.2.1帶余除法

帶余除法一般形式

帶余除法-舉例

1.2.2最大公因數(shù)

最大公因數(shù)-舉例

故168和99的最大公因數(shù)為(168,90)=2×3=6.最大公因數(shù)的基本性質(zhì)

最大公因數(shù)的基本性質(zhì)

【例1.2.3】計(jì)算最大公因數(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ù)學(xué)家,他最著名的著作《幾何原本》被廣泛的認(rèn)為是歷史上最成功的教科書,從古至今已經(jīng)有了上千種版本,這本書介紹了從平面到剛體幾何以及數(shù)論的知識(shí).人們關(guān)于歐幾里德的生平所知很少,現(xiàn)存的歐幾里德畫像都是出于畫家的想像.當(dāng)兩個(gè)數(shù)很大且共同的素因數(shù)也很大時(shí),短除法用起來(lái)就不方便了.例如,求46480和39423的最大公因數(shù).這里介紹另外一種求最大公因數(shù)的方法─歐幾里德算法,該方法有較高的效率,而且易于程序?qū)崿F(xiàn).歐幾里德算法,中文通常稱為輾轉(zhuǎn)相除法,主要用于求兩個(gè)整數(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語(yǔ)言的一種程序?qū)崿F(xiàn)方法下面給出C語(yǔ)言的一種程序?qū)崿F(xiàn)方法.intgcd(inta,intb){while(b!=0){intr=b;b=a%b;a=r;}returna;}

裴蜀等式

裴蜀等式-舉例

計(jì)算過(guò)程備注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裴蜀等式-舉例計(jì)算過(guò)程備注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]);////////////回代過(guò)程///////////////////////////////////

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; }}下面給出程序的一個(gè)運(yùn)行結(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為自己的學(xué)號(hào)，b=210，求整數(shù)s,t，使得as+tb=(a,b)1.3最小公倍數(shù)

【例1.3.1】求最小公倍數(shù)[168,90].解:前面用短除法得到了(168,90).求解過(guò)程如下.故168和99的最小公倍數(shù)[168,90]=2×3×28×15=2520.最小公倍數(shù)的性質(zhì)

最小公倍數(shù)的性質(zhì)

最小公倍數(shù)的性質(zhì)

最小公倍數(shù)的性質(zhì)

1.4算術(shù)基本定理

標(biāo)準(zhǔn)分解式

最大公因數(shù)和最小公倍數(shù)

最大公因數(shù)和最小公倍數(shù)【例1.4.3】