密碼學(xué)的數(shù)論基礎(chǔ).

1、第第7 7講講 數(shù)論基礎(chǔ)數(shù)論基礎(chǔ)第第7 7講講 數(shù)論基礎(chǔ)數(shù)論基礎(chǔ)1.定義：定義： 設(shè)整數(shù)設(shè)整數(shù)a和和b,且且a 0，如果存在整數(shù)，如果存在整數(shù)k使得使得b=ak， 那么就說那么就說a整除整除b（或（或b能被能被a整除）整除），記作，記作a|b，或者說，或者說b是是a的倍數(shù)。的倍數(shù)。 2.整除的基本性質(zhì)整除的基本性質(zhì)( N 整數(shù)集整數(shù)集) (1) a(a0), a|0,a|a (同理同理 b N,1|b) (2) b|a, cb|ca (3) a|b, b|c a|c.（傳遞性）（傳遞性） (4) a|b, a|c a|(xb+yc) (x,y N) (5) b|a 且且a0 |b|a| (6)

2、 cb|ca, b|a1.定義：定義： 一個(gè)大于一個(gè)大于1的整數(shù)的整數(shù)p，只能被，只能被1或者是它本身整除或者是它本身整除,而不能而不能被其他整數(shù)整除，則稱整數(shù)為素?cái)?shù)被其他整數(shù)整除，則稱整數(shù)為素?cái)?shù)(prime number)，否，否則就叫做合數(shù)則就叫做合數(shù)(composite)。 eg 素?cái)?shù)（素?cái)?shù)（2，3，5，7，11，13等）等） 合數(shù)（合數(shù)（4，6，8，9，12等）等） 2.補(bǔ)充定理補(bǔ)充定理(1)：設(shè)：設(shè)a是任一大于是任一大于1的整數(shù)，則的整數(shù)，則a的的除除1外的最小正因子外的最小正因子q是素?cái)?shù)，并且當(dāng)是素?cái)?shù)，并且當(dāng)a是合數(shù)是合數(shù)時(shí)：時(shí)：素?cái)?shù)補(bǔ)充定理qa2.補(bǔ)充定理補(bǔ)充定理(2)：若：若p

3、是一個(gè)素?cái)?shù)，是一個(gè)素?cái)?shù)，a是任一整數(shù)，是任一整數(shù)，則有則有p|a或或(p,a)=1素?cái)?shù)補(bǔ)充定理（續(xù)）素?cái)?shù)補(bǔ)充定理（續(xù)）2.補(bǔ)充定理：補(bǔ)充定理： p為素?cái)?shù)，且為素?cái)?shù)，且p|ab,那么那么p|a或或p|b。 更一般地，如果更一般地，如果abz能夠被素?cái)?shù)能夠被素?cái)?shù)p整除，那么整除，那么a,b,z中的某個(gè)數(shù)必能被中的某個(gè)數(shù)必能被p整除。整除。3.素?cái)?shù)個(gè)數(shù)定理（素?cái)?shù)個(gè)數(shù)定理（1）：）： 素?cái)?shù)的個(gè)數(shù)是無限的素?cái)?shù)的個(gè)數(shù)是無限的原因：原因：（1）N（N1）的除）的除1外的最小正因數(shù)外的最小正因數(shù)q是一個(gè)素?cái)?shù)是一個(gè)素?cái)?shù)（2）如果）如果q=pi，（，（i1,2,k), 且且q|N，因此，因此q|(N- p1p2,

4、.pk)，所以，所以q|1，與，與q是素?cái)?shù)矛盾。是素?cái)?shù)矛盾。素?cái)?shù)個(gè)數(shù)定理及證明證明：反證法證明：反證法假設(shè)正整數(shù)個(gè)數(shù)是有限的，設(shè)為假設(shè)正整數(shù)個(gè)數(shù)是有限的，設(shè)為p1,p2,.,pk令：令：p1p2pk+1=N (N1)則則N有一個(gè)素?cái)?shù)有一個(gè)素?cái)?shù)p，且，且ppi（i=1,2,k).故故p是上述是上述k個(gè)素?cái)?shù)外的另外一個(gè)素?cái)?shù)。個(gè)素?cái)?shù)外的另外一個(gè)素?cái)?shù)。因此與假設(shè)矛盾。因此與假設(shè)矛盾。素?cái)?shù)定義及素?cái)?shù)個(gè)數(shù)定理3.素?cái)?shù)個(gè)數(shù)定理（素?cái)?shù)個(gè)數(shù)定理（2）：）： 設(shè)設(shè) (x)是小于是小于x的素?cái)?shù)個(gè)數(shù)，則的素?cái)?shù)個(gè)數(shù)，則 (x) x / lnx, 即即x時(shí)，比值時(shí)，比值 (x) /(x / lnx) 1 eg:可以估算可

5、以估算100位素?cái)?shù)的個(gè)數(shù)：位素?cái)?shù)的個(gè)數(shù)： (10100) - (1099) 10100/(ln10100) 1099/(ln1099) 3.9 * 1097.1.整數(shù)的唯一分解定理定理（算術(shù)基本定理）整數(shù)的唯一分解定理定理（算術(shù)基本定理）: 設(shè)設(shè)nZ, 有分解式有分解式, n = p1e1p2e2.pmem,其中其中p1, p2, pmZ+是互不相同的素?cái)?shù)是互不相同的素?cái)?shù), e1,e2,emZ+, 并且數(shù)對并且數(shù)對(p1, e1), (p2, e2),(pm, em)由由n唯一確定（即唯一確定（即如果不考慮順序，如果不考慮順序，n的分解是唯一的）的分解是唯一的）.eg: 504=23327,

6、1125 = 3253整數(shù)的唯一分解定理就是在所有比就是在所有比1大的整數(shù)中大的整數(shù)中,除了除了1和它本身以外和它本身以外,不再有別的約數(shù)不再有別的約數(shù),這種整數(shù)這種整數(shù)叫做質(zhì)數(shù)叫做質(zhì)數(shù),質(zhì)數(shù)又叫做素?cái)?shù)。質(zhì)數(shù)又叫做素?cái)?shù)。判斷方法：小的素?cái)?shù)要記住，比如判斷方法：小的素?cái)?shù)要記住，比如11、13、17、19、23、29、31等，最等，最好把好把100以內(nèi)的素?cái)?shù)都記以內(nèi)的素?cái)?shù)都記?。鹤。?57111317192329313741434753596167717379838997對于大數(shù)，首先看能不能被對于大數(shù)，首先看能不能被2、3、5、7整除，如果不能，就看能不能被更整除，如果不能，就看能不能被更大的素

7、數(shù)整除，這樣你記住的相對小素?cái)?shù)就有用了，一個(gè)一個(gè)試，從大的素?cái)?shù)整除，這樣你記住的相對小素?cái)?shù)就有用了，一個(gè)一個(gè)試，從11開開始，以此試始，以此試13、17、19、23、29、31等。要一直試到比這個(gè)數(shù)的平方根等。要一直試到比這個(gè)數(shù)的平方根大的第一個(gè)數(shù)，如果沒有能整除的，則這個(gè)數(shù)是素?cái)?shù)。大的第一個(gè)數(shù)，如果沒有能整除的，則這個(gè)數(shù)是素?cái)?shù)。2. 求最大公約數(shù)的兩種方法：求最大公約數(shù)的兩種方法： (1)因數(shù)分解：因數(shù)分解： eg:1728 = 2632,4536 = 23347, gcd(1728, 4536) = 2332=72.(2)歐幾里得歐幾里得(Euclid)算法算法 設(shè)設(shè)a, b N, ab0

8、, 用以下方法可求出用以下方法可求出 gcd(a,b).最大公約數(shù)的歐幾里得算法. ,)gcd( ,0 , . )gcd( ,0 ,)gcd( ,0 ,)gcd()gcd( ,0 ,1111123223332121122211111nnnnnnnnnnnnrqrr,rrrrrqrr,rrrrrqrr,rrrrrqrbb,ra,bbrrbqa 歐幾里得算法抽象歐幾里得算法抽象112 1213 2324 342111b.gcd( , )kk kkkkkkaqbrq rrrq rrrq rrrq rrrqra br規(guī)律：余數(shù)除數(shù)被除數(shù)忽略最大公約數(shù)的歐幾里得算法 歐幾里得算法實(shí)現(xiàn)歐幾里得算法實(shí)現(xiàn)10

9、11112gcd( , ):;101(,.,):gcd( , )mmmrmrmmm mmmma bra rb mwhilerdoqrrq rmmreturnq qqrcommenta br算法最大公約數(shù)的歐幾里得算法 模運(yùn)算典型實(shí)例時(shí)鐘模12的運(yùn)算證明：證明：必要性必要性:設(shè)設(shè)ab (mod m), a=mp+r, b=mq+r, 0rm a-b=m(p-q), m|(a-b).充分性充分性:設(shè)設(shè)m|(a-b), a=mp+r, b=mq+s, 0r, sm a-b=m(p-q)+(r-s) m|(r-s) 0|r-s|1，如果，如果gcd(a, n) = 1,則則:a?(n) 1mod n.

10、 eg: 求求7803的后三位數(shù)字的后三位數(shù)字 解：解： 7803（mod 1000）的結(jié)果）的結(jié)果 ?(1000) = 1000(1-1/2)(1-1/5) = 400， 有有7803 (7400)273 343 (mod 1000)推論（推論（ Fermat小定理）小定理）: p素?cái)?shù)素?cái)?shù),a是整數(shù)且不能被是整數(shù)且不能被p整除整除,則則:a p-1 1 mod p. 例如：例如： 求求 253 (mod 11) = ? 由由Fermat小定理小定理: 210 = 1024 1 (mod 11) 253 = (210)523 1523 8 (mod 11) 解：解：（1）由費(fèi)爾馬定理）由費(fèi)爾馬

11、定理2100（mod 1001）1（mod 101）（2）243210 (2100) 432210 210 1024 (mod 101)=14eg: 計(jì)算計(jì)算243210 （mod 101） 解：因?yàn)榻猓阂驗(yàn)?1是素?cái)?shù)，所以由費(fèi)馬定理有是素?cái)?shù)，所以由費(fèi)馬定理有 1777401（mod 41），而），而 1841 = 46 * 40 + 1 所以所以17771841 1777 14 (mod 41)， a=14eg: 17771841 a（mod 41），求），求a在在0到到41的值。的值。 解：解：由歐拉定理得由歐拉定理得1061（mod7），），下面求下面求1010被被6除所得的余數(shù)，除所得

12、的余數(shù)， 1010(-2)10=4555-2 4(mod6)， 所以所以1010 =6q+4，其中，其中q是一個(gè)正整數(shù)。于是是一個(gè)正整數(shù)。于是 (1010)10=106q+4=(106)q10410434=9222=4（mod7），），因此，因此，再過再過(1010)10天是星期五。天是星期五。eg: 如果今天是星期一，問從今天起再過如果今天是星期一，問從今天起再過(1010)10天天是星期幾？是星期幾？ eg: 1、 21000000mod 77=?1 1 2 21 12(mod 789)2(mod 789)7 7 2 26464367(mod 789)367(mod 789)2 2 2 2

13、2 24(mod 789)4(mod 789)8 8 2 2128128559(mod 789)559(mod 789)3 3 2 24 416(mod 789)16(mod 789)9 9 2 225625637(mod 789)37(mod 789)4 4 2 28 8256(mod 789)256(mod 789)10 10 2 2512512580(mod 789)580(mod 789)5 5 2 2161649(mod 789)49(mod 789)11 11 2 210241024286(mod 789)286(mod 789)6 6 2 2323234(mod 789)34(m

14、od 789)計(jì)算計(jì)算Xa ( mod n) ,其中其中 x, a, n Z+ Eg:計(jì)算計(jì)算21234 (mod 789) 一種有效的方法：一種有效的方法： 24 16 28 256 216 2562 49 232 492 34 264 342 367 2128 3672 559 2256 5592 37 2512 372 580 21024 5802 286 1234 = 1024+128+64+16+2 （1234 = (10011010010)2） 21234 = 286 559 367 49 4 481 (mod 789)優(yōu)勢：優(yōu)勢：模的冪運(yùn)算可快速完成，并且模的冪運(yùn)算可快速完成，并

15、且不需要太大內(nèi)存不需要太大內(nèi)存22/ 2 (2-1) / 2 (yyyyyyy表 示除 以取 整 ， 即 ：是 偶 數(shù)（是 奇 數(shù) ）但是，上述計(jì)算過程并不適合于計(jì)算機(jī)程序?qū)嵉?，上述?jì)算過程并不適合于計(jì)算機(jī)程序?qū)崿F(xiàn)。為此，可以采用現(xiàn)。為此，可以采用“重復(fù)平方重復(fù)平方-乘乘”運(yùn)算來運(yùn)算來進(jìn)行指數(shù)模運(yùn)算。進(jìn)行指數(shù)模運(yùn)算。2222() () (yyyxyxxxy因 此 ：是 偶 數(shù)是 奇 數(shù) ）重復(fù)平方重復(fù)平方-乘算法乘算法 求模指數(shù)運(yùn)算的重復(fù)平方-乘算法 輸入：整數(shù) x，y，n：x0，y?0，n1 輸出：(mod )yxn 算法描述： 00 mod_exp(x,y, n) 01 if y=0 r

16、eturn(1) 02 if y (mod 2)=0 return(mod_exp(x2(mod n), y2, n)（mod n） 03 return(x mod_exp(x2(mod n), y2, n)(mod n) 由歐拉定理知道：如果由歐拉定理知道：如果(a, m)1，m1，則，則a?(n) 1(mod m)也就是說，如果也就是說，如果(a, m)1，m1，則存在一個(gè)整數(shù)，則存在一個(gè)整數(shù)滿足滿足:a 1(mod m)定義（整數(shù)的次數(shù)）：定義（整數(shù)的次數(shù)）： 若若(a, m)1，m1，則使得同余式，則使得同余式 a 1(mod m)成立的成立的最小正整數(shù)最小正整數(shù)叫做叫做a對模對模m的

17、的次數(shù)次數(shù)。定理：設(shè)定理：設(shè)a對模數(shù)對模數(shù)m的次數(shù)為的次數(shù)為l，an1（mod m），則），則l|n。證明：證明： 如果結(jié)論不成立，則必有兩個(gè)整數(shù)如果結(jié)論不成立，則必有兩個(gè)整數(shù)q和和r，使得：，使得： nqlr（0rl） 而而1 an a(qlr) aqlar ar (mod m)，因此與，因此與l的定義相的定義相違背。違背。 推論：設(shè)推論：設(shè)a對模數(shù)對模數(shù)m的次數(shù)為的次數(shù)為l，則，則l|?(m)。整數(shù)次數(shù)的計(jì)算：整數(shù)次數(shù)的計(jì)算： 因?yàn)橐驗(yàn)閘|?(m)，因此可以通過計(jì)算以下對模數(shù)，因此可以通過計(jì)算以下對模數(shù)m的值求出。的值求出。例如：例如：m7，a2(m)62322（mod 7）423（mod

18、 7）1因此因此a對模數(shù)對模數(shù)m的次數(shù)為的次數(shù)為3。s1212s,.dd .dmdddaaa，（其中，是 （）的諸因子）整數(shù)次數(shù)的有效計(jì)算方法（整數(shù)次數(shù)的有效計(jì)算方法（1）：）：1212.killlklimpppmp如 果是的 標(biāo) 準(zhǔn) 分 解 式 ， 整 數(shù) a對 模 數(shù) m的 次 數(shù)等 于 整 數(shù) a對 模 數(shù)的 諸 次 數(shù) 的 最 小 公 倍 數(shù) 。1212a1, 2,.,),.,0|(1, 2,.,),.,iiiliiklddilddiikfpikdfffapamdmdddamapfdikdfff證 明 ： 設(shè)表 示對 模 數(shù)（1(mod )1(mod )如 果不 是 模 數(shù)的 次 數(shù)

19、， 則 設(shè) 其 次 數(shù) 為1(mod )1(mod )與是的 最 小 公 倍 數(shù) 矛 盾 。整數(shù)次數(shù)的有效計(jì)算方法（整數(shù)次數(shù)的有效計(jì)算方法（1）：）：amam例如：設(shè) 2，45，求 對的次數(shù)。解 ：45 5 92對 模 數(shù) 5的 次 數(shù) 是 42對 模 數(shù) 9的 次 數(shù) 是 6因 此 2對 模 數(shù) 45的 次 數(shù) 為 ：4,6=12。整數(shù)次數(shù)的有效計(jì)算方法（整數(shù)次數(shù)的有效計(jì)算方法（2）：）：211212|1 2 jjfijjjjjjpapffffpfpafjifpfji定 理 （ 次 數(shù) 的 求 法 之 二 ）設(shè)是 一 個(gè) 素 數(shù) ，對 模 數(shù)的 次 數(shù) 是， 則 ：=或=； 又 設(shè)， 則 有

20、 ：10102apaf例 如 ： 設(shè) 7， 2， 求對 模 數(shù)的 次 數(shù)。122410410127148,2| 4822128fff解 ：， 所 以 ：定理：設(shè)定理：設(shè)a對模數(shù)對模數(shù)m的的次數(shù)次數(shù)為為l，1,a, a2,，al-1對對模數(shù)模數(shù)m兩兩不同余。兩兩不同余。證明：證明： 如果結(jié)論不成立，則有某對如果結(jié)論不成立，則有某對j，k（0jkl-1，使得：，使得： aj ak（mod m） 因此：因此： ak-j 1（mod m） 而而1k-j0,(g,m)=1, 如果整數(shù)如果整數(shù)g對對m的的次數(shù)次數(shù)為為?(m) ，則，則g叫做叫做m的一個(gè)的一個(gè)本原根本原根（或（或原根原根）. eg: 3是模

21、是模7的的本原根本原根 因?yàn)橐驗(yàn)? ?(7) 36 1(mod 7) w37 mod 7 = 3 38 mod 7 = 2w39 mod 7 = 6 310 mod 7 = 4w311 mod 7 = 5 312 mod 7 = 1例如：例如：m7，a2(m)62322（mod 7）423（mod 7）1因此：因此： a對模數(shù)對模數(shù)m的次數(shù)為的次數(shù)為3 (m) 所以：所以： 2不是不是7的本元根。的本元根。定理（原根）定理（原根） 設(shè)整數(shù)設(shè)整數(shù)m0,(g,m)=1,則則g是是m的一個(gè)原根的充要的一個(gè)原根的充要條件是：條件是： g，g2，g?(m)組成模數(shù)組成模數(shù)m的一組縮系。的一組縮系。定理說

22、明：如果定理說明：如果g是是m的一個(gè)原根，則模數(shù)的一個(gè)原根，則模數(shù)m的一的一組縮系可表示為形如定理中的幾何級數(shù)。組縮系可表示為形如定理中的幾何級數(shù)。2.定理：定理： 設(shè)對素?cái)?shù)設(shè)對素?cái)?shù)p而言，如果而言，如果g是一個(gè)是一個(gè)本原根本原根 (1)如果如果n是是整數(shù)，那么整數(shù)，那么gn 1(mod p)當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) n0(mod p-1) (2)如果如果j和和k都是整數(shù)，那么都是整數(shù)，那么gj gk當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)j k(mod p-1)問題：是否所有的正整數(shù)都有原根？問題：是否所有的正整數(shù)都有原根？例如：例如：m12(m)623，與，與m互素的正整數(shù)包括互素的正整數(shù)包括5，7，11。52（mod

23、12）1因此，因此，5對對12的次數(shù)是的次數(shù)是272（mod 12）1因此因此7對模數(shù)對模數(shù)m的次數(shù)為的次數(shù)為2112（mod 12）1因此因此11對模數(shù)對模數(shù)m的次數(shù)為的次數(shù)為2因此因此m12沒有原根。沒有原根。定理（整數(shù)存在原根的必要條件）：定理（整數(shù)存在原根的必要條件）： 設(shè)設(shè)m1，若，若m有原根，則有原根，則m必為下列諸數(shù)之一：必為下列諸數(shù)之一：2，4，pl，2pl（l1，p為奇素?cái)?shù)）。為奇素?cái)?shù)）。定理（整數(shù)存在原根的充分條件）：定理（整數(shù)存在原根的充分條件）： 設(shè)設(shè)m2，4，pl，2pl（l1，p為奇素?cái)?shù)）時(shí)，則為奇素?cái)?shù)）時(shí)，則m有原有原根。根。定理（整數(shù)原根個(gè)數(shù)）：定理（整數(shù)原根個(gè)

24、數(shù)）： 設(shè)設(shè)m有一個(gè)原根有一個(gè)原根g，則，則m恰有恰有?(?(m)個(gè)對模數(shù)個(gè)對模數(shù)m不同余不同余的原根，這些原根由以下集合給出：的原根，這些原根由以下集合給出：|1( ),( , ( ) 1tSgtmtm 17gmmmmm1( ),( , ( ) 13 mod733 mod75mtmtm 例如，已知 3是 7的一個(gè)原根，求 的所有元根。解：（ ）62 3（ ）（6）2因此 有兩個(gè)元根。滿足條件的t=1,5即 有兩個(gè)元根，分別為3和5原根的判斷：原根的判斷： 一般來說，判斷一般來說，判斷g是否時(shí)一個(gè)素?cái)?shù)是否時(shí)一個(gè)素?cái)?shù)m的原根時(shí)，的原根時(shí)，不需要逐一計(jì)算不需要逐一計(jì)算g1，g2，g?(m)，而僅需

25、要，而僅需要計(jì)算計(jì)算gt(modm），其中），其中t|?(m)。 23gmm4 mod74 mod7)24 mod7) 14 mod71m16例如，判斷 4是否是 7的一個(gè)原根解：（ ）62 3滿足條件t| (m)的t=1,2,3,6（）4（）因此4不是 的本元根。定理（原根的計(jì)算）：定理（原根的計(jì)算）： 12( )2.11(mod )(1,2,., )ismqmmqqqgmgmgm is設(shè)，（ ）的所有不同的素因子是 ， ， ，（ ， ），則 是 的一個(gè)原根的充要條件是： 3121220812412525)20,812mod4140112mod411811241gmmqqmmqqm例如，證明

26、 是 的原根。證明：（ ），（）（）由定理是 的一個(gè)原根。 12gm6 2 32,33;2mod7mod763 m 7mqqmm1223例如，判斷 3是否是 7的原根。解：（ ）所以（ ）（ ）qq3 （）2 13 （）1因此 是 的原根。 12gmm2,33;2mod7mod7m=7qqmm1223例如，判斷 4是否是 7的一個(gè)原根解：（ ）62 3所以（ ）（ ）qq4 （）2 14 （）1因此4不是的本元根。定理（原根的計(jì)算）：定理（原根的計(jì)算）： 1 ,1,2,.,papd dpd設(shè) 對模數(shù)奇素?cái)?shù) 的次數(shù)是（），則：a都不是 的原根。 12.1,12.dadpdddpadpd證明：因?yàn)?/p>

27、 （ ， ， ）對模數(shù) 的次數(shù)為，而（ ， ）所以 （ ， ， ）都不是 的原根。（ ， ）一個(gè)計(jì)算原根的算法：一個(gè)計(jì)算原根的算法： 2112.1221112, 2,., 2(3)1111dppppaapddppdpp （）列出數(shù)， ， （）取 ，計(jì)算 對 的次數(shù) ，如果 ，2就是 的原根，算法結(jié)束；如果，在步驟中列出的數(shù)中除去以下各數(shù)：在步驟（）列出的數(shù)中再取一個(gè)，重復(fù)步驟（），直到步驟（）縮列出的數(shù)僅剩下（ ）個(gè)。41例如：求出 的原根。1解 ：（ ） 列 出1， 2， 3， .， 40 （ 1）（2）取2，因?yàn)?對模數(shù)41的次數(shù)為20，因此（1）式中除去以下各數(shù)：2，4，8，16，32，

28、23，5，10，20，40，39，37，33，25，9，18，36，31，21，1得到：3，6，7，11，12，13，14，15，17，19，22，24，26，27，28，29，30，34，35，38 41例如：求出 的原根。解(續(xù)）：（3）取3，因?yàn)?對模數(shù)41的次數(shù)為8，因此在（1）式中除去以下各數(shù)：3，9，27，40，38，32，14，1其中1，9，32，40在第一次已經(jīng)除去，得到：6，7，11，12，13，15，17，19，22，24，26，28，29，30，34，35這剩下的（40）16個(gè)數(shù)就是41的原根。如果整數(shù)如果整數(shù)m0有一個(gè)元根有一個(gè)元根g，g，g2，g?(m)(或數(shù)或數(shù)1,

29、g，g，g2，g?(m)-1）組成模數(shù)）組成模數(shù)m的一組縮系。的一組縮系。例如，例如， 3是模是模7的的本原根，因此本原根，因此： 31 3 32 2 33 6 34 4 35 5 36 1 上述六個(gè)數(shù)剛好是模數(shù)上述六個(gè)數(shù)剛好是模數(shù)m的一組縮系。的一組縮系。定義：任一整數(shù)定義：任一整數(shù)n，（，（n，m）1，必有唯一的整，必有唯一的整數(shù)數(shù)k（0k ?（m），滿足：），滿足： ngk（mod m） 其中其中k叫做叫做n對模數(shù)對模數(shù)m的指數(shù)，記做的指數(shù)，記做kindgn（簡（簡記為記為ind n） (指數(shù)也叫做指數(shù)也叫做離散對數(shù)離散對數(shù))。xg mod m (mod )xngm對于已知元根g和模數(shù)m

30、，求任意整數(shù)n的離散對數(shù)k,可以通過得到：( )(13) 12(1,2,.,12)(0( ) 2 (mod13)iiikimn ikkmn例：g=2是m=13的元根,。求的離散對數(shù)：指數(shù)的性質(zhì)：設(shè)指數(shù)的性質(zhì)：設(shè)g是是m的原根，如果的原根，如果(a,m)(b,m)1：11g11()( )(mod ( )(2)(mod ( )(1)(3)1 0,1( )(4)( 1)(2)2(5)mind a(mod ( )nggind abinda ind bmindanindamnindindgmindmgind a ind gm（）設(shè) 也是 的一個(gè)原根，則(mod13)()( )(mod ( )(mod13

31、)311(mod12)3(mod12)ind abinda ind bmindindxindindx3x113x11例：求解同余方程3x 11(mod13)解：上述方程與gg同解。因?yàn)樗苑匠蘥g與同解，其指數(shù)為8，因此x=8即是方程解。55(mod12)5939(mod12)39(mod12)8,11,75indindindxindxx33例：求解同余方程x(mod13)解：解上述方程只需要解3indx。因?yàn)樗运詉ndx=3,7,11是的解。因此是方程x(mod13)的解。3(mod ( )(1)23(mod12)nindanindamnxindindx例：求解冪同余方程2(mod13)

32、解：因?yàn)樗缘慕饩褪窃匠痰慕?。ind2=4,ind3=9所以2x=8(mod 12)即x=4就是原方程的解。0-1(mod ),kpykpygppp gy猜想（離散對數(shù)困難問題）對于一個(gè)奇素?cái)?shù) ，整數(shù) ，存在唯一的滿足。選擇一個(gè)適當(dāng)大的 ，如果已知和 ，計(jì)算離散對數(shù)k是十分困難的?；陔x散對數(shù)困難性假設(shè)，基于離散對數(shù)困難性假設(shè)，EIGamal提出了提出了EIgamal公鑰公鑰密碼體制。密碼體制。21()(mod)()()attatatttmyypmb gmb gmb bm12mod113412det234 112424215343131291(mod11)75注意：注意：5 5是是-2-2的

33、的乘法逆元素乘法逆元素注意：括號里的注意：括號里的是是A A的伴隨矩陣的伴隨矩陣定義定義(二次剩余）二次剩余） 設(shè)設(shè)n是一個(gè)大于是一個(gè)大于1的正整數(shù)，的正整數(shù)， aZ, a 0 (mod n). 如果同余方程如果同余方程 x2a (mod n) 有一個(gè)解有一個(gè)解1xn-1, 則稱則稱a是是模數(shù)模數(shù)n的的二次剩余二次剩余，而，而x稱之為稱之為a模模n的平方根。的平方根。如果上述方程無解，則如果上述方程無解，則a稱之為模數(shù)稱之為模數(shù)n的非二次剩余。的非二次剩余。群的定義 設(shè)G為非空集合，在G內(nèi)定義了一種代數(shù)運(yùn)算為，若滿足下述公理：(1)有封閉性。對任意a、bG，恒有abG. (2)結(jié)合律成立。對任

34、意a、b、cG，有(ab)c=a(bc)(3)G中有一恒等元e存在，對任意aG, 有eG, 使ae=ea=a(4)對任意aG，存在a的逆元a-1G，使aa-1= a-1a =e則G構(gòu)成一個(gè)群。若群G滿足交換律，則稱群G為交換群群舉例例如，對于非空集合G=0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10，在mod11的情況下做加法運(yùn)算，構(gòu)成一個(gè)群，且是交換群。下面看看G，+滿足公理的情況。(1)封閉性。對任意a、bG，恒有a+b(mod11)G. 例如, 8+9=176(mod11)G, 滿足封閉性性質(zhì)。 (2)結(jié)合律成立。對任意a、b、cG，有(a+b) +c=a+ (b+c)。這個(gè)容易理解。(3)G中有一恒等元e存在，對任意aG, 有eG, 使a+e=e+a=a. 在給定的集合G中，e=0, 滿足上面的性質(zhì)，故恒等元存在。(4)對任意aG，存在a的逆元a-1G，使a+a-1= a-1+a=e. 例如, 7在集合中的逆元為4，因7+4(mod11) 0顯然，加法滿足交換律，故該群是交換群群的例子 又如，對于非空集合