數(shù)論問題 (2)

1、青蛙的約會 (POJ1061)大意：兩只青蛙在網(wǎng)上相識了，它們聊得很開心，于是覺得很有必要見一面。它們很高興地發(fā)現(xiàn)它們住在同一條緯度線上，于是它們約定各自朝西跳，直到碰面為止。青蛙們都是很樂觀的，它們覺得只要一直朝著某個方向跳下去，總能碰到對方的。但是除非這兩只青蛙在同一時間跳到同一點(diǎn)上，不然是永遠(yuǎn)都不可能碰面的。為了幫助這兩只樂觀的青蛙，你被要求寫一個程序來判斷這兩只青蛙是否能夠碰面，會在什么時候碰面。,我們把這兩只青蛙分別叫做

2、青蛙A和青蛙B，并且規(guī)定緯度線上東經(jīng)0度處為原點(diǎn)，由東往西為正方向，單位長度1米，這樣我們就得到了一條首尾相接的數(shù)軸。設(shè)青蛙A的出發(fā)點(diǎn)坐標(biāo)是x，青蛙B的出發(fā)點(diǎn)坐標(biāo)是y。青蛙A一次能跳m米，青蛙B一次能跳n米，兩只青蛙跳一次所花費(fèi)的時間相同。緯度線總長L米?，F(xiàn)在要你求出它們跳了幾次以后才會碰面。 輸入只包括一行5個整數(shù)x，y，m，n，L，其中x≠y < 2000000000，0 < m、n < 2000000000，

3、0 < L < 2100000000。輸出碰面所需要的跳躍次數(shù)，如果永遠(yuǎn)不可能碰面則輸出一行"Impossible",數(shù) 論 問 題,華哲邦 00848122,※整除性和約數(shù)a|b： a能整除b整數(shù)a的約數(shù) 稱1和a為平凡約數(shù) 其他的約數(shù)稱為非平凡約數(shù),※素數(shù)和合數(shù)僅有平凡約數(shù)的數(shù)為素數(shù)（質(zhì)數(shù)），其他為合數(shù)定理:素數(shù)有無窮多個構(gòu)造法 p1,p2,p3….pn pn+1=p1

4、83; p2 ·...· pn + 1,※除法定理 余數(shù) 同模[a]n={ a+kn : k∈ Z }Zn={0,1,……,n-1},※公約數(shù) 最大公約數(shù)d=gcd(a,b)=ax+by (x,y) ∈ ZGCD遞歸定理gcd(a,b)= gcd(b,a mod b),歐幾里得算法EUCLID(a,b) if b=0 then return a else ret

5、urn EUCLID(b,a mod b),下面分析一下歐幾里得算法的運(yùn)行時間,引理1：如果a>b>0并且EUCLID(a,b)執(zhí)行了k>0次遞歸調(diào)用，則a≥Fk，b≥Fk+1。其中，F(xiàn)k為斐波那契數(shù)列項(F1=F2=1)。證明可以通過歸納法：設(shè)k=1，則b≥1=F2，a>b則有a≥2=F3假設(shè)k-1次遞歸調(diào)用時成立。EUCLID(a,b)遞歸調(diào)用EUCLID(b,a mod b)。由歸納知b ≥Fk+1，

6、(a mod b) ≥ Fk，所以有：a ≥ b+(a mod b) ? a ≥ b+(a mod b) ≥ Fk+1 + Fk = Fk+2,由此我們可以得到Lamé定理,,Lamé定理對任意整數(shù)k，如果a>b≥1且b<Fk+1，則EUCLID(a,b)的遞歸調(diào)用次少于k次。所以EUCLID(a,b)執(zhí)行遞歸調(diào)用次數(shù)為O(lgb),歐幾里得算法的推廣形

7、式為了求出 d=gcd(a,b)=ax+by (x,y) ∈ Z 中的x、y，可以使用EXTENDED-EUCLID算法其輸入為一對非負(fù)整數(shù)，返回一個三元式(d,x,y),EXTENDED-EUCLID(a,b) if b=0 then return (a,1,0) (d’,x’,y’)=EXTENDED-EUCLID(b,a mod b) (d ,x ,y )=(d’,y’,x’-

8、 ) return (d, x, y),,,,d=bx’+(a mod b)y’? d=bx’+(a- b)y’? d=ay’+b(x’- ),基本概念：有限群,群G是一個元素集合和G上的二元運(yùn)算⊕滿足以下性質(zhì)：封閉性：若存在 ，那么結(jié)合律：單位元：存在 ，對于任意 都滿足逆元素：對任意 ，存在 ，使得 記|G

9、|<∞,則它是一個有限群,,定義模n加法與乘法如下:[a]n+n[b]n=[a+b]n[a]n·n[b]n=[ab]n則可得有限可交換群:(Zn,+n)與(Zn*,·n)其中(Zn,+n) 同前面定義, (Zn*,·n)={ [a]n∈Zn ; gcd(a,n)=1 }由歐拉公式容易得出|Zn*|=φ(n)=n∏(1- )其中p為n的所有質(zhì)因數(shù) 并有φ(p)=p-1(p為質(zhì)數(shù)),定

10、義：一個有限群的非空封閉子集是一個子群給出一種生成一個有限群 的子群的方法：選取一個元素a，并取出根據(jù)群上的運(yùn)算由a所能生成的所有元素。由則a生成的子群={ a(k) : k≥1 } 例如在Z6中，有={0} ={0,1,2,3,4,5}={0,2,4},定義：在群S中a的階用ord(a)來表示，定義為滿足a(t)=e的最小正整數(shù)t。定理：對任意有限群 和任意 ，一個元素的階等于它所生

11、成的子群的規(guī)模，即ord(a)=||由此可以得到一些推論：序列a(1),a(2),……是周期性序列，其周期為t=ord(a)；即a(i)=a(j)當(dāng)且公當(dāng)i≡j(mod t)。如果 是一個具有單位元e的有限群，則對所有的 ，有a(|S|)=e這些定理將為下面的一些結(jié)論做鋪墊,求解模線性方程考慮求解下列方程的問題： ax ≡ b (mod n)其中a>0，n>0。這個問題有若干種應(yīng)用；例如，在RSA公

12、鑰密碼系統(tǒng)中，尋找密鑰過程的一部分。 該方程可能沒有解，也有可能有一個或多個解。定理：對任意正整數(shù)a和n，如果d=gcd(a,n)，則在Zn中=={0,d,2d,3d,…,((n/d)-1)d}因此有 ||=n/d,大概證明過程：由ax’+ny’=d可以得ax’≡ d (mod n)，所以d∈。由于d∈，所以d的所有倍數(shù)均屬于，所以再證明 。如果m ∈，則對某個整數(shù)x有m=ax mod n，所以對

13、某個整數(shù)y有m=ax+ny。但是，d|a并且d|n，所以有d|m。因此m ∈。綜上得證。,推論：方程ax ≡ b (mod n)或者對模n有d個不同的解，其中d=gcd(a,n)且要有d|b；或者無解，即d不能整除b時。大概證明：如果有一個解，則b∈ ∈{0,d,2d,3d,…,((n/d)-1)d}，||=n/d，則可得一個周期為n/d的周期性數(shù)列，在x從0到n-1這n個數(shù)中，可得d組周期，其中每一組得一個解，即共有d個不同的解

14、x。,如果d|b，設(shè)d=ax’+ny’，則方程有一個解的值為x0，滿足x0=x’(b/d)mod nax0 ≡ ax’(b/d) (mod n) ≡ d(b/d) (mod n) ≡ b (mod n) 所以x0是一個解綜上，我們可以得到在有解的情況下的d個解xi=x0+i(n/d) (i=1,2,…,d-1),下列算法可以求解方程ax ≡ b (mod n)，輸入為a、n、b，輸

15、出為所有解或無解MODULAR-LINEAR-EQUATION-SOLVER(a,b,n) (d,x’,y’)=EXTENDED-EUCLID(a,b) //求出d=gcd(a,b)=ax’+by’ if d|b then x0=x’(b/d) mod n for i=0 to d-1

16、 do print (x0+i(n/d)) mod n else print “no solutions”,回頭看青蛙約會的問題,就是要有 x+mi ≡y+ni (mod L) ? (m-n)i ≡y-x (mod L)所以方程有解的條件是 gcd(m-n,L)|y-x在有解的情況下,可以根據(jù)上面求解模線性方程的方法先求出一個解,然后再求出一個最小正整數(shù)解,中國余數(shù)定理(孫子定理)大約公元前00年，中國的

17、數(shù)學(xué)家孫子解決了以下問題：找出被3,5和7除時余數(shù)分別為2,3和2的所有整數(shù)x。有一個解為x=23；所有的解是形如23+105k（k為任意整數(shù)）的整數(shù)下面，我們要找出這樣問題的通用解法。注意到，上面給出的3,5,7是互質(zhì)的，我們先將問題歸為：n1,n2,…,nk互質(zhì)，求除它們分別余a1,a2,…ak的整數(shù),,設(shè)n=n1*n2*…*nk，我們可以求出在對n取模下的唯一解設(shè)mi=n/ni，即mi=n1*n2*…ni-1*ni+1*

18、…*nk則顯然有mi與ni互質(zhì)，所以(mi-1 mod ni)有定義定義ci=mi(mi-1 mod ni)a ≡ (a1c1+a2c2+…+akck) (mod n),其正確性是顯然的，考慮k時，對于i≠k,顯然有aici ≡ 0(mod nk)對于i=k，akck ≡akmi(mi-1 mod nk) (mod ni) ≡ak (mod ni)至此，我們解出了原方程的解，并且可以證明是一一對應(yīng)

19、的，即解的唯一性,元素的冪歐拉定理：對于任意整數(shù)n>1,aφ(n) ≡ 1 (mod n)對所有a ∈Zn*都成立費(fèi)馬定理：如果p是素數(shù)，則ap-1 ≡ 1 (mod p),對于冪的問題，經(jīng)常要做的就是求一個數(shù)的冪對另外一個數(shù)的模運(yùn)算ak mod n，也稱模取冪?？梢圆捎枚M(jìn)制來表示b，采用反復(fù)平方法。我們設(shè)(bk,bk-1,…,b1,b0)是b的二進(jìn)制表示,反復(fù)平方法MODULAR-EXPONENTIATION(a,b,

20、n) c=0 d=0 let (bk,bk-1,…,b1,b0) be the binary representaion of b for i=k downto 0 do c=2c d=(d*d) mod n if bi=1 then c=c+1 d=(d*a)mod

21、n return d,數(shù)論的應(yīng)用RSA公鑰加密系統(tǒng)（public-key cyptosystem）在公鑰加密系統(tǒng)中，每個參與者都用一把公鑰和一把密鑰。每把密鑰是一條信息。在密碼學(xué)中常把參與者“Alice”和”Bob”作為例子用PA和SA分別表示Alice的分鑰和密鑰，用PB和SB分別表示Bob的公鑰和密鑰。 C為密文，M為明文,,PA,Bob加密,,,竊密者,信道 C=PA(M),SA,Alice解密,,M,對于竊密者，即使得到

22、了密文，但不知道密鑰，也是無法破譯的；而Alice則可以。所以說，任何人都可以得到Alice的公鑰PA進(jìn)行加密，再傳送給Alice，而只有Alice本人可以解密。這就確保了信息的安全性以及傳遞信息的便捷性。所以關(guān)鍵即在于如何選擇這樣的公鑰、密鑰。下面簡單介紹一種方案：,1.隨機(jī)選取兩個大素數(shù)p和q，且p≠q，p和q很大2.令n=pq3.選取一個與φ(n)互質(zhì)的小奇數(shù)e4.對模φ(n)，計算出e的乘法逆元d的值5.輸出對P=(

23、e,n)，作為RSA公鑰6.把對S=(d,n)保密，作為RSA密鑰這個方案的域為Zn。加密變換為P(M)=Me(mod n)解密變換為S(C)=Cd(mod n)顯然Cd (mod n) =(Me)d (mod n)=M,其正確性是顯然的，關(guān)鍵在于安全性。也就在于別人能否輕易得算出密鑰中的d。Alice本人知道n=pq，所以很容易得到φ(n)=(p-1)(q-1)，再用歐幾里得算法的推廣形式及模線性方程解法可以求出e

24、x ≡1(mod φ(n))中的e。別人則不知道n是如何分解的，要知道，分解一個這樣極大的數(shù)是很難的（在2001年，RSA模數(shù)通常是在768位到2048位范圍內(nèi)），這在上目前數(shù)論算法的設(shè)計方法還沒有有效的解法。,關(guān)于素數(shù)的測試Miller_Rabin隨機(jī)性素數(shù)測試方法?；?費(fèi)馬定理：如果p是素數(shù)，則ap-1 ≡ 1 (mod p)其合數(shù)判斷是決對正確的；素數(shù)判斷時，加上取多個a的判斷，其準(zhǔn)確性也是相當(dāng)高的，并且隨位數(shù)升高而更

25、準(zhǔn)確。,POJ 2417 Discrete Logging Time Limit:5000MS  Memory Limit:65536K題目大意:對于方程：BL ≡ N (mod P) 輸入為多組數(shù)據(jù)：質(zhì)數(shù)P, 2 <= P < 231,整數(shù) B, 2 <= B < P,整數(shù) N, 2 <= N < P,輸出最小正整數(shù) L例如 INPUT： 5 3 2 P=5 B=3 N

26、=2 最小的L為3 滿足33 ≡ 2 (mod 5) OUTPUT： 3,直接暴力搜，顯然要從0搜到p-1，由于對質(zhì)數(shù)P取冪模，其循環(huán)周期長可達(dá)φ(P)=P-1=231-1，肯定會超時。又沒有求解冪模方程的通解公式。所以只有考慮先通過數(shù)學(xué)上的變換進(jìn)行簡化。,解BL ≡ N (mod P)的方程,求最小的L值我們?nèi)=sqrt(p-1)取上整設(shè)L=i*m+j (0<i<m,0<j<m)則方程化

27、為 (N*B-m*i ) % p = Bj % p?(N*(B-m)i) % p = Bj % p而我們又知道 B-m % p= B(p-1)-m % p于是，我們只要算出B-m % p，然后窮舉i，再對j進(jìn)行搜索即可求得最小解。但是如果我們直接搜j，那其實還是m2≈p的搜索次數(shù)，于是需要一些簡化。,可以定義數(shù)組，struct nummod{ int num,val; } arr [1000000];其中

28、 val ≡ Bnum(mod p)num從0到m-1，分別計算出值存入，然后進(jìn)行排序。以val為第一關(guān)鍵字，num為第二關(guān)鍵字從小到大排序，以便于二分搜索j，且可以保證當(dāng)有解時其為最小解。如果搜索結(jié)束仍無合適解，則為無解。,作業(yè) POJ 1061 青蛙的約會(很水~)POJ 1006 生理周期（用孫子定理解一下）POJ 2417 Discrete Logging ACM 3604 Professor Ben （關(guān)于整數(shù)