密碼學(xué)中的數(shù)論基礎(chǔ)PPT參考課件

1、1,數(shù)論是密碼學(xué)特別是公鑰密碼學(xué)的基本工具。 數(shù)論概念: 研究“離散數(shù)字集合” 運(yùn)算是“+” ,“” 例:整數(shù): 5 + 9 = 14; 5 3 = 5 + 5 + 5 = 15 多項(xiàng)式: x2+1 + x = x2+x+1; x x2+1 = x3+x,1. 數(shù)論簡(jiǎn)介,2,運(yùn)算概念,運(yùn)算: 模數(shù)運(yùn)算 模多項(xiàng)式運(yùn)算 進(jìn)一步運(yùn)算: 指數(shù)運(yùn)算,逆運(yùn)算,3,整除,對(duì)整數(shù) b!=0 及 a , 如果存在整數(shù) m 使得 a=mb,稱 b 整除 a, 也稱b是a的因子 記作 b|a 例 1,2,3,4,6,8,12,24 整除 24,4,1. 因子: 設(shè)a，b(b0)是兩個(gè)整數(shù)，如果存在另一整數(shù)m，使得a

2、=mb，則稱b整除a，記為b|a，且稱b是a的因子。,1.1 素?cái)?shù)和互素?cái)?shù),5,整數(shù)具有以下性質(zhì)： a|1，那么a=1。 a|b且b|a，則a=b。 對(duì)任一b (b0)，b|0。 b|g，b|h則對(duì)任意整數(shù)m、n有 b|(mg+nh)。,1.1 素?cái)?shù)和互素?cái)?shù),6,這里只給出的證明，其他3個(gè)性質(zhì)的證明都很簡(jiǎn)單。 性質(zhì)的證明： 由b|g，b|h知，存在整數(shù)g1、h1，使得g=bg1,h=bh1所以mg+nh=mbg1+nbh1 =b(mg1+nh1),因此b|(mg+nh)。,1.1 素?cái)?shù)和互素?cái)?shù),7,2. 素?cái)?shù):稱整數(shù)p(p1)是素?cái)?shù)，如果p的因子只有1，p。 任一整數(shù)a(a1)都能惟一地分解為

3、以下形式： 其中p1p2pt是素?cái)?shù)，ai0(i=1,t)。 例如91=711，11011=711213,1.1 素?cái)?shù)和互素?cái)?shù),8,這一性質(zhì)稱為整數(shù)分解的惟一性，也可如下陳述：設(shè)P是所有素?cái)?shù)集合，則任意整數(shù)a (a1)都能惟一地寫成以下形式： 其中ap0,等號(hào)右邊的乘積項(xiàng)取所有的素?cái)?shù)，然而大多指數(shù)項(xiàng)ap為0。相應(yīng)地，任一正整數(shù)也可由非0指數(shù)列表表示。例如： 11011可表示為a7=1,a11=2,a13=1。 兩數(shù)相乘等價(jià)于對(duì)應(yīng)的指數(shù)相加，即由k=mn 可得：對(duì)每一素?cái)?shù)p,kp=mp+np。而由a|b可得： 對(duì)每一素?cái)?shù)p,apbp。這是因?yàn)閜k只能被pj(jk)整除。,1.1 素?cái)?shù)和互素?cái)?shù),9,

4、3. 互素?cái)?shù) 稱c是兩個(gè)整數(shù)a、b的最大公因子，如果 c是a的因子也是b 的因子，即c是a、b的公因子。 a和b的任一公因子，也是c的因子。 表示為c=gcd(a, b)。,1.1 素?cái)?shù)和互素?cái)?shù),10,由于要求最大公因子為正，所以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=223152； 18=2132 gcd(18,300)=213150=6 一般由c=gcd(a,b)可得：

5、對(duì)每一素?cái)?shù)p，cp=min(ap,bp)。,1.1 素?cái)?shù)和互素?cái)?shù),11,由于確定大數(shù)的素因子不很容易，所以這種方法不能直接用于求兩個(gè)大數(shù)的最大公因子，如何求兩個(gè)大數(shù)的最大公因子在下面介紹。 如果gcd(a,b)=1，則稱a和b互素。,1.1 素?cái)?shù)和互素?cái)?shù),12,整數(shù)互素,整數(shù) a, b 互素是指 它們沒(méi)有除1之外的其它因子 8 與15 互素 8的因子1,2,4,8 15的因子 1,3,5,15 1 是唯一的公因子,13,素?cái)?shù)與不可約多項(xiàng)式,素?cái)?shù): 只有因子 1 和自身 1 是一個(gè)平凡素?cái)?shù) 例 2,3,5,7 是素?cái)?shù), 4,6,8,9,10 不是 素多項(xiàng)式或不可約多項(xiàng)式irreducible:

6、不可寫成其他因式的乘積 x2+x = x x+1 是非不可約多項(xiàng)式; x3+x+1 是不可約多項(xiàng)式,14,一些素?cái)?shù),200 以內(nèi)的素?cái)?shù): 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199,15,素?cái)?shù)分解,把整數(shù)n寫成素?cái)?shù)的成績(jī) 分解整數(shù)要比乘法困難 整數(shù) n的素?cái)?shù)分解是把它寫素?cái)?shù)的乘積 eg:91 = 7 13 ; 3600 = 24 3

7、2 52,16,設(shè)n是一正整數(shù)，a是整數(shù)，如果用n除a，得商為q，余數(shù)為r，則 a=qn+r,0rn, 其中x為小于或等于x的最大整數(shù)。 用a mod n表示余數(shù)r，則 。 如果(a mod n)=(b mod n)，則稱兩整數(shù)a和b模n同余，記為ab mod n。稱與a模n同余的數(shù)的全體為a的同余類，記為a，稱a為這個(gè)同余類的表示元素。 注意： 如果a0(mod n)，則n|a。,1.2 模運(yùn)算,17,同余有以下性質(zhì)： 若n|(a-b)，則ab mod n。 (a mod n)(b mod n)，則ab mod n。 ab mod n,則ba mod n。 ab mod n,bc mod n

8、,則ac mod n。 從以上性質(zhì)易知，同余類中的每一元素都可作為這個(gè)同余類的表示元素。,1.2 模運(yùn)算,18,求余數(shù)運(yùn)算（簡(jiǎ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。 (a mod n)(b mod n) mod n=(ab) mod n。,1.2 模運(yùn)算,19,性質(zhì)的證明： 設(shè)（a mod n）=ra，(b mod n)=rb， 則存在整數(shù)j、k使得a=j

9、n+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ì)、的證明類似。,1.2 模運(yùn)算,20,例：Z8=0,1,7，考慮Z8上的模加法和模乘法，結(jié)果如下表所示。,1.2 模運(yùn)算,從加法結(jié)果可見(jiàn)，對(duì)每一x，都有一y，使得x+y0 mod 8。如對(duì)2，有6，使得2+60 mod 8，稱y為x的負(fù)數(shù)，也稱為加法逆元。,21,對(duì)x，若有y，使得xy1 mod 8，如331 mod 8，則稱y為x的倒數(shù)，也稱為乘法逆元。本例可見(jiàn)并非每一x都有乘法逆元。,22,一般地，

10、定義Zn為小于n的所有非負(fù)整數(shù)集合，即Zn=0,1, ,n-1，稱Zn為模n的同余類集合。其上的模運(yùn)算有以下性質(zhì)： 交換律 (w+x) mod n=(x+w) mod n (wx) mod n=(xw) mod n 結(jié)合律 : (w+x)+y mod n=w+(x+y) mod n (wx)y mod n=w(xy) mod n,1.2 模運(yùn)算,23, 分配律 w(x+y) mod n=wx+wy mod n 單位元 (0+w) mod n=w mod n (1w) mod n=w mod n 加法逆元 對(duì)wZn，存在zZn，使得w+z0 mod n，記z=-w。,1.2 模運(yùn)算,24,此外還

11、有以下性質(zhì)： 如果(a+b)(a+c) mod n，則bc mod n，稱為加法的可約律。 該性質(zhì)可由(a+b)(a+c) mod n的兩邊同加上a的加法逆元得到。,1.2 模運(yùn)算,25,然而類似性質(zhì)對(duì)乘法卻不一定成立。例如63672 mod 8，但37 mod 8。原因是6乘以0到7得到的8個(gè)數(shù)僅為Z8的一部分，見(jiàn)上例。 即如果將對(duì)Z8作6的乘法6Z8（即用6乘Z8中每一數(shù)）看作Z8到Z8的映射的話，Z8中至少有兩個(gè)數(shù)映射到同一數(shù)，因此該映射為多到一的，所以對(duì)6來(lái)說(shuō)，沒(méi)有惟一的乘法逆元。但對(duì)5來(lái)說(shuō)，551 mod 8，因此5有乘法逆元5。 仔細(xì)觀察可見(jiàn)，與8互素的幾個(gè)數(shù)1，3，5，7都有乘法

12、逆元。 這一結(jié)論可推廣到任一Zn。,1.2 模運(yùn)算,26,定理1 設(shè)aZn，gcd(a, n)=1，則a在Zn中有乘法逆元。 證明： 首先證明a與Zn中任意兩個(gè)不相同的數(shù)b、c（不妨設(shè)cb）相乘，其結(jié)果必然不同。否則設(shè)abac mod n，則存在兩個(gè)整數(shù)k1,k2，使得ab=k1n+r，ac=k2n+r，可得a(b-c)=(k1-k2)n，所以a是(k1-k2)n的一個(gè)因子。,1.2 模運(yùn)算,27,又由gcd(a，n)=1，得a是k1-k2的一個(gè)因子，設(shè)k1-k2=k3a，所以a(b-c)=k3an，即b-c=k3n，與0cbn矛盾。 所以|aZn|=|Zn|，又知aZnZn，所以aZn=Zn

13、。因此對(duì)1Zn，存在xZn，使得ax1 mod n，即x是a的乘法逆元。記為x=a-1。 （證畢）,1.2 模運(yùn)算,28,設(shè)p為一素?cái)?shù)，則Zp中每一非0元素都與p互素，因此有乘法逆元。類似于加法可約律，可有以下乘法可約律： 如果(ab)(ac) mod n且a有乘法逆元，那么對(duì)(ab)(ac) mod n兩邊同乘以a-1，即得bc mod n,1.2 模運(yùn)算,29,模算式,除法取余運(yùn)算 同余( congruence) for a = b mod n 如果a,b 除以n,余數(shù)相同 eg. 100 = 34 mod 11 b 叫做a模n的剩余 通常 0=b=n-1 eg. -12mod7 = -5

14、mod7 = 2mod7 = 9mod7 可以進(jìn)行整數(shù)運(yùn)算,30,模運(yùn)算舉例,-21 -20 -19 -18 -17 -16 15 -14 -13 -12 -11 -10 -9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34,31,模算術(shù)運(yùn)算,加法 a+b mod n 減法 a-b mod n = a+(-b) mod n,32,乘法除法,乘法 a.b mod n 重復(fù)加法 除法 a/b mod n 乘以b

15、的逆元: a/b = a.b-1 mod n 如果n是素?cái)?shù), b-1 mod n 存在 s.t b.b-1 = 1 mod n 例. 2.3=1 mod 5 hence 4/2=4.3=2 mod 5,33,模遞歸運(yùn)算,模遞歸運(yùn)算是“模除求余” 例.r = a mod n 計(jì)算 a = d.n + r 33 mod 7 = 4.7 + 5; 得數(shù)是 5 通常, r 取正數(shù) 例 -18 mod 7 = -3.7 + 3; 答案是3 a+/-b mod n = a mod n +/- b mod n mod n,34,費(fèi)爾瑪 (Fermat) 定理和歐拉 (Euler) 定理在公鑰密碼體制中起著重

16、要作用。 Fermat定理：若p是素?cái)?shù)，a是正整數(shù)且gcd(a, p)=1，則ap-11 mod p。 Euler 定理：若a和n互素，則a(n)1 mod n。,1.3 費(fèi)爾瑪定理和歐拉定理,35,費(fèi)爾瑪定理證明： 當(dāng)gcd(a, p)=1時(shí),aZp=Zp，其中aZp表示a與Zp中每一元素做模p乘法。又知a00 mod p，所以aZp-0=Zp-0，a(Zp-0)=Zp-0。即a mod p,2a mod p,(p-1)a mod p =1,2,p-1 例如P=7,a=3 3,6,9,12,15,18mod 7=3,6,2,5,1,4,費(fèi)爾瑪定理,36,所以 a2a(p-1)a(a mod

17、p) (2a mod p)(p-1)a mod p) mod p (p-1)! mod p 另一方面 a2a(p-1)a=(p-1)!ap-1 因此 (p-1)!ap-1(p-1)! mod p 由于(p-1)!與p互素，因此(p-1)!有乘法逆元，由乘法可約律得ap-11 mod p。 （證畢）,費(fèi)爾瑪定理,37,Fermat定理也可寫成如下形式： 設(shè)p是素?cái)?shù)，a是任一正整數(shù)，則apa mod p。,費(fèi)爾瑪定理,38,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-

18、1。,歐拉定理,39,定理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，且AB=，否則ip=jq，其中1iq-1，1jp-1,則p是jq的因子，因此是j的因子，設(shè)j=kp，k1。則ip=kpq，i=kq，與1iq-1矛盾。所以 (n)=|Zn|-|A|+|B|+|C|=pq-(q-1)+(p-1)+1 =(p-1)(q-1)=(p)(q) （證畢）,歐拉定理,40,例如： 由21=37，得(21)=(3)(7)=26=12。,歐拉定理

19、,41,3. 歐拉定理（Euler） 若a和n互素，則a(n)1 mod n。 證明： 設(shè)R=x1,x2,x(n)是由小于n且與n互素的全體數(shù)構(gòu)成的集合，aR=ax1 mod n,ax2 mod n,ax(n) mod n，對(duì)aR中任一元素axi mod n，因a與n互素，x1與n互素，所以axi與n互素，且axi mod nn，因此axi mod nR，所以aRR。,歐拉定理,42,又因aR中任意兩個(gè)元素都不相同，否則axi mod n=axj mod n，由a與n互素知a在 mod n下有乘法逆元，得xi=xj。所以|aR|=|R|，得aR=R，所 以 ， , ，,歐拉定理,43,由每一x

20、i與n互素，知 與n互素， 在 mod n下有乘法逆元。 所以a(n)1 mod n。 (證畢）,歐拉定理,44,素性檢驗(yàn)是指對(duì)給定的數(shù)檢驗(yàn)其是否為素?cái)?shù)。對(duì)于大數(shù)的素性檢驗(yàn)來(lái)說(shuō)沒(méi)有簡(jiǎn)單直接的方法，本節(jié)介紹一個(gè)概率檢驗(yàn)法，為此需要以下引理。,1.4 素性檢驗(yàn),45,引理 如果p為大于2的素?cái)?shù)，則方程 x2 1(mod p)的解只有x1和x-1。 證明：由x21 mod p，有x2-10 mod p，(x+1)(x-1)0 mod p，因此p|(x+1)或p|(x-1)或 p|(x+1)且p|(x-1)。 若p|(x+1)且p|(x-1)，則存在兩個(gè)整數(shù)k和j，使得x+1=kp，x-1=jp,兩式

21、相減得2=(k-j)p，為不可能結(jié)果。所以有p|(x+1)或p|(x-1)。 設(shè)p|(x+1)，則x+1=kp，因此x-1(mod p)。 類似地可得 x1(mod p)。（證畢）,1.4 素性檢驗(yàn),46,引理的逆否命題為：如果方程x21 mod p有一解x0-1,1，那么p不為素?cái)?shù)。 例如： 考慮方程x21(mod 8)由Z8上模乘法的結(jié)果得 121 mod 8, 321 mod 8, 521 mod 8, 721mod 8 又5-3 mod 8，7-1 mod 8，所以方程的解為1，-1，3，-3，可見(jiàn)8不是素?cái)?shù)。,1.4 素性檢驗(yàn),47,下面介紹Miller-Rabin的素性概率檢測(cè)法。

22、首先將n-1表示為二進(jìn)制形式bkbk-1b0，并給d賦初值1，則算法Witness(a,n)的核心部分如下： for i=k downto 0 do xd; d(dd) mod n; if d=1 and(x1)and(xn-1)then return False; if bi=1 then d(da) mod n if d1 then return False; return True.,1.4 素性檢驗(yàn),48,此算法有兩個(gè)輸入?yún)?shù)，n是待檢驗(yàn)的數(shù)，a是小于n的整數(shù)。如果算法的返回值為False，則n肯定不是素?cái)?shù)，如果返回值為True，則n有可能是素?cái)?shù)。 for循環(huán)結(jié)束后，有dan-1 mo

23、d n，由Fermat定理知，若n為素?cái)?shù)，則d為1。因此若d1，則n不為素?cái)?shù)，所以返回False。 因?yàn)閚-1-1 mod n，所以(x1)and(xn-1),指x21 (mod n)有不在-1,1中的根，因此n不為素?cái)?shù)，返回False。,1.4 素性檢驗(yàn),49,該算法有以下性質(zhì)： 對(duì)s個(gè)不同的a，重復(fù)調(diào)用這一算法，只要有一次算法返回為False，就可肯定n不是素?cái)?shù)。如果算法每次返回都為True，則n是素?cái)?shù)的概率至少為1-2-s，因此對(duì)于足夠大的s，就可以非?？隙ǖ叵嘈舗為素?cái)?shù)。,1.4 素性檢驗(yàn),50,歐幾里得（Euclid）算法是數(shù)論中的一個(gè)基本技術(shù)，是求兩個(gè)正整數(shù)的最大公因子的簡(jiǎn)化過(guò)程。

24、而推廣的Euclid算法不僅可求兩個(gè)正整數(shù)的最大公因子，而且當(dāng)兩個(gè)正整數(shù)互素時(shí)，還可求出其中一個(gè)數(shù)關(guān)于另一個(gè)數(shù)的乘法逆元。,1.5 歐幾里得算法,51,1. 求最大公因子 Euclid算法是基于下面一個(gè)基本結(jié)論： 對(duì)任意非負(fù)整數(shù)a和正整數(shù)b，有g(shù)cd(a, b)=gcd(b, a mod b)。 證明：b是正整數(shù)，因此可將a表示為a=kb+rr mod b，a mod b=r,其中k為一整數(shù)，所以a mod b =a-kb。,1.5 歐幾里得算法,52,設(shè)d是a，b的公因子，即d|a，d|b，所以d|kb。由d|a和d|kb得d|(a mod b)，因此d是b和a mod b的公因子。 所以得

25、出a，b的公因子集合與b，a mod b的公因子集合相等，兩個(gè)集合的最大值也相等。（證畢）,1.5 歐幾里得算法,53,例如： gcd(55, 22)=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。,1.5 歐幾里得算法,54,Euclid算法就是用這種方法，因gcd(a, b)= gcd(|a|, |b|)，因此可假定算法的輸入是兩個(gè)正整數(shù)，設(shè)為d，f，并設(shè)f d

26、。 Euclid（f, d） 1. Xf; Yd； 2. if Y=0 then return X=gcd(f,d)； 3. R=X mod Y； 4. X=Y； 5. Y=R； 6. goto 2。,1.5 歐幾里得算法,55,例： 求gcd(1970, 1066)。 1970=11066+904, gcd(1066, 904) 1066=1904+162,gcd(904, 162) 904=5162+94,gcd(162, 94) 162=194+68,gcd(94, 68) 94=168+26,gcd(68, 26) 68=226+16,gcd(26, 16) 26=116+10,gcd

27、(16, 10) 16=110+6, gcd(10, 6) 10=16+4,gcd(6, 4) 6=14+2,gcd(4, 2) 4=22+0,gcd(2, 0) 因此gcd(1970, 1066)=2。,1.5 歐幾里得算法,56,2. 求乘法逆元 如果gcd(a, b)=1 ，則b在mod a下有乘法逆元（不妨設(shè)ba），即存在一x (xa)，使得bx1 mod a。推廣的Euclid算法先求出gcd(a, b)，當(dāng)gcd(a, b)=1時(shí)，則返回b的逆元。,1.5 歐幾里得算法,57,Extended Euclid(f, d) （設(shè) f d） 1. (X1,X2,X3)(1,0,f);(Y

28、1,Y2,Y3)(0,1,d); 2. if Y3=0 then return X3=gcd(f, d)；no inverse; 3. if Y3=1 then return Y3=gcd(f, d)；Y2=d-1 mod f; 4. Q=X3Y3 ； 5. (T1,T2,T3)(X1-QY1,X2-QY2,X3-QY3); 6. (X1,X2,X3)(Y1,Y2,Y3); 7. (Y1,Y2,Y3)(T1,T2,T3); 8. goto 2。,1.5 歐幾里得算法,58,算法中的變量有以下關(guān)系： fT1+dT2=T3;fX1+dX2=X3;fY1+dY2=Y3 在算法EUCLID (f, d

29、)中，X等于前一輪循環(huán)中的Y，Y等于前一輪循環(huán)中的X mod Y。而在算法Extended Euclid(f, d)中，X3等于前一輪循環(huán)中的Y3，Y3等于前一輪循環(huán)中的X3-QY3，由于Q是Y3除X3的商，因此Y3是前一輪循環(huán)中的Y3除X3的余數(shù)，即X3 mod Y3，可見(jiàn)Extended Euclid(f, d)中的X3、Y3與Euclid(f, d)中的X、Y作用相同，因此可正確產(chǎn)生gcd(f, d)。,1.5 歐幾里得算法,59,如果gcd(f, d)=1，則在最后一輪循環(huán)中Y3=0，X3=1，因此在前一輪循環(huán)中Y3=1。由Y3=1可得: fY1+dY2=Y3，fY1+dY2=1，dY

30、2=1+(-Y1)f，dY21 mod f，所以Y2d-1 mod f。,1.5 歐幾里得算法,60,例： 求gcd(1769, 550)。 算法的運(yùn)行結(jié)果及各變量的變化情況如表42所示。（見(jiàn)83頁(yè)表4.2） 所以gcd(1769,550)=1，550-1 mod 1769=550。,1.5 歐幾里得算法,61,中國(guó)剩余定理是數(shù)論中最有用的一個(gè)工具，定理說(shuō)如果已知某個(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 20，x mod 53?？芍桥紨?shù)且被5除

31、后余數(shù)是3，所以可得8是滿足這一關(guān)系的惟一的x。,1.6 中國(guó)剩余定理,62,定理4.5（中國(guó)剩余定理） 設(shè)m1,m2,mk是兩兩互素的正整數(shù)， ，則一次同余方程組 對(duì)模M有惟一解: 其中ei滿足,1.6 中國(guó)剩余定理,63,證明：設(shè) ,i=1,2,k，由Mi 的定義得Mi與mi是互素的，可知Mi在模mi下有惟一的乘法逆元，即滿足 的ei是惟一的。,1.6 中國(guó)剩余定理,64,下面證明對(duì)i1,2,k，上述x滿足ai(mod mi)x。注意到當(dāng)ji時(shí)，mi|Mj，即Mj0(mod mi)。所以 (Mjej mod mj) mod mi (Mj mod mi)(ej mod mj) mod mi)

32、 mod mi 0 而(Mi(ei mod mi) mod mi(Miei) mod mi1 所以x(mod mi)ai，即ai(mod mi)x,1.6 中國(guó)剩余定理,65,下面證明方程組的解是惟一的。設(shè)x是方程組的另一解，即 xai(mod mi)(i=1,2,k) 由xai(mod mi)得x-x0(mod mi)，即mi|(x-x)。 再根據(jù)mi兩兩互素，有M|(x-x)，即 x-x0(mod M)，所以x(mod M)= x(mod M)。 (證畢),1.6 中國(guó)剩余定理,66,中國(guó)剩余定理提供了一個(gè)非常有用的特性，即在模M下可將非常大的數(shù)x由一組小數(shù)(a1,a2,ak)表達(dá)。,1.

33、6 中國(guó)剩余定理,67,例： 由以下方程組求x。 解： M=2357=210，M1=105，M2=70，M3=42，M4=30,易求e1M-11 mod 21,e2M-12mod 31,e3M-13 mod 53,e4M-14 mod 74,所以 x mod 210(10511+7012+4233+3045) mod 210173，或?qū)懗蓌173 mod 210。,1.6 中國(guó)剩余定理,68,例： 將973 mod 1813由模數(shù)分別為37和49的兩個(gè)數(shù)表示。 解： 取x=973, M=1813, m1=37,m2=49。 由a1973 mod m111,a2973 mod m342得x在模3

34、7和模49下的表達(dá)為（11,42）。,1.6 中國(guó)剩余定理,69,1. 求模下的整數(shù)冪 Euler定理指出如果gcd(a, n)=1，則a(n)1 mod n?，F(xiàn)在考慮如下的一般形式: am1 mod n 如果a與n互素，則至少有一整數(shù)m（比如m=(n)）滿足這一方程。稱滿足方程的最小正整數(shù)m為模n下a的階。,1.7 離散對(duì)數(shù),70,例如： a=7，n=19，則易求出717 mod 19,7211 mod 19,731 mod 19，即7在模19下的階為3。 由于73+j=737j7j mod 19, 所以747 mod 19,7572 mod 19, , 即從74 mod 19開(kāi)始所求的冪出

35、現(xiàn)循環(huán)，循環(huán)周期為3，即循環(huán)周期等于元素的階。,模下的整數(shù)冪,71,定理4.6 設(shè)a的階為m，則ak1 mod n的充要條件是k為m的倍數(shù)。 證明：設(shè)存在整數(shù)q，使得k=qm，則ak(am)q1 mod n。 反之，假定ak1 mod n，令k=qm+r,其中0rm-1，那么 ak(am)qarar1(mod n) 與m是階矛盾。（證畢）,模下的整數(shù)冪,72,推論：a的階m整除(n)。 如果a的階m等于(n)，則稱a為n的本原根。如果a是n的本原根，則 a,a2,a(n) 在mod n下互不相同且都與n互素。 特別地，如果a是素?cái)?shù)p的本原根，則 a,a2,ap-1在 mod p下都不相同。,模

36、下的整數(shù)冪,73,例如：n=9，則(n)=6，考慮2在mod 9下的冪21 mod 92,22 mod 94 23 mod 98,24 mod 97，25 mod 95, 26 mod 91。即2的階為(9)，所以2為9的本原根。,模下的整數(shù)冪,74,例如： n=19，a=3在mod 19下的冪分別為 3，9，8，5，15，7，2，6，18，16，10，11，14，4，12，17，13，1。 即3的階為18=(19)，所以3為19的本原根。,模下的整數(shù)冪,75,本原根不惟一。可驗(yàn)證除3外，19的本原根還有2，10，13，14，15。 注意并非所有的整數(shù)都有本原根，只有以下形式的整數(shù)才有本原根：

37、 2,4,p,2p 其中p為奇素?cái)?shù)。,模下的整數(shù)冪,76,2. 指標(biāo) 一般對(duì)數(shù)的概念:指數(shù)函數(shù)y=ax(a0,a1)的逆函數(shù)稱為以a為底x的對(duì)數(shù)，記為y=logax。 對(duì)數(shù)函數(shù)有以下性質(zhì)： loga1=0,logaa=1,logaxy=logax+logay,logaxy=ylogax 在模運(yùn)算中也有類似的函數(shù)。設(shè)p是一素?cái)?shù)，a是p的本原根，則a,a2,ap-1產(chǎn)生出1到p-1之間的所有值，且每一值只出現(xiàn)一次。因此對(duì)任意b1,p-1，都存在惟一的i(1ip-1)，使得bai mod p。稱i為模p下以a為底b的指標(biāo)，記為i=inda,p(b)。,指標(biāo),77,指標(biāo)有以下性質(zhì)： inda,p(1)

38、=0。 inda,p(a)=1。 分別由以下關(guān)系得出： a0 mod p=1 mod p=1,a1 mod p=a。 以上假定模數(shù)p是素?cái)?shù)，對(duì)于非素?cái)?shù)也有類似的結(jié)論。,指標(biāo),78,例： 設(shè)p=9，則(p)=6，a=2是p的一個(gè)本原根，a的不同的冪為（模9下） 201,212,224,238,247,255,261 由此可得a的指數(shù)表如下所示。,指標(biāo),79,在討論指標(biāo)的另兩個(gè)性質(zhì)時(shí)，需要利用如下結(jié)論： 若azaq mod p，其中a和p互素，則有zq mod (p)。 證明：因a和p互素，所以a在模p下存在逆元 a-1，在azaq mod p兩邊同乘以(a-1)q，得 az-q1 mod p。由

39、Euler定理a(p)1 mod p 知存在一整數(shù)k，使得z-qk(p)，所以 zq mod (p)。,指標(biāo),80,由上述結(jié)論可得指標(biāo)的以下兩個(gè)性質(zhì)： inda,p(xy)=inda,p(x)+inda,p(y) mod (p)。 inda,p(yr)=rinda,p(y) mod (p)。 性質(zhì)是性質(zhì)的推廣。 從指標(biāo)的以上性質(zhì)可見(jiàn)，指標(biāo)與對(duì)數(shù)的概念極為相似。,指標(biāo),81,性質(zhì)的證明：設(shè) 由模運(yùn)算的性質(zhì)得： 所以inda,p(xy)=inda,p(x)+inda,p(y) mod (p) （證畢）,指標(biāo),82,3. 離散對(duì)數(shù) 設(shè)p是素?cái)?shù)，a是p的本原根，即a1,a2,ap-1在 mod p下產(chǎn)

40、生1到p-1的所有值，所以對(duì)b1,p-1，有惟一的i1,p-1使得bai mod p。稱i為模p下以a為底b的離散對(duì)數(shù)， 記為 ilogab(mod p)。,離散對(duì)數(shù),83,當(dāng)a、p、i已知時(shí)，用快速指數(shù)算法可比較容易地求出b，但如果已知a、b和p，求i則非常困難。目前已知的最快的求離散對(duì)數(shù)算法其時(shí)間復(fù)雜度為： 所以當(dāng)p很大時(shí)，該算法也是不可行的。,離散對(duì)數(shù),84,設(shè)p是一素?cái)?shù)，a小于p，稱a是p的平方剩余，如果方程 x2a (mod p) 有解。否則稱為非平方剩余。,1.8 平方剩余,85,求離散對(duì)數(shù)的shank算法,86,求5x mod 23=3 m=4; L:=array(1.4,50

41、mod 23,51 mod 23,52 mod 23,53 mod 23)=1,5,2,10; A:=5(22-4) mod 23=6; 3*6 mod 23=18;18*6 mod 23=16; 16*6 mod 23=4;4*6 mod 23=1; q:=4;x:=q*d+0; 516 mod 23 =3;,87,1.8平方剩余,定義：設(shè)n2, 若x2a(mod n)有解, 則稱a是模p的二次剩余; 若無(wú)解, 則稱a是模p的二次非剩余. 二次剩余集合QRn 二次非剩余集合QNRn.,88,容易證明，模p的平方剩余的個(gè)數(shù)為(p-1)/2，且與模p的非平方剩余的個(gè)數(shù)相等。如果a是模p的一個(gè)平方

42、剩余，那么a恰有兩個(gè)平方根，一個(gè)在0到(p-1)/2之間，另一個(gè)在(p-1)/2到(p-1)之間，且這兩個(gè)平方根中的一個(gè)也是模p的平方剩余。,1.8 平方剩余,89,歐拉準(zhǔn)則,定理 (歐拉準(zhǔn)則)設(shè)p為一奇素?cái)?shù), p不能整除x, 則有: x屬于QRp 證明: （1）若存在y2x(mod p), （2）若 ，但y2x(mod p)無(wú)解 對(duì)任意1 i p-1, 總有一整數(shù)j, 使得: ij x(mod p). 由于y2x(mod p)無(wú)解. 故ij. 因此, 1,2,p-1可分成(p-1)/2對(duì), 每對(duì)之積(mod p). 因此, (p-1)! a(p-1)/2 1(mod p). 根據(jù)威爾遜定理知, (p-1)! -1(mod p), 所以命題得證.,90,定義1 設(shè)p是素?cái)?shù)，a是一整數(shù)，符號(hào) 的定義如下： 稱符號(hào) 為L(zhǎng)egendre符號(hào)。,1.8 平方剩余,91,例如： 計(jì)算 有一個(gè)簡(jiǎn)單公式： 例如：p=23，a=5，a(p-1)/2