第四講-數(shù)論

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ù)論簡介,運(yùn)算概念,運(yùn)算:模數(shù)運(yùn)算模多項(xiàng)式運(yùn)算進(jìn)一步運(yùn)算:指數(shù)運(yùn)算,逆運(yùn)算,整除,對整數(shù) b!=

2、0 及 a , 如果存在整數(shù) m 使得 a=mb,稱 b 整除 a, 也稱b是a的因子記作 b|a 例 1,2,3,4,6,8,12,24 整除 24,1. 因子 設(shè)a，b(b≠0)是兩個(gè)整數(shù)，如果存在另一整數(shù)m，使得a=mb，則稱b整除a，記為b|a，且稱b是a的因子。,1.1 素?cái)?shù)和互素?cái)?shù),整數(shù)具有以下性質(zhì)： ① a|1，那么a=±1。② a|b且b|a，則a=±b。③ 對任一b (b

3、≠0)，b|0。④ b|g，b|h，則對任意整數(shù)m、n有b|(mg+nh)。,1.1 素?cái)?shù)和互素?cái)?shù),這里只給出④的證明，其他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)。,1.1 素?cái)?shù)和互素?cái)?shù),2. 素?cái)?shù) 稱整數(shù)p(p>1)是素?cái)?shù)，如果p的因子只有±

4、;1，±p。 任一整數(shù)a(a>1)都能惟一地分解為以下形式： 其中p1>p2>…pt是素?cái)?shù)，ai>0(i=1,…,t)。例如91=7×11，11011=7×112×13,1.1 素?cái)?shù)和互素?cái)?shù),這一性質(zhì)稱為整數(shù)分解的惟一性，也可如下陳述：設(shè)P是所有素?cái)?shù)集合，則任意整數(shù)a (a>1)都能惟一地寫成以下形式： 其中ap≥0,等號(hào)右邊的乘

5、積項(xiàng)取所有的素?cái)?shù)，然而大多指數(shù)項(xiàng)ap為0。相應(yīng)地，任一正整數(shù)也可由非0指數(shù)列表表示。例如： 11011可表示為{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)整除。,1.1 素?cái)?shù)和互素?cái)?shù),3. 互素?cái)?shù) 稱c是兩個(gè)整數(shù)a、b的最大公因子，如果① c是a的因子也是b 的因

6、子，即c是a、b的公因子。② a和b的任一公因子，也是c的因子。表示為c=gcd(a, b)。,1.1 素?cái)?shù)和互素?cái)?shù),由于要求最大公因子為正，所以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

7、15;52； 18=21×32gcd(18,300)=21×31×50=6一般由c=gcd(a,b)可得： 對每一素?cái)?shù)p，cp=min(ap,bp)。,1.1 素?cái)?shù)和互素?cái)?shù),由于確定大數(shù)的素因子不很容易，所以這種方法不能直接用于求兩個(gè)大數(shù)的最大公因子，如何求兩個(gè)大數(shù)的最大公因子在下面介紹。 如果gcd(a,b)=1，則稱a和b互素。,1.1 素?cái)?shù)和互素?cái)?shù),整

8、數(shù)互素,整數(shù) a, b 互素是指 它們沒有除1之外的其它因子8 與15 互素 8的因子1,2,4,8 15的因子 1,3,5,15 1 是唯一的公因子,素?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: 不可寫成其他因式的乘積 x2+x = x × x+1 是非不可約多項(xiàng)式;

9、 x3+x+1 是不可約多項(xiàng)式,一些素?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,素?cái)?shù)分解,把整數(shù)n寫成素?cái)?shù)的成績分解整數(shù)要比乘法困難整數(shù)

10、n的素?cái)?shù)分解是把它寫素?cái)?shù)的乘積 eg. 91 = 7 × 13 ; 3600 = 24 × 32 × 52,設(shè)n是一正整數(shù)，a是整數(shù)，如果用n除a，得商為q，余數(shù)為r，則a=qn+r,0≤r<n, 其中x為小于或等于x的最大整數(shù)。 用a mod n表示余數(shù)r，則 。 如果(a mod n)=(b m

11、od n)，則稱兩整數(shù)a和b模n同余，記為a≡b mod n。稱與a模n同余的數(shù)的全體為a的同余類，記為[a]，稱a為這個(gè)同余類的表示元素。注意： 如果a≡0(mod n)，則n|a。,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 mod n,b≡c mod n,則a≡c

12、 mod n。 從以上性質(zhì)易知，同余類中的每一元素都可作為這個(gè)同余類的表示元素。,1.2 模運(yùn)算,求余數(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。③ [(

13、a mod n)×(b mod n)] mod n=(a×b) mod n。,1.2 模運(yù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

14、 （證畢）性質(zhì)②、③的證明類似。,1.2 模運(yùn)算,例：Z8={0,1,…,7}，考慮Z8上的模加法和模乘法，結(jié)果如下表所示。,1.2 模運(yùn)算,從加法結(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都有乘法逆

15、元。,一般地，定義Zn為小于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=

16、[w×(x×y)] mod n,1.2 模運(yùn)算,③ 分配律 [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。,1.2 模運(yùn)算,此外還有以下性

17、質(zhì)： 如果(a+b)≡(a+c) mod n，則b≡c mod n，稱為加法的可約律。 該性質(zhì)可由(a+b)≡(a+c) mod n的兩邊同加上a的加法逆元得到。,1.2 模運(yùn)算,然而類似性質(zhì)對乘法卻不一定成立。例如6×3≡6×7≡2 mod 8，但37 mod 8。原因是6乘以0到7得到的8個(gè)數(shù)僅為Z8的一部分，見上例。 即如果將對Z8作6的乘法6×Z8（即用6乘Z8中每一數(shù)

18、）看作Z8到Z8的映射的話，Z8中至少有兩個(gè)數(shù)映射到同一數(shù)，因此該映射為多到一的，所以對6來說，沒有惟一的乘法逆元。但對5來說，5×5≡1 mod 8，因此5有乘法逆元5。 仔細(xì)觀察可見，與8互素的幾個(gè)數(shù)1，3，5，7都有乘法逆元。這一結(jié)論可推廣到任一Zn。,1.2 模運(yùn)算,定理1 設(shè)a∈Zn，gcd(a, n)=1，則a在Zn中有乘法逆元。 證明： 首先證明a與Zn中任意兩個(gè)不相同的數(shù)b、c（

19、不妨設(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-k2)n的一個(gè)因子。,1.2 模運(yùn)算,又由gcd(a，n)=1，得a是k1-k2的一個(gè)因子，設(shè)k1-k2=k3a，所以a(b-c)=k3an，即b-c=k3n，與0<c<b<n矛盾。 所

20、以|a×Zn|=|Zn|，又知a×ZnZn，所以a×Zn=Zn。因此對1∈Zn，存在x∈Zn，使得a×x≡1 mod n，即x是a的乘法逆元。記為x=a-1。 （證畢）,1.2 模運(yùn)算,設(shè)p為一素?cái)?shù)，則Zp中每一非0元素都與p互素，因此有乘法逆元。類似于加法可約律，可有以下乘法可約律

21、： 如果(a×b)≡(a×c) mod n且a有乘法逆元，那么對(a×b)≡(a×c) mod n兩邊同乘以a-1，即得b≡c mod n,1.2 模運(yùn)算,模算式,除法取余運(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

22、. -12mod7 = -5mod7 = 2mod7 = 9mod7 可以進(jìn)行整數(shù)運(yùn)算,模運(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

23、 29 30 31 32 33 34,模算術(shù)運(yùn)算,加法 a+b mod n 減法 a-b mod n = a+(-b) mod n,乘法\除法,乘法a.b mod n 重復(fù)加法 除法 a/b mod n 乘以b的逆元: 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,模遞

24、歸運(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,,,,,,費(fèi)爾瑪 (Fermat) 定理和歐拉 (Euler) 定理在公鑰密碼體制中起著重要作用。Fermat定理：

25、若p是素?cái)?shù)，a是正整數(shù)且gcd(a, p)=1，則ap-1≡1 mod p。Euler 定理：若a和n互素，則aφ(n)≡1 mod n。,1.3 費(fèi)爾瑪定理和歐拉定理,費(fèi)爾瑪定理證明：當(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

26、mod p,2a mod p,…,(p-1)a mod p} ={1,2,…,p-1}例如P=7,a=3{3,6,9,12,15,18}mod 7={3,6,2,5,1,4},費(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

27、×…×(p-1)a=(p-1)!ap-1 因此 (p-1)!ap-1≡(p-1)! mod p 由于(p-1)!與p互素，因此(p-1)!有乘法逆元，由乘法可約律得ap-1≡1 mod p。 （證畢）,費(fèi)爾瑪定理,Fermat定理也可寫成如下形式： 設(shè)p是素?cái)?shù)，a是任一正整數(shù)，則ap≡a mod p。,費(fèi)爾瑪定理,2. 歐拉函數(shù) 設(shè)n

28、是一正整數(shù)，小于n且與n互素的正整數(shù)的個(gè)數(shù)稱為n的歐拉函數(shù)，記為φ(n)。例如： φ(6)=2 ，φ(7)=6 ，φ(8)=4。若n是素?cái)?shù)，則顯然有φ(n)=n-1。,歐拉定理,定理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,

29、…,(p-1)q},C={0}，且A∩B=Φ，否則ip=jq，其中1≤i≤q-1，1≤j≤p-1,則p是jq的因子，因此是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) （證畢）,歐拉定理,例如： 由21=3×7，得φ(21)

30、=φ(3)×φ(7)=2×6=12。,歐拉定理,3. 歐拉定理（Euler） 若a和n互素，則aφ(n)≡1 mod n。 證明： 設(shè)R={x1,x2,…,xφ(n)}是由小于n且與n互素的全體數(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 mo

31、d 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。所以|a×R|=|R|，得a×R=R，所以 ， ,

32、 ，,歐拉定理,,由每一xi與n互素，知 與n互素， 在 mod n下有乘法逆元。所以aφ(n)≡1 mod n。 (證畢）,歐拉定理,素性檢驗(yàn)是指對給定的數(shù)檢驗(yàn)其是否為素?cái)?shù)。對于大數(shù)的素性檢驗(yàn)來說沒有簡單直接的方法，本節(jié)介

33、紹一個(gè)概率檢驗(yàn)法，為此需要以下引理。,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-1)或 p|(x+1)且p|(x-1)。 若p|(x+1)且p|(x-1)，則存在兩個(gè)整數(shù)k和j，使得x+1=kp，x-1=jp,兩式相減得2

34、=(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)。（證畢）,1.4 素性檢驗(yàn),引理的逆否命題為：如果方程x2≡1 mod p有一解x0{-1,1}，那么p不為素?cái)?shù)。 例如： 考慮方程x2≡1(mod 8)由Z8上模乘法的結(jié)果得12≡1 mod 8, 32≡1 mod 8, 52≡1 mod 8

35、, 72≡1mod 8 又5≡-3 mod 8，7≡-1 mod 8，所以方程的解為1，-1，3，-3，可見8不是素?cái)?shù)。,1.4 素性檢驗(yàn),下面介紹Miller-Rabin的素性概率檢測法。首先將n-1表示為二進(jìn)制形式bkbk-1…b0，并給d賦初值1，則算法Witness(a,n)的核心部分如下： for i=k downto 0 do{x←d;d←(d×d) mod n;if d=1 a

36、nd(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.,1.4 素性檢驗(yàn),此算法有兩個(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é)束后，有d≡an-1 m

37、od 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。,1.4 素性檢驗(yàn),該算法有以下性質(zhì)： 對s個(gè)不同的a，重復(fù)調(diào)用這一算法，只要有一次算法返回為False，就可肯定n不是素?cái)?shù)。如果算法每次返回都為True，則n是素?cái)?shù)

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

39、 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。,1.5 歐幾里得算法,設(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è)集合

40、的最大值也相等。（證畢）,1.5 歐幾里得算法,例如： 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 歐幾里得算法,Euclid算法就是用這種方法，因gc

41、d(a, b)= gcd(|a|, |b|)，因此可假定算法的輸入是兩個(gè)正整數(shù)，設(shè)為d，f，并設(shè)f >d。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。,1.5 歐幾里得算法,例： 求gcd(1970, 1066)。1970=1×1066+904,

42、 gcd(1066, 904)1066=1×904+162,gcd(904, 162)904=5×162+94,gcd(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

43、15;10+6, gcd(10, 6) 10=1×6+4,gcd(6, 4)6=1×4+2,gcd(4, 2) 4=2×2+0,gcd(2, 0)因此gcd(1970, 1066)=2。,1.5 歐幾里得算法,2. 求乘法逆元 如果gcd(a, b)=1 ，則b在mod a下有乘法逆元（不妨設(shè)b<a），即存在一x (x<a)，

44、使得bx≡1 mod a。推廣的Euclid算法先求出gcd(a, b)，當(dāng)gcd(a, b)=1時(shí)，則返回b的逆元。,1.5 歐幾里得算法,Extended Euclid(f, d) （設(shè) f >d） 1. (X1,X2,X3)←(1,0,f);(Y1,Y2,Y3)←(0,1,d);2. if Y3=0 then return X3=gcd(f, d)；no inverse;3. if Y3=1 then retu

45、rn 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 歐幾里得算法,算法中的變量有以下關(guān)系：fT1+dT2=T3;fX1+dX2=X3;fY1+dY2=Y3在算法EUCLID (f, d)中，

46、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，可見Extended Euclid(f, d)中的X3、Y3與Euclid(f, d)中的X、Y作用相同，因此可正確產(chǎn)生gcd(f, d)。,1.5 歐幾里得算法,如果gc

47、d(f, d)=1，則在最后一輪循環(huán)中Y3=0，X3=1，因此在前一輪循環(huán)中Y3=1。由Y3=1可得: fY1+dY2=Y3，fY1+dY2=1，dY2=1+(-Y1)×f，dY2≡1 mod f，所以Y2≡d-1 mod f。,1.5 歐幾里得算法,例： 求gcd(1769, 550)。 算法的運(yùn)行結(jié)果及各變量的變化情況如表42所示。（見83頁表4.2） 所以gcd(1769,550)=1，550-1 m

48、od 1769=550。,1.5 歐幾里得算法,中國剩余定理是數(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)系的惟一的x。,1.6 中國剩余定理,定理4

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

50、od 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 mi)≡ai，即ai(mod mi)≡x,1.6 中國剩余定理,

51、下面證明方程組的解是惟一的。設(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)。 (證畢),1.6 中國剩余定理,中國剩余定理提供了一個(gè)非常有用的特性，即在模M下可將非常大的數(shù)x

52、由一組小數(shù)(a1,a2,…,ak)表達(dá)。,1.6 中國剩余定理,例： 由以下方程組求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+

53、42×3×3+30×4×5) mod 210≡173，或?qū)懗蓌≡173 mod 210。,1.6 中國剩余定理,例： 將973 mod 1813由模數(shù)分別為37和49的兩個(gè)數(shù)表示。 解： 取x=973, M=1813, m1=37,m2=49。 由a1≡973 mod m1≡11,a2≡973 mod m3≡42得x在模37和模49下的表達(dá)為（11,42）。,1.6 中國剩

54、余定理,1. 求模下的整數(shù)冪 Euler定理指出如果gcd(a, n)=1，則aφ(n)≡1 mod n?，F(xiàn)在考慮如下的一般形式:am≡1 mod n 如果a與n互素，則至少有一整數(shù)m（比如m=φ(n)）滿足這一方程。稱滿足方程的最小正整數(shù)m為模n下a的階。,1.7 離散對數(shù),例如： a=7，n=19，則易求出71≡7 mod 19,72≡11 mod 19,73≡1 mod 19，即7在模19下的階為3。

55、 由于73+j=73·7j≡7j mod 19, 所以74≡7 mod 19,75≡72 mod 19, …, 即從74 mod 19開始所求的冪出現(xiàn)循環(huán)，循環(huán)周期為3，即循環(huán)周期等于元素的階。,模下的整數(shù)冪,定理4.6 設(shè)a的階為m，則ak≡1 mod n的充要條件是k為m的倍數(shù)。證明：設(shè)存在整數(shù)q，使得k=qm，則ak≡(am)q≡1 mod n。反之，假定ak≡1 mod n，令k=qm+r,其中0<r

56、≤m-1，那么ak≡(am)qar≡ar≡1(mod n)與m是階矛盾。（證畢）,模下的整數(shù)冪,推論：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下都不相同。,模下的整數(shù)冪,例如：n=9，則φ(n)=6，考慮2在mod 9下的冪21

57、 mod 9≡2,22 mod 9≡4 23 mod 9≡8,24 mod 9≡7，25 mod 9≡5, 26 mod 9≡1。即2的階為φ(9)，所以2為9的本原根。,模下的整數(shù)冪,例如： 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ù)冪,本原根不惟一。可驗(yàn)證除3外，19的本原根還

58、有2，10，13，14，15。注意并非所有的整數(shù)都有本原根，只有以下形式的整數(shù)才有本原根： 2,4,pα,2pα 其中p為奇素?cái)?shù)。,模下的整數(shù)冪,2. 指標(biāo)首先回憶一下一般對數(shù)的概念，指數(shù)函數(shù)y=ax(a>0,a≠1)的逆函數(shù)稱為以a為底x的對數(shù)，記為y=logax。對數(shù)函數(shù)有以下性質(zhì)： loga1=0,logaa=1,logaxy=logax+logay,logaxy=ylogax在模運(yùn)算中也有類似的函數(shù)。設(shè)p是一素?cái)?shù)

59、，a是p的本原根，則a,a2,…,ap-1產(chǎn)生出1到p-1之間的所有值，且每一值只出現(xiàn)一次。因此對任意b∈{1,…,p-1}，都存在惟一的i(1≤i≤p-1)，使得b≡ai mod p。稱i為模p下以a為底b的指標(biāo)，記為i=inda,p(b)。,指標(biāo),指標(biāo)有以下性質(zhì)： ① inda,p(1)=0。② inda,p(a)=1。 分別由以下關(guān)系得出： a0 mod p=1 mod p=1,a1 mod p=a。 以

60、上假定模數(shù)p是素?cái)?shù)，對于非素?cái)?shù)也有類似的結(jié)論。,指標(biāo),例： 設(shè)p=9，則φ(p)=6，a=2是p的一個(gè)本原根，a的不同的冪為（模9下）20≡1,21≡2,22≡4,23≡8,24≡7,25≡5,26≡1由此可得a的指數(shù)表如下所示。,指標(biāo),在討論指標(biāo)的另兩個(gè)性質(zhì)時(shí)，需要利用如下結(jié)論： 若az≡aq mod p，其中a和p互素，則有z≡q mod φ(p)。證明：因a和p互素，所以a在模p下存在逆元a-1，在az≡aq mod p兩

61、邊同乘以(a-1)q，得az-q≡1 mod p。由Euler定理aφ(p)≡1 mod p知存在一整數(shù)k，使得z-q≡kφ(p)，所以 z≡q mod φ(p)。,指標(biāo),由上述結(jié)論可得指標(biāo)的以下兩個(gè)性質(zhì)： ③ inda,p(xy)=[inda,p(x)+inda,p(y)] mod φ(p)。④ inda,p(yr)=[r×inda,p(y)] mod φ(p)。性質(zhì)④是性質(zhì)③的推廣。從指標(biāo)的以上性質(zhì)可見，指

62、標(biāo)與對數(shù)的概念極為相似。,指標(biāo),性質(zhì)③的證明：設(shè)由模運(yùn)算的性質(zhì)得：所以inda,p(xy)=[inda,p(x)+inda,p(y)] mod φ(p)（證畢）,指標(biāo),3. 離散對數(shù) 設(shè)p是素?cái)?shù)，a是p的本原根，即a1,a2,…,ap-1在 mod p下產(chǎn)生1到p-1的所有值，所以對b∈{1,…,p-1}，有惟一的i∈{1,…,p-1}使得b≡ai mod p。稱i為模p下以a為底b的離散對數(shù)，

63、 記為 i≡logab(mod p)。,離散對數(shù),當(dāng)a、p、i已知時(shí)，用快速指數(shù)算法可比較容易地求出b，但如果已知a、b和p，求i則非常困難。目前已知的最快的求離散對數(shù)算法其時(shí)間復(fù)雜度為：所以當(dāng)p很大時(shí)，該算法也是不可行的。,離散對數(shù),求離散對數(shù)的shank算法,,求5^x mod 23=3m=4;L:=array(1..4,[5^0 mod 23,5^1 mod 23,5^2 mod 23,5^3 mod 23])=[1

64、,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;5^16 mod 23 =3;,設(shè)p是一素?cái)?shù)，a小于p，稱a是p的平方剩余，如果方程 x2≡a (mod p)有解。否則稱為非平方剩余。,1.8 平方剩余,1.8平方剩余,定義：設(shè)n≥2, 若x2?a(mod n)有解

65、, 則稱a是模p的二次剩余; 若無解, 則稱a是模p的二次非剩余.二次剩余集合QRn二次非剩余集合QNRn.,容易證明，模p的平方剩余的個(gè)數(shù)為(p-1)/2，且與模p的非平方剩余的個(gè)數(shù)相等。如果a是模p的一個(gè)平方剩余，那么a恰有兩個(gè)平方根，一個(gè)在0到(p-1)/2之間，另一個(gè)在(p-1)/2到(p-1)之間，且這兩個(gè)平方根中的一個(gè)也是模p的平方剩余。,1.8 平方剩余,歐拉準(zhǔn)則,定理 (歐拉準(zhǔn)則)設(shè)p為一奇素?cái)?shù), p不能整除x,

66、則有: x屬于QRp證明: （1）若存在y2?x(mod p), （2）若 ，但y2?x(mod p)無解 對任意1≤ i ≤p-1, 總有一整數(shù)j, 使得: ij ?x(mod p). 由于y2?x(mod p)無解. 故i≠j. 因此, 1,2,…,p-1可分成(p-1)/2對, 每對之積(mod p). 因此, (p-1)! ?a(p-1)/2 ?1(mod p).

67、根據(jù)威爾遜定理知, (p-1)! ?-1(mod p), 所以命題得證.,定義1 設(shè)p是素?cái)?shù)，a是一整數(shù)，符號(hào) 的定義如下：稱符號(hào) 為Legendre符號(hào)。,1.8 平方剩余,例如：計(jì)算 有一個(gè)簡單公式： 例如：p=23，a=5，a(p-1)/2 mod p≡511 mod p=-1，所以5不是模23的平方剩余。,1.8 平方剩余,為了簡化“x2?a(mod p)有解”這一較長的

68、說法, 今引人勒讓德(Legendre)符號(hào) ,其定義如下:設(shè)p為奇素?cái)?shù), 且p不能整除a, 則: 當(dāng)a是模戶二次剩余; 當(dāng)a是模p二次非剩余.例如, , 因?yàn)閤2?3(mod 5)無解; ,因?yàn)?是模5的二次剩余.,勒讓

69、德符號(hào),下面給出Legendre符號(hào)的三條簡單而又重要的性質(zhì)定理6.16 ①若a?b(mod p), 則 ②若p不能整除a, 則 ③若p不能整除a與b, 則:,類似可證, 若 , a?b(mod p),則 .②顯然, 若 , a?b(mod p), 則③由歐拉準(zhǔn)則知: 故

70、:,由于同余式兩端只能是1或-1, 這兩數(shù)對模p要同余, 只有相等就行, 故有:③表明了,兩個(gè)剩余的乘積是剩余;兩個(gè)非剩余的乘積也是一剩余; 一個(gè)剩余和一個(gè)非剩余的乘積是一非剩余.,若 其中, 是素?cái)?shù), 1≤i≤n, 則有:因?yàn)?所以任給一整數(shù)a, 計(jì)算只需要計(jì)算出三種值: 其中q為奇