密碼學的數論基礎

1、第第7 7講講 數論基礎數論基礎第第7 7講講 數論基礎數論基礎1.定義：定義： 設整數設整數a和和b,且且a 0，如果存在整數，如果存在整數k使得使得b=ak， 那么就說那么就說a整除整除b（或（或b能被能被a整除）整除），記作，記作a|b，或者說，或者說b是是a的倍數。的倍數。 2.整除的基本性質整除的基本性質( N 整數集整數集) (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.定義：定義： 一個大于一個大于1的整數的整數p，只能被，只能被1或者是它本身整除或者是它本身整除,而不能而不能被其他整數整除，則稱整數為素數被其他整數整除，則稱整數為素數(prime number)，否，否則就叫做合數則就叫做合數(composite)。 eg 素數（素數（2，3，5，7，11，13等）等） 合數（合數（4，6，8，9，12等）等） 2.補充定理補充定理(1)：設：設a是任一大于是任一大于1的整數，則的整數，則a的的除除1外的最小正因子外的最小正因子q是素數，并且當是素數，并且當a是合數是合數時：時：素數補充定理qa2.補充定理補充定理(2)：若：若p

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

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

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

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

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

8、, 用以下方法可求出用以下方法可求出 gcd(a,b).最大公約數的歐幾里得算法. ,)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ī)律：余數除數被除數忽略最大公約數的歐幾里得算法 歐幾里得算法實現歐幾里得算法實現10

9、11112gcd( , ):;101(,.,):gcd( , )mmmrmrmmm mmmma bra rb mwhilerdoqrrq rmmreturnq qqrcommenta br算法最大公約數的歐幾里得算法 模運算典型實例時鐘模12的運算證明：證明：必要性必要性:設設ab (mod m), a=mp+r, b=mq+r, 0rm a-b=m(p-q), m|(a-b).充分性充分性:設設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的后三位數字的后三位數字 解：解： 7803（mod 1000）的結果）的結果 ?(1000) = 1000(1-1/2)(1-1/5) = 400， 有有7803 (7400)273 343 (mod 1000)推論（推論（ Fermat小定理）小定理）: p素數素數,a是整數且不能被是整數且不能被p整除整除,則則:a p-1 1 mod p. 例如：例如： 求求 253 (mod 11) = ? 由由Fermat小定理小定理: 210 = 1024 1 (mod 11) 253 = (210)523 1523 8 (mod 11) 解：解：（1）由費爾馬定理）由費爾馬

11、定理2100（mod 1001）1（mod 101）（2）243210 (2100) 432210 210 1024 (mod 101)=14eg: 計算計算243210 （mod 101） 解：因為解：因為41是素數，所以由費馬定理有是素數，所以由費馬定理有 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除所得的余數，除所得

12、的余數， 1010(-2)10=4555-2 4(mod6)， 所以所以1010 =6q+4，其中，其中q是一個正整數。于是是一個正整數。于是 (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)計算計算Xa ( mod n) ,其中其中 x, a, n Z+ Eg:計算計算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)勢：模的冪運算可快速完成，并且模的冪運算可快速完成，并

15、且不需要太大內存不需要太大內存22/ 2 (2-1) / 2 (yyyyyyy表 示除 以取 整 ， 即 ：是 偶 數（是 奇 數 ）但是，上述計算過程并不適合于計算機程序實但是，上述計算過程并不適合于計算機程序實現。為此，可以采用現。為此，可以采用“重復平方重復平方-乘乘”運算來運算來進行指數模運算。進行指數模運算。2222() () (yyyxyxxxy因 此 ：是 偶 數是 奇 數 ）重復平方重復平方-乘算法乘算法 求模指數運算的重復平方-乘算法 輸入：整數 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，則存在一個整數，則存在一個整數滿足滿足:a 1(mod m)定義（整數的次數）：定義（整數的次數）： 若若(a, m)1，m1，則使得同余式，則使得同余式 a 1(mod m)成立的成立的最小正整數最小正整數叫做叫做a對模對模m的

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

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

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

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

21、是模7的的本原根本原根 因為因為3 ?(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對模數對模數m的次數為的次數為3 (m) 所以：所以： 2不是不是7的本元根。的本元根。定理（原根）定理（原根） 設整數設整數m0,(g,m)=1,則則g是是m的一個原根的充要的一個原根的充要條件是：條件是： g，g2，g?(m)組成模數組成模數m的一組縮系。的一組縮系。定理說

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

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

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

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

26、 是 的原根。證明：（ ），（）（）由定理是 的一個原根。 12gm6 2 32,33;2mod7mod763 m 7mqqmm1223例如，判斷 3是否是 7的原根。解：（ ）所以（ ）（ ）qq3 （）2 13 （）1因此 是 的原根。 12gmm2,33;2mod7mod7m=7qqmm1223例如，判斷 4是否是 7的一個原根解：（ ）62 3所以（ ）（ ）qq4 （）2 14 （）1因此4不是的本元根。定理（原根的計算）：定理（原根的計算）： 1 ,1,2,.,papd dpd設 對模數奇素數 的次數是（），則：a都不是 的原根。 12.1,12.dadpdddpadpd證明：因為

27、 （ ， ， ）對模數 的次數為，而（ ， ）所以 （ ， ， ）都不是 的原根。（ ， ）一個計算原根的算法：一個計算原根的算法： 2112.1221112, 2,., 2(3)1111dppppaapddppdpp （）列出數， ， （）取 ，計算 對 的次數 ，如果 ，2就是 的原根，算法結束；如果，在步驟中列出的數中除去以下各數：在步驟（）列出的數中再取一個，重復步驟（），直到步驟（）縮列出的數僅剩下（ ）個。41例如：求出 的原根。1解 ：（ ） 列 出1， 2， 3， .， 40 （ 1）（2）取2，因為2對模數41的次數為20，因此（1）式中除去以下各數：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，因為3對模數41的次數為8，因此在（1）式中除去以下各數：3，9，27，40，38，32，14，1其中1，9，32，40在第一次已經除去，得到：6，7，11，12，13，15，17，19，22，24，26，28，29，30，34，35這剩下的（40）16個數就是41的原根。如果整數如果整數m0有一個元根有一個元根g，g，g2，g?(m)(或數或數1,

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

30、，求任意整數n的離散對數k,可以通過得到：( )(13) 12(1,2,.,12)(0( ) 2 (mod13)iiikimn ikkmn例：g=2是m=13的元根,。求的離散對數：指數的性質：設指數的性質：設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（）設 也是 的一個原根，則(mod13)()( )(mod ( )(mod13

31、)311(mod12)3(mod12)ind abinda ind bmindindxindindx3x113x11例：求解同余方程3x 11(mod13)解：上述方程與gg同解。因為所以方程gg與同解，其指數為8，因此x=8即是方程解。55(mod12)5939(mod12)39(mod12)8,11,75indindindxindxx33例：求解同余方程x(mod13)解：解上述方程只需要解3indx。因為所以所以indx=3,7,11是的解。因此是方程x(mod13)的解。3(mod ( )(1)23(mod12)nindanindamnxindindx例：求解冪同余方程2(mod13)

32、解：因為所以的解就是原方程的解。ind2=4,ind3=9所以2x=8(mod 12)即x=4就是原方程的解。0-1(mod ),kpykpygppp gy猜想（離散對數困難問題）對于一個奇素數 ，整數 ，存在唯一的滿足。選擇一個適當大的 ，如果已知和 ，計算離散對數k是十分困難的?；陔x散對數困難性假設，基于離散對數困難性假設，EIGamal提出了提出了EIgamal公鑰公鑰密碼體制。密碼體制。21()(mod)()()attatatttmyypmb gmb gmb bm12mod113412det234 112424215343131291(mod11)75注意：注意：5 5是是-2-2的

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

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