1、第二章第二章 密碼數學基礎（密碼數學基礎（1） 1 整數運算整數運算 一、整數集一、整數集 Z = 0, 1, 2, 3, . 為整數集。為整數集。 Z+ = 0, 1, 2, 3, . 為正整數集。為正整數集。 N = 1, 2, 3, . 為自然數集。為自然數集。 在在N、Z+上能進行普通加法和乘法運算，上能進行普通加法和乘法運算， 不能做普通減法和除法運算；不能做普通減法和除法運算； 在在Z上能進行加法、減法、乘法運算，上能進行加法、減法、乘法運算， 不能做普通除法運算；不能做普通除法運算；運算運算不能封閉！不能封閉！二、整數除法二、整數除法 帶余除法帶余除法 a = qn + r 25

2、5=23*11+2 25511 = 23 2 規定：除數規定：除數 n 為正數，余數為正數，余數 r 非負。非負。 an = q r -255= (-23*11) +(-2) = (-24*11) +9 商數商數 -1,余數余數+11 -897= -12-5 = -132 a = qn + r 被除數被除數 ：a為整數為整數 商數商數 ：q為整數為整數 余數余數 ：r為非負整數為非負整數 除數除數 ：n為正整數為正整數 我們在整數集我們在整數集 Z 上的除法運算上的除法運算:三、整除性三、整除性 (divisibility) 當余數當余數 r = 0 時，時， a = qn， 稱為稱為“n整除

3、整除 a”，或，或 “ a被被n整除整除”， 記為：記為： n | a 可以說可以說 :“n是是a的一個因子的一個因子”,“a含有因子含有因子 n” Z上的整除有如下基本性質：上的整除有如下基本性質： （1）若）若 a |1，則，則 a = 1 （2）若）若 a|b，且，且 b|a，則，則 a =b （3）若）若 a|b，且，且 b|c，則，則 a|c （4）若）若 a|b，且，且 a|c，則，則 a|(mb+nc) m，n 為任意整數為任意整數 divisor: 因子，因數，約數因子，因數，約數思考：在正思考：在正整數集上的整數集上的性質？性質？三、整性三、整性 例例1： 4 | 32, 1

4、1 | (-33) 5 | 0, -8 | 0 3 | 27, -6 | 24, 6 | -24 例例2： 5 |(-5), -5 | 5 5 |25, 25 | 100 = 5 | 100 7 |35, 7 | 21 = 7 | (m*35+n*21) = 7 | (35+21) = 56 = 7 | (35-21) = 14 = 7 | (2*35-6*21) = -56 四、最大公約數（最大公因子）四、最大公約數（最大公因子） 正整數正整數 a 的因子有：的因子有：1，a本身，其它因子本身，其它因子 1 只能被只能被 1整除整除 素數只能被素數只能被 1或自身整除或自身整除 不是不是1且

5、非素數的正整數稱為且非素數的正整數稱為“合數合數”， 合數除了合數除了 1和自身之外，還有其它因子。和自身之外，還有其它因子。若若 a|b，a|c，則稱，則稱 a 是是 b，c 的公因子；的公因子；若其它公因子都能整除若其它公因子都能整除 a（都是（都是a的因子），的因子）， a 是是所有公因子中最大的一個，稱為所有公因子中最大的一個，稱為“最大公因子最大公因子” greatest common divisor gcd b與與c 的最大公因子記為的最大公因子記為: gcd(b, c) gcd(b, c)是能同時整除是能同時整除b和和c的最大整數。的最大整數。三、最大公約數（最大公因子）三、最大

6、公約數（最大公因子） 例例3 12=1*2*2*3， 12的因子有：的因子有：1，2，3，4 ，6，12 140=1*2*2*5*7， 12的因子有：的因子有： 1，2，4，5，7，10，14，20， 28，35，70，140 12與與140的公因子有：的公因子有： 1，2，4 所以，所以，gcd(12,140) = 4麻煩！麻煩！不是好方法！不是好方法！ 求求 gcd(12,140)五、五、Euclidean算法算法 輾轉相除輾轉相除 定理定理 1 gcd (a, 0) = a 證明：只需規定：任何整數都是證明：只需規定：任何整數都是0的因子。的因子。 定理定理 2 若若 a= qb+r ,

7、 則則 gcd(a, b) = gcd(b, r) 證明：設證明：設d=gcd(a,b), d* =gcd(b,r), 則則 d|a, d|b, 則則 d| (a-qb)，即，即 d|r， d也是也是b,r的公因子，所以的公因子，所以 d|d*。 同理，同理，d*|b,d*|r, 則則 d*|(qb+r), 即即 d*|a d*也是也是a,b的公因子，所以的公因子，所以 d*|d。 因此，因此，d*|b且且d*|d, 可知可知 d*= d。 當當 a和和b都是正整數時，都是正整數時， gcd(a, b) = gcd(b, r) 輾轉相除算法：輾轉相除算法： 例例4 求求 gcd(12,140)

8、 140 =11*12+8 = gcd(140,12)=gcd(12,8) 12 =1*8+4 = gcd(12,8) = gcd(8, 4) 8 =2*4+0 = gcd(8,4) = gcd(4,0) = 4 所以，所以，gcd(140，12) = 4 例例5 求求 gcd(36,10) 36 =3*10+6 = gcd(36,10)=gcd(10,6) 10 =1*6+4 = gcd(10,8) = gcd(6, 4) 6 =1*4+2 = gcd(6,4) = gcd(4,2) 所以，所以，gcd(36，10) = 2 4 =2*2+0 = gcd(4,2) = gcd(2,0)=2

9、例例6 求求 gcd(2740, 1760) q r1 r2 r 27401760198017609801780980780120078020031802001801201802090200 算法分析：算法分析： r1= a; r2 = b r r1; r2 r r1; r2 0 r1; 0 r1 a；r2 b 當當 r2 0 時時 q r1 / r2; r r1-q*r2；r1 r2; r2 r; gcd(a,b) = r1 q q q 例例7 求求 gcd(25, 60) q r1 r2 r 256002560252102510251052050 gcd(25,60) = 5六、擴展六、擴

10、展Euclidean算法算法 定理定理 3 若若 gcd (a, b) = d，必存在整數，必存在整數 s，t 使使 d = s*a+t*b 例例8 將將 gcd(726,393) = 3 表示為表示為 s*726+t*393 qr1r2r172639333313933336053336033160332713327642763263030 3=27- 4*6 3=27- 4*(33-27) = -4*33+5*27 3=-4*33+5*(60-33)=5*60-9*33 3=5*60-9*(333-5*60)=-9*333+50*60 3=-9*333+50*(393-333)=50*393

11、-59*333 3=50*393-59*(726-393) 3 =-59+726+109*393 s= -59, t=109 算法分析：算法分析： 設：設：r = s*a+t*b; r1=s1*a+t1*b; ; r2=s2*a+t2*b 帶入基本關系帶入基本關系 r = r1- q*r2 s*a+t*b=(s1*a+t1*b) q*(s2*a+t2*b) 比較兩端比較兩端 a b 的系數：的系數： s = s1 - q*s2 t = t1 - q*t2 初始值初始值: r = a - q*b = r1= a; r2=b = s1=1; t1= 0 = s2=0; t2= 1 與與r=r1-q

12、*r2計算公式相同計算公式相同!與與r=r1-q*r2初始值不同初始值不同! 算法設計：算法設計： r1= a; r2 = b； r r1; r2； r r1; r2； 0 r1; 0； gcd(a,b)=r1 s1= 1; s2 = 0； s s1; s2； s s1; s2； s s1; s2 s=s1 t1= 0; t2 = 1； t t1; t2； t t1; t2； t t1; t2 t= t1 迭代方法相同；初始值不同迭代方法相同；初始值不同 算法分析：算法分析： r1 a；r2 b s1 1；s2 0 t1 0； t2 1 當當 r2 0 時時 q r1 / r2; r r1-q

13、*r2； r1 r2; r2 r; gcd(a,b) r1; s s1-q*s2； s1 s2; s2 s; t t1-q*t2； t1 t2; t2 t; s s1; t t1; 初始值初始值 循環迭代循環迭代 結果輸出結果輸出 例例9 求求 gcd(161, 28) q r1 r2 r s1 s2 s t1 t2 t 5 161 28 21 1 0 1 0 1 -5 1 28 21 7 0 1 -1 1 -5 6 3 21 7 0 1 -1 4 -5 6 -23 7 0 -1 4 6 -23 gcd(161, 28) = 7 = (-1)* 161+ 6* 28 定理定理 4 若若 gcd

14、 (a, b) = 1 （a與與b互素），互素）， 必存在整數必存在整數 s和和t，使，使 s*a+t*b =1 七、線性丟番圖方程的解法七、線性丟番圖方程的解法 整數一次不定方程整數一次不定方程 : ax + by = c 稱為稱為“丟番圖方程丟番圖方程”。 (1) 求出求出 d = gcd (a, b)若若 d | c , 則方程兩邊除以則方程兩邊除以 d，化為同解方程，化為同解方程 a1 x + b1 y = c1 此時此時 gcd (a1, b1) =1 , a1與與b1 互素，互素，c1是整數是整數(3) 擴展歐氏算法求出擴展歐氏算法求出 s*a1+t*b1 = 1兩端乘兩端乘c1,

15、 得到得到 (c1*s)*a1+(c1*t)*b1= c1, 得到特解：得到特解： x0 = c1* s, y0 = c1* t通解：通解： x = x0 + k*b1 ; y = y0 k*a1(2) 若若 d 不能整除不能整除 c， 則方程無解。則方程無解。 七、線性丟番圖方程的解法七、線性丟番圖方程的解法 結論：結論： ax + by = c 若若 d = gcd(a,b) 不能整除不能整除 c， 則方程無解。則方程無解。 若若 d | c , 則方程有無窮多組解。則方程有無窮多組解。 兩端同除兩端同除d, 化為化為 a1 x+b1y= c1，同解。，同解。 通解為：通解為： x = s

16、*c1 + k*b1 y = t*c1 k*a1 其中其中 s和和 t 滿足滿足 s*a1+t*b1 = 1 驗證：驗證： a1*(s*c1+k*b1)+b1*(t*c1-k*a1) = (a1*s+b1*t )*c1+(a1*b1-a1*b1)*k = 1*c1+ 0*k = c1OK! 例例10 求解整數方程求解整數方程 21x+14y = 35 (1) 計算計算 d = gcd( 21,14) = 7 (2) 兩端除以兩端除以 d， 3x+2y = 5, 為同解方程為同解方程 (3) 擴展歐氏算法求解擴展歐氏算法求解: gcd(3,2) = 1= 3s+2t 得到：得到： s =1, t

17、 = -1, 即即 3*(1)+2*(-1) = 1 (4) 兩端乘兩端乘5：3*(5) +2*(-5) = 5 特解特解 x0 =5, y0 = -5 (5) 通解通解 x = 5 +2*k y = -5 - 3*k 直接用直接用通解公式：通解公式： x = s*c1 + k*b1= 1*5+2k y = t*c1 k*a1 = -1*5-3kqr1r2rs1s2st1t2t132110101-1221001-21-13101-2-13 例例11 用用20元和元和5元的鈔票付元的鈔票付100元賬，元賬， 有多少種方法？有多少種方法？ (2) 計算計算 d = gcd( 20, 5) = 5

18、(3) 兩端除以兩端除以 d， 4x+y = 20 為同解方程為同解方程 (4) 擴展歐氏算法求解擴展歐氏算法求解: 4s + t = 1 得到得到 s =0, t =1, 4*(0)+1*(1) = 1 (5) 兩端乘兩端乘20： 4*(0) +1*(20) = 20 特解特解 x0 =0, y0 = 20 (6) 通解通解 x = k; y = 20 -4k (1) 列方程：列方程：20 x+5y = 100 (7) 據題意據題意, 0 x 5, 0 y 20，知，知 0 k 5 (0, 20) (1, 16) (2, 12) (3, 8) (4, 4) (5, 0)qr1r2rs1s2s

19、t1t2t441010101-410011-4 2 模運算模運算 一、模算符一、模算符 比如比如：（：（1）27 mod 5=2若若 ，記為：，記為： a =qn+r a mod n = r ,（r = 0,1,2，n-1） （2）36 mod 12=0 （3）-18 mod 14 =10（余數為（余數為-4，-4+14=10） （4）-7 mod 10 = 3 （余數為（余數為-7，-7+10=3） 整數集整數集Z 模模n后得到后得到 集合集合 Zn = 0, 1, 2, 3, , n-1 鐘表計時鐘表計時模模12，星期，星期模模7，角度，角度模模360星期九星期九=星期二星期二18點點=

20、6點點420度度 = 60度度 二、同余類二、同余類 0=0, 05, 025, 035, n=5時：余數時：余數 0，1，2，3，4 1=1, 15, 110, 115, 2=2, 25, 210, 215, 3=3, 35, 310, 315, 4=4, 45, 410, 415,同余是同余是Z上的一種等價關系：自反性、對稱性、傳遞性上的一種等價關系：自反性、對稱性、傳遞性 利用該等價關系可以對利用該等價關系可以對Z的元素進行分類的元素進行分類 余數相同的整數屬于同類余數相同的整數屬于同類 同余類同余類 有有5個同余類個同余類 Z5 =0,1,2,3,4 整數集整數集Z 模模n后得到后得到

21、 集合集合 Zn = 0, 1, 2, 3, , n-1 可以在圓上表示同余類：可以在圓上表示同余類：2 modn = k*n+23 modn = k*n+3 三、三、Zn上的運算（模運算）上的運算（模運算）例例1 在在Z15中求中求 7+14： （7+14）mod 15= 6 7- 11： （7- 11）mod 15= 11 7* 11： （7*11）mod 15= 2 在在Z13中求中求 7+14： （7+14）mod 13 = 8 7- 11： （7- 11）mod 13 = 9 7* 11： （7*11）mod 13 = 12 在在Z10中求中求 7+14： （7+14）mod 10

22、= 1 7- 11： （7- 11）mod 13 = 6 7* 11： （7*11）mod 13 = 7 加法表加法表 0 1 2 3 4 5 6 7 8 9 0 0 1 2 3 4 5 6 7 8 91 1 2 3 4 5 6 7 8 9 02 2 3 4 5 6 7 8 9 0 13 3 4 5 6 7 8 9 0 1 24 4 5 6 7 8 9 0 1 2 35 5 6 7 8 9 0 1 2 3 46 6 7 8 9 0 1 2 3 4 57 7 8 9 0 1 2 3 4 5 68 8 9 0 1 2 3 4 5 6 79 9 0 1 2 3 4 5 6 7 8Z10中加法中加法

23、乘法表乘法表 0 1 2 3 4 5 6 7 8 9 0 0 0 0 0 0 0 0 0 0 01 0 1 2 3 4 5 6 7 8 9 2 0 2 4 6 8 0 2 4 6 8 3 0 3 6 9 2 5 8 1 4 7 4 0 4 8 2 6 0 4 8 2 65 0 5 0 5 0 5 0 5 0 56 0 6 2 8 4 0 6 2 8 47 0 7 4 1 8 5 2 9 6 38 0 8 6 4 2 0 8 6 4 29 0 9 8 7 6 5 4 3 2 1Z10中乘法中乘法例例2 (17+27) mod 14=2 (12-43) mod 13=(-31) mod 13=8

24、(123(-10) mod 19=(-1230) mod 19=5另法計算另法計算: (17 mod 14)+(27 mod 14)= (3+13) mod 14 =2(12 mod 13)-(43 mod 13)=(12-4) mod 13 = 8 (123 mod 19) (-10 mod 19)=9(-10) mod 19 = (-90) mod 19=(-14) mod19 = 5 定理定理 1 (ab) mod n= (a modn) (a mod n) (ab) mod n= (a modn) (a mod n)例例3 10n mod x = (10 mod x)n 10n mod

25、 3=(10 mod 3)n =1 10n mod 9=(10 mod 9)n =1 10n mod 7=(10 mod 7)n = 3n mod 7 10n mod 5=(10 mod 5)n = 0 ( n0) 100 mod 11= 1 101 mod11= -1 100 mod 7 = 1101 mod 7 = 3102 mod 7 = 2103 mod 7 = 6104 mod 7 = 4105 mod 7 = 5 102 mod 11= 1 103 mod11= -1 102k mod 11= 1 10(2k+1) mod11= -1 例例4 十進制十進制 a = an10n+an

26、-110n-1+a1101+a0100a mod 3=(an10n) mod 3 +(a1101) mod 3+(a0100) mod 3=(an mod 3)(10n mod 3) +(a1 mod 3)(101 mod 3) +(a0 mod 3) (100 mod 3)=an mod 3+a1 mod 3+a0 mod 3=(an +a1 +a0) mod 3比如：比如： 1236 mod 3 = 12 mod3 = 0 268750 mod 3 = 28 mod3 = 1 十進制數被十進制數被3或或9 整除整除 ，當且僅當各位數碼之和能被，當且僅當各位數碼之和能被3或或9整除。整除。模

27、模9運算運算類似！類似！ 十進制數模十進制數模3或?；蚰?，等于各位數碼之和模，等于各位數碼之和模3或?；蚰?。 (1723345 + 2124945) mod 3= (1+7+2+3+3+4+5) mod 3 +(2+1+2+4+9+4+5) mod 3= (25 mod 3)+(27 mod 3)=1+0 =1 (1723345 - 2124945) mod 3= (25 mod 3)-(27 mod 3) =1- 0 =1 (1723345 * 2124945) mod 3= (25 mod 3)*(27 mod 3) = 1*0 = 0 例例5 1723345 mod 5= (0+0+

28、0+0+0+0+5) mod 5 = 0 (1723347 + 2124949) mod 5= 7 mod5 + 9 mod5 = 1 (1723347 * 2124949) mod5= (7*9) mod 5 = 3 例例6 1723348 mod 5= (0+0+0+0+0+0+8) mod 5 = 8 mod 5 =3模模5運算運算 等于等于個位！個位！ (1723347 - 2124949) mod 5= 7 mod5 9 mod5 = 3 1723345 mod 11= (1-7+2-3+3-4+5) mod 11 = -3 mod11 = 8 (1723345 + 212494)

29、mod 11= 8 mod11 + (-2+1-2+4-9+4) mod 11 = 8 mod11 - 4 mo11= 4 (1723345 * 212494) mod11= (-3)*(-4) mod 11 = 1 例例7 (1723345 - 212494) mod 11= 8 - (-4) mod 11 = 1 五、五、Zn中的逆元素與逆運算中的逆元素與逆運算加法逆：加法逆： - a = (n-a) mod n， - a 稱為稱為 a 的加法逆（負元）。的加法逆（負元）。在在Z10中：中：a 0 1 2 3 4 5 6 7 8 9-a 0 9 8 7 6 5 4 3 2 1 做減法等于做

30、減法等于 加負元加負元 . 若若 a+b = 0 mod n，則，則 a與與b互為加法逆。互為加法逆。2 乘法逆：乘法逆：b = a -1 可能存在，也可能不存在?？赡艽嬖?，也可能不存在。 a有乘法逆有乘法逆 gcd(a, n) =1，即，即a與與n互素互素 若若 ab =1 mod n，則，則 a與與 b 互為乘法逆。互為乘法逆。若若 a -1 存在，稱其為存在，稱其為a 的乘法逆（逆元）。的乘法逆（逆元）。 做除法等同做除法等同于乘逆元素于乘逆元素 定理定理 2 0沒有沒有乘法逆元乘法逆元 例例8 在在Z10中，中，8的乘法逆的乘法逆 8-1 =？ 由于由于 gcd (8, 10) = 2

31、 1，8沒有乘法逆。沒有乘法逆。 在在Z10中，沒有任何數字中，沒有任何數字 與與8相乘相乘 = 1 !012345678900000000000112345678924680246839258147460482655050566284795384291例例9 求求Z10中的乘法逆中的乘法逆gcd(10, 1)=1gcd(10, 4)=2gcd(10, 7)=1gcd(10, 0)=10gcd(10, 2)=2gcd(10, 3)=1gcd(10, 5)=5gcd(10, 6)=2gcd(10, 8)=2gcd(10, 9)=1 從乘法表中可以看到從乘法表中可以看到: 1, 3, 7, 9 有

32、乘法逆有乘法逆 1-1 = 1 3-1 = 7 7-1 = 3 9-1 = 9 其余其余 0, 2, 4, 5, 6, 8 都沒有乘法逆。都沒有乘法逆。 構成三對構成三對 乘法逆乘法逆：(1, 1) (3,7) (9, 9） 驗證定理：驗證定理： 例例10 求求Z11中的乘法逆中的乘法逆 由于由于 11 是質數，是質數， gcd ( k, 11) = 1, 所以除所以除 0 外，外，1, 2, , 10 都有乘法逆。都有乘法逆。 利用乘法表，可知有利用乘法表，可知有6對對 乘法逆乘法逆： (1, 1) (2, 6) ( 3, 4 ) (5, 9) (7, 8) (10, 10) 五、五、 Zn

33、中的逆元素與逆運算中的逆元素與逆運算3 乘法逆的求法乘法逆的求法Euclid（輾轉相除）（輾轉相除）設設 gcd(n, b) =1，b-1 存在存在可求出：可求出：sn+bt = 1(sn) mod n + (bt) mod n = 1 mod n(bt) mod n = 1 b-1 = t mod n = 0 mod n 例例8 在在Z26 中求中求 11-1解：解：n = 26，b = 11，求，求 s26+ t11 = 1q r1 r2 r t1 t2 t2 26 11 4 0 1 -22 11 4 3 1 -2 51 4 3 1 -2 5 -73 3 1 0 5 -7 26 1 0 -

34、7 26 即即 (11, 19)互為乘法逆?；槌朔?。 t = -7 mod 26 = 19 , 11*19 = 1 mod 26 例例9 在在Z100 中求中求 23的乘法逆，的乘法逆，23-1 mod 100解：解：n = 100， b = 23q r1 r2 r t1 t2 t4 100 23 8 0 1 -42 23 8 7 1 -4 91 8 7 1 -4 9 -137 7 1 0 9 -13 100* 1 0 * -13 100 * t1 = -13 mod100 = 87 ，所以，所以，( 23, 87)互逆。互逆。例例10 求求 12-1 mod 26 （對應（對應26個英文

35、字母）個英文字母）由于由于gcd (26, 12) = 2 1，12在在 Z26中沒有逆。中沒有逆。 六、加法集和乘法集六、加法集和乘法集 加法集加法集 Zn （有加法逆的元素全體）（有加法逆的元素全體）Z6=0, 1, 2, 3, 4, 5 乘法集乘法集 Zn*（有乘法逆的元素全體）（有乘法逆的元素全體）加法加法乘法乘法Z6* =1, 5Z7=0, 1, 2, 3, 4, 5, 6Z10=0, 1, 2, , 9 Z7*=1, 2, 3, 4, 5, 6Z10*= 1, 3, 7, 9不一定有乘法逆不一定有乘法逆一定有乘法逆一定有乘法逆 可以施行可以施行 加減法加減法 可以施行可以施行 乘除

36、法乘除法 在密碼學中，將在密碼學中，將n取成素數取成素數 pZp*=1, 2, , p-1Zp= 0, 1, 2, , p-1 3 矩陣的模運算矩陣的模運算 一、一、A=（aij）lm ， aij Zn二、二、 A+B, AB, 行列式行列式 ，按元素模，按元素模n運算運算 四、四、 加法逆：加法逆： 若若 A+B = O，A, B互為加法逆互為加法逆 此時此時 B = - A 乘法逆：乘法逆： 若若 AB = BA = I，A,B互為乘法逆互為乘法逆 此時此時 B = A-1 三、三、 A = B：對應元素模：對應元素模 n相等相等 定理定理: 若若 gcd( |A| , n) = 1，則，

37、則 存在存在 A-1 mod n 3 5 7 2A= 1 4 7 2 6 3 9 17 13 5 4 16 23 21 19 24 -A= 25 22 19 24 20 23 17 8 13 21 22 10| A | = det A = 21 mod26例例1 在在 Z26中，所有運算中，所有運算 皆為皆為 模模 26 運算。運算。 15 21 0 15A-1 = 23 9 0 22 15 16 18 3 24 7 15 3det(A-1）= 5 mod 26 gcd( |A|, 26) = gcd(21, 26) = 1, 逆矩陣存在：逆矩陣存在： 例例2 模模7的矩陣運算的矩陣運算= (

38、6+ 0 +1) mod7 = 0 2 (1) (3 7 10) 4 = (6+28+120) mod7 12 3 4 6 2 0 1 1 1 8 + 1 1 0 5 8 3 5 2 8 5 4 7 = 2 2 8 mod7 10 12 11 5 4 0 = 2 2 1 3 5 6 例例3(1) det mod 10 =3 3 01 1 det mod 10 = 2 4 21 1 (2) =1/3 mod 10 1 0-1 33 0 -11 1 = 7 =1 09 3 7 0 3 1gcd (3, 10) =1, 可逆。可逆。gcd (2, 10) =2, 不可逆。不可逆。 =1/2 mod 10 1 -2-1 44 2 -11 11/2 mod 10 不存在不存在 4 模模n線性方程組線性方程組 一、一、ax = b mod n 的解的解 1. 若若 gcd(a, n) = d，且且d | b，則方程有，則方程有d 個解。個解。 兩端除兩端除d： (a/d)x = (b/d) mod (n/d) 化為：化為： a1 x = b1 mod n1特解：特解：x0 = a1 -1 b1 通解：通解：x = x0 +k*n1 ，k = 0, 1, 2, , d-12. 若