《信息安全数学基础》部分课后习题答案

资源大全更新时间:2025-05-04 02:56:40

2024年1月4日发(作者：六年级升初中数学试卷)

《信息安全数学基础》课后作业及答案

第1章课后作业答案 .......................................................................... 2

第2章课后作业答案 .......................................................................... 6

第3章课后作业答案 ........................................................................ 13

第4章课后作业答案 ........................................................................ 21

第5章课后作业答案 ........................................................................ 24

第6章课后作业答案 ........................................................................ 27

第7章课后作业答案 ........................................................................ 33

第8章课后作业答案 ........................................................................ 36

第9章课后作业答案 ........................................................................ 40

第10章课后作业答案 ...................................................................... 44

第11章课后作业答案 ...................................................................... 46

第12章课后作业答案 ...................................................................... 49

第13章课后作业答案 ...................................................................... 52

1

第1章课后作业答案

习题1：2, 3, 8(1), 11, 17, 21, 24, 25, 31

2. 证明：存在整数k，使得5 | 2k + 1，并尝试给出整数k的一般形式。

证明 k = 2时，满足5 | 2k + 1。

5 | 2k + 1，当且仅当存2k + 1 = 5q。k, q为整数。

即k = (5q – 1)/2。

只要q为奇数上式即成立，即q = 2t + 1，t为整数

即，k = 5t + 2，t为整数。

3. 证明：3 3k + 2，其中k为整数。

证明因为3 | 3k，如果3 | 3k + 2，则得到3 | 2，矛盾。

所以，3 3k + 2。

8. 使用辗转相除法计算整数x, y，使得xa + yb = (a, b)：

(1) (489, 357)。

解 489 = 357×1 + 132,

357 =132 × 2 + 93,

132 = 93 × 1 + 39,

93 = 39 × 2 + 15,

39 = 15 × 2 + 9,

15 = 9 × 1 + 6,

2

9 = 6 × 1 + 3,

6 = 3 × 2 + 0,

所以，(489, 357) = 3。

132 = 489 – 357×1,

93 = 357 – 132 × 2 = 357 – (489 – 357×1) × 2 = 3 × 357 – 2 ×489,

39 = 132 – 93 × 1 = (489 – 357×1) – (3 × 357 – 2 ×489) × 1 = 3 ×

489 – 4× 357,

15 = 93 – 39 × 2 = (3 × 357 – 2 × 489) – (3 ×489 – 4× 357) × 2 =

11× 357 – 8 × 489,

9 = 39 – 15 × 2 = (3 ×489 – 4× 357) – (11× 357 – 8 × 489) × 2 = 19

× 489 – 26× 357,

6 = 15 – 9 × 1 = (11× 357 – 8 × 489) – (19 × 489 – 26× 357) = 37 ×

357 – 27 × 489,

3 = 9 – 6 × 1 = (19 × 489 – 26× 357) – (37 × 357 – 27 × 489) = 46 ×

489 – 63 × 357。

11. 证明每个奇数的平方具有形式8k + 1。

证明任一奇数可以写成2t + 1其中t为整数。

(2t + 1)2 = 4t2 + 4t + 1 = 4t(t + 1) + 1 = 8k + 1，k为整数。

17. 设a, b∈ Z，证明(a, b) = (a, ka + b)，其中k为任意整数。

证明1 (a, b) | a, (a, b) | b，则(a, b) | ka + b，所以(a, b) | (a, ka + b)；

3

又因为(a, ka + b) | a, (a, ka + b) | (ka + b)，则(a, ka + b) | ka + b –

ka，因此(a, ka + b) | b。

故(a, ka + b) | (a, b)。

因此，(a, b) = (a, ka + b)。

证明2 设r = ka + b，则由定理1.2，(r, a) = (a, b)，所以(a, b) = (a, ka

+ b)。

21. 设u, v ∈ Z，(u, v) = 1，证明(u + v, u – v) = 1或2。

证明1 设d = (u + v, u – v)，则

d | u + v, d | u – v，

所以

d | 2u, d | 2v，

所以 d ≤ (2u, 2v)，

因为(u, v) = 1，所以(2u, 2v)为2或1。

证明2 (u + v, u – v) = (u + v, 2u)

由第20题【设a, b, c ∈ Z，(a, b) = 1，证明(a, bc) = (a, c)。】，因为(u + v, u) = 1，所以(u + v, 2u) = (u + v, 2) = 1 或2。

24. 求388与572的最小公倍数。

解先(388, 572)。

4

572 = 388×1 + 184,

388 = 184 × 2 + 20,

184 = 20 × 9 + 4,

20 = 4 × 5 + 0,

所以，(388, 572) = 4。

于是，[388, 572] =

25. 设a, b ∈ Z，m ∈ Z+，证明(ma, mb) = m(a, b)，[ma, mb] = m[a, b]。

证明设(a, b) = sa + tb，x, y ∈ Z，则

m(a, b) = msa + mtb。

因为(ma, mb) | ma, (ma, mb) | mb, 所以 (ma, mb) | msa + mtb，即(ma, mb) | m(a, b)。

(a, b) | a, (a, b) | b，所以，m(a, b) | ma, m(a, b) | mb，所以m(a, b)

| (ma, mb)。

两者相互整除，于是，(ma, mb) = m(a, b)。

[ma, mb] =

mambmambmabm[a,b]。

(ma,mb)m(a,b)(a,b)388572= 55484。

431. 是否存在这样的整数a, b, c，使得a | bc，但a b, a c？

证明 a = 15, b = 3, c = 5，即有a | bc，但a b, a c。

5

第2章课后作业答案

习题2：1, 3, 11（只做Z5, Z8情况）, 13, 33, 38, 39（(1), (2)）,45, 47, 57。

1. 设a1, a2, …, an, N ∈ Z，n ≥ 1，证明：不定方程

a1x1 + a2x2 + … +anxn = N

有解的充要条件是(a1, a2, …, an) | N。

证明 “=>” 假设a1x1 + a2x2 + … + anxn = N有解，设其解为b1, b2, …,

bn，并设(a1, a2, …, an) = d, a1 = a1´d, a2 = a2´d, …, an = an´d，则

a1b1 + a2b2 + … + anbn = N

即,

d(a1´b1 + a2´b2 + … + an´bn) = N

所以,

d | N。

“<=” 已知(a1, a2, …, an) | N，根据定理1.7，存在整数s1, s2, …, sn，使

s1a1 + s2a2 + … + snan = (a1, a2, a3, ..., an)。

于是，存在整数k，使得

ks1a1 + ks2a2 + … + ksnan = N。

ks1, ks2, ..., ksn就是方程

a1x1 + a2x2 + … +anxn = N

的解。

6

3. 计算215 (mod 31), 233 (mod 31), 2100 (mod 31)。

解因为25 ≡ 1 (mod 31)，所以

(1) 215 = (25)3 ≡ 1 (mod 31)；

(2) 233 = (215)223 ≡ 8 (mod 31)；

(3) 2100 = (25)20 ≡ 1 (mod 31)。

11. 构造Z5, Z8, Z10的加法与乘法表。

Z5的加法表：

⊕ 0

0

1

2

3

4

0

1

2

3

4

1

2

3

4

0

2

3

4

0

1

3

4

0

1

2

4

0

1

2

3

Z5的乘法表：

⊗ 0

0 0

1 0

2 0

3 0

4 0

Z8的加法表：

7

1

0

1

2

3

4

2

0

2

4

1

3

0

3

1

4

2

4

0

4

3

2

1

⊕ 0 1 2 3 4 5 6 7

0 0 1 2 3 4 5 6 7

1 1 2 3 4 5 6 7 0

2 2 3 4 5 6 7 0 1

3 3 4 5 6 7 0 1 2

4 4 5 6 7 0 1 2 3

5 5 6 7 0 1 2 3 4

6 6 7 0 1 2 3 4 5

7 7 0 1 2 3 4 5 6

Z8的乘法表：

⊗ 0 1 2 3 4 5 6 7

0 0 0 0 0 0 0 0 0

1 0 1 2 3 4 5 6 7

2 0 2 4 6 0 2 4 6

3 0 3 6 1 4 7 2 3

4 0 4 0 4 0 4 6 4

5 0 5 2 7 4 1 6 3

6 0 6 4 2 0 6 4 2

7 0 7 6 5 4 3 2 1

Z10的加法表：

⊕ 0 1 2 3 4 5 6 7 8

0 0 1 2 3 4 5 6 7 8

8

9

1

2

3

4

5

6

7

8

9

1

2

3

4

5

6

7

8

9

2

3

4

5

6

7

8

9

0

3

4

5

6

7

8

9

0

1

4

5

6

7

8

9

0

1

2

5

6

7

8

9

0

1

2

3

6

7

8

9

0

1

2

3

4

7

8

9

0

1

2

3

4

5

8

9

0

1

2

3

4

5

6

9

0

1

2

3

4

5

6

7

0

1

2

3

4

5

6

7

8

Z10的乘法表：

⊗ 0

0 0

1 0

2 0

3 0

4 0

5 0

6 0

7 0

8 0

9 0

1

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

6

2

6

5

0

5

0

5

0

5

0

5

0

5

6

0

6

2

8

4

0

6

2

8

4

7

0

7

4

1

8

5

2

9

6

3

8

0

8

6

4

2

0

8

6

4

2

9

0

9

8

7

6

5

4

3

2

1

13. 证明：当m > 2时，02, 12, …, (m – 1)2一定不是模m的一组完全 9

剩余系。

证明因为(m – 1)2 ≡ 12 (mod m)，所以02, 12, …, (m – 1)2最多包含m –

1 个模m的剩余类，因此，02, 12, …, (m – 1)2一定不是模m的一组完全剩余系。

33. 设m ∈ Z+，整数a满足(a(a – 1), m) = 1，证明1 + a + a2 + … +

aυ(m)-1 ≡ 0 (mod m)。

证明 ∵(a, m) = 1，根据欧拉定理，有

aυ(m) ≡ 1 (mod m)。

∴ aυ(m) – 1 = (a – 1)(1 + a + a2 + … + aυ(m)-1) ≡ 0 (mod m)。

由于(a(a – 1), m) = 1，所以，

1 + a + a2 + … + aυ(m)-1 ≡ 0 (mod m)。

38. 证明：m是合数，当且仅当υ(m) < m – 1。

证明 υ(m) < m – 1 <=> 存在2, …, m – 1中的某个数与m不互素

<=> m是合数。

39. 求下列一次同余方程的解

(1) 2x ≡ 13 (mod 17), (2) 5x ≡ 11 (mod 19)。

解 (1) ∵ (2, 17) = 1，∴该同余式恰有一个解。x ≡ 15 (mod 17)。

(2) ∵ (5, 11) = 1，∴该同余式恰有一个解。x ≡ 6 (mod 11)。

45. 求以下同余方程组

3x ≡ 2 (mod 13)

2x ≡ 5 (mod 11)

6x ≡ 7 (mod 19)

10

解原同余方程组可化为

x ≡ 5 (mod 13)

x ≡ 8 (mod 11)

x ≡ 17 (mod 19)

根据中国剩余定理

m = 13·11·19 = 2717,

M1 = m/m1 = 271/13 = 209, M1-1 (mod 13) = 1;

M2 = m/m2 = 271/13 = 247, M2-1 (mod 11) = 9;

M3 = m/m3 = 271/13 = 143, M3-1 (mod 19) = 2。

故该同余方程组的解是

x ≡ 209·1·5 + 247·9·8 + 143·2·17 (mod 2717) ≡ 1955 (mod 2717)。

47. 设m, n为互素的整数，证明mυ(n) + nυ(m) ≡ 1 (mod mn)。

证明 ∵mυ(n) ≡ 1 (mod n)，nυ(m) ≡ 1 (mod m)，

∴ mυ(n) + nυ(m) ≡ 1 (mod m)；

mυ(n) + nυ(m) ≡ 1 (mod n)。

又∵(m, n) = 1，

∴ mυ(n) + nυ(m) ≡ 1 (mod mn)。

57. 设n = 23×29 = 667，用户公钥e = 17，明文m = 400。求出n的欧拉函数值，私钥d，以及密文c，并写出其加解密过程。

解 ∵ n = 23·29 = 667，

∴ υ(m) = 22·28 = 616，

17d ≡ 1 (mod 616)

11

解得d = 145。

加密：

c = me (mod 667) = 40017 (mod 667) = 509

解密：

d145m = c (mod 667) = 509

(mod 667) = 400

12

第3章课后作业答案

习题3：3, 9, 19, 31（做其中1小题）, 35。

3. 设p为奇素数，则1, 2, …, p – 1中有(p – 1)/2个模p的二次剩余，有(p – 1)/2个模p的二次非剩余。

证 ∵ p为奇素数

∴xp10(modp)

=> x ≡p-1p1(x2p11)(x21)0(modp)

由定理2.20，上式恰有p – 1 个解，

所以，

p1x210(modp)

与

p1x210(modp)

各有(p – 1)/2个解。

显然，p1x2即至少有(p – 1)/210(modp)的解都是二次非剩余，个二次非剩余；

{12, 22, …, (p – 1)2}都是模p的二次剩余且有(p – 1)/2个元素，即至少有(p – 1)/2个二次剩余。

综上，{1, 2, …, (p – 1)}中，至少有(p – 1)/2个二次非剩余，至少有(p – 1)/2个二次剩余。

所以，1, 2, …, p – 1中的二次剩余和二次非剩余各有(p – 1)/2个。

a9. 设p为奇素数，证明0。

a1pp 13

证因为1, 2, …, p – 1中有(p – 1)/2个模p的二次剩余，有(p – 1)/2个模p的二次非剩余。

所以，

abpp

aQR(p)bNQR(p) 。（= (p – 1)/2）

即，



ap0。

a1pa19. 设p是奇素数，a ∈ Z+，p a，证明a。

pp4a证明 (1) 若a为奇数，则

ap4a(1)a1p4a122p4a(1)aa1p122pa。

ap(2) 若a为偶数，设a = 2ka1，其中k为某整数，a1为奇数，则

a2p4ap4aka12p4ap4aka1p；

因为a为偶数，所以下式成立

2p4a(p4a)218(1)p28ap16a218(1)p21(1)82p；

所以

2p4aka12ppka12ka1appp。

综上述证明，有

aapp4a。

 14

31. 判断下列同余方程是否有解：

(1) x2 ≡ 5 (mod 227)；

(2) x2 ≡ – 14 (mod 117)；

(3) 17x2 ≡ – 6 (mod 47)；

(4) 11x2 ≡ – 15 (mod 6193)。

解 (1)

5（-1）22275-1227-122272=

-1。

55(3) 17x2 ≡ – 6 (mod 47)；

两边同乘以17-1 (mod47)将x2的系数转化成1，

求17-1 (mod47)：

47 = 2×17 + 13

17 = 1×13 + 4

13 = 3×4 + 1

于是，

13 = 47 – 2×17

4 = 17 – 1×13，即4 = 17 – 1× (47 – 2×17) = 3×17 – 47

1 = 13 – 3×4，即1 = (47 – 2×17) – 3×(3×17 – 47) = 4× 47 – 11 ×17

所以，17-1 (mod47) = – 11 (mod47) = 36

17x2 ≡ 41 (mod 47)的两边同乘以36，得

x2 ≡ 19 (mod 47)

因为

19(1)4719147122479(1)19199119122191所以无解。

1，99 15

35. 求满足同余方程E：y2 = x3 + 3x + 3 (mod 7)的所有点。

解 x = 0, y2 ≡ 3 (mod 7)，无解；

x = 1, y2 ≡ 0 (mod 7)，y = 0；

x = 2, y2 ≡ 3 (mod 7)，无解；

x = 3, y2 ≡ 4 (mod 7)，y = ± 2；

x = 4, y2 ≡ 2 (mod 7)，y = 3, 4；

x = 5, y2 ≡ 3 (mod 7)，无解；

x = 6, y2 ≡ 6 (mod 7)，无解；

所以，同余方程E：y2 = x3 + 3x + 3 (mod 7)的所有点是(1, 0), (3, 2), (3,

5), (4, 3), (4, 4)。

38. 设素数p = 4k + 3，在有解的情况下，求解同余式x2 ≡ a (mod p)。

解根据定理3.11，解为

x ≡±

4. 设p为奇素数，证明12·32·52·…·(p – 2)2 ≡ (– 1)(p+1)/2 (mod p)。

证明 12·32·52·…·(p – 2)2 ≡ 1(p – 1)·3(p – 3)·5(p – 5)·…·(p – 2)(2)·(–

1)(p-1)/2

≡ 1·2·3·4·5·…·(p – 2)(p – 1)·(– 1)(p-1)/2 (mod p)

下面证明(p – 1)! ≡ 1·2·3·4·5·…·(p – 2)(p – 1) ≡ – 1 (mod p)。 16

ap14(mod p)。

（Wilson定理）

事实上，在模p的剩余类集{1, 2, 3, …, p – 1}中，只有1, p – 1满足x2 ≡ 1 (mod p)，则可做如下配对：

取x1 ∈ A = {2, 3, …, p – 2}，则存在x2 ∈A{x1}，满足

x1x2 ≡ 1 (mod p)；

取x3 ∈A{x1, x2}，则存在x4∈A{x1, x2, x3}，满足

x3x4 ≡ 1 (mod p)；

…

取xp-4 ∈A{x1, x2, ..., xp-5}，则存在x p-3 ∈{x1, x2, ..., xp-5, xp-3}，满足

xp-4x p-3 ≡ 1 (mod p)。

所以，(p – 1)! ≡ 1·2·3·4·5·…·(p – 2)(p – 1) ≡ 1·(– 1)·x1x2·x3x4·…·xp-4x

p-3 ≡ – 1 (mod p)。

axb10. 设奇素数p a，证明0。

x1pp证明 (1) 首先证明模素数p的一组完全剩余系中，模p的二次剩余的个数等于二次非剩余的个数。

设a1, a2, …, ak是模p的二次剩余，b1, …, bs是模p的二次非剩余。

假设k ≠ s，不妨设k > s，即模p二次剩余的个数大于二次非剩余的个数。

则b1a1, b1a2, …, b1ak是模p的二次非剩余，b1b1, …, b1bs是模p的二次剩余，由此得出模p二次剩余的个数小于二次非剩余的个数。

两者矛盾，所以，假设错误，故，k = s。

17

因此，模素数p的一组完全剩余系中，模p的二次剩余的个数等于二次非剩余的个数。

(2) 下面证明ax + b（x = 1, 2, …, p）遍历模p的一组完全剩余系。

因为(a, p) = 1，所以0, a, 2a, 3a, …, (p – 1)a遍历模p的完全剩余系，进一步

0 + b, a, 2a + b, 3a + b, …, (p – 1)a + b也遍模p的完全剩余系。

根据(1)，有



axbp0。

x1p128028. 求雅可比符号值。

4113解因为1280 = 28·5，所以

1280255。

441138因为5 ≡ 1 (mod 4)，所以

54113352

1。41135533其它：

171717(1)622317117117(1)2217131131221427171717171(1)13337731717(1)22

232323232(1)1162292931231(1)22231291222962323232323232(1)133

1311111111111112121

60602353535 18

1213121323243723...1

43229

32. 设p是奇素数，a是整数，(a, p) = 1，证明同余方程ax2 + bx + c ≡

b24ac。

0 (mod p)的解数是1p证明因为(4a, p) = 1，则原方程等价于

4a2x2 + 4abx + 4ac ≡ 0 (mod p)，

即

(2a + b)2 ≡ b2 – 4ac (mod p)。

若若若b24ac2，方程有两解。 b – 4ac是模p的二次剩余，则1pb24ac20，方程无解。 b – 4ac是模p的二次非剩余，则1pb24ac21，方程仅有一个解。 p | b – 4ac，则1p235. 求满足同余方程E：y2 ≡ x3 + x + 1 (mod 19)的所有点。

解令f(x) = x3 + x + 1，有

f(0) = 1，解为y = 1, 18；

31f(1) = 3，，无解；

1（由定理3.6）1931182f(2) = 11，，解为1（由定理3.5）19111112431f(3) ≡ 12，1，无解；

19191933y = 7, 12；

f(4) ≡ 12，无解。

171921，解为y = 6, 13；

f(5) ≡ 17，1917171427719521，无解；

f(6) ≡ 14，19191919775f(7) ≡ 9，解为y = 3, 16；

19

82f(8) ≡ 8，1，无解；

19193f(9) ≡ 17，解为y = 6, 13；

f(10) ≡ 4，解为y = 2, 17；

13192331f(11) ≡ 13，1，无解；

19131313133f(12) ≡ 12，无解；

72f(13) ≡ 7，1，无解；

197f(14) ≡ 4，解为y = 2, 17；

f(15) ≡ 9，解为y = 3, 16；

f(16) ≡ 9，解为y = 3, 16；

10254f(17) ≡ 10，1，无解；

19191951f(18) ≡ 18，，无解。

1（由推论3.3）19因此，同余式y2 ≡ x3 + x + 1 (mod 19)的所有解为

(0, 1), (0, 18), (2, 7), (2, 12), (5, 6), (5, 13), (7, 3), (7, 16), (9, 6), (9,

13), (10, 2), (10, 17), (14, 2), (14, 17), (15, 3), (15, 16), (16, 3), (16, 16)。

20

第4章课后作业答案

习题4：1, 2(1) a = 2, 3, 9。

1. 证明2是模29的原根。

证明第一种方法：

因为(2, 29) = 1，υ(29) = 28 = 2 × 2 × 7，ord229的可能值是1, 2, 4,

7, 14, 28。

逐个验证2d (mod 29)。

21 ≡ 2, 22 ≡ 4, 24 ≡ 16, 27 ≡ 12, 214 ≡ 28, 228 ≡ 1。

所以ord229 = 29 = υ(29)，2是模29的一个原根。

第二种方法：

υ(29) = 28 = 2 × 2 × 7，υ(m)的所有不同素因子是q1 = 2，q2 = 7，计算

228/22≢ 1 (mod m)，228/716≢ 1 (mod m)。

根据定理4.17，所以，2是模29的原根。

2. 计算下列整数的阶ordam：

(1) m = 13, a = 2, 3, 6；

解 (1) φ(13) = 12，所以Z13中非零元素的阶只可能是1, 2, 3, 4, 6, 12。

当a = 2时，21 ≡ 2 (mod 13), 22 ≡ 4 (mod 13), 23 ≡ 8 (mod 13), 24 ≡ 3

(mod 13), 26 ≡ 12 (mod 13), 212 ≡ 1 (mod 13)。所以ord213 = 12。

当a = 3时，31 ≡ 3 (mod 13), 32 ≡ 9 (mod 13), 33 ≡ 1 (mod 13)。所以ord313 = 3。

21

当a = 6时，61 ≡ 6 (mod 13), 62 ≡ 10 (mod 13), 63 ≡ 8 (mod 13), 64 ≡

9 (mod 13), 66 ≡ 12 (mod 13), 612 ≡ 1 (mod 13)。所以ord613 = 12。

3. 设素数p = 4k + 1，证明：a是模p的原根当且仅当– a是模p的原根。

证明假设a不是模p的原根，则

当且仅当存在p – 1的素因子q，有

(a)p1qap1q1(modp)。

当且仅当– a也不是模p的原根。

9. 设p是奇素数，n ≥ 2，a是模pn的原根，证明a是模p的原根。

证明假设a不是模p的原根，并设a模p的阶是d, d < p – 1，则

ad ≡ 1 (mod p)。

即存在某整数k，有

ad = kp + 1。

于是，

(ad)p = (kp + 1)p =

((ad)p)p = (kp + 1)p =

1。

…

(ad)pn1p1p1(kp)pC1...Cp(kp)1

p(kp)= k1p2 + 1。

p1p1(kp)pC1...Cp(kp)1

p(kp)= (k1p2 + 1)p = k2p3 +

kn1pn1。

n1所以，(ad)p1(modpn)。

这与已知a是模pn的原根相矛盾。

22

14. 定义一个函数µ（Möbius函数）：

1n1，

(n)0n含平方因数，l(1)npl不同素数的乘积。设A为模p的全体原根之和，证明A ≡ µ(p – 1) (mod p)。

证明

15. 求出模31的一个原根g，分别写出指数表indgi, i = 1, 2, …, 30。

解取g = 3，由于υ(31) = 30 = 2 × 3 × 5，只要验证

36,

310,

315≢ 1 (mod 31)，可确定3是模31的原根。

35

26

36

16

37

17

38

20

39

29

310

25

gk

gk (mod

31)

gk

gk (mod

31)

gk

gk (mod

31)

31

3

32

9

33

27

34

19

311

13

312

8

313

24

314

10

315

30

316

28

317

22

318

4

319

12

320

5

321

15

322

14

323

11

324

2

325

6

326

18

327

23

328

7

329

21

330

1

所以，ord31 = 0, ord32 = 24, ord33 = 1, ...。

23

第5章课后作业答案

习题5：9,17, 18； 21选作。

定义5.1 设m是一个合数，如果存在整数a ((a, n) = 1)使得同余式

am-1 ≡ 1 (mod m)

成立，则m称为对于基a的拟素数。

9. 证明：45对于基17和基19的拟素数。

证明因为(17, 45) = 1，45 = 3 × 3 × 5是合数，

且 1744 ≡ 1 (mod 45)，1944 ≡ 1 (mod 45)，

所以，45是对于基17和基19的拟素数。

定义5.3 设m是一个奇合数，如果整数a ((a, n) = 1)使得同余式

m1a2a(modm)

m成立，则m称为对于基a的欧拉拟素数。

17. 证明：561是对于基2的欧拉拟素数。

证明 561 = 3 × 11 × 17是合数，

22221

56131117且

561-122（1mod561）。

即，561-1222（）

mod561561 24

所以，561是对于基2的欧拉拟素数。

18. 如果整数m是对于基b1, b2的欧拉拟素数，证明m是对于基b1b2的欧拉拟素数。

证明整数m是对于基b1, b2的欧拉拟素数，则

b1m12m1bb1(modm),

b222(modm)，

mm所以，(b1b2bb12(modm)。

mmbbbb由雅可比符号的性质，1212。

mmmm1)2故，m是对于基b1b2的欧拉拟素数。

定义5.4 设m为奇合数，有表示式m – 1 = 2st，其中t为奇数，整数a与m互素，如果有

at ≡ 1 (mod m)

成立，或者存在一个整数r, 0 ≤ r < s使得

a2t1(modm)

r成立。则m称为对于基a的强拟素数。

21. 证明1373653是对于基2和3的强拟素数。

证明 1373653 = 829 × 1657是合数，且(1373653, 2) = (1373653, 3) =

1。

1373653 – 1 = 1373652 = 22 × 343413 = 22 × 33 × 7 × 23 × 79。

(1) 验证

25

2343413 ≡ 890592 ≢ 1 (mod 1373653)，

22×343413

≡ – 1 ≢ 1 (mod 1373653)，

所以，1373653是对于基2的强拟素数。

关于计算2343413 (mod 1373653)，

2300000240000230002400213(mod1373653)

8192

((240)5)2

(((2100)5)2)3

((((2400)5)2)5)2

((((23000)5)2)5)2

(2) 验证

3343413 ≡ 1 (mod 1373653)，

所以，1373653是对于基2的强拟素数。

关于计算3343413 (mod 1373653)，

3300000340000330003400313(mod1373653)

220670

((340)5)2 307621

((((350)2)5)2)3 802977

((((3400)5)2)5)2 278052

((((33000)5)2)5)2 87988

26

第6章课后作业答案

习题6：1, 3, 9, 15, 26, 29。

1. 如果a, b是群G中的任意元素，证明(ab)-1 = b-1a-1。

证明 (ab)b-1a-1 = a(bb-1)a-1 = aea-1 = aa-1 = e。

b-1a-1(ab) = b-1(a-1a)b = b-1eb = b-1b = e。

3. 设集合G = {(a, b) | a, b为实数且a ≠ 0}，规定(a, b) ◦ (c, d) = (ac, ad

+ b)，证明G对所规定的运算“◦”构成群。

证明 (1) 封闭性

对任意的(a, b), (c, d) ∈ G, 有

[(a, b) ◦ (c, d)] = (ac, ad + b)

其中，ac, ad + b为实数，且ac ≠ 0。

所以，(ac, ad + b) ∈ G。

(2) 结合律

对任意的(a, b), (c, d), (e, f) ∈ G,

[(a, b) ◦ (c, d)] ◦ (e, f) = (ac, ad + b) ◦ (e, f) = (ace, acf

+ ad + b)，

(a, b) ◦ [(c, d) ◦ (e, f)] = (a, b) (ce, cf + d) = (ace, acf

+ ad + b)；

所以，[(a, b) ◦ (c, d)] ◦ (e, f) = (a, b) ◦ [(c, d) ◦ (e, f)]。

(3) 单位元

设 (a, b) ◦ (c, d) = (ac, ad + b) = (a, b)，则

27

ac = a, ad + b = b，

于是，

c = 1, d = 0。

且 (1, 0)(a, b) = (a, b)。

(4) 逆元

设(a, b) ◦ (c, d) = (ac, ad + b) = (1, 0)，则

ac = 1, ad + b = 0，

于是，

c = a-1，d = – ba-1。

且(a-1，–a-1b)(a, b) = (1, 0)。

综上所述，G对所规定的运算“◦”构成群。

9. 设a, b是群G中的元素，证明：a与a-1的阶相同；相同；对任意的c ∈ G，cac-1的阶与a的阶相同。

证明 (1) 设a的阶为m，a-1的阶为n。

则(an)-1 = (a-1)n = e, 所以an = e。

因为a的阶为m，所以m | n。

同理，(a-1)m = (am) -1 = e。

因为a-1的阶为n，所以n | m。

因此，m = n。

(2) 设ab的阶为m，ba的阶为n，

则(ba)n = ba × ba × …× ba = e。

28

ab与ba的阶

于是，等式两边同时左乘以a, 右乘以b，则有a × ba × ba × …×

ba × b = ab，

即(ab)n+1 = ab，

得(ab)n = e。

因为ab的阶为m，则m | n。

同理，(ba)m = ab ×ab × …×ab = e，

于是，等式两边同时左乘以b, 右乘以a，则有b × ab ×ab × …×ab × a

= ba，

即(ba)m+1 = ba，

得(ba)m = e。

因为ba的阶为n，则 n | m。

故，ab与ba的阶相同。

(3) 设a的阶为m，cac-1的阶为n，

则(cac-1)m = cac-1 ×cac-1 × …×cac-1 = camc-1

= cec-1= e，

因为cac-1的阶为n，所以n | m。

进一步，由(cac-1)n = e，则canc-1

= e，

于是，等式两边同时左乘以c-1，有乘以c，得

an

= c-1c

= e。

因为a的阶为m，所以m | n。

故，cac-1的阶与a的阶相同。

定理6.12 设N是G的子群，则下面条件等价：

(1) 对任意的a ∈ G，有aN = Na；

29

(2) 对任意的a ∈ G，有aNa-1 = N；

(3) 对任意的a ∈ G，有aNa-1 ⊆ N。

定义6.14 设N是群G的一个子群，我们称N为群G的正规子群（记为NG），如果它满足定理6.12的条件。

15. 设G是群，Cent(G) = {a ∈ G | ab = ba，对任意的b ∈ G}。证明：Cent(G)是G的正规子群。

证明 (1) 证明Cent(G)是G的子群。

对任意的a, b ∈Cent(G)，以及任意的c ∈ G，有

ab-1c = a(c-1b)-1 = a(bc-1)-1 = acb-1 = c ab-1，

所以，ab-1∈Cent(G)。

因此，Cent(G)是G的子群。

(2) 证明Cent(G)是G的正规子群。

设c为群G的任意元素，则对于cCent(G)c-1中的任意元素cac-1，a ∈Cent(G)，有

cac-1 = acc-1 = a ∈Cent(G)。

所以，cCent(G)c-1 ⊆ Cent(G)。

故，Cent(G)是G的正规子群。

17. 如果H ≤ G，| G : H | = 2，证明H是G的正规子群。

证明因为，H ≤ G， | G : H | = 2，

所以，子群H在G中的左陪集有H, aH，其中a∈G，a∉H。

另外，子群H在G中的右陪集有H, Ha。

30

又因为，G = H∪aH = H∪Ha，

所以，多任意的a∈G，，aH = Ha，H是G的正规子群。

26. 若G是一个素阶群，证明G是循环群。

证明设群G的阶为素数p，则群G中的任意元素a的阶是1或p。

若a ≠ e，则| a | = p，所以a, a2, a3, …, ap = 1是群G中的不同元素。

又因为| G | = p，

因此G = {a, a2, a3, …, ap} = 是循环群。

29. 设G´是循环群G的同态像，则G´也是循环群。

证明设循环群G = ，υ是G到G´的同态。

由定理6.13的(4)，G´也是群。

对于G´中的任意元素b，存在某个整数k使得，

υ(ak) = b。

即υ(a)k = b。

所以，G´中的任意元素是υ(a)的幂的形式。

即G´= <υ(a)>是循环群。

31. 设1234567812345678，，在51432867731524861234567815143286752543178611234567852543178651432867

2345678

14328672345678

1432867S8中计算σ2, τ2, σ-1, τ-1, στ, τσ。

178617123787313526481773152486

1234567881723564

51432867112345678

1234567825431786

73152486112345678

1234567835264817

12345678123514328677311234567864521378

12345678123731524865141234567827513648

12342534352648212345645678

2. 设R是有单位元的环，证明：R关于a ◦ b = a + b – ab, a⊙b = a + b

(a⊙b)⊙c = (a + b – 1) ⊙c = a + b + c – 2,

a⊙(b⊙c) = a⊙(b + c – 1) = a + b + c – 2;

a⊙(– a + 2) = a + (– a + 2) – 1 = 1,

(– a + 2) ⊙a = (– a + 2) + a – 1 = 1.

(2) 运算◦满足结合律

(a ◦ b) ◦ c = (a + b – ab) ◦ c = a + b + c – ab – ac – bc + abc,

a ◦ (b ◦ c) = a ◦ (b + c – bc) = a + b + c – ab – ac – bc + abc,

(3) ◦对⊙满足分配率

(a ⊙ b) ◦ c = (a + b – 1) ◦ c = a + b – 1 - ac - bc + 2c

(a ◦ c) ⊙( b ◦ c) = (a + c – ac)⊙(b + c – bc) = a + c – ac + b + c –

33

bc – 1;

c ◦ (a ⊙ b) = c ◦ (a + b – 1) = a + b – 1 – ca – cb + 2c

(c ◦ a) ⊙(c ◦ b) = (c + a –ca)⊙(c + b –cb) = c + a –ca + b + c – cb –

1;

所以，(R, ⊙, ◦)是一个环。

3. 在环R中，(a + b)n (a, b ∈ R)的展开式是否适用牛顿二项定理？在什么条件下适用？

证明牛顿二项定理公式为(a + b) = a +

n1Cnnn1n-1Cnab +

2n-22Cnab + … +

abn-1 + bn。

而(a + b)n = (a + b) (a + b)... (a + b) = (a2 + ab + ba + b2) (a + b)... (a +

b)

当R为非交换环时，ab未必等于ab，上式未必成立。

若R为交换环时，ab = ba。于是

(a + b)n = (a + b) (a + b)... (a + b)

= (a2 + 2ab + b2) (a + b)... (a + b)

6. 证明：若环R中没有零因子，则环R中的消去律成立。

证明设ac = bc, 其中a, b c ∈ R, c ≠ 0，则(a – b)c = 0，因为R中无 34

零因子，且c ≠ 0，所以只有 a – b = 0，即 a = b，消去率成立。

7. 若环{R, +, ·}中非零元在乘法运算下构成群，则称环{R, +, ·}为除环。证明：除环一定有单位元且除环中无零因子。

证明因为R的非0元素构成群，所以存在单位元e，对任意R的中非0元素b，有be = eb = b。

设除环R存在零因子，则存在a ≠ 0, b ≠ 0，使得ab = 0。

因为a ≠ 0，所以存在a的逆元a-1，于是

a-1ab = eb = b = 0，与假设b ≠ 0相矛盾。

所以，除环R中无零因子。

4. 如果环R中的每个元素都满足a2 = a，则称R为布尔环，证明：布尔环中的任意元素a, b都满足a + a = 0, ab = ba。

证明 a + a = (a + a)2 = a2 + a2 + 2a2 = 4a2

所以，a + a = 0。

a + b = (a + b)2 = a2 + b2 + ab + ba

1. 设F = {a + bi | a, b ∈实数域R}，证明：F关于数的加法和乘法构成一个域。

证明 (1) 加法群；

(2) 非零元素构成乘法交换群；

(3) 乘法对加法满足分配率。

9. 证明：(Zm, +, ·)是域的充要条件是m为素数。

证明 “<=”

如果m为素数，证明(Zm, +, ·)是一个域（域的三个条件）。

“=>” 反证法。

已知(Zm, +, ·)是域。

假设m = m1m2（1 < m1, m2 < m）为合数，则m1 ∈ Zm*，但m1不存在模m的逆元。

故，m为合数时，(Zm, +, ·)不是域。这与已知矛盾。

16. 令f(x) = x4 + 3x2 + 2x + 1, g(x) = x7 + x5 + 5x4 + 2x3 + 3x2 + x + 1，计算(f(x), g(x))及m(x), n(x)，使得

(f(x), g(x)) = m(x)f(x) + n(x)g(x)。

解 g(x) = f(x)(x3 – 2x + 3) + 5x3 – 3x – 2;

f(x) = (5x3 – 3x – 2)x/5 + x2/18 + 12x/5 + 1;

36

22. 证明：域F上代数元的和、差、积、商仍为F上的代数元。

证明假设α, β是F上的代数元，则β是F(α)上的代数元。

所以，F(α)是F的有限次扩域，F(α)(β)是F(α)的有限次扩域。

又因为[F(α, β) : F] = [F(α)(β) : F(α)] [F(α) : F]

所以，F(α)(β)是F的有限次扩域，即是F的代数扩域，F(α, β)中的元素都是F上的代数元。

α与β的和、差、积、商都是F(α, β)中的元素，因此都是F上的代数元。

27. 求多项式x4 – 2 ∈ Z5[x]的分裂域。

解 x4 – 2 = (x2 +2)( x2 –2) = (x +

42i)(x –42i)(x +

42)(x –42)

故，Z5(42i,42)是多项式x4 – 2 ∈ Z5[x]的分裂域。

18. 设f(x), g(x)是域F上的多项式，则

f(x)g(x) = [f(x), g(x)](f(x), g(x))。

解设(f(x), g(x)) = d(x), f(x) = f1(x)d(x), g(x) = g1(x)d(x)，且(f1(x), g1(x))

= 1。

则[f(x), g(x)] = f1(x)g1(x)d(x)。

所以，f(x)g(x) = [f(x), g(x)](f(x), g(x))。

37

定义7.7 设R为交换环，称R为一个整环，如果R有单位元，但无零因子。

17. 如果R是整环，证明R[x]也是整环，并且∀f(x), g(x) ∈ R[x]，若f(x) ≠ 0, g(x) ≠ 0，则f(x)g(x) ≠ 0，deg(f(x)g(x)) = degf(x) + deg(g(x))。

证明 1. R[x]在多项式加法与乘法运算下构成多项式环。

设任意f(x) = fnxn + … + f1x + f0, g(x) = gmxm + … + g1x + g0, h(x) = hkxk

+ … + h1x + h0 ∈ R[x]。

(1) R[x]是加法群。

(a) 加法结合律

[f(x) + g(x)] + h(x) = f(x) + [g(x) + h(x)]；

(b) 0是加法零元

(c) f(x)的负元是 – f(x) = –fnxn – …– f1x – f0；

(2) 乘法对加法满足分配率

f(x)[g(x) + h(x)] = f(x)g(x) + f(x)h(x)；

[g(x) + h(x)]f(x) = g(x)f(x) + h(x)f(x)；

2. R[x]是交换环

f(x)b(x) = fnbmxm+n + (fn-1gm + fngm-1)xm+n-1 + … + (f0g1 + f1g0)x + f0g0

= gmfnxm+n + (gmfn-1 + gm-1fn)xm+n-1 + … + (g1f0 + g0f1)x + g0f0

设f(x) ≠ 0, g(x) ≠ 0，不妨设两个多项式的首项系数fn ≠ 0, gm ≠ 0，则f(x)g(x) = fngmxm+n + …≠ 0。

进一步，若f(x) ≠ 0, g(x) ≠ 0，degf(x)g(x) = n + m = deg f(x) + deg

g(x)。

39

第9章课后作业答案

习题9：1, 2, 10（乘法表做一部分即可）, 14（至少计算到g(x)9）, 31（选做）。

1. 写出下面各域的特征：

GF(4)，GF(5)，GF(32)，GF(49)，GF(81)。

解因为| GF(4) | = 22, Char(GF(4)) = 2;

因为| GF(5) | = 51, Char(GF(4)) = 5;

Char(GF(32)) = 2, Char(GF(49)) = 7, Char(GF(81)) = 3。

2. 若f(x)为Z2上的多项式，证明(f(x))2 = f(x2)。

证明设f(x) = anxn + an-1xn-1 + ... + a1x + a0，

则(f(x))2 = f(x)f(x) = (anxn + an-1xn-1 + ... + a1x + a0)(anxn + an-1xn-1 + ... +

a1x + a0)

= an2x2n + (anan-1 + an-1an)x2n-1 + (anan-2 + an-1an-1 + an-2an)x2n-2

+ … + (a2a0 + a1a1 + a0a2)x2 + (a1a0 + a0a1)x + a02，

在GF(2)上，an2 = an, 2anan-1 = 0, …, anan-2 + an-1an-1 + an-2an = an-12 =

an-1, …, a2a0 + a1a1 + a0a2 = a1, a02 = a0。

所以，(f(x))2 = anx2n + an-1x2(n-1) + ... + a1x2 + a0 = f(x2)。

10. 在F2[x]中利用不可约多项式x4 + x + 1构造一个具有16个元素的有限域，并给出乘法表。

40

解记p(x) = x4 + x + 1，因为p(x)是F2[x]中的不可约多项式，所以F2[x]/(p(x))是一个4次扩域，且含有24 = 16个元素。

这16个元素的形式为a = a0 + a1x + a2x2 + a3x3, a0, a1, a2, a3 ∈ {0,

1}，即这16个元素为

0, 1, x, x + 1,

x2, x2 +1, x2 + x, x2 + x + 1,

x3, x3 + 1, x3

+ x, x3 + x + 1,

x3 + x2, x3 + x2 + 1, x3 + x2 + x, x3 + x2 + x + 1。

14. 已知m(x) = x8 + x4 + x3 + x + 1是F2[x]中的不可约多项式，g(x) = x

+ 1是域F28

F2[x]/(m(x))的本原元，求g(x)t, t = 1, 2, …, 32。

解对于t = 1, 2, ..., 6，计算gt(x) (mod x8 + x4 + x3 + x + 1)：

g0(x) = 1, g1(x) = x + 1, g2(x) = x2 + 2x + 1 = x2 + 1,

g3(x) = x3 + x2 + x + 1, g4(x) = x4 + 1, g5(x) = x5 + x4 + x + 1,

g6(x) = x6 + x4 + x2 + 1, g7(x) = x7 + x6 + x5 + x4 + x3 + x2 + x + 1, g8(x)

= x8 + 1 = x4 + x3 + x,

g(x)9 = x5 + x3 + x2+ x,

g11(x) = x7 + x4 + x2 + x, g16(x) = x6 + x4 + x3 + x2 + x + 1, g32(x) = x7

+ x6 + x5 + x2 + 1,...

42

43

第10章课后作业答案

习题10：1, 5（或者验证例10.4中的表10.3、或者验证例10.6）

1. 验证例10.4中的结果(5, 22) + (16, 27) = (13, 6)，2(5, 22) = (14, 6)；并计算(8, 19) + (17, 19)以及2(8, 19)。

解设P = (5, 22), Q = (16, 27)，

x4 = k2 – x1 – x2 (mod p) = 121 – 5 – 16 (mod 29) =

13；

y4 = k(x1 – x4) – y1 (mod p) = 11(5 – 13) – 22 (mod

x4 = k2 – x1 – x2 (mod p) = 169 – 5 – 5 (mod 29) =

14；

y4 = k(x1 – x4) – y1 (mod p) = 11(5 – 14) – 22 (mod

29) = 6。

所以，2P = (14, 6)。

44

设P = (8, 19), Q = (17, 19)，计算P + Q:

k =

y2y1x2x1=1919 = 0

165x4 = k2 – x1 – x2 (mod p) = 0 – 8 – 17 (mod 29) = 4；

y4 = k(x1 – x4) – y1 (mod p) = – 19 (mod 29) = 10。

x4 = k2 – x1 – x2 (mod p) = 252 – 8 – 8 (mod 29) =

0；

y4 = k(x1 – x4) – y1 (mod p) = 25(8 – 0) – 19 (mod

29) = 7。

所以，2P = (0, 7)。

5. 列出E23(1, 1)的所有点。

解 E23(1, 1)对应的椭圆曲线方程是y2 = x3 + x + 1。

验证Δ = – 16(4a3 + 27b2) = 10 ≠ 0。

E23(1, 1)的所有点是(0, 1), (0, 22), (1, 7), (1, 16), (3, 10), (3, 13), (4,

0), (5, 4), (5, 19), (6, 4), (6, 19), (7, 11), (7,12 ), (9, 7), (9, 16), (11, 3), (11,

20), (12, 4), (12,19), (13, 7), (13, 16), (17, 3), (17, 11), (18, 3), (18,20 ),

+ c1x + c2x2 + … + cn-1xn-1

+ cnxn，

其中常数ci = 0或1 (i = 1, 2, …, n), c0 = cn = 1，在LFSR的电路图中，可用开关的闭合实现ci = 0或1，如图12.3。

输出序列

a1a0cn-1cn⊕⊕...⊕⊕图12.3 n级线性反馈移位寄存器

2. 四级线性移位寄存器对应的特征多项式是f(x) = x4

+ x3+ 1，其初始状态为(a0 a1 a2 a3) = (0 1 0 1)，画出该LFSR的逻辑框图，并求其输出序列与周期。

解特征多项式f(x) = 1 + x3 + x4对应的LFSR的逻辑框图是

a3a2a1a0⊕⊕...⊕⊕

其输出序列为…

周期T = 15。

GF(2)上的n级m序列{ai}的2n位连续比特(at, at+1, …, at+2n-1)可以写成n个n维向量的形式

At = (at at+1 .. at+n-2 at+n-1)

46

At+1 = (at+1 at+2 .. at+n-1 at+n)

…

At+n-1 = (at+n-1 at+n .. at+2n-2 at+2n-1)

令

at1...atn1ataa...at2tnAt1，

...atn1atn...at2n2显然，有

cnatnacAn1tn1。

ca1t2n1 (12.15)

5. 已知某5级LFSR的输出序列为1，求其反馈关系式的系数。

a0a1a2a3a4a5a6a7a8a9

10A011001101101101，于是

1010010010011101求得A111110110,

010101c500c411c30

0c200c11解

47

于是

c501c410cA100。

3c20110c1

48

第12章课后作业答案

习题12：3, 5。

3. 证明：模乘法a · b (mon n)的比特计算量为O((log n)2)。

证明设t = | a | = | b | = | n | = lon n（如果a 或b大于n，先执行模n运算），< a >2 = atat-1…a1a0, < b >2 = btbt-1…b1b0, < n >2 = ntnt-1…n1n0。

a · b约需要t2次比特加法运算，事实上

atat1...a1a0btbt1...b1b0b0atb0at1...b0a1b0a0b1atb1at1...btatbtat1...bta1bta0c2tc2t1...c1c0

上述比特级乘法运算得到的结果为a · b，共执行约t2次加法运算。

接下来统计模n的运算量，

c2tntnt1...n1n0c2t1dt

dt-1

… d1

d0

...ctct1...c1c0dtntdtnt1...dtn0e2t1...1...r1r0

上述带余除法运算得到的结果为a · b (mon n)，共执行约t2次加法运算。

因此，模乘法a · b (mon n)的比特计算量为O((log n)2)。

5. 给出模逆a-1 (mod n)算法并分析其计算复杂度。

49

更多推荐

整数,证明,存在,剩余

本文发布于:2024-01-04 06:42:34，感谢您对本站的认可！

本文链接:https://www.sxydy.com/post/shijuan/4ca43477bf7ee5472da7ee7c289b2a90.html

整数证明存在剩余

上一篇：最新《信息安全数学基础》课程教学大纲资料
下一篇：信安数学基础---课后习题答案(2022修订版)- 第2版

发布评论取消回复

评论列表（有 0 条评论）

《信息安全数学基础》部分课后习题答案

发布评论取消回复

最近发表

热门文章

标签列表

《信息安全数学基础》部分课后习题答案

相关文章

发布评论取消回复

最近发表

热门文章

标签列表