補充材料數論基礎

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

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

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

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

5、接用于求兩個大數的最大公因子，如何求兩個大數的最大公因子在下面介紹。如果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整數能整除0，可得gcd(a,0)=|a|。如果將a，b都表示為素數的乘積，則gcd（a, b）極易確定。例如：300=22×31×

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

7、如果(a mod n)=(b mod n)，則稱兩整數a和b模n同余，記為a≡b mod n。稱與a模n同余的數的全體為a的同余類，記為[a]，稱a為這個同余類的表示元素。注意： 如果a≡0(mod n)，則n|a。,4.1.2 模運算,同余有以下性質： ① 若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。從以上性質易知，同余類中的每一元素都可作為這個同余類的表示元素。,求余數運算（簡稱求余運算）a mod n將整數a映射到集合{0,1, …,n-1}，稱求余運算在這個集合上的算術運算為模運算，模運算有以下性質： ① [(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。,性質①的證明： 設（a mod n）=ra，(b mod n)=rb，則存在整數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 （證畢）性質

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

11、為小于n的所有非負整數集合，即Zn={0,1, …,n-1}，稱Zn為模n的同余類集合。其上的模運算有以下性質： ① 交換律 (w+x) mod n=(x+w) mod n(w×x) mod n=(x×w) mod n② 結合律 [(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。,此外還有以下性質： 如果(a+b)≡(a+c) mod n，則b≡c mod n，稱為加法的可約律。該性質可由(a+b)≡(a+c) mo

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

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

15、-k2)n的一個因子。又由gcd(a，n)=1，得a是k1-k2的一個因子，設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、 （證畢）,設p為一素數，則Zp中每一非0元素都與p互素，因此有乘法逆元。類似于加法可約律，可有以下乘法可約律： 如果(a×b)≡(a×c) mod n且a有乘法逆元，那么對(a×b)≡(a×c) mod n兩邊同乘以a-1，即得b≡c mod n,費爾瑪 (Fermat) 定理和歐拉 (Euler) 定理在公鑰密碼體制中起著重要作用。1. 費爾瑪定理定理4

17、.2 (Fermat)若p是素數，a是正整數且gcd(a, p)=1，則ap-1≡1 mod p。證明：由4.1.2的討論知當gcd(a, p)=1時,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 費爾瑪定理和歐拉定理,所以 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定理也可寫成如下形式： 設p是素數，a是任一正整數，則ap≡a mod p。2. 歐拉函數設n是一正整數，小于n且與n互素的正整數的個數稱為n的歐拉函數，記為φ(n)。例如： φ(6)=2 ，φ(7)=6 ，φ(8)=4。若n是素數，則顯然有φ(n)=n-1。例如： 由21=

20、3×7，得φ(21)=φ(3)×φ(7)=2×6=12。,定理4.3 若n是兩個素數p和q的乘積，則φ(n)=φ(p)×φ(q)=(p-1)×(q-1)。證明：考慮Zn={0,1,…,pq-1}，其中不與n互素的數有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的因子，設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。證明： 設R={x1,x2,…,xφ(n)}是由小于n且與n互素的

22、全體數構成的集合，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中任意兩個元素都不相同，否則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、 (證畢）,素性檢驗是指對給定的數檢驗其是否為素數。對于大數的素性檢驗來說沒有簡單直接的方法，本節(jié)介紹一個概率檢驗法，為此需要以下引理。,4.1.4 素性檢驗,引理 如果p為大于2的素數，則方程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)，則存在兩個整數k和j，使得x+1=kp，x-1=jp,兩式相減得2=(k-j)p，為不可能結果。所以有p|(x+1)或p|(x-1)。設p|(x+1)，則x+1=kp，因此x≡-1(mod p)。類似地可得 x≡1(mod p)。（證畢）,引理的逆否命題為：如果方程x2≡1 mod p有一解x0{-1,1}，那么p不為素數。例如： 考慮方程x2≡1(mo

26、d 8)由4.1.2節(jié)Z8上模乘法的結果得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不是素數。,下面介紹Miller-Rabin的素性概率檢測法。首先將n-1表示為二進制形式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.,此算法有兩個輸入參數，n是待檢驗的數，a是小于n的整數。如果算法的返回值為False，則n肯定不是素數，如果返回值為True，則n

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

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

30、b)=gcd(b, a mod b)。證明：b是正整數，因此可將a表示為a=kb+r≡r mod b，a mod b=r,其中k為一整數，所以a mod b =a-kb。設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的公因子集合相等，兩個集合的最大值也相等。（證畢）,例如： gcd(55, 22)=

31、gcd(22, 55 mod 22)=gcd(22,11)=gcd(11, 0)=11。在求兩個數的最大公因子時，可重復使用以上結論。例如： 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|)，因此可假定算法的輸入是兩個正整數，設為d，f，并設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。,中國剩余定理是數論中最有用的一個工具，定理說如果已知某個數關于一些兩兩互素的數的同余類集，就可重構這個數。例如：Z10中每個數都可從這個數關于2和5（10的兩個互素的因子）的同余類重構。比如已知x關于2和5的同余類分別是[0]和[3]，即x mod 2≡0，x mod 5≡3?？芍桥紨登冶?除后余數是3，所以可得8是滿足這一關系的惟一的

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

36、i是惟一的。,下面證明對i∈{1,2,…,k}，上述x滿足ai(mod mi)≡x。注意到當j≠i時，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,下面證明方程組的解是惟一的。設x′是方程組的另一解，即x′≡ai(mod mi)(i=1,2,…,k)由x≡ai(mod mi)得x′-x≡0(mod mi)，即mi|(x′-x)。再根據mi兩兩互素，有M|(x′-x)，即x′-x≡0(mod M)，所以x′(mod M)=x(mod M)。(證畢)中國剩余定理提供了一個非常有用的特性，即在模M下可將非常大的數x由一組小數(a1,a

38、2,…,ak)表達。,例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