補(bǔ)充材料數(shù)論基礎(chǔ)

1、數(shù)論基礎(chǔ),4.1 數(shù)論簡介習(xí)題,4.1.1 素?cái)?shù)和互素?cái)?shù)1. 因子設(shè)a，b(b≠0)是兩個(gè)整數(shù)，如果存在另一整數(shù)m，使得a=mb，則稱b整除a，記為b|a，且稱b是a的因子。,4.1 數(shù)論簡介,數(shù)論是密碼學(xué)特別是公鑰密碼學(xué)的基本工具，本章首先介紹密碼學(xué)中常用的一些數(shù)論知識(shí)，然后介紹公鑰密碼體制的基本概念和幾種重要算法。,整數(shù)具有以下性質(zhì)： ① a|1，那么a=±1。② a|b且b|a，則a=±b。③

2、 對任一b (b≠0)，b|0。④ b|g，b|h，則對任意整數(shù)m、n有b|(mg+nh)。這里只給出④的證明，其他3個(gè)性質(zhì)的證明都很簡單。性質(zhì)④的證明： 由b|g，b|h知，存在整數(shù)g1、h1，使得g=bg1,h=bh1所以mg+nh=mbg1+nbh1=b(mg1+nh1),因此b|(mg+nh)。,2. 素?cái)?shù)稱整數(shù)p(p>1)是素?cái)?shù)，如果p的因子只有±1，±p。任一整數(shù)a(a>1)都能惟一

3、地分解為以下形式： 其中p1>p2>…pt是素?cái)?shù)，ai>0(i=1,…,t)。例如91=7×11，11011=7×112×13,這一性質(zhì)稱為整數(shù)分解的惟一性，也可如下陳述： 設(shè)P是所有素?cái)?shù)集合，則任意整數(shù)a (a>1)都能惟一地寫成以下形式：其中ap≥0,等號(hào)右邊的乘積項(xiàng)取所有的素?cái)?shù)，然而大多指數(shù)項(xiàng)ap為0。相應(yīng)地，任一正整數(shù)也可由非0指數(shù)列表表示。例如： 11011可表

4、示為{a7=1,a11=2,a13=1}。兩數(shù)相乘等價(jià)于對應(yīng)的指數(shù)相加，即由k=mn 可得：對每一素?cái)?shù)p,kp=mp+np。而由a|b可得： 對每一素?cái)?shù)p,ap≤bp。這是因?yàn)閜k只能被pj(j≤k)整除。,3. 互素?cái)?shù)稱c是兩個(gè)整數(shù)a、b的最大公因子，如果① c是a的因子也是b 的因子，即c是a、b的公因子。② a和b的任一公因子，也是c的因子。表示為c=gcd(a, b)。由于確定大數(shù)的素因子不很容易，所以這種方法不能直

5、接用于求兩個(gè)大數(shù)的最大公因子，如何求兩個(gè)大數(shù)的最大公因子在下面介紹。如果gcd(a,b)=1，則稱a和b互素。,由于要求最大公因子為正，所以gcd(a,b)=gcd(a,-b)=gcd(-a,b)=gcd(-a,-b)。一般gcd(a,b)=gcd(|a|,|b|)。由任一非0整數(shù)能整除0，可得gcd(a,0)=|a|。如果將a，b都表示為素?cái)?shù)的乘積，則gcd（a, b）極易確定。例如：300=22×31×

6、5218=21×32gcd(18,300)=21×31×50=6一般由c=gcd(a,b)可得： 對每一素?cái)?shù)p，cp=min(ap,bp)。,設(shè)n是一正整數(shù)，a是整數(shù)，如果用n除a，得商為q，余數(shù)為r，則a=qn+r,0≤r<n, 其中x為小于或等于x的最大整數(shù)。用a mod n表示余數(shù)r，則 。

7、如果(a mod n)=(b mod n)，則稱兩整數(shù)a和b模n同余，記為a≡b mod n。稱與a模n同余的數(shù)的全體為a的同余類，記為[a]，稱a為這個(gè)同余類的表示元素。注意： 如果a≡0(mod n)，則n|a。,4.1.2 模運(yùn)算,同余有以下性質(zhì)： ① 若n|(a-b)，則a≡b mod n。② (a mod n)≡(b mod n)，則a≡b mod n。③ a≡b mod n,則b≡a mod n。④ a≡b mo

8、d n,b≡c mod n,則a≡c mod n。從以上性質(zhì)易知，同余類中的每一元素都可作為這個(gè)同余類的表示元素。,求余數(shù)運(yùn)算（簡稱求余運(yùn)算）a mod n將整數(shù)a映射到集合{0,1, …,n-1}，稱求余運(yùn)算在這個(gè)集合上的算術(shù)運(yùn)算為模運(yùn)算，模運(yùn)算有以下性質(zhì)： ① [(a mod n)+(b mod n)] mod n=(a+b) mod n。② [(a mod n)-(b mod n)] mod n=(a-b) mod n。③

9、 [(a mod n)×(b mod n)] mod n=(a×b) mod n。,性質(zhì)①的證明： 設(shè)（a mod n）=ra，(b mod n)=rb，則存在整數(shù)j、k使得a=jn+ra，b=kn+rb。因此(a+b) mod n=[(j+k)n+ra+rb] mod n=(ra+rb) mod n= [(a mod n)+(b mod n)] mod n （證畢）性質(zhì)

10、②、③的證明類似。,例4.1 設(shè)Z8={0,1,…,7}，考慮Z8上的模加法和模乘法，結(jié)果如表4.1所示。（見77頁表4.1）從加法結(jié)果可見，對每一x，都有一y，使得x+y≡0 mod 8。如對2，有6，使得2+6≡0 mod 8，稱y為x的負(fù)數(shù)，也稱為加法逆元。對x，若有y，使得x×y≡1 mod 8，如3×3≡1 mod 8，則稱y為x的倒數(shù)，也稱為乘法逆元。本例可見并非每一x都有乘法逆元。,一般地，定義Zn

11、為小于n的所有非負(fù)整數(shù)集合，即Zn={0,1, …,n-1}，稱Zn為模n的同余類集合。其上的模運(yùn)算有以下性質(zhì)： ① 交換律 (w+x) mod n=(x+w) mod n(w×x) mod n=(x×w) mod n② 結(jié)合律 [(w+x)+y] mod n=[w+(x+y)] mod n[(w×x)×y] mod n=[w×(x×y)] mod n③

12、分配律 [w×(x+y)] mod n=[w×x+w×y] mod n④ 單位元 (0+w) mod n=w mod n(1×w) mod n=w mod n⑤ 加法逆元 對w∈Zn，存在z∈Zn，使得w+z≡0 mod n，記z=-w。,此外還有以下性質(zhì)： 如果(a+b)≡(a+c) mod n，則b≡c mod n，稱為加法的可約律。該性質(zhì)可由(a+b)≡(a+c) mo

13、d n的兩邊同加上a的加法逆元得到。,然而類似性質(zhì)對乘法卻不一定成立。例如6×3≡6×7≡2 mod 8，但37 mod 8。原因是6乘以0到7得到的8個(gè)數(shù)僅為Z8的一部分，見例4.1。即如果將對Z8作6的乘法6×Z8（即用6乘Z8中每一數(shù)）看作Z8到Z8的映射的話，Z8中至少有兩個(gè)數(shù)映射到同一數(shù)，因此該映射為多到一的，所以對6來說，沒有惟一的乘法逆元。但對5來說，5×5≡1 mod 8，因此5

14、有乘法逆元5。仔細(xì)觀察可見，與8互素的幾個(gè)數(shù)1，3，5，7都有乘法逆元。這一結(jié)論可推廣到任一Zn。,定理4.1 設(shè)a∈Zn，gcd(a, n)=1，則a在Zn中有乘法逆元。證明： 首先證明a與Zn中任意兩個(gè)不相同的數(shù)b、c（不妨設(shè)c<b）相乘，其結(jié)果必然不同。否則設(shè)a×b≡a×c mod n，則存在兩個(gè)整數(shù)k1,k2，使得ab=k1n+r，ac=k2n+r，可得a(b-c)=(k1-k2)n，所以a是(k1

15、-k2)n的一個(gè)因子。又由gcd(a，n)=1，得a是k1-k2的一個(gè)因子，設(shè)k1-k2=k3a，所以a(b-c)=k3an，即b-c=k3n，與0<c<b<n矛盾。所以|a×Zn|=|Zn|，又知a×ZnZn，所以a×Zn=Zn。因此對1∈Zn，存在x∈Zn，使得a×x≡1 mod n，即x是a的乘法逆元。記為x=a-1。

16、 （證畢）,設(shè)p為一素?cái)?shù)，則Zp中每一非0元素都與p互素，因此有乘法逆元。類似于加法可約律，可有以下乘法可約律： 如果(a×b)≡(a×c) mod n且a有乘法逆元，那么對(a×b)≡(a×c) mod n兩邊同乘以a-1，即得b≡c mod n,費(fèi)爾瑪 (Fermat) 定理和歐拉 (Euler) 定理在公鑰密碼體制中起著重要作用。1. 費(fèi)爾瑪定理定理4

17、.2 (Fermat)若p是素?cái)?shù)，a是正整數(shù)且gcd(a, p)=1，則ap-1≡1 mod p。證明：由4.1.2的討論知當(dāng)gcd(a, p)=1時(shí),a×Zp=Zp，其中a×Zp表示a與Zp中每一元素做模p乘法。又知a×0≡0 mod p，所以a×Zp-{0}=Zp-{0}，a×(Zp-{0})=Zp-{0}。即{a mod p,2a mod p,…,(p-1)a mod p}={

18、1,2,…,p-1},4.1.3 費(fèi)爾瑪定理和歐拉定理,所以 a×2a×…×(p-1)a≡[(a mod p)×(2a mod p)×…×((p-1)a mod p)] mod p≡(p-1)! mod p另一方面a×2a×…×(p-1)a=(p-1)!ap-1因此(p-1)!ap-1≡(p-1)! mod p由于(p-1)

19、!與p互素，因此(p-1)!有乘法逆元，由乘法可約律得ap-1≡1 mod p。 （證畢）,Fermat定理也可寫成如下形式： 設(shè)p是素?cái)?shù)，a是任一正整數(shù)，則ap≡a mod p。2. 歐拉函數(shù)設(shè)n是一正整數(shù)，小于n且與n互素的正整數(shù)的個(gè)數(shù)稱為n的歐拉函數(shù)，記為φ(n)。例如： φ(6)=2 ，φ(7)=6 ，φ(8)=4。若n是素?cái)?shù)，則顯然有φ(n)=n-1。例如： 由21=

20、3×7，得φ(21)=φ(3)×φ(7)=2×6=12。,定理4.3 若n是兩個(gè)素?cái)?shù)p和q的乘積，則φ(n)=φ(p)×φ(q)=(p-1)×(q-1)。證明：考慮Zn={0,1,…,pq-1}，其中不與n互素的數(shù)有3類，A={p,2p,…,(q-1)p}，B={q,2q,…,(p-1)q},C={0}，且A∩B=Φ，否則ip=jq，其中1≤i≤q-1，1≤j≤p-1,則p是jq的因子

21、，因此是j的因子，設(shè)j=kp，k≥1。則ip=kpq，i=kq，與1≤i≤q-1矛盾。所以φ(n)=|Zn|-[|A|+|B|+|C|]=pq-[(q-1)+(p-1)+1] =(p-1)×(q-1)=φ(p)×φ(q) （證畢）,3. 歐拉定理定理4.4（Euler） 若a和n互素，則aφ(n)≡1 mod n。證明： 設(shè)R={x1,x2,…,xφ(n)}是由小于n且與n互素的

22、全體數(shù)構(gòu)成的集合，a×R={ax1 mod n,ax2 mod n,…,axφ(n) mod n}，對a×R中任一元素axi mod n，因a與n互素，x1與n互素，所以axi與n互素，且axi mod n<n，因此axi mod n∈R，所以a×RR。,又因a×R中任意兩個(gè)元素都不相同，否則axi mod n=axj mod n，由a與n互素知a在 mod n下有乘法逆元，得xi=xj。

23、所以|a×R|=|R|，得a×R=R，所以 ， , ，由每一xi與n互素，知 與n互素， 在 mod n下有乘法逆元。所以aφ(n)≡1 mod n。

24、 (證畢）,素性檢驗(yàn)是指對給定的數(shù)檢驗(yàn)其是否為素?cái)?shù)。對于大數(shù)的素性檢驗(yàn)來說沒有簡單直接的方法，本節(jié)介紹一個(gè)概率檢驗(yàn)法，為此需要以下引理。,4.1.4 素性檢驗(yàn),引理 如果p為大于2的素?cái)?shù)，則方程x2≡1(mod p)的解只有x≡1和x≡-1。證明：由x2≡1 mod p，有x2-1≡0 mod p，(x+1)(x-1)≡0 mod p，因此p|(x+1)或p|(x-

25、1)或 p|(x+1)且p|(x-1)。若p|(x+1)且p|(x-1)，則存在兩個(gè)整數(shù)k和j，使得x+1=kp，x-1=jp,兩式相減得2=(k-j)p，為不可能結(jié)果。所以有p|(x+1)或p|(x-1)。設(shè)p|(x+1)，則x+1=kp，因此x≡-1(mod p)。類似地可得 x≡1(mod p)。（證畢）,引理的逆否命題為：如果方程x2≡1 mod p有一解x0{-1,1}，那么p不為素?cái)?shù)。例如： 考慮方程x2≡1(mo

26、d 8)由4.1.2節(jié)Z8上模乘法的結(jié)果得12≡1 mod 8, 32≡1 mod 8, 52≡1 mod 8, 72≡1mod 8又5≡-3 mod 8，7≡-1 mod 8，所以方程的解為1，-1，3，-3，可見8不是素?cái)?shù)。,下面介紹Miller-Rabin的素性概率檢測法。首先將n-1表示為二進(jìn)制形式bkbk-1…b0，并給d賦初值1，則算法Witness(a,n)的核心部分如下： for i=k downto 0 do

27、{x←d;d←(d×d) mod n;if d=1 and(x≠1)and(x≠n-1)then return False;if bi=1 then d←(d×a) mod n}if d≠1 then return False;return True.,此算法有兩個(gè)輸入?yún)?shù)，n是待檢驗(yàn)的數(shù)，a是小于n的整數(shù)。如果算法的返回值為False，則n肯定不是素?cái)?shù)，如果返回值為True，則n

28、有可能是素?cái)?shù)。for循環(huán)結(jié)束后，有d≡an-1 mod n，由Fermat定理知，若n為素?cái)?shù)，則d為1。因此若d≠1，則n不為素?cái)?shù)，所以返回False。因?yàn)閚-1≡-1 mod n，所以(x≠1)and(x≠n-1),指x2≡1 (mod n)有不在{-1,1}中的根，因此n不為素?cái)?shù)，返回False。該算法有以下性質(zhì)： 對s個(gè)不同的a，重復(fù)調(diào)用這一算法，只要有一次算法返回為False，就可肯定n不是素?cái)?shù)。如果算法每次返回都為Tru

29、e，則n是素?cái)?shù)的概率至少為1-2-s，因此對于足夠大的s，就可以非?？隙ǖ叵嘈舗為素?cái)?shù)。,歐幾里得（Euclid）算法是數(shù)論中的一個(gè)基本技術(shù)，是求兩個(gè)正整數(shù)的最大公因子的簡化過程。而推廣的Euclid算法不僅可求兩個(gè)正整數(shù)的最大公因子，而且當(dāng)兩個(gè)正整數(shù)互素時(shí)，還可求出其中一個(gè)數(shù)關(guān)于另一個(gè)數(shù)的乘法逆元。,4.1.5 歐幾里得算法,1. 求最大公因子Euclid算法是基于下面一個(gè)基本結(jié)論： 對任意非負(fù)整數(shù)a和正整數(shù)b，有g(shù)cd(a,

30、b)=gcd(b, a mod b)。證明：b是正整數(shù)，因此可將a表示為a=kb+r≡r mod b，a mod b=r,其中k為一整數(shù)，所以a mod b =a-kb。設(shè)d是a，b的公因子，即d|a，d|b，所以d|kb。由d|a和d|kb得d|(a mod b)，因此d是b和a mod b的公因子。所以得出a，b的公因子集合與b，a mod b的公因子集合相等，兩個(gè)集合的最大值也相等。（證畢）,例如： gcd(55, 22)=

31、gcd(22, 55 mod 22)=gcd(22,11)=gcd(11, 0)=11。在求兩個(gè)數(shù)的最大公因子時(shí)，可重復(fù)使用以上結(jié)論。例如： gcd(18,12)=gcd(12,6)=gcd(6,0)=6, gcd(11,10)=gcd(10,1)=gcd(1,0)=1。,Euclid算法就是用這種方法，因gcd(a, b)=gcd(|a|, |b|)，因此可假定算法的輸入是兩個(gè)正整數(shù)，設(shè)為d，f，并設(shè)f >d

32、。Euclid（f, d）1. X←f; Y←d；2. if Y=0 then return X=gcd(f,d)；3. R=X mod Y；4. X=Y；5. Y=R；6. goto 2。,例4.2 求gcd(1970, 1066)。1970=1×1066+904,gcd(1066, 904)1066=1×904+162,gcd(904, 162)904=5×162+94,g

33、cd(162, 94) 162=1×94+68,gcd(94, 68) 94=1×68+26,gcd(68, 26)68=2×26+16,gcd(26, 16) 26=1×16+10,gcd(16, 10) 16=1×10+6,gcd(10, 6) 10=1×6+4,gcd(6, 4)6=1×4+2,gcd(4, 2)

34、 4=2×2+0,gcd(2, 0)因此gcd(1970, 1066)=2。,中國剩余定理是數(shù)論中最有用的一個(gè)工具，定理說如果已知某個(gè)數(shù)關(guān)于一些兩兩互素的數(shù)的同余類集，就可重構(gòu)這個(gè)數(shù)。例如：Z10中每個(gè)數(shù)都可從這個(gè)數(shù)關(guān)于2和5（10的兩個(gè)互素的因子）的同余類重構(gòu)。比如已知x關(guān)于2和5的同余類分別是[0]和[3]，即x mod 2≡0，x mod 5≡3。可知是偶數(shù)且被5除后余數(shù)是3，所以可得8是滿足這一關(guān)系的惟一的

35、x。,4.1.6 中國剩余定理,定理4.5（中國剩余定理） 設(shè)m1,m2,…,mk是兩兩互素的正整數(shù)， ，則一次同余方程組對模M有惟一解:其中ei滿足,證明：設(shè) ,i=1,2,…,k，由Mi的定義得Mi與mi是互素的，可知Mi在模mi下有惟一的乘法逆元，即滿足 的e

36、i是惟一的。,下面證明對i∈{1,2,…,k}，上述x滿足ai(mod mi)≡x。注意到當(dāng)j≠i時(shí)，mi|Mj，即Mj≡0(mod mi)。所以(Mj×ej mod mj) mod mi ≡((Mj mod mi)×((ej mod mj) mod mi)) mod mi ≡0而(Mi×(ei mod mi)) mod mi≡(Mi×ei) mod mi≡1所以x(mod

37、 mi)≡ai，即ai(mod mi)≡x,下面證明方程組的解是惟一的。設(shè)x′是方程組的另一解，即x′≡ai(mod mi)(i=1,2,…,k)由x≡ai(mod mi)得x′-x≡0(mod mi)，即mi|(x′-x)。再根據(jù)mi兩兩互素，有M|(x′-x)，即x′-x≡0(mod M)，所以x′(mod M)=x(mod M)。(證畢)中國剩余定理提供了一個(gè)非常有用的特性，即在模M下可將非常大的數(shù)x由一組小數(shù)(a1,a

38、2,…,ak)表達(dá)。,例4.4 由以下方程組求x。解： M=2·3·5·7=210，M1=105，M2=70，M3=42，M4=30,易求e1≡M-11 mod 2≡1,e2≡M-12mod 3≡1,e3≡M-13 mod 5≡3,e4≡M-14 mod 7≡4,所以x mod 210≡(105×1×1+70×1×2+42×3×3+30