acm入門數(shù)論初等的概念

1、1ACM 數(shù)論數(shù)論 2初等數(shù)論的概念初等數(shù)論的概念n整除性和約數(shù)：整除性和約數(shù)：n假設(shè)假設(shè)d和和a是整數(shù)，是整數(shù)，d|a（讀作（讀作d整除整除a），意），意味著存在某個整數(shù)味著存在某個整數(shù)k，有，有a=kd。n如果如果d|a，并且，并且d0，則稱，則稱d是是a的約數(shù)。的約數(shù)。n每個整數(shù)每個整數(shù)a都可以被其平凡約數(shù)都可以被其平凡約數(shù)1和和a整除，整除，a的非平凡約數(shù)也稱為的非平凡約數(shù)也稱為a的因子。的因子。3初等數(shù)論的概念n素數(shù)和合數(shù)素數(shù)和合數(shù)n對于某個整數(shù)對于某個整數(shù)a1，如果它僅有平凡約數(shù)，如果它僅有平凡約數(shù)1和和a則稱則稱p是素數(shù)。否則是素數(shù)。否則p是合數(shù)。是合數(shù)。n可以證明素數(shù)有無限多個

2、。可以證明素數(shù)有無限多個。n篩法求素數(shù)。篩法求素數(shù)。4求素數(shù)方法n1）pN存儲所有的素數(shù)，二重循環(huán)，存儲所有的素數(shù)，二重循環(huán)，用已經(jīng)求出的不大于平方根的所有素數(shù)用已經(jīng)求出的不大于平方根的所有素數(shù)試除試除nfor(i=2;in;+i)nfor(j=0;jm & pj*pj=n;+j)n如果如果pj整除整除i，則，則i不是素數(shù)不是素數(shù)n如果都不能整除，則如果都不能整除，則i是素數(shù)，添加到素是素數(shù)，添加到素數(shù)列表數(shù)列表pN;5n2）給定一個范圍（求這個范圍內(nèi)的素）給定一個范圍（求這個范圍內(nèi)的素數(shù)），進(jìn)行如下步驟：數(shù)），進(jìn)行如下步驟： 0.從從2開始，開始，2是第一個素數(shù)。也是第一是第一個素數(shù)。也是第

3、一個新素數(shù)。取出個新素數(shù)。取出2。 1.篩掉所有新素數(shù)的倍數(shù)。篩掉所有新素數(shù)的倍數(shù)。 2.留下來的數(shù)里面第一個（最小的）是留下來的數(shù)里面第一個（最小的）是新素數(shù)。取出這個新素數(shù)。新素數(shù)。取出這個新素數(shù)。 3.重復(fù)重復(fù)1和和2直到?jīng)]有數(shù)存在。直到?jīng)]有數(shù)存在。 Eratosthenes篩法篩法6初等數(shù)論概念初等數(shù)論概念n除法定理，余數(shù)除法定理，余數(shù)n除法定理：對任意整數(shù)除法定理：對任意整數(shù)a和任意正整數(shù)和任意正整數(shù)n，存，存在唯一的整數(shù)在唯一的整數(shù)q和和r，使得，使得a=qn+r，其中，其中0rn。n值值q成為除法的商，值成為除法的商，值r=a(mod n)稱為除法稱為除法的余數(shù)。的余數(shù)。7初等數(shù)

4、論的概念n公約數(shù)與最大公約數(shù)公約數(shù)與最大公約數(shù)nd是是a的約數(shù)并且也是的約數(shù)并且也是b的約數(shù)，則的約數(shù)，則d是是a和和b的公約數(shù)。的公約數(shù)。n兩個不同時為兩個不同時為0的整數(shù)的整數(shù)a和和b的最大公約數(shù)的最大公約數(shù)表示為表示為gcd(a, b)。8初等數(shù)論的概念ngcd(a, b) 的性質(zhì)：的性質(zhì)：n定理：如果定理：如果a，b是不全為是不全為0的任意整數(shù)，則的任意整數(shù)，則gcd(a, b)是是a與與b的線性組合的線性組合ax+by:x,yZ中的最小正元素。中的最小正元素。n推論推論1：對于任意整數(shù)：對于任意整數(shù)a，b，如果，如果d|a并且并且d|b，則，則d|gcd(a, b)。n推論推論2：對

5、于所有整數(shù)：對于所有整數(shù)a和和b以及任意非負(fù)整數(shù)以及任意非負(fù)整數(shù)n，gcd(an, bn)=n*gcd(a,b)。n推論推論3：對所有正整數(shù)：對所有正整數(shù)n，a和和b，如果，如果n|ab并且并且gcd(a, n)=1，則，則n|b。9初等數(shù)論的概念n互質(zhì)數(shù)：互質(zhì)數(shù)：n如果兩個整數(shù)如果兩個整數(shù)a與與b只有公因數(shù)只有公因數(shù)1，即如果，即如果gcd(a, b)=1，則，則a與與b稱為互質(zhì)數(shù)（互素）。稱為互質(zhì)數(shù)（互素）。n定理：對任意整數(shù)定理：對任意整數(shù)a，b和和p，如果，如果gcd(a, p)=1且且gcd(b, p)=1，則，則gcd(ab, p) = 1。10最大公約數(shù)最大公約數(shù) gcd（最大公

6、因子）（最大公因子）nEuclidean算法求兩個正整數(shù)算法求兩個正整數(shù)a和和b的的gcd。先令先令r0為為a，r1為為b，接著執(zhí)行如下運算：，接著執(zhí)行如下運算：11最大公約數(shù)nGCD遞歸定理：對任意非負(fù)整數(shù)遞歸定理：對任意非負(fù)整數(shù)a和任意正和任意正整數(shù)整數(shù)b，gcd(a, b) = gcd(b, a mod b)。12n歐幾里德算法：歐幾里德算法：nEUCLID(a, b)n if b = 0n than return an else return EUCLID(b, a % b)13n二進(jìn)制最大公約數(shù)算法：二進(jìn)制最大公約數(shù)算法：n如果如果a和和b都是都是偶數(shù)，那么都是都是偶數(shù)，那么gcd(

7、a, b) = 2gcd(a/2, b/2)。n如果如果a是奇數(shù)，是奇數(shù)，b是偶數(shù)，那么是偶數(shù)，那么gcd(a, b) = gcd(a, b/2)。n如果如果a和和b都是奇數(shù)，那么都是奇數(shù)，那么gcd(a, b) = (ab)/2, b)。14n思考：思考：n 將兩個整數(shù)的歐幾里德算法推廣到求將兩個整數(shù)的歐幾里德算法推廣到求m個整數(shù)的最大公約數(shù)。個整數(shù)的最大公約數(shù)。15Extended-Euclidean 算法算法n定理：對于不完全為定理：對于不完全為0的非負(fù)整數(shù)的非負(fù)整數(shù)a，b，gcd（a，b）表示）表示a，b的最大公約數(shù)的最大公約數(shù)d，必然存在，必然存在整數(shù)對整數(shù)對x，y，使得，使得gcd

8、（a，b）=d=ax+by。 16擴(kuò)展歐幾里德算法擴(kuò)展歐幾里德算法n對于對于gcd(a,b) = d，對，對(a, b)用歐幾里德輾用歐幾里德輾轉(zhuǎn)相除會最終得到轉(zhuǎn)相除會最終得到(d, 0)。此時對于把。此時對于把a(bǔ) =d, b = 0 代入代入a*x + b*y = d，顯然，顯然x = 1，y可以為任意值?？梢詾槿我庵?。n我們可以用我們可以用a = d, b = 0的情況逆推出來任的情況逆推出來任何何gcd(a, b) = d 滿足滿足a*x + b*y = d的解。的解。如果如果x0，y0是是b*x + (a%b)*y = d 的解，的解，那么對于那么對于a*x + b*y = d的解呢？

9、的解呢？17擴(kuò)展歐幾里德算法擴(kuò)展歐幾里德算法b*x + (a%b)*y = d b*x + (a - a/b*b)*y = a*y + b*(x - a/b*y)，所以所以a*x + b*y = d的解的解x1 = y0， y1= x0 - a/b*y0; 這樣我們可以程序迭代了。這樣我們可以程序迭代了。注：注：a,b為正整數(shù)，設(shè)集合為正整數(shù)，設(shè)集合A = x*a+y*b|x,y是是整數(shù)整數(shù)，則，則A中最小正元素是中最小正元素是gcd(a,b)18n擴(kuò)展歐幾里德算法：擴(kuò)展歐幾里德算法：nEXTENDED-EUCLID(a, b)n if b = 0n then return (a, 1, 0)

10、n (d,x,y) EXTENDED-EUCLID(b, a%b)n (d, x, y) (d, y, x (a/b) * y)n return (d, x, y)19擴(kuò)展歐幾里德算法擴(kuò)展歐幾里德算法20例如：例如：a4864，b3458，則由上述算法可，則由上述算法可得得gcd（4864，3458）38，且，且（4864）（）（38）（）（3458）（）（45）3821LCM(Least Common Multiple)n有了有了 GCD, LCM 就好辦了就好辦了nLCM ( a, b ) = a * b / GCD ( a, b ) n實際上最好寫成實際上最好寫成a/GCD(a,b)*b

11、n思考：為什么下面的寫法好？思考：為什么下面的寫法好？22初等數(shù)論概念n唯一因子分解唯一因子分解n唯一質(zhì)因子分解定理：合數(shù)唯一質(zhì)因子分解定理：合數(shù)a僅能以一種方僅能以一種方式，寫成如下的乘積形式：式，寫成如下的乘積形式：na=p1e1p2e2prern其中其中pi為素數(shù)，為素數(shù)，p1p21，如果，如果gcd(a, n)=1，則方程則方程ax=b(mod n)對模對模n有唯一解。有唯一解。n定理：對任意定理：對任意n1，如果，如果gcd(a, n)=1，則方程則方程ax=1(mod n)對模對模n有唯一解，否有唯一解，否則無解。則無解。37n公元公元56世紀(jì)前后的孫子算經(jīng)中有世紀(jì)前后的孫子算經(jīng)中

12、有“物不知數(shù)物不知數(shù)”問題：問題：“今有物不知其數(shù)，三三數(shù)之余二今有物不知其數(shù)，三三數(shù)之余二 ，五五數(shù)，五五數(shù)之余三之余三 ，七七數(shù)之余二，問物幾何？，七七數(shù)之余二，問物幾何？”答為答為“23”。也就是求同余式組也就是求同余式組x2 （mod3），），x3 （mod5 ），），x2 （mod7）的正整數(shù)解。）的正整數(shù)解。n明朝程大位用歌謠給出了該題的解法：明朝程大位用歌謠給出了該題的解法：“三人同行三人同行七十稀，五樹梅花廿一枝，七子團(tuán)圓月正半，除百七十稀，五樹梅花廿一枝，七子團(tuán)圓月正半，除百零五便得知。零五便得知?！奔唇鉃榧唇鉃?x27032121523323(mod105）。）。 中國剩余

13、定理中國剩余定理381111111111,(mod),11.(mod),(1),1(mod),(1)kkjjkkkkjjjjjjmmaaxamjkxM M aM M ammmm mm MjkMM Mmjk設(shè)是兩兩互素的正整數(shù)，那么，對任意整數(shù)一次同余方程組必有解，且解數(shù)為 事實上，該同余方程組的解是這里以及是滿足的一個整數(shù)。中國剩余定理（孫子定理）中國剩余定理（孫子定理）39歐拉函數(shù)nEuler函數(shù)函數(shù) ：設(shè)：設(shè)m是正整數(shù)，是正整數(shù)，1，2，m中與中與m互素的數(shù)的個數(shù)?；ニ氐臄?shù)的個數(shù)。n定理：定理：( )m121212111( )(1)(1)(1)reeerrmp ppmmppp若，則40()

14、1() 1( ,)11(mod).(mod)FermatEuler( ,)1,(mod)mpma mampaaapa mamaam定理：設(shè)，則有特別當(dāng) 為素數(shù)時，對任意的 有通常把第二個式子稱為小定理。把第一個式子稱為定理。推論：設(shè)則 對模 的逆41n定理：如果定理：如果p是一個奇素數(shù)且是一個奇素數(shù)且e1，則方程，則方程x2=1(mod pe)僅有兩個解：僅有兩個解：x=1和和x=-1。n定理：如果對模定理：如果對模n存在存在1的非平凡平方根，則的非平凡平方根，則n是和數(shù)。是和數(shù)。42元素的冪n3k mod 7為：為：ni 0 1 2 3 4 5 6 7 8 9 10 11n3k mod 7

15、1 3 2 6 4 5 1 3 2 6 4 5n2k mod 7為：為：ni 0 1 2 3 4 5 6 7 8 9 10 11n2k mod 7 1 2 4 1 2 4 1 2 4 1 2 443離散對數(shù)n定義：離散對數(shù)問題（定義：離散對數(shù)問題（Discrete Logarithm problom）是這樣的一個問題：給定一個素）是這樣的一個問題：給定一個素數(shù)數(shù)p，p在在Zp*上的一個原根上的一個原根a，以及一個整數(shù)，以及一個整數(shù)b Zp*。求一個整數(shù)。求一個整數(shù)x（0 xp-1)，使得，使得ax=b(mod p)。記作：。記作：x=logab44離散對數(shù)n例：令例：令p=11，它的一個原根是

16、，它的一個原根是2，因為，因為26=9(mod n)，所以，所以log29=6。另外還有。另外還有26=216=226=9(mod n)45離散對數(shù)n一般離散對數(shù)問題（一般離散對數(shù)問題（GDLP）：給定一個）：給定一個n階的有限循環(huán)群階的有限循環(huán)群G和它的一個原根，以及元和它的一個原根，以及元素素b，求一個整數(shù)，求一個整數(shù)x（0 xn-1），使得），使得ax=b.46離散對數(shù)n計算離散對數(shù)計算離散對數(shù)n窮舉搜索窮舉搜索nBaby-step Giant-step算法算法(Shanks算算法）法）47離散對數(shù)nBaby-step Giant-step算法：算法：nBaby-step Giant-s

17、tep是一個用空間換時間的是一個用空間換時間的對窮舉算法的一個改進(jìn)，令對窮舉算法的一個改進(jìn)，令m=(p-1)1/2，如，如果果b=ax，那么可以把，那么可以把x重寫為重寫為x=i*m+j，其，其中中0 i, j m，于是，于是b=ai*m * aj，兩邊同，兩邊同除得除得b(a-m)i=aj，然后可以通過下面的算法來，然后可以通過下面的算法來計算計算x。48mjmjjm + jx = imibaapm ).(return then if ) (j, then 1 to0 from for (5) (4) (3) (j, p) (mod then m to0jfor (2).1 (1)p) b,

18、 (a, step-giant step-Baby是否存在查看二元組計算并記錄二元組計算49離散對數(shù)nBaby-step Giant-step算法：n復(fù)雜度分析：需要保存(p-1)1/2個二元組，生成這些二元組需要的時間為O(p-1)1/2)，對二元組進(jìn)行排序需要的時間為O(log(p-1)1/2)*(p-1)1/2) .第（5）步的循環(huán)最多執(zhí)行(p-1)1/2次，每次如果采用二分查找來尋找指定元素那么總的時間復(fù)雜度為O(p-1)1/2 log(p-1)1/2)50離散對數(shù)例：令p=113，a=3，b=57執(zhí)行算法：m=11計算出的二元組排好序為：j 0 1 8 2 5 9 3 7 6 10

19、43j(mod 113) 1 3 7 9 17 21 27 40 51 63 81計算a-1=3-1(mod 113) = 38，然后計算a-m=3811(mod 113) = 58執(zhí)行循環(huán)過程中r=b*a-mi，查找過程中的(i, r)為：i 0 1 2 3 4 5 6 7 8 9r 57 29 100 37 112 55 26 39 2 3最終返回：i * m + j = 9 * 11 + 1 = 10051RSA算法算法RSA 算法描述算法描述RSA是是Rivet，Shamir和和Adleman于于1978年年在美國麻省理工學(xué)院研制出來的，它是一種在美國麻省理工學(xué)院研制出來的，它是一種比

20、較典型的公開密鑰加密算法。比較典型的公開密鑰加密算法?；A(chǔ)基礎(chǔ) 大數(shù)分解和素性檢測大數(shù)分解和素性檢測將兩個大素數(shù)相將兩個大素數(shù)相乘在計算上很容易實現(xiàn)，但將該乘積分解為乘在計算上很容易實現(xiàn)，但將該乘積分解為兩個大素數(shù)因子的計算量是相當(dāng)巨大的，以兩個大素數(shù)因子的計算量是相當(dāng)巨大的，以至于在實際計算中是不能實現(xiàn)的。至于在實際計算中是不能實現(xiàn)的。 521.RSA密碼體制的建立：密碼體制的建立：(1)(1)選擇兩個大素數(shù)選擇兩個大素數(shù)p p和和q q；(2)(2)計算乘積計算乘積n=pqn=pq和和(n)=(p-1)(q-1)(n)=(p-1)(q-1)； (3)(3)選擇大于選擇大于1 1小于小于(n

21、)(n)的隨機(jī)整數(shù)的隨機(jī)整數(shù)e e，使得，使得gcd(e,(n)=1gcd(e,(n)=1；(4)(4)計算計算d d使得使得de=1mod (n)de=1mod (n)；(5)(5)對每一個密鑰對每一個密鑰k=(n,p,q,d,e)k=(n,p,q,d,e)，定義加密變換為，定義加密變換為 Ek(x)=xemodnEk(x)=xemodn，解密變換為，解密變換為Dk(x)=ydmodnDk(x)=ydmodn，這里，這里x,yZnx,yZn；(6)(6)以以e,ne,n為公開密鑰，為公開密鑰，p,q,dp,q,d為私有密鑰。為私有密鑰。532.RSA算法實例算法實例:下面用兩個小素數(shù)下面用兩

22、個小素數(shù)7和和17來建立一個簡單的來建立一個簡單的RSA算法：算法：(1)選擇兩個素數(shù)選擇兩個素數(shù)p=7和和q=17；(2)計算計算n=pq=7 17=119，計算，計算(n)=(p-1)(q-1)=6 16=96；(3)選擇一個隨機(jī)整數(shù)選擇一個隨機(jī)整數(shù)e=5，它小于，它小于(n)96并并且于且于96互素；互素；(4)求出求出d，使得，使得de=1mod96且且d96，此處求，此處求出出d=77，因為，因為 77 53854 961；(5)輸入明文輸入明文M19，計算，計算19模模119的的5次冪，次冪，Me19566mod119,傳出密文傳出密文C66；(6)接收密文接收密文66，計算，計算

23、66模模119的的77次冪；次冪；Cd=667719mod119得到明文得到明文19。 54n如果要計算如果要計算Me，將，將e寫成二進(jìn)制形式寫成二進(jìn)制形式bkbk-1b0，這里這里bk1，則有，則有 。因此：。因此：02iibe012021222222()ibikkbbbbbeMMMMMMMMkb計算模指數(shù)的有效算法計算模指數(shù)的有效算法“平方乘平方乘”算法。算法。55這樣可以構(gòu)造一個計算這樣可以構(gòu)造一個計算Memod n的算法：的算法： d=1； for i=k downto 0 do d=d2 mod n； if bi=1 then d=(dM) mod n； return d；計算模指數(shù)

24、的有效算法計算模指數(shù)的有效算法“平方乘平方乘”算法。算法。56如果把如果把M看作矩陣，上面方法可應(yīng)用于矩看作矩陣，上面方法可應(yīng)用于矩陣乘方陣乘方n改進(jìn)乘方算法應(yīng)用于改進(jìn)乘方算法應(yīng)用于fibonacci：普通的算法：普通的算法求求Fn的時間復(fù)雜度為的時間復(fù)雜度為O(n)，當(dāng)然如果要求求，當(dāng)然如果要求求出所有的出所有的Fn，這種已經(jīng)是最優(yōu)的了，但是如，這種已經(jīng)是最優(yōu)的了，但是如果只求某一個果只求某一個Fn，可以改進(jìn)：，可以改進(jìn)：Fn11Fn1Fn-110Fn2n-2Fn11F2Fn-110F157素數(shù)測試的一個有用的近似。素數(shù)定理給出。，個，分別是的素數(shù)總共有等于，因為小于素數(shù)的個數(shù)。例如的描述了小于等于素數(shù)分布函數(shù))(75324104)10(n)(nn58素數(shù)測試。，而，這時時，其誤差不超過當(dāng)如，相當(dāng)精確的估計值。例可以給出也，近似計算是即使對于比較小的素數(shù)定理：48254942ln/50847534)(%610n)(ln/n1ln/)(9limnnnnnnnnnn59素數(shù)測試字減少一半）奇數(shù)，還可以把這個數(shù)試。（通過只選位長的整數(shù)進(jìn)行素數(shù)測的個隨機(jī)選取的素數(shù)，大約需要對位出一個個整數(shù)。例如，為了找進(jìn)的附查在相同的素數(shù)，大約要檢一個長度與。因此為了找到是素數(shù)的概率為整數(shù)算出一個隨機(jī)選取的運