附錄：數(shù)學基礎

1、四川大學1/72上周講到應用密碼學應用密碼學(數(shù)論、有限域和計算復雜性基礎數(shù)論、有限域和計算復雜性基礎 )四川大學電子信息學院2/72一、數(shù)論基礎一、數(shù)論基礎整數(shù)具有以下性質(zhì)：（整數(shù)具有以下性質(zhì)：（1）b | a，c | b，則，則c | a（2）a | 1，則，則a=1（3）對任一）對任一b（b0）, b 0（4） b | g， b | h，則對任意整數(shù)，則對任意整數(shù)m, n有有b | (mg+nh)定理定理1 1：任給兩個整數(shù)任給兩個整數(shù)a，b，其中，其中 b0，則存在兩個唯一的整數(shù)，則存在兩個唯一的整數(shù)q和和r，使得使得 a = qb + r ， 0 r b 成立。成立。余數(shù)，也叫做非負

2、最小剩余余數(shù)，也叫做非負最小剩余不完全商不完全商1.1.素數(shù)與互為素數(shù)素數(shù)與互為素數(shù) 整除與因子的概念：整除與因子的概念： 任給兩個整數(shù)任給兩個整數(shù)a，b，其中，其中 b0，如果存在一個整數(shù)，如果存在一個整數(shù)q使得等式使得等式 a = q b 成立，此時稱成立，此時稱b整除整除a，記為，記為b | a，并稱，并稱b為為a的的因子因子，把，把a為為b的的倍數(shù)倍數(shù)。 否則否則b不整除不整除a，記為，記為 b a四川大學電子信息學院3/72 最大公因數(shù)與輾轉(zhuǎn)相除法最大公因數(shù)與輾轉(zhuǎn)相除法定義：定義：設設a1，a2，an是是n個不全為零的整數(shù)，若整數(shù)個不全為零的整數(shù)，若整數(shù)d（通?？紤]（通?？紤]d0）是

3、它們之中每一個的因數(shù)是它們之中每一個的因數(shù)(子子)，那么，那么d 就叫做設就叫做設a1,a2,an的一個公因數(shù)。的一個公因數(shù)。 公因數(shù)只有有限個，其中最大的一個公因數(shù)叫最大公因數(shù)公因數(shù)只有有限個，其中最大的一個公因數(shù)叫最大公因數(shù)(子子) 。 記為記為： （ a1,a2,an ）， 若（若（ a1,a2,an ）=1，則稱，則稱a1，a2，an互素?；ニ?。 對于整數(shù)對于整數(shù)a, b，其最大公因數(shù)等價的定義形式是：，其最大公因數(shù)等價的定義形式是： （a, b）maxk， k | a且且k | b注意：注意： （a, b）= （a, b）= （a, b）= （|a|，|b|）定理定理2 2：設設a,

4、 b, c是任意不全為零的整數(shù)，且是任意不全為零的整數(shù)，且 a = qb + c ；其中其中q是整數(shù)，是整數(shù)， 則有則有 （ a, b ）=（ b, c ）。 即被除數(shù)和除數(shù)的最大公因子與除數(shù)和余數(shù)最大公因子相同。即被除數(shù)和除數(shù)的最大公因子與除數(shù)和余數(shù)最大公因子相同。a 除以b, 商q余c例：(18, 12) = ( 12, 6) = (6, 0) = 6 (11, 10) = ( 10, 1) = (1, 0) = 1四川大學電子信息學院4/72輾轉(zhuǎn)相除法輾轉(zhuǎn)相除法: （Euclid算法，歐幾里德算法）任給兩個整數(shù)任給兩個整數(shù)a，b，設，設 a b0，由代余數(shù)的除法，有下列等式：，由代余數(shù)的

5、除法，有下列等式： a = bq1 + r1，0 r1 b， b = r1 q2 + r2，0 r2 r1 ， （1） rn-2 = rn-1 qn + rn ，0 r1 r2 r3 , 故經(jīng)有限次代余數(shù)除法后，總可以得到故經(jīng)有限次代余數(shù)除法后，總可以得到一個余數(shù)是零，即上式中一個余數(shù)是零，即上式中rn+1 = 0。定理定理3 3：任給整數(shù)任給整數(shù) a b 0 ，則（，則（a, b）就是（）就是（1）中最后一個不等于）中最后一個不等于零的余數(shù)，即（零的余數(shù)，即（a, b）= rn （舉例）（舉例）定理定理4 4：任給整數(shù)任給整數(shù) a b 0 ，則存在兩個整數(shù)，則存在兩個整數(shù) m, n 使得使得

6、 （a, b）= m a + n b 由上式，顯然有推論：由上式，顯然有推論：a 和和 b 的公因數(shù)是的公因數(shù)是(a, b)的因數(shù)的因數(shù)。轉(zhuǎn)一次不定方程5/72 288 = 1581 + 130， 158 = 130 1 + 28， 130 = 28 4 + 18， 28 = 18 1 + 10， 18 = 10 1 + 8， 10 = 8 1 + 2， 8 = 2 4 + 0 因此，最大公因數(shù)因此，最大公因數(shù) (a, b) = 2 再進行逆向迭代，再進行逆向迭代，2 = 108 1 (代代2) = 10(1810) 1 (代代8) = 102 18 = (2818 1)2 18 (代代10)

7、 = 282183 = 282(13028 4 )3 (代代18) = 28141303 = (158130 1 )14 1303 (代代28) = 1581413017 = 15814(2881581 )17 (代代130) = 1583128817 = 17 288 + 31158所以所以 m = 17, n=31例：用輾轉(zhuǎn)相除法求，例：用輾轉(zhuǎn)相除法求，a=288，b=158的最大公因數(shù)和的最大公因數(shù)和m, n，使，使ma + nb=(a, b)四川大學電子信息學院6/72最小公倍數(shù)：最小公倍數(shù)：)(:00bababababa，的最小公倍數(shù)，有：， 素數(shù)素數(shù)(質(zhì)數(shù)質(zhì)數(shù))的概念的概念： 大于

8、大于1的整數(shù)的整數(shù) 被稱為被稱為素數(shù)素數(shù)是指是指 p 的因子僅有的因子僅有1, 1, p, p。定義：若（定義：若（a，b）=1，則，則a與與b互素?；ニ?。引理引理1 1：若若p是素數(shù)，是素數(shù)，a是任意整數(shù)，則有是任意整數(shù)，則有 p | a 或或 (p, a) = 1 即素數(shù)與一個數(shù)要么互素，要么可整除該數(shù)。即素數(shù)與一個數(shù)要么互素，要么可整除該數(shù)。引理引理2 2：若若p是素數(shù)，是素數(shù)， p | ab ，則，則 p | a 或或 p | b 四川大學電子信息學院7/72定理定理5 5：任一整數(shù)任一整數(shù) a ( a 1)都能唯一地分解為以下形式：都能唯一地分解為以下形式：5325322212021

9、03212121如：是素數(shù)，其中，)k,.,i (p.ppp.ppaikkk （整數(shù)的惟一分解性定理）（整數(shù)的惟一分解性定理）推論推論1 1：若若d | a，則，則d一定有形一定有形式：式：kkxkxxxxpppdk0.0;.112121這里如整數(shù)如整數(shù)120120的所有因子可表示為：的所有因子可表示為：16)120(16224120D記為：所有可能的因數(shù)個數(shù)為) 1).(1)(1()(,21kaDaZa的因數(shù)個數(shù)：則推廣到一般：轉(zhuǎn)一次不定方程轉(zhuǎn)一次不定方程101030532321321xxxxxx；，且四川大學電子信息學院8/72 有有 5050個隊員，分別編號為個隊員，分別編號為1 1、2

10、 2、5050；另有；另有5050盞電燈盞電燈（為拉線式開關），分別編號為（為拉線式開關），分別編號為(1)(1)、(2)(2)、(50)(50)。規(guī)則：規(guī)則：若某燈的編號正好是某隊員編號的倍數(shù)，則該隊員就若某燈的編號正好是某隊員編號的倍數(shù)，則該隊員就拉該燈一次。拉該燈一次。 如如1 1號隊員將對號隊員將對5050個燈都拉一次；個燈都拉一次； 3 3號隊員將拉號隊員將拉(3)(3)、(6)(6)、(9)(9)、(45)(45)、(48)(48)號燈各一次；號燈各一次； 50 50號隊員將只拉號隊員將只拉(50)(50)號燈一次；號燈一次； 問題：問題：最后有哪幾盞燈是亮的最后有哪幾盞燈是亮的?

11、 ?（設初始為全熄）。（設初始為全熄）。結(jié)果：共結(jié)果：共7 7盞燈是亮的。即：盞燈是亮的。即： (1)(1)，(4)(4)，(9)(9)，(16)(16)，(25)(25)，(36)(36)，(49)(49)一個趣味問題一個趣味問題推論推論2 2：a是一個完全平方數(shù)是一個完全平方數(shù) D(D(a) )是奇數(shù)。是奇數(shù)?！袄瓱衾瓱簟眴栴}：問題：定理定理5 5四川大學電子信息學院9/722.2.一次不定方程一次不定方程二元一次不定方程是指：二元一次不定方程是指： a1x + a2 y = n （1）其中其中a1，a2，n是給定的整數(shù)，是給定的整數(shù)， a1，a2 0定理定理6 6：方程方程 (1) 有解

12、的充分必要條件是：有解的充分必要條件是： ( a1，a2 ) | n由前面定理由前面定理4，當，當 (a1，a2 ) =1，存在整數(shù)，存在整數(shù)s，t 使：使： s a1 + t a2= (a1，a2 ) =1兩邊乘以兩邊乘以n， s na1 + tn a2= n與與(1)式比較，有解：式比較，有解： x0 = s n ， y0 = t n ，充分條件得證。，充分條件得證。此為方程此為方程(1)的一組特解，而全部解可由下面定理給出：的一組特解，而全部解可由下面定理給出：定理定理7 7：(a1，a2 ) =1，則方程，則方程 (1) 一定有解，且全部解（通解）為：一定有解，且全部解（通解）為：1)

13、b ,a(b)b ,a(aZb ,a，有可利用性質(zhì)：不失一般性對轉(zhuǎn)同余方程（組）轉(zhuǎn)同余方程（組）x = x0 + a2 k y = y0 a1 k其中，其中，k Z， x0, y0是是方程方程 (1) 的一組特解。（證明略）的一組特解。（證明略）證明：證明： 式式 (1) 有解有解 (a1，a2 ) | n顯然成立，必要條件得證。顯然成立，必要條件得證。當當(a1，a2 ) | n，不失一般性不失一般性，可假設，可假設 (a1，a2 ) =1, a1 0，a2 0 四川大學電子信息學院10/72 得得 s = 2，t = 3 所以所求特解為：所以所求特解為： x0 =224=48， y0 =

14、324 = 72 所以，方程的完全解為：所以，方程的完全解為： x = x0 +a2k = 48 +7k y = y0a1k = 7210k 其中其中 k Z 【例例】 解方程解方程 10 x + 7y = 24解：此例，解：此例， a1=10， a2=7， n=24， 因為因為(10, 7) = 1 所以方程有解。所以方程有解。由輾轉(zhuǎn)相除法計算滿足下式的由輾轉(zhuǎn)相除法計算滿足下式的s和和t： 10s + 7t = 1 ，有，有10 =71+3 7 =32+1 1= 732 = 7(1071) 2 = 10(2) + 73四川大學電子信息學院11/723.3.模運算與同余式模運算與同余式定義：設

15、定義：設 n 是一正整數(shù)，是一正整數(shù)，a是整數(shù)，如果用是整數(shù)，如果用n除除a，得商為，得商為q，余數(shù)為，余數(shù)為r， 則則 a = qn + r ，0 r n， q = a/n 其中，其中， x 為小于或等于為小于或等于x的最大整數(shù)。的最大整數(shù)。 用用a mod n 表示余數(shù)表示余數(shù) r，則，則 a = a/n n + a mod n 如果如果 (a mod n ) = (b mod n ) ，則稱兩整數(shù)，則稱兩整數(shù) a 和和 b 模模n 同同余，記為：余，記為： a b mod n 稱與稱與 a 模模 n 同余的數(shù)的全體為同余的數(shù)的全體為 a 的的同余類同余類，記為，記為a，并稱并稱 a 為該

16、同余類的表示元素。為該同余類的表示元素。（顯然，同余類中的每一元素都可作為這個同余類的表示元素）（顯然，同余類中的每一元素都可作為這個同余類的表示元素） 如果如果 a 0 mod n ，n|a四川大學電子信息學院12/723.3.模運算與同余式（續(xù)）模運算與同余式（續(xù)） (2) 同余的性質(zhì)：同余的性質(zhì)：如果如果(a mod n ) = (b mod n ) ，則，則a b mod n； (定義定義)自反性：自反性： a a mod n； 對稱性：對稱性： 如果如果a b mod n，則則b a mod n； 傳遞性：傳遞性： 如果如果則則a b mod n，b c mod n，則則a c mo

17、d n； 四川大學電子信息學院13/72如果如果 n|(ab)，則則a b mod n ；證明：證明：必要性：必要性：設設 a b mod n，則有，則有 a= k1n + r，b= k2n + r，0rn故故 a b = n ( k1k2 ) 顯然有顯然有， n|(a-b) 充分性：充分性：設設 a= k1n + r1， b= k2n + r2， 0r1n，0r2n 有有 a b = n(k1k2)+ r1r2， 如果有如果有，n|(a b)，必有必有 n|(r1r2) ，而而 |r1r2| n 所以所以 r1 = r2， 即即 a b mod n a, b對模對模n同余的充要條件：同余的充

18、要條件：返回模運算性質(zhì)返回模運算性質(zhì)四川大學電子信息學院14/72(3) 模運算及性質(zhì)：模運算及性質(zhì)：模運算性質(zhì)模運算性質(zhì)：模n下的算術(shù)運算性質(zhì) 下面設 a, b, c, d 都是整數(shù)，而 n 為正整數(shù)，有模運算性質(zhì)： (ab)mod n = (a mod n)(b mod n ) mod n 證明： 設 a mod n = ra ， b mod n = rb ，有： a =jn + ra ， b = kn + rb ，j，k分別為兩個整數(shù)。有： (ab)mod n =(jn + ra kn rb ) mod n = (rarb + jnkn) mod n = (rarb) mod n = (

19、a mod n)(b mod n ) mod n (ab)mod n = (a mod n)(b mod n ) mod n 概念：概念：求余數(shù)運算求余數(shù)運算 a mod n 將整數(shù)將整數(shù) a 映射到映射到非負整數(shù)集合非負整數(shù)集合Zn= 0, 1, , n-1，稱為求余運算，在這個集合上的運算稱為模運算。，稱為求余運算，在這個集合上的運算稱為模運算。四川大學電子信息學院15/72交換律交換律: (a * b) mod n = (b * a) mod n ; “ * ”可為可為 +、結(jié)合律結(jié)合律: a * ( b * c) mod n = ( a * b ) * c mod n ; “ * ”可

20、為可為 +、分配律分配律: a ( b + c) mod n = a b + a c) mod n 恒等恒等: ( 0 + a ) mod n = ( 1a ) mod n = a mod n 加法逆元加法逆元: 對每一個對每一個w Zn ，存在一個存在一個u，使得，使得 w + u0 mod n 記為，記為，u = w，顯然，顯然: 在模在模n下，下， w n w滿足交換律、結(jié)合律、分配律、恒等、加法逆元。滿足交換律、結(jié)合律、分配律、恒等、加法逆元。（證明略）模運算性質(zhì)模運算性質(zhì)(續(xù)續(xù))四川大學電子信息學院16/72如果如果 a b mod n c d mod n 則有則有 (1) (ac)

21、 (bd) mod n ；特例：特例： ac bc mod n 更一般式：更一般式： (ax cy) (bx dy) mod n x, y Z (2) ac bd mod n ；特例：特例： ac bc mod n (3) f (a) f (b) mod n 其中其中f (x)為任給定的一個整系數(shù)多項式為任給定的一個整系數(shù)多項式證證(1)：因為：因為n|(ab)， n|(cd)，故，故 n| x(ab)y (cd ) 即，即，n| (axc y) ( bxdy ) 即即(ax cy) (bx dy) mod n 證證(2)：由：由 n| c(ab) b (cd ) 即即n| ac b d )

22、所以所以 ac bd mod n 模運算性質(zhì)模運算性質(zhì)(續(xù)續(xù))四川大學電子信息學院17/72解：解： 實際上是要證明：實際上是要證明： 5601(mod56), 223 1(mod47) (1) 有：有：560 = ( 56 )10 = (53 )2 )10 ( ( (53) mod56 )2 ) mod56)10 (mod56) 而而 5 3=12513(mod56) 于是于是 (5 3 )21691(mod56) (5 3 ) 2 ) 10 1 (mod56) ， 于是有：于是有： 56 5601。 (2) 有：有： 223 = (26)3 25 26 = 64 17 mod(47) (2

23、6)3 17 3 25mod(47) (26)325 25 32 1 mod(47) 于是有：于是有： 47 223 1 轉(zhuǎn)同余充要條件【例例1】 通過同余式演算證明通過同余式演算證明: 5601是是56的倍數(shù)，的倍數(shù)，2231是是47的倍數(shù)。的倍數(shù)。四川大學電子信息學院18/72【例例2】證明：正整數(shù)證明：正整數(shù) N 被被 9 整除的充要條件是整除的充要條件是 N 的各位數(shù)字的各位數(shù)字(10進制進制)的和被的和被9整除。整除。證明：證明： 實際上是要證明實際上是要證明正整數(shù)正整數(shù) N 與與N 的各位數(shù)字的和的各位數(shù)字的和在模在模9下同余。下同余。 設設 N = a0 +10a1 + 10 2

24、 a2 + 10 k ak ，將，將N看成是看成是10的整的整系數(shù)多項式系數(shù)多項式, f () a0 +a1 +2 a2 +k ak N記為：記為： N = f (10) ，顯然有：，顯然有： f (1) = a0 +a1 + a2 + ak 有有 10 1mod 9 由模運算性質(zhì)，有由模運算性質(zhì)，有 f (10) f (1) mod 9 即：即： N a0 +a1 + a2 + ak mod 9四川大學電子信息學院19/72證明證明: dncbcbdndndadnacbdadncbanmod: )( |1),(),()(|)(|)( 同同余余充充要要條條件件有有，再再由由從從而而，有有又又由

25、由，故故，有有充充要要條條件件由由同同余余性性質(zhì)質(zhì)如果如果 (ab) (ac) mod n，且且 (a, n) = d，則，則dncbmod（乘法的消去律）（乘法的消去律）如果如果 (ab) (ac) mod n，則則b c mod n； (加法的可約律加法的可約律) 例如：例如：(5 23) (5 7) mod 8， 23 7md 8 定理定理8：加法的加法的可約律與乘法的消去律可約律與乘法的消去律四川大學電子信息學院20/72推論推論1：如果如果 (ab) (ac) mod n，且且 (a, n) = 1， 則則b c mod n。（消去律）推論推論2： 如果如果 (a, n) =1，則，

26、則 a Zn = Zn 。 這里這里， aZn 表示表示 a 與中每一元素做模與中每一元素做模 n 乘法乘法。定義：定義：模模n下的乘法逆元下的乘法逆元：如果，(a, n) = 1，則 a 在 mod n下有存在一個 x ( x a0 ， ，則，則存在兩個整數(shù)存在兩個整數(shù) x, y 使得使得 xa + yn = (a, n)當當(a, n) = 1時，即有時，即有 xa + yn = 1等式兩端取模等式兩端取模n，有，有 xa mod n=1 即存在一個即存在一個 x ，使得，使得 a x 1 mod n。如何求如何求 x ? 用輾轉(zhuǎn)相除法求乘法逆元用輾轉(zhuǎn)相除法求乘法逆元，即擴展的，即擴展的E

27、uclid算法算法【 例例 】計算550 1mod1769有有 x = 550, y = 171 所以所以 550 1mod 1769 = 550 1769 = 5503 + 119， 1 = 133 4 (代代3) 550 = 1194 + 74， =13(16131)4 =135164 (代代13) 119 = 74 1 + 45， = (29161 )5164 = 295 169 (代代16) 74 = 451 + 29， = 295 (45291 )9 =2914 459 (代代29) 45 = 291 + 16， = (74451 )14459 =74144523 (代代45) 29

28、 = 161 + 13， =7414(119741)23 = 7437 11923 (代代74) 16 = 131 + 3 = (5501194 )37 11923=55037 119171(代代119) 13 = 3 4 + 1 =55037(1769 5503 )171= 550550 1769171正向迭代過程正向迭代過程逆向迭代過程逆向迭代過程四川大學電子信息學院22/724.4.剩余類與完全剩余類剩余類與完全剩余類全體整數(shù)：全體整數(shù)：Z=0, 1 , 2 , 3 ，前面已定義：，前面已定義：a Z，稱與稱與 a 模模 n 同余的數(shù)的同余的數(shù)的全體全體為為 a 的同余類，顯然的同余類，

29、顯然全體全體整數(shù)模整數(shù)模 n 的同余類共有的同余類共有 n 個，他們分別為個，他們分別為n k+0， n k+1， n k+2， n k+(n -1)，( kz) ，共，共 n 類；類；若取若取n=4，整數(shù)分為，整數(shù)分為 4 類：類： C0 = 4k | kZ C1 = 4k +1 | kZ C2 = 4k +2 | kZ C3 = 4k +3 | kZ 所以，當所以，當n 1時，整數(shù)分為時，整數(shù)分為 n 類：類： C0 ， C1 ，Cn-1 Cj = nk +j | kZ ；j = 0,1,2,n1稱稱Cj為模為模n的一個的一個剩余類剩余類（即（即“一類余數(shù)一類余數(shù)”）。）。四川大學電子信息

30、學院23/724.4.剩余類與完全剩余類（續(xù)）剩余類與完全剩余類（續(xù)） 若從所有剩余類若從所有剩余類C0 ， C1 ，Cn-1類中各取一個數(shù)類中各取一個數(shù)構(gòu)成集合，該集合則稱為模構(gòu)成集合，該集合則稱為模n的一組的一組完全剩余系。完全剩余系。 顯然，這樣的集合有無數(shù)個，而最簡單的完全剩余系為：顯然，這樣的集合有無數(shù)個，而最簡單的完全剩余系為： 0, 1, 2, , n1稱為稱為非負最小完全剩余或標準完全剩余系。非負最小完全剩余或標準完全剩余系。 如，如，Z模模12的標準剩余系為：的標準剩余系為：0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11定理定理9 9：設設a1，a2

31、 ，an是是 模模n的一組完全剩余系。的一組完全剩余系。 有整數(shù)有整數(shù)k，且，且 ( k, n ) = 1 ， 則則 k a1， k a2， ，k an也是一組完全剩余系。也是一組完全剩余系。 24/725.5.費馬費馬(Fermat)(Fermat)小定理與歐拉小定理與歐拉(Euler)(Euler)定理定理 (這兩個定理在公鑰密碼體制中起著重要作用)定義：如果一個模定義：如果一個模n的剩余類里面的數(shù)都與的剩余類里面的數(shù)都與n互素，就把該?；ニ?，就把該剩余類稱為余類稱為與模數(shù)與模數(shù)n互素的剩余類互素的剩余類。 如如n=4， C3 = 4k +3 | kZ ， C3為與模數(shù)為與模數(shù)4互素的剩余

32、類互素的剩余類 在在與模數(shù)與模數(shù)n互素的的互素的的全部全部剩余類中，各取一數(shù)所組成的集剩余類中，各取一數(shù)所組成的集合叫模合叫模n的一組的一組縮系縮系。如。如1，3為模為模4的一組的一組縮系?？s系。定義：定義：歐拉函數(shù)歐拉函數(shù) (n)是一個定義在正整數(shù)正整數(shù)集上的函數(shù)， (n)的值等于小于的值等于小于n且與且與 n互素的正整數(shù)的個數(shù)。互素的正整數(shù)的個數(shù)。歐拉函數(shù)：歐拉函數(shù)：例如：例如： (4) = (6) =2，(7) = 6， (8) = 4，25/72歐拉函數(shù)歐拉函數(shù)(續(xù)續(xù))定理：定理：設整數(shù)設整數(shù)n (1)的唯一性分解形式為：的唯一性分解形式為：),.,2 , 1(0.2112121kip

33、ppppppnikkiikik是素數(shù)，其中，kiiippni11) 1()(則例如，例如，n = 120736 = 25 7311 (n) = 24 72610 = 47040 26/72特別，特別，當當 p 是一個素數(shù)，有是一個素數(shù)，有 ( p) = p1 當當 n 是兩個素數(shù)是兩個素數(shù) p 和和 q的乘積，則對的乘積，則對n = p q，有，有 (n) = (p q) = (p) (q) = (p1)(q1) 證明：證明： 考慮?？紤]模 n 的標準完全剩余系為的標準完全剩余系為0，1，( pq1)，而不與而不與n 互素的元素包括：互素的元素包括：p因子集合因子集合p，2p，(q1)p，q因

34、子集合因子集合q，2q，(p1)q和和0。 因此，有：因此，有： (n) = pq(q1)+ (p1) +1 = pq(p+ q) +1 (p1) (q1) = (p) (q) 例如：例如： (21) (37) = (3) (7) (31) (71)2 6=12歐拉函數(shù)歐拉函數(shù)(續(xù)續(xù))四川大學電子信息學院27/72證明：當證明：當 x 過模過模 n 的一組縮系，則的一組縮系，則 ax 通過通過 (n) 個整數(shù)，個整數(shù)，由于由于（a，n）=1， （ xi， n ）=1 所以所以， （ a xi， n ）=1 i, j =1,2,. (n) 若若 a xi= a xj，可得可得 a xi a xj

35、 mod n 與所設與所設 x 過模過模 n 的一組的一組縮系矛盾，縮系矛盾， 故故 a x也過也過 n 的一組縮系。的一組縮系。定理定理1212：若（若（a，n）=1，x 過模過模 n 的一組縮系的一組縮系 ( 即即 x 取取x1， x (n) ，且，且xi與與 n 互素互素 ), 則則 a x也過也過 n 的一組縮系的一組縮系 。定理定理1111： 若若a1，a (n) 是是 (n) 個與個與n互素的整數(shù)，則互素的整數(shù)，則a1，a (n) 是模是模n的一組縮系的充要條件是它們兩兩對模的一組縮系的充要條件是它們兩兩對模n不同余。不同余。（從定義看，定理（從定義看，定理10，11時顯然的）時顯

36、然的）定理定理1010：模數(shù)模數(shù)n的一組縮系的元素個數(shù)為的一組縮系的元素個數(shù)為 (n) 。四川大學電子信息學院28/72定理定理1313 ：若：若 p 是素數(shù)，且不能整除是素數(shù)，且不能整除a，則有：，則有： a p1 1 mod p 或或 a p a mod p 顯然，顯然， a k (p1) 1 mod p a N = a k (p1) + r a N mod (p1) mod p 費馬小定理應用舉例：費馬小定理應用舉例： 計算計算 7 7560 560 mod 31 = ? mod 31 = ? 7560 = 7560mod (311) = 7(311)18+20 720 mod31 75

37、757575 mod31 5555 5 mod31 費馬小定理費馬小定理29/72證明：設證明：設 r1， r (n) 是模是模 n 的一組縮系，則由定理的一組縮系，則由定理12， ar1， ar (n) 也是模也是模 n 的一組縮系，的一組縮系， 故故 (ar1)(ar1 )(ar (n) r1r (n) mod n 即即 a (n) r1r (n) r1r (n) mod n 由于由于 ( ri, n ) =1 i=1,2,. (n) 故故 ( r1r (n) , n ) =1 由由定理定理8的推論的推論1（消去律）（消去律），有：，有： a (n) 1 mod n 得證得證定理定理141

38、4（EulerEuler定理）定理） ：設 n , a Z，且(a，n)=1， 則 a (n) 1 mod n 如， a = 3，n = 10； (10) = 4，34 = 81 1 mod 10 a = 2，n = 11； (11) = 10，210 = 1024 1 mod 11 30/72 有有 a k (n)+1 a mod n ( kZ )EulerEuler定理的推論定理的推論 : 給定兩個素數(shù)給定兩個素數(shù) p, q，以及整數(shù)，以及整數(shù) n = p q 和和 m， 其中其中0 m 0，則同余式：，則同余式： a x b mod n 恰有一個解。恰有一個解。而而 x = ba (n)

39、 1 就是其唯一解。就是其唯一解。 ( a1 a (n) 1 mod n ) 思路：思路：讓讓 x 過模過模 n 一個完全剩余系，一個完全剩余系，x = b = b1 1,b,b2 2, ,.,b.,bn n1 1， ax= = ab b1 1, , ab b2 2, ,., ., ab bn n1 1， 因為因為(a，n) = 1，所以，所以 ax 也過一個完全剩余系也過一個完全剩余系 故一定有一個故一定有一個 xi，使，使 a xi = b b mod n 故有解故有解( (其解可其解可代入證明代入證明) ) 定理定理1616： 設設 n 0，則同余式：，則同余式： a x b mod n

40、 有解的充要條件是：有解的充要條件是： (a, n)|b 且恰有且恰有(a, n)個解。個解。 6.6.同余方程（組）與中國剩余定理同余方程（組）與中國剩余定理四川大學電子信息學院32/72 例例: (1) 求求 2 x 179 mod 562 的整數(shù)解。的整數(shù)解。(2) 求求 256 x 179 mod 337 的整數(shù)解。的整數(shù)解。因為因為(256, 337) = 1, 所以所以同余式同余式有一個整數(shù)解。有一個整數(shù)解。 解法解法1： ( 256, 337 ) = 1 256在模在模337有逆元存在。有逆元存在。 2561 mod 337 = 104 用用104 乘以同余方程兩邊，有乘以同余方

41、程兩邊，有 104256 x 104179 mod 337 即即 x 104179 81 mod 337 解法解法2： 考慮二元一次不定方程：考慮二元一次不定方程：256 x+337 y=179 .(1) 由不定方程有解的充要條件，由不定方程有解的充要條件， 當當(256, 337) = 1 ,則一次不定方程則一次不定方程(1) 一定有解一定有解 。 利用擴展的利用擴展的Euclid算法，不定方程算法，不定方程(1)的一組特解為：的一組特解為： x0 = 104179 y0 = 79179顯然，對式顯然，對式(1)等式兩端取等式兩端取 mod337，即為同余式，即為同余式256 x 179 m

42、od 337所以得同余式解：所以得同余式解： x = 104179 81 mod 337 因為因為(2, 562)=2, 而而2 | 179, 故同余式?jīng)]有整數(shù)解。故同余式?jīng)]有整數(shù)解。 四川大學電子信息學院33/72例子：（孫子算經(jīng)）今有物不知其數(shù)；三三數(shù)之余二；五五數(shù)之余三；例子：（孫子算經(jīng)）今有物不知其數(shù)；三三數(shù)之余二；五五數(shù)之余三； 七七數(shù)之余二。問物幾何？七七數(shù)之余二。問物幾何？ 設設 x 為所求未知數(shù)。原問題為求解同余方程組：為所求未知數(shù)。原問題為求解同余方程組：7mod25mod33mod2xxx 對此方程組的一般解法，在明朝程大位的對此方程組的一般解法，在明朝程大位的“算法統(tǒng)算法

43、統(tǒng)宗宗”(1593)里有一首歌謠給出了答案：里有一首歌謠給出了答案： 三三人同行人同行七十七十稀，稀，五五樹梅花樹梅花廿一廿一枝，枝， 七七子團圓子團圓月正半月正半，除，除百零五百零五便得知。便得知。 其解為：其解為： x 702 + 213 +152 mod 105 = 23一般應如何求解同余方程組？一般應如何求解同余方程組？中國剩余定理中國剩余定理四川大學電子信息學院34/727mod25mod33mod2xxx(1) 3，5 = 15， 15mod 7 = 1 152 mod 7 = 2(2) 3，7 = 21， 21mod 5 = 1 213 mod 5 = 3 5，7 = 35， 3

44、5mod 3 = 2 351 mod 3 = 2顯然，顯然， 152 + 213 + 351 = 128 是一個解（但還不是最小解）是一個解（但還不是最小解）有：有：128k 3, 5,7 = 233 +k 105 ； kZ 所以最小正整數(shù)解為：所以最小正整數(shù)解為：x = 23普通解法：普通解法：四川大學電子信息學院35/72 設設m1, m2, mk是是 k 個兩兩互素的正整數(shù)，個兩兩互素的正整數(shù)， 并記并記 M = m1 m2 mk，Mi= M/mi， 則同余方程組：則同余方程組：在模在模 M 同余的意義下同余的意義下有唯一解有唯一解： x M1 M1 b1 M2 M2 b2 Mk Mk

45、bk mod M （2） 其中其中 Mi Mi 1 mod mi定理定理17（中國剩余定理，（中國剩余定理，CRT-China Residue Theorem ）：）：第 2 周)(mod.)(mod)(mod2211kkmbxmbxmbx（1）四川大學電子信息學院36/72定理定理17（中國剩余定理證明（中國剩余定理證明 ）：）：證明：由于證明：由于( mi , mj) =1，i j，所以，所以 (Mi , mi) = 1 注意到注意到 M = Mi mi 所以當所以當 i j， mi | Mj，即，即 Mj 0 mod mi，故故 M1 M1 b1 M2 M2 b2 Mk Mk bk （應

46、用模運算性質(zhì)）（應用模運算性質(zhì)） Mi Mi bi bi mod mi 故故(2)為為(1)的解的解 ( 注意：注意： Mi Mi 1 mod mi )另外，設整數(shù)另外，設整數(shù)y 也能同時滿足式也能同時滿足式(1)，由于，由于(2)式是滿足式是滿足(1)的正整數(shù)解，的正整數(shù)解，即即 y x mod m1，y x mod m2，y x mod mk， 也即，也即， m1 | ( x y )， m2 | ( x y )， ， mk | ( x y )由于由于m1, m2, mks兩兩互素，所以兩兩互素，所以 (m1 m2mk )| ( x y ) 所以所以 x y mod M 即在模即在模 M 同

47、余的意義下同余的意義下(2)是唯一解。是唯一解。第第 2 周周四川大學電子信息學院37/72 【舉例舉例】 11數(shù)剩數(shù)剩3，12數(shù)剩數(shù)剩2，13數(shù)剩數(shù)剩1，求本數(shù)。，求本數(shù)。解：依題意有，解：依題意有，3mod112mod121mod13xxx即即 m1 =11，m2 =12，m3 =13，b1 =3， b2 =2， b3 =1， 此時有：此時有： M =1112 13 =1716， M1 = 1716 /11=156，M2 = 1716 /12=143，M3 = 1716 /13=132而而M1 為一正整數(shù)，它滿足：為一正整數(shù)，它滿足：M1 M1 1 mod 11，即即1 M1 M1 156

48、 M1 mod 11 2 M1 mod 11 ，易得，易得 M1 = 6(可用擴展可用擴展Euclid算法求得：算法求得：M1 = M11 mod m1 = 1561 mod 11 = 21 mod 11 ) 同理，可求出：同理，可求出：M2 = 11， M3 = 7由由CRT，得解：，得解：x b1 M1 M1 b2 M2 M2 b3 M3 M3 3 156 6 + 2 143 11 + 1 132 7 14mod 1716所以，完全解為：所以，完全解為： x =14 + 1716 k kZ 四川大學電子信息學院38/72中國剩余定理的主要應用：中國剩余定理的主要應用：1、求解同余方程組、求

49、解同余方程組（模（模M下的唯一解）下的唯一解）；2、在模、在模M下可將一個非常大的數(shù)下可將一個非常大的數(shù)N，用一組較小的數(shù)組成的，用一組較小的數(shù)組成的 k 元組元組 (b1，b2，bk)來表達。來表達。 且在模且在模M下，下， N與與(b1，b2，bk) 唯一對應。唯一對應。3、ZM上元素的運算等價于上元素的運算等價于k 元組元組 對應元素之間的運算，即如果：對應元素之間的運算，即如果： A (a1，a2，ak)， B (b1，b2，bk) 則則 (A + B)mod M (a1 + b1) mod m1， (ak + bk) mod mk (AB)mod M (a1 b1) mod m1，

50、(akbk) mod mk (AB)mod M (a1b1) mod m1， (akbk) mod mk 四川大學電子信息學院39/72中國剩余定理的主要應用（續(xù)）中國剩余定理的主要應用（續(xù)） 例例: 將將973 mod 1813用模數(shù)為用模數(shù)為37和和49的兩個數(shù)表示（的兩個數(shù)表示（1813 = 3749 ）。）。 解：可取解：可取 N=973，M=1813， m1 =37，m2 =49， 有：有： b1 = N mod m1 = 973 mod 37=11 b2 = N mod m2 = 973 mod 49=42 所以所以 973 (11，42)若要計算若要計算 973mod1813 +

51、 678mod1813，則可先求出：，則可先求出： 678 (678 mod 37 , 678 mod 49)即即 678 (12 , 41)，應用上面性質(zhì)可得加法表達為：，應用上面性質(zhì)可得加法表達為： (11 + 12) mod 37, (42 +41) mod 49 = (23，34)四川大學電子信息學院40/727.7.離散對數(shù)離散對數(shù) 1 1）求模下的整數(shù)冪）求模下的整數(shù)冪 由由EulerEuler定理，如果定理，如果 ( (a, n)=1, n)=1，則，則 a (n) 1 mod n 現(xiàn)考慮一般形式，現(xiàn)考慮一般形式， a m 1 mod n ； m為一正整數(shù)為一正整數(shù) (1)如果如

52、果 ( (a,n)=1,n)=1，則至少有一整數(shù)，則至少有一整數(shù)m ( m = = (n) )滿足該方程。滿足該方程。定義：定義：滿足式滿足式(1)(1)的的最小正整數(shù)最小正整數(shù) m 為模為模n 下下a 的階的階( (又稱次數(shù)又稱次數(shù)) )。 例：例： a =7=7，n=19n=19，則易求出，則易求出 7 1 7 mod 19 ， 7 2 11 mod 19，7 3 1 mod 19， 即即7在模在模19下的階為下的階為3。四川大學電子信息學院41/727.7.離散對數(shù)離散對數(shù) 1 1）求模下的整數(shù)冪）求模下的整數(shù)冪( (續(xù)續(xù)) ) 由于由于7 3kj 7 3k7 j 7 j mod 19

53、所以，所以， 7 4 7 mod 19 ， 7 5 7 2 mod 19，即從，即從7 4 mod 19 開始，所求的冪出現(xiàn)循環(huán)，循環(huán)周期為開始，所求的冪出現(xiàn)循環(huán)，循環(huán)周期為3，即等于元素，即等于元素 7在模在模19下的階。下的階。 性質(zhì)性質(zhì)1 1：a的階的階m 整除整除 (n) ，即，即 m| (n) （注意：（注意： ( (a,n)=1,n)=1 ） 證：若證：若m不能整除不能整除 (n) ，可令，可令 (n) = k m+r，其中其中 0 r m1，那么由那么由EulerEuler定理：定理： a (n) =a k m+ r =(a m ) k a r mod n a r mod n 1

54、 mod n 即即 a r 1 mod n 與與m是模是模n下下a 的階矛盾。的階矛盾。 實際上，任意滿足式實際上，任意滿足式(1)的整數(shù)的整數(shù)m一定是一定是a的的階的倍數(shù)。階的倍數(shù)。 四川大學電子信息學院42/72定義：如果定義：如果 a 的階等于的階等于 (n) ，則稱，則稱a為為n的本原元（又稱為素根）。的本原元（又稱為素根）。特別地，如果特別地，如果a是是素數(shù)素數(shù) p p 的本原元，則的本原元，則 a, ,a2 2, , ,ap p1 1 (p-1) (p-1)個數(shù)在模個數(shù)在模 p p 下互不相同，且均與下互不相同，且均與 p p 互素?；ニ亍Ｐ再|(zhì)性質(zhì)2 2：如果：如果a是是n n的本

55、原元，則的本原元，則 a, ,a2 2, , ,a ( (n) )在模在模n下互不相同，且均與下互不相同，且均與n互素?；ニ亍ＷC明：證明： 因為因為a, ,n互素，互素，ak k與與n互素顯然?；ニ仫@然。 設設 ai a j mod mod n ；0 0 i 0 )，則稱該算，則稱該算法是多項式階的；法是多項式階的；l 若對某個常數(shù)若對某個常數(shù)a ( a1) 和多項式和多項式h(n)，算法的運行時間，算法的運行時間 T = O( ah(n) ), 則稱該算法是指數(shù)階的。則稱該算法是指數(shù)階的。 空間復雜性與時間復雜性空間復雜性與時間復雜性四川大學電子信息學院74/72 假設一臺計算機在假設一臺計

56、算機在1秒鐘內(nèi)可以執(zhí)行秒鐘內(nèi)可以執(zhí)行100萬條指令，輸入規(guī)模萬條指令，輸入規(guī)模n=106 。下表列出該臺計算機上執(zhí)行不同時間復雜度算法所需的運行時間。下表列出該臺計算機上執(zhí)行不同時間復雜度算法所需的運行時間。 空間復雜性與時間復雜性空間復雜性與時間復雜性( (續(xù)續(xù)) ) 當當T = O( n3 )，在串行機上執(zhí)行算法在計算上變得不可行了，但在串行機上執(zhí)行算法在計算上變得不可行了，但當采用當采用100萬個處理器的機器就可在大約萬個處理器的機器就可在大約10天內(nèi)完成計算。天內(nèi)完成計算。 但對于但對于T = O( 2n )，即使我們采用上萬億個處理器并行工作，要，即使我們采用上萬億個處理器并行工作，要執(zhí)行這類算法在計算上也是不可行的。執(zhí)行這類算法在計算上也是不可行的。 因此，如果破譯一個密碼體制所需的時間是因此，如果破譯一個密碼體制所需的時間是指數(shù)階指數(shù)階的，則它是的，則它是計算上安全的。計算上安全的。算法類型算法類型復雜度復雜度n106時的時的運算次數(shù)運算次數(shù)時間需求時間需求常數(shù)線性二次方三次方指數(shù)O(1)O(n)O(n2)O(n3)O(2n)110610121018103010301微秒1秒10天27397年3 10301016年四川大學電子信息學院75/72 許多密碼可以采用窮盡搜索整個密鑰空間來破譯，即嘗試每許多密碼可以采用窮盡搜索整個密鑰空間來破譯，即嘗試每個可能的密鑰斷定