《密码学数学基础》习题集

北京电子科技学院密码学数学基础习题集信息安全系密码教研室2015 年 10 月目录第一章 带余除法.3一、整数的最大公因子及其表示.3二、多项式的最大公因子及其表示. 7三、标准分解和最小公倍数. 9四、其他类型题. 11第二章同余方程. 12一、同余性质（剩余系）. 12二、模幂运算. 14三、模逆运算. 16四、一次同余方程求解. 18第三章 原根计算.26一、阶、原根、指数. 26二、阶的计算. 30三、原根的计算. 32四、综合. 36第四章 二次剩余.38第五讲群. 49一、群的概念. 49二、循环群的生成元求解(可求原根) . 49三、子群及其陪集. 50四、置换群上的计算. 53五、群同态. 54第六章环的性质. 55一、环的概念. 55二、商环. 57第七章域上计算. 58第一章 带余除法重点概念：最大公因子、辗转相除法、标准分解式重点内容：用辗转相除法求解最大公因子及其表示。一、整数的最大公因子及其表示1.(288，392)8，2.设 a = 1435, b = 3371，计算 (a, b)。答： 3371 = 2 ?1435 + 5011435 = 2 ? 501+ 433501 = 433 + 68433 = 6 ? 68 + 2568 = 2 ? 25 + 1825 = 18 + 718 = 2 ? 7 + 47 = 4 + 34 = 3 +13 = 3?1所以 (1435,3371) = 13.用辗转相除法求整数 x，y，使得 1387x - 162y = (1387, 162)。答：用辗转相除法，如下表计算：x-yq138710162018911-8171-191202-17311-760199-7712-161374173-625x=73，y=625, (1387, 162)=1.4.计算：(27090, 21672, 11352)。答：(27090, 21672, 11352) = (4386, 10320, 11352) = (4386, 1548, 2580)= (1290, 1548, 1032) = (258, 516, 1032) = (258, 0, 0) = 258。5.用辗转相除法计算以下数组的最大公因子。(1) (1046,697)(2) (2030 1044)解：(1) 1046 = 1 697 + 349697 = 1349+ 348349 = 1?348 +1348 = 348?1因此 (1046,697)=1(2)2030 = 1?1044+9861044 = 1? 986 + 58986 = 17 ?58因此 (2030 1044)=586.用辗转相除法计算以下数组的最大公因子(1) (2104,2720,1046)(2) (27090, 21672,11352)解：(1) 先求出 (2104,2720) 的公因子 d1 ，再求 (d1,1046) 的公因子 d 2 ， d 2 即为最终要求的公因子。因此：2720 = 1? 2104+6162104 = 3? 616+256616=2? 256+104256 = 2?104+48104=2? 48+848=6?8因此 (2104, 2720) = 8，再求 (8,1046)，1046 = 130?8 + 6，8 = 1? 6 + 26 = 3? 2因此 (2104, 2720,1046) = 2(2) 先求出 (27090, 21672)的公因子 d1 ，再求 (d1,11352) 的公因子 d 2 ， d 2 即为最终要求的公因子。因此：27090 = 1? 21672+541821672 = 4 ? 5418因此 (27090, 21672) = 5418，再求 (5418,11352)，11352 = 2 ? 5418 + 5165418 = 10 ? 516 + 258516 = 2 ? 258因此 (27090, 21672,11352) = 2587.用辗转相除法求以下数组的最大公因子，并把它表示为这些数的整系数线性组合。(1) 1387,162(2) 2046,1620解：(1) 用列表法可求出 (1387,162) 的公因子及相应的系数组合，如表 1 所示：表 1 求 (1387,162) 的公因子及相应系数uvq138710162917120119201-12-79-161-89-1760-771378113114173-62520由上表可得： (1387,162) = 1 = 1387? 73 + 162? (-625) 。(2) 用列表法可求出 (2046,1620) 的公因子及相应的系数组合，如表 2 所示：表 2 求 (2046,1620) 的公因子及相应的系数组合uvq204610162042634284601-34-191-14-5241314140由上表可得： (2046,1620) = 6 = 1387 ? (-19) + 162? 24 。8.计算 4389，5313，399 的最大公因子，并把它表示为这些数的整系数线性组合。解：先求 4389 与 5313 的最大公因子，如下表 3，公因子为 213。再求 213与 399 的最大公因子，如表 4，公因子为 21。表 3 求 4389 与 5313 的最大公因子表 4 求 213 与 399 的最大公因子uvquvq53131039910438992469323101-451-15-61413231168634201-131-12-51121021-4720又由表 3、4 可分别得到如下两式：231 = 5313? 5 + 4389 ? (-6)21 = 399 ? (-4) + 231? 7(1)(2)将（2）式的 231 用（1）式等式右边代替并化解可得如下式：21 = 399 ? (-4) + 5313? 35 + 4389 ? (-42)所以得到 4389，5313，399 的最大公因子为 21，及其相应系数组合为-42，35，-4。二、多项式的最大公因子及其表示1、求有理数域上多项式的最大公因式 ( f (x), g(x) ，其中f (x) = x5 + x4 + x2 + 2x + 1,g (x) = x4 + x3 + x2 + 2x + 1.答：用辗转相除法计算如下x5 + x4 + x2 + 2x + 1 = x(x4 + x3 + x2 + 2x + 1) - x3 - x2 + x + 1x4 + x3 + x2 + 2x + 1 = -x(-x3 - x2 + x + 1) + (2x2 + 3x + 1)-x3 - x2 + x + 1 =12x(2x2 + 3x + 1) +3x 34 48 4 3x 33 3 4 4因此 ( f (x), g(x) = x + 12、求有理数域上多项式的最大公因式 ( f (x), g(x) ，并计算 u(x), v(x) ，使得( f (x), g(x) = u(x) f (x) + v(x)g(x) ，其中f (x) = x5 + x3 + x2 + 1,g (x) = x 4 + x 2 + x - 1.答：由列表法可求出 ( f (x), g(x) 的公因子及相应系数组合，如表 5 所示：表 5 求 ( f (x), g(x) 的公因子及相应的系数组合u( x)v( x)q+2x2 + 3x + 1 = ( x + )(+ ) = (2x + 1)(x + 1)x5 + x3 + x2 + 110x4 + x2 + x -1x +1011- xxx3 - x2 + 2x -10因此 ( f (x), g(x) = x + 1 = (1)(x5 + x3 + x2 + 1) + (-x)(x4 + x2 + x - 1)m ( x) = 1v( x) = - x3、求二元域上多项式的最大公因式 ( f (x), g(x) ，其中f (x) = x5 + x3 + x2 + 1,g (x) = x4 + x 2 + 1.答：用辗转相除法计算如下x5 + x3 + x2 + 1 = x(x4 + x2 + 1) + x2 + x + 1x4 + x2 + 1 = (x2 + x + 1)(x2 + x + 1)因此 ( f (x), g(x) = x2 + x + 14、 f (x), g(x) ? F2x 且有f (x) = x6 + x5 + x4 + x3 ,g (x) = x5 + x 2 + x + 1.求 m(x) 和n (x) ，使得 ( f (x), g(x) = m(x) f (x) + g(x)n (x)。答：由列表法可求出 ( f (x), g(x) 的公因子及相应系数组合，如表 6 所示：表 6 求 ( f (x), g(x) 的公因子及相应的系数组合u( x)v( x)qx6 + x5 + x4 + x310x5 + x2 + x + 101x +1x 4 + 1x 2 + 11xx +1x2 + x +1xx 2 + 10因此 ( f (x), g(x) = x2 + 1 = x(x6 + x5 + x4 + x3 ) + (x2 + x + 1)(x5 + x2 + x + 1)m(x) = xv(x) = x2 + x + 15.求有理数域上多项式的最大公因式（ f (x), g(x) ），其中f (x) = x5 + x4 + x2 + 2x + 1,g (x) = x4 + x3 + x2 + 2x + 1.答： ( f (x), g(x) = x + 1。6.求有理数域上多项式的最大公因式（ f (x), g(x) ），并计算 u(x), v(x) ，使得( f (x), g(x) = u(x) f (x) + v(x)g(x) ，其中f (x) = x5 + x3 + x2 + 1,g (x) = x 4 + x 2 + x - 1.答： x +1 = f (x) - xg(x) 。三、标准分解和最小公倍数1. 288，392 14112。212600 的标准分解式是_2332527。3.547 是_.（填“素数”或“合数”）。3528 的标准分解式是_23*32*72_。4.计算以下数组的最小公倍数。(1) 1046,697(2) 2030 1044(3) 195, 72,90(4) 2104,2720,1046，解：(1) 由第 2 题计算得 (1046,697)=1，因此 1046,697=1046? 697=729062。(2) 由第 2 题计算得 (2030 1044)=58 ，因此 2030 1044=2030 ?1044 ? 58=36540 。(3) 由辗转相除法可计算得 (195,72,90) = 3，因此195,72,90 = 195? 72 ? 90 ? 3 = 4680(4) 由第 3 题计算得 (2104, 2720,1046) = 2，因此2104,2720,1046=2104? 2720?1046 ? 2=374133280 。5.求正整数 a, b ，使得 a + b = 120,(a, b) = 24,a, b = 144 。答 ： 由 a + b = 120 及 ab = (a, b)a, b = 24 ?144 = 3456 解 得 a = 4 8b,=a = 72, b = 48。6.设 a, b是正整数，证明： (a + b)a, b = ab, a + b 。7或2答：只须证 (a + b)ab b ( a + b )(a, b) (b, a + b)，即只须证 (b, a + b) = (a, b) 此式显然。7.写出下列数的的标准分解式。(1)22345680(2) 166896912(3) 22345680解：(1)22345680 = 24 ? 3? 5 ? 7 ? 47 ? 283。448.判断 561 与 967 是否为素数。解：由 3 | 561，所以 561 不是素数，由 2,3,是素数。967， ，= a(2) 166896912 = 2 ? 3? 7 ?13?19 ? 2011 。(3) 22345680 = 2 ?3?5?7?47?283。, 殛 都不能整除 967，所以 967四、其他类型题1.证明：若 m - p?mn + pq，则 m - p?mq + np。答：由恒等式 mq + np = (mn + pq) - (m - p)(n - q)及条件 m - p?mn + pq 可知 m - p?mq + np。2.证明：任意给定的连续 39 个自然数，其中至少存在一个自然数，使得这个自然数的数字和能被 11 整除。答：在给定的连续 39 个自然数的前 20 个数中，存在两个自然数，它们的个位数字是 0，其中必有一个的十位数字不是 9，记这个数为 a，它的数字和为 s，则 a, a + 1, L, a + 9, a + 19 的数字和为 s, s + 1, L, s + 9, s + 10，其中必有一个能被 11 整除。3.设 a，b 是正整数，证明：(a + b)a, b = ab, a + b。答：只须证 (a + b)ab(a, b)= ab(a + b)(b, a + b)，即只须证(b,a + b) = (a, b)，此式显然。4.求正整数 a，b，使得 a + b = 120，(a, b) = 24，a, b = 144。答：由 a + b = 120 及 ab = (a, b)a, b = 24 ? 144 = 3456 解得 a = 48，b = 72或 a = 72，b = 48。5.计算 2050 与 3768 的二进制表示和十六进制表示。解：2050 的二进制表示： 2050 = (100000000010)22050 的十六进制表示： 2050 = (802)163768 的二进制表示： 3768 = (111010111000)23768 的十六进制表示： 3768 = (EB8)166.证明 6 | n(n +1)(2n + 1)，其中 n 为任意整数。证明： n(n +1)(2n +1) = n(n +1)(n -1+ n + 2) = (n -1)n(n +1) + n(n +1)(n + 2) ；(n -1), n,(n +1) 是连续三个整数，其中必有一个是 3 的倍数，至少有一个是 2 的倍数，因此 6 | (n -1)n(n +1) ，同理 6 | n(n + 1)(n + 2)，因此 6 | n(n +1)(2n + 1)。7.证明：若 m - p | mn + pq ，则 m - p | mq + np 。答 ： 由 恒 等 式 m q+ n p=( m n+p) q-(m ) p - 及q m - p | mn + pq 条 件 可 知m - p| m + n。8.证明：任意给定的连续 39 个自然数，其中至少存在一个自然数，使得这个自然数的数字和能被 11 整除。答：在给定的连续 39 个自然数的前 20 个数中，存在两个自然数，它们的个位数字是 0，其中必有一个的十位数字不是 9，记这个数为 a，它的数字和为 s，则 a,a+ 1, L, a+ 9, a+ 19 的数字和为 s,s+ 1, L, s+ 9, s+ 10，其中必有一个能被 11整除。第二章 同余方程重点内容：同余的性质、完全剩余系、模逆运算、模幂运算（利用欧拉定理进行降幂，再用从右向左或者从左向右算法计算）、一次同余方程求解一、同余性质（剩余系）1. 将 612 - 1 分解成素因数之积。答：612 - 1 = 5?7?13?31?37?43 ?97。2.写出完全剩余系和简化剩余系（缩系）的概念，并举例说明（3 分）；写出 154440 的标准分解式（7 分）。3.证明：1978103 - 19783 能被 103 整除。答：因 103 = 2353，显然 1978103 - 19783 ? 0 (mod 23)，再由 1978100 ? 1 (mod 53)得 1978103 - 19783 ? 0 (mod 53)，故 1978103 - 19783 ? 0 (mod 103)。- ( n )q p4.证明：对于任意的整数 a，(a, 561) = 1，都有 a560 ? 1 (mod 561)，但 561是合数。答案：因 561 = 3 ?11 ?17，对于一切整数 a，(a, 561) = 1，有(a, 3) = 1，(a, 11) = 1，(a, 17) = 1，由费马定理可得 a560 = (a2)280 ? 1 (mod 3)，a560 = (a10)56 ? 1 (mod 11)，a560 = (a16)35 ? 1 (mod 17)，故 a560 ? 1 (mod 561)。5.一般地，模 10 的最小非负完全剩余系为 0,1,2,3,4,5,6,7,8,9 ；模 10 的简化剩余系为（或缩系）1,3,7,9 。6一般地，模 6 的最小非负完全剩余系为；模 6 的简化剩余系为（或缩系）。7(120)-(100)_。2(100) -(72)_16_。8一般地，模 8 的最小非负完全剩余系为0,1,2,3,4,5,6,7 ；模 8 的简化剩余系为（或缩系）1,3,5,7。9.写出模 15，24 的缩系。答：15 的缩系为 1, 2, 4,7,8,11,13,14；24 的缩系为 1,5,7,11,13,17,19, 23。10.求 19，27，40 的欧拉函数值。答： j (19) = 19 -1 = 18；131 12 511.若 (m, n) = 1，证明： mj ( n) + nj ( m) ? 1(mod mn) 。证明：可将 mn 分解列出方程如下：祜mj ( n) + nj ( m) ? 0 + 1 ? 1(mod m)镱m + n ? 1 + 0 ? 1(mod n)? mj ( n ) + nj ( m) ? 1(mod mn)12.证明：对于任意正整数 m 有?d|m,d 0f(d ) = m 。? j ( n) j ( m)证明：当 n = 1时， ?f (d ) =1，设 n = p1a1d|npka k ，则?f (d ) = ? f (d1 )d |n?d k 1| pk kf (d k )= 1 + ( p1 -1) + ( p1a1 - p1a1 -1 ) 1 + ( pk -1) + ( pka k - pka k -1)= p1a1pka k = n。13.设 m 与 n 是正整数，证明：j(mn)j(m, n) = (m, n)j(m)j(n) 。证明：设 m = p1a1pkak m1，n = p1b1pkbk n1， pi/ m1，pi / n1， (m1, n1) = 1，则1 1pa k + b k m1n1 ) = pa1 + b1ki =11pi)f (m1 )f (n1 ) ，1 1ki =11pi)，由此得1ki =11pi)f (m1) p b1ki =11pi)f (n1)= (m, n)j(m)j(n) 。14 证明： 70! ? 61!(mod 71) 。证 明 ： 由 题 得 只 需 证 明 7 ?0-( 9 ? 8?1 ) ? ，因此得证。 7 1 )6? 9 ?6? 21， ( 即m o d 7 1 )二、模幂运算242. 求 313159 被 7 除的余数。答：313159 =6 (mod 7)。3.简述一种简便模幂运算（从右向左或从左向右计算）的思路。（10 分）5134. 欧拉函数 j(7) =610mod7。2005 年 7 月 26 日是星期二，问此天后第 21000 天是星期几？d1| p1 1| |pka k + b k ? (1 -k 1pkmina k ,b k ) = (m, n)? (1 -pka k ? (1 -pkb k ? (1 -11 ( m o d1.写出欧拉定理和费马小定理（3 分），用这两个定理计算 5 mod 21（7 分）。至少用两种方法计算 79 (mod 315) 。（共 20 分），利用欧拉定理计算1010 = 4解依题意，我们需要求 21000 mod7 ，即整数 21000 模 7 的最小非负剩余。因10003 333因此，第 21000 天是星期四。5. 3 408写成十进制时的最后两位数是 61。6运用从左向右（或从右向左）的算法计算： 2 567 mod 61。答案： (2,61) = 1， j(61) = 60,567 = 60 ? 9 + 27 ，567 27用从左向右计算方法，有 27 的二进制表示 11011，列表格计算如下：5677.用欧拉定理求下列模幂运算。246mod 8答：1851mod15(1)(2)j(8) = 4 ，因此 3246 ? 3246(mod 4) ? 32 ? 1mod8。j (15) = 8，因此 51851 ? 51851(mod8) ? 53 ? 5mod15 。解答：1025mod15根据 af ( m )? 1(mod m) 计算 得出 31025 ? 3(mod15)9.用快速算法求下列模幂运算。33iki31222=82082=311322=18011822=38为 23 mod7 = 1，所以 2 mod 7 = (2999 ? 2) mod 7= (2 ) mod 7 ? 2 mod 7) mod 7 = 2 ，所以 2 mod 61 = 2 mod 61，2 mod 61 = 38(1) 3(2) 58.计算 3(1) 13 mod 4758答：(1) 33 的二进制表示：100001(2) 58 的二进制表示：111010三、模逆运算1、求 35(mod 41) 的乘法逆元。-1 393539 ? 34(mod 41) 。2、求 23(mod1800) 的乘法逆元。答：利用扩展欧几里德辗转相除法列表计算如下：vq18000ikix40213 2830228 3220232 3710237 60126 1345ikix41211 115831258 112020220 6511265 114400244 60(2) 11 mod 67答： 35 (mod 41) ? 35j (41)-1 ? 35 (mod 41) ，利用模幂快速算法可计算得236511-78235-313783150因此 23-1 ? -313 ? 1487(mod1800) 。3、求11(mod 26) 的乘法逆元解答：26 = 11? 2 + 44 = 26 -11? 211 = 4 ? 2 + 33 = 11 - 4 ? 2 = 11 -（ 26 -11? 2）? 2 = -2 ? 26 + 5 ?114 = 3?1 + 11 = 4 - 3?1 =（ 26 -11? 2）-（ - 2 ? 26 + 5 ?11）?1 = 3 ? 26 - 7 ?11- 14、求 5(mod14)的乘法逆元解答：14 = 5 ? 2 + 45 = 4 +11 = 5 - 4 = 5 -（ 14 - 5 ? 2） = 5 ? 3 -14即 5?3 = 14?1+1- 15、用欧几里得算法计算 1234 mod 4321 的乘法逆元解答：QX1X2X3Y1Y2Y310432101123430112341-361911-3619-146151-146152-741532-74-307107541-30710752309-10821即11 (mod 26) ? -7(mod 26) ? 19? 5 (mod14) ? 34321-1082=3239-1解答：由欧拉定理，有15? 73 ? 343(mod17) ? 73 ? 3(mod17) ? 715 ? 5(mod17) ? 715 ? 5(mod17) 。 7-1 ? 5(mod17) 。四、一次同余方程求解1同余方程 15x12(mod99)关于模 99 的解是_144780_。2. 解同余方程：(1) 6x ? 2(mod9)；(2) 31x ? 5(mod17) ；(3) 3215x ? 160(mod 235) 。答：(1) 因为 (6,9) = 3 /| 2 ，因此同余式 6x ? 2(mod9) 无解；(2) 由 (31,17) = 1，因此x ? (31)-1 ? 5(mod17)x ? 11? 5(mod17)x ? 4(mod17)(3) 由 (3215, 235) = 5 |160，因此方程有 5 个解，先求一个解：643x ? 32(mod 47)x ? (643)-1 ? 32(mod 47)x ? 25 ? 32(mod 47)x ? 1(mod 47)因此，5 个解为 xi ? 1 + 47i(mod 235), i = 0,1, 2,43.解同余方程组：6、计算 7 mod177-1 ? 7 (mod17) ，其中 (17)=16?3x ? 1(mod10)?答：方程可化解为? x ? 7(mod10)? x ? 1(mod 2)? x ? 0(mod 3)?x ? b1(mod 5)?4.解同余方程组： ?镱x ? b4 (mod11) 。答：x ? 3?462?b1 + 1?385?b2 + 1?330?b3 + 1?210?b4 (mod 2310)。解同余方程组：? x ? 2(mod 5)? x ? 4(mod 9)答：利用中国剩余定理方程可解得x ? 157(mod 315)?x ? 8(mod15)?x ? 13(mod 25) 。答：方程等价为? x ? 2(mod 3)? x ? 13(mod 25)利用中国剩余定理解得： x 413(mod 600)。6.求解同余式组? x ? 2(mod9)?4 x ? 3(mod7)解 因为 3-1 mod5 = 2， 4 -1 mod 7 = 2，所以同余式 3x ? 4(mod5) 和 4x ? 3(mod7) 的解分别为x ? 3(mod5)和 x ? 6(mod7) ，?4x ? 3(mod15)? x ? 12(mod15)? ? x ? 2(mod 5) ? x ? 27(mod 30)?x ? b2 (mod 6)?x ? b3 (mod 7)? x ? 3(mod 7)5. 解同余方程组： ?x ? 5(mod 8)? x ? 5(mod 8)?3x ? 4(mod5)?因此求解原同余式组等价于求解同余式组?x ? 2(mod9)?x ? 6(mod7)m1 = 9, m2 = 5, m3 = 7， M 1 = 35, M 2 = 63, M 3 = 45 ，利用乘法逆元素的性质可以分别计算 M1?, M 2? , M 3? 为M1? = M1-1 mod 9 = 35 -1 mod 9 = 8；M 2? = M 2-1 mod 5 = 63 -1 mod 5 = 2 ；M 3? = M 3-1 mod 7 = 45 -1 mod 7 = 3-1 mod 7 = 5，从而同余式组的解为 x ? 35 ? 8 ? 2 + 63 ? 2 ? 3 + 45 ? 5 ? 6(mod315) ，即 x ? 560 + 378 + 1350 ? 83(mod315) 。?x ? 2(mod 7)?x ? 11(mod15)?x ? 2(mod 7)?x ? 5(mod 9)答案：方程组等价于 ?镱x ? 11(mod 5)，?x ? 1(mod 5)?x ? 5(mod 9)m = 5? 7 ? 9 = 315，M1 = 63, M1-1 ? 2 mod 5;M 2 = 45, M 2-1 ? 5 mod 7;M 3 = 35, M 3-1 ? 8 mod 93i =1= 63? 2 ?1 + 45 ? 5 ? 2 + 35 ? 8 ? 5(mod 315)= 86(mod 315)? x ? 3(mod5)7.