信息安全数学基础部分习题答案(2)

又17x≡1（mod21） 所以 特解x0`≡5（mod21）

同余式17x≡14（mod21）的一个特解x0≡14* x0`=14*5≡7（mod21） 所有解为：x≡7（mod21） 2．（1）解：因为（127，1012）=1 | 833 故原同余式有解

又127x≡1（mod1012） 所以 特解x0`≡255（mod1012） 同余式127x≡833（mod1012）的一个特解x0≡833* x0`=833*255≡907（mod1012） 所有解为：x≡907（mod1012） 3．见课本3.2例1 7．（1）解：因为（5，14）=1

由Euler定理知，同余方程5x≡3（mod14）的解为：

(14)-1

x≡5?*3≡9（mod14） （2）解：因为（4，15）=1

由Euler定理知，同余方程4x≡7（mod15）的解为：

(15)-1

x≡4?*7≡13（mod15） （3）解：因为（3，16）=1

由Euler定理知，同余方程3x≡5（mod16）的解为：

(16)-1

x≡3?*5≡7（mod16）

11．证明：由中国剩余定理知方程解为：

x≡a1M1M1`+ a2M2M2`+……+ akMkMk`（mod m）

因为mi两两互素，又中国剩余定理知：MiMi`≡1（mod mi） 又Mi=m/mi 所以（m，Mi）≡1（mod mi）

(mi)

所以MiMi`=Mi?≡（mod mi）

(m1)(m2)(mk)

代入方程解为x≡a1 M1?+ a2 M2?+……+ ak Mk?(mod m) 得证。 12．（1）解：由方程组得：3x+3y≡2(mod7)

6x+6y≡4(mod7) x+y≡-4(mod7) X≡5(mod 7) y≡5 (mod 7)

（2）解：由方程组得：2x+6y≡2(mod7) 2x-y≡2(mod7) 6x+8y≡4(mod7) x-y≡-4(mod7) X≡6(mod 7) y≡3 (mod 7) 13．见课本3.2例4

1000000

14．同课本3.2例3 2≡562（mod1309） 15．（1）解：等价同余式组为： 23x≡1（mod4） 23x≡1（mod5） 23x≡1（mod7）

所以 x≡3（mod4） x≡2（mod5） x≡4（mod7） 所以x≡3*35*3 + 2*28*2 + 4*20*6≡67（mod140） （2）解：等价同余式组为： 17x≡1（mod4） 17x≡1（mod5） 17x≡1（mod7） 17x≡1（mod11） 所以 x≡1（mod4） x≡2（mod5） x≡-3（mod7） x≡7（mod11） 所以x≡1*385*1 + 2*308*2 + (-3)*220*5 + 7*140*7 ≡557（mod1540）

6

19．解：3x+4x+2x+x+x+x+12x+x≡0（mod7）

776426522

左边=(x-x)( 3x+4x+2x+x+3x+4)+ x+2x+2x+15x+5x

6522

所以原同余式可化简为：x+2x+2x+15x+5x≡0（mod7） 直接验算得解为：x≡0（mod7） x≡6（mod7）

3

20．解：f`(x) ≡ 4x+7（mod243）

直接验算的同余式f（x）≡0(mod3)有一解：x1≡1（mod3）

3-1

f`(x1) ≡4*1*7=-1(mod3) f`(x1)≡-1(mod3)

-11

所以t1≡-f（x1）*( f`(x1)(mod3))/3≡1(mod 3) x2≡ x1+3 t1≡4(mod 9)

-12

t2≡-f（x2）*( f`(x1)(mod3))/3≡2(mod 3)

2

x3≡ x2+3 t2≡22(mod 27)

-13

t3≡-f（x3）*( f`(x1)(mod3))/3≡0(mod 3)

3

x4≡ x3+3 t3≡22(mod 81)

-14

t5≡-f（x4）*( f`(x1)(mod3))/3≡2(mod 3)

4

x5≡ x4+3 t4≡184(mod 243)

所以同余式f（x）≡0(mod243)的解为：x5 ≡184(mod 243)

1413119632

第四章 二次同余式与平方剩余

2．解：对x=0,1,2,3,4,5,6时，分别求出y

2

x=0,y≡1(mod7),y≡1,6(mod7)

2

x=4,y≡4(mod7),y≡2,5(mod7) 当x=1,2,3,5,6时均无解

5．解：对x=0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16时，分别求出y

2

x=0,y≡1(mod17),y≡1,16(mod17)

2

x=1,y≡3(mod17),无解

2

x=2,y≡11(mod17),无解

2

x=3,y≡14(mod17),无解

2

x=4,y≡1(mod17),y≡1,16(mod17)

2

x=5,y≡12(mod17),无解

2

x=6,y≡2(mod17),y≡6,11(mod17)

2

x=7,y≡11(mod17),无解

2

x=8,y≡11(mod17),无解

2

x=9,y≡8(mod17),y≡5,12(mod17)

2

x=10,y≡8(mod17),y≡5,12(mod17)

2

x=11,y≡0(mod17),y≡0(mod17)

2

x=12,y≡7(mod17),无解

2

x=13,y≡1(mod17),y≡1,16(mod17)

2

x=14,y≡5(mod17),无解

2

x=15,y≡8(mod17),y≡5,12(mod17)

2

x=16,y≡16(mod17),y≡4,13(mod17)

(17-1)(37-1)/(2*2)

10．解：(1）.（17/37）=(-1)*(37/17)=-1

(2003-1)(911-1)/(2*2)

(4）.（911/2003）=(-1)*(2003/911)=1/3=1

(7-1)(20040803-1)/(2*2)

(6）.（7/20040803）=(-1)*(20040803/7)=1 12．解：（1）.因为（-2/67）=(65/67)=1

7

所以-2是67的平方剩余

2

所以x≡-2(mod67)有2个解。

(37*37-1)/8

（4）.因为（2/37）=(-1)=-1 所以2是37的平方非剩余

2

所以x≡2(mod37)无解。 14．证明：（1）因为p为其素数，模p的所有二次剩余个数为(p-1)/2个，

设为a1, a2, a3, …a(p-1)/2

2222

则a1*a2*a3…a(p-1)/2≡1*2*3…((p-1)/2)(mod p)

≡1*2*3…((p-1)/2)*(-(p-1))*(-(p-2))*…(-(p-(p-1)/2))(mod p)

(p-1)/2

≡1*2*3…((p-1)/2)*(p-(p-1)/2)…*(p-2)*(p-1)(-1)(mod p)

(p-1)/2

≡(p-1)!*(-1)(mod p)

(p-1)/2

≡(-1)*(-1)(mod p) （2.4定理3）

(p+1)/2

≡(-1)(mod p)

(p+1)/2

所以模p的所有二次剩余乘积模p的剩余为(-1)得证。

（2）1，2，3,…p-1为p的一个完全剩余系

(p+1)/2(p-1)/2

1*2*2…*(p-1)≡-1(mod p) ≡(-1)(-1)(mod p)

(p+1)/2

因为模p的所有二次剩余乘积模p的剩余为(-1)

(p－1)/2

所以模p的所有非二次剩余乘积模p的剩余为(-1)

（3）当p=3时，其二次剩余只有1，所以p=3时，模p的所有二次剩余之和模p

的剩余为1

当p>3时，由（1）得a1+a2+a3…+a(p-1)/2≡p(p-1)(p+1)/24(mod p)

因为p为奇素数，所以p只能取3k-1或3k+1形式，代入上式得0

所以当p>3时，模p的所有二次剩余之和模p的剩余为0。

（4）因为模p的所有二次非剩余之和与所有二次剩余之和的和可以被p整除 所以由(3)得，当p=3时，模p的所有二次非剩余之和模p的剩余为-1;

当p>3时，模p的所有二次非剩余之和模p的剩余为0。

(227-1)(7-1)/(2*2)

16．解：(1）.因为（7/227）=(-1)*(227/7)= 1 所以7是227的二次剩余

2

所以x≡7(mod227)有解 (3）.因为11对91的逆元是58

2

所以原同余方程等价于x≡16(mod91) 又16是91的平方剩余

2

所以11x≡-6(mod91)有解 21．证明：应用模重复平方法

013

11=2+2+2

令x=23,b=2,a=1

2

(1)x0=1 a0=a*b≡2(mod23) b1=b≡4(mod23)

2

(2)x1=1 a1=a0*b1≡8(mod23) b2=b1≡16(mod23)

02

(3)x2=0 a2=a1*b2≡8(mod23) b3=b2≡3(mod23) (4)x3=1 a3=a2*b3≡1(mod23)

1111

所以2≡1(mod23) 即23|2-1

23251

47|2-1与503|2-1 应用同样的方法得证。

第五章 原根与指标

8

1．解：因为?(13)=12,所以只需对12的因数d=1,2,3,4,6,12,计算a(mod12)

d

因为2≡2, 2≡4, 2≡8, 2≡3, 2≡-1, 2≡1(mod13) 所以2模13的指数为12；

同理可得：5模13的指数为4，10模13的指数为6。

d

2．解：因为?(19)=18,所以只需对18的因数d=1,2,3,6,9,18计算a(mod12) 因为3≡3, 3≡9, 3≡8, 3≡7, 3≡-1, 2≡1(mod13) 所以3模19的指数为18；

同理可得：7模19的指数为3，10模19的指数为18。

3

3．解：因为?(m)=?(81)=54=2*3,所以?(m)的素因数为q1=2,q2=3,进而 ?(m)/q1=27, ?(m)/q2=18

这样，只需验证：g,g模m是否同余于1。对2，4，5，6…逐个验算：

2718

因为2?1(mod81) 2?1(mod81) 根据5.2定理8得 所以2是模81的原根

stst

7．证明：因为（a, m）=1, 故由ordm(a)=st知：a≡1(mod m) 即(a)≡1(mod m)

ssr

不妨令ordm(a)=r 则a≡1(mod m) 所以st|sr

st

由(a)≡1(mod m)得r|t 即t＝k*r k?N≥1 r≤t 所以sr≤st 所以sr=st 所以r=t

s

所以ordm(a)=t

8．解：存在

举例：如n=7,d=3 因为?(7)=6 d=3|6

(7)3

存在a=2 (2,7)=1, 2?≡1(mod 7) 又2≡1(mod 7)

所以ord7(2)=3 满足条件。

10．证明：因为p为一个奇素数，p-1/2也是一个奇素数

所以?(p)=p-1=2*(p-1)/2 即?(p)的不同素因数为2，p-1/2

(p)/2p-1/2(p)/[(p-1)/2]2

又因为a?=a?1(mod p) a?=a?1(mod p)

根据5.2定理8得a是模p的原根。 15．证明：反证法

m

假设n是一个合数，令ordn(a)=m 则a≡1(mod n)

n-1

因为a≡1(mod n) 所以由5.1定理1得m|n-1 即n-1=k*m 对n-1的所有素因数q，必可找到一个q1使m|((n-1)/q1)

n-1/qm*t

所以a=a≡1(mod n) 与已知条件矛盾，故假设不成立，原结论得证。 16．解：因为d=(n,?(m))=(22,?(41))=(22,40)=2 ind5=22 所以(n,?(m))|ind5，同余式有解

等价同余式为22indx≡ind5(mod40) 即11indx≡11(mod20) 解得：indx=1,21(mod40)

所以原同余式解为x=6,35(mod41)

17．解：因为d=(n,?(m))=(22,?(41))=(22,40)=2 ind29=7 (2,7)=1 所以原同余式无解。

27

18

1

2

3

6

9

18

1234612

第六章 素性检验

1．证明：因为91=13*7是奇合数， (3,91)=1

691-190615

又3=729≡1(mod91) 则3=3≡(3)≡1(mod91) 则91是对于基3的拟素数。

2．证明：因为45=5*3*3是奇合数， (17,45)=1

9

由Euler定理：17≡1(mod5) 17≡1(mod3)

44

所以17≡1(mod3) 所以17≡1(mod45)

45-144411

则17=17≡(17)≡1(mod45) 则45是对于基17的拟素数。 同理45是对于基19的拟素数。

3

10．证明：25=5*5是奇素数 设n=25 n-1=24=2*3 则t=3 (7,25)=1

32*3

7≡18(mod25) 7≡-1(mod25) 所以25是基于7的强拟素数。

15．证明：n=561=3*11*17 为奇素数 （561,2）=1

(n-1)/2(561-1)/2280

b≡2≡2≡1(mod561)

(561*561-1)/8

(b/n)=(2/561)=(-1)=1

280

所以2≡(2/561)(mod561)

所以561是对于基2的Euler拟素数

42

第八章 群

2. 证明：群G是交换群的充要条件是对任意a,b?G，有(ab)2?a2b2。 证明：?必要性：若G是交换群，则对任意a,b?G，有ab?ba，从而

(ab)2?abab?aabb?a2b2。

?充分性：若对任意a,b?G，有(ab)2?a2b2。那么

ba?ebae?a?1(ab)2b?1?a?1a2b2b?1?eabe?ab。

因此群G是交换群。

4. 设G是n阶有限群。证明：对任意元a?G，有a?e。

证明：任取a?G，考虑a生成的循环群a。不妨设a?q。根据拉格朗日定理，有q|n，

qnqkk从而存在正整数k，使得n?qk。因为a?e（否则a?q），所以a?(a)?e?e。

n6. 设G是一个群。记cent(G)?{a?G|(?b?G)ab?ba}。证明：cent(G)是G的正规子群。

证明：首先证明cent(G)是G的子群。任取a1,a2?cent(G)，b?G。计算

?1?1?1?1?1ba1a2?a1ba2?a1(b?1)?1a2?a1(a2b?1)?1?a1(b?1a2)?1?a1a2(b?1)?1?a1a2b。

因此，a1a2?cent(G)，从而cent(G)是G的子群。

1再证明cent(G)是G的正规子群。任取a?G, x?a centG(?)a 。那么存在

?1y?centG(，使得)x?aya?1。由y的交换性，有x?aya?1?aa?1y?ey?y?cent(G)。

10

百度搜索“70edu”或“70教育网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，70教育网，提供经典综合文库信息安全数学基础部分习题答案(2)在线全文阅读。