信息安全數(shù)學基礎第1章 整數(shù)的可除性

信息平安數(shù)學根底信息平安工程大學第1章整數(shù)的可除性1.1整除

整除的一些根本性質

整除的一些根本性質

素數(shù)

素數(shù)

埃拉托色尼斯篩法

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

素數(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〕取得了關于孿生素數(shù)和歌德巴赫猜測的重要結果.1966年發(fā)表?Ontherepresentationofalargeevenintegerasthesumofaprimeandtheproductofatmosttwoprimes?〔?大偶數(shù)表為一個素數(shù)及一個不超過二個素數(shù)的乘積之和?,簡稱“1+2〞〕,成為哥德巴赫猜測研究上的里程碑.而他所發(fā)表的成果也被稱之為陳氏定理.【人物傳記】張益唐美籍華裔數(shù)學家張益唐〔1955-〕于1978年進入北京大學數(shù)學科學學院攻讀本科,1982年讀碩士,師從潘承彪,1985年入讀普渡大學,導師為莫宗堅.2021年由于在研究孿生素數(shù)猜測上取得了重大突破,于第六屆世界華人數(shù)學家大會中榮獲晨興數(shù)學卓越成就獎,后來他也獲頒Ostrowski獎和RolfSchock獎.2021年,美國數(shù)學學會更將崇高的柯爾數(shù)論獎授予張益唐.同年7月4日,張益唐中選為中央研究院第30屆數(shù)理科學組院士.同年9月,張益唐獲得了該年度的麥克阿瑟獎〔俗稱“天才〞獎〕.帶余除法

帶余除法一般形式

帶余除法-舉例

1.2.2最大公因數(shù)

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

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

最大公因數(shù)的根本性質

【例】計算最大公因數(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ù)的根本性質

【人物傳記】歐幾里德【人物傳記】歐幾里德〔Euclid,前325年—前265年〕,古希臘數(shù)學家,他最著名的著作?幾何原本?被廣泛的認為是歷史上最成功的教科書,從古至今已經(jīng)有了上千種版本,這本書介紹了從平面到剛體幾何以及數(shù)論的知識.人們關于歐幾里德的生平所知很少,現(xiàn)存的歐幾里德畫像都是出于畫家的想像.當兩個數(shù)很大且共同的素因數(shù)也很大時,短除法用起來就不方便了.例如,求46480和39423的最大公因數(shù).這里介紹另外一種求最大公因數(shù)的方法─歐幾里德算法,該方法有較高的效率,而且易于程序實現(xiàn).歐幾里德算法,中文通常稱為輾轉相除法,主要用于求兩個整數(shù)的最大公因數(shù),從而為求解一次同余方程及一次同余方程組做鋪墊.1.2.3歐幾里德算法

歐幾里德算法

歐幾里德算法

歐幾里德算法-舉例【例】利用歐幾里德算法求〔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語言的一種程序實現(xiàn)方法下面給出C語言的一種程序實現(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; }}下面給出程序的一個運行結果：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、設a為自己的學號，b=210，求整數(shù)s,t，使得as+tb=(a,b)1.3最小公倍數(shù)

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

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

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

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

1.4算術根本定理

標準分解式

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