信息安全数学基础 课后习题答案,裴定一,徐详 编著 ,人民邮电出版社.pdf

1 ? ? 1.11111111101, 3FD 1.22 1.3374133280 1.4510 11766 737 8142 = 6. 1.5?a = pt1a1,b = pt2b1,?(p,a1) = (p,b1) = 1,?ordp(a) = t1,ordp(b) = t2.?t1 t2,?a + b = pt2(pt1t2a1+b1)?ordp(a + b) t2=minordp(a),ordp(b),? t1 t2,?pt1t2a1+ b16= 0,?(p,pt1t2a1+ b1) = 1,? 1.61,2, ,n?pi? h n pi i ,?1,2, ,n?pi? ?pi+1? h n pi i h n pi+1 i ,? ordp(n!) = X i=1 i( h n pi i h n pi+1 i ) = X i=1 h n pi i 1.7?2|n(n + 1)(2n + 1)?n = 3s + r,0 r 0?x,y Z? ax + by = (a,b) ? amx + bmy = (a,b)m. ?c?c|am,c|bm,?c|(a,b)m?(am,bm) = (a,b)m? 1.9?(a1,a2, ,an) = d,(a1,a2, ,as) = d1,(as+1, ,an) = d2,(d1,d2) = d3, ?d|d3?d3|d1,d3|d2?d3|ai,i = 1,2 ,n?d3|d? ?d,d3?d = d3? 1.10?a1,a2, ,an = m,a1,a2, ,as = m1,as+1, ,an = m2,m1,m2 = m3, ?m1|m3,m2|m3?ai|m3,i = 1,2 ,n?m|m3? ?ai|m,i = 1,2 ,n?m1|m,m2|m?m3|m?m = m3? 1.11?(a,c) = 1?x,y? ax + cy = 1 ?abx + cby = b?c|ab?c|b? 1.12 (1) 3k + 1?k?2h?3k + 1 = 6h + 1? 2 (2) 3k 1?k?2h?3k 1 = 6h 1? 1.13? n p ? n p = p1p2, ,pt,t 2?p?n = pp1p2pt n 1 3 n 1 3n 1 3 |z t+1 n? 1.14?n m?Fn= (Fm 1)2 nm + 1?d|Fn,d|Fm?d|2?d? ?Fn?Fn? ? 1.15 p = 2k + 1?p = (k + 1)2 k2? 1.16?a = 2u,b = 2v?u,v?a + b = 2(u + v) = 4s(?u + v?)? (a + b,4) = 4? 1.17 100,10,10; 100,20,10; 100,50,10; 50,20,10; 100,50,20; 50,20,20; 50,50,20; 100,100,10. 1.18 h n pj i = ha0 + a1p + + aj1pj1 pj + aj+ aj+1p + + akpkj i =aj+ aj+1p + + akpkj? ? h n pj i p h n pj+1 i = aj ? 2.1 x 27 (mod 30)? 2.2 x 157 (mod 315)? 2.3 x 67 (mod 90)? 2.4 (1) 1,3,5,7,9,11,13,15,17,19,21? (2) 0,2,4,6,8,10,12,14,16,18,20? 2.5?t0,t1, ,tm1?m?ti i (mod m)? ti= mqi+ i,i = 0,1, ,m 1 ?m?t0,t1, ,tm1? 2.6?16?1?3?5?7?9?11?13?15? ?18?1?5?7?11?13?17? 2.7 m(n) 1 (mod n)?n(m) 1 (mod m)? n|m(n) 1,m|n(m) 1. ? n|m(n)+ n(m) 1,m|m(n)+ n(m) 1. ?(m,n) = 1?mn|m(n)+ n(m) 1?m(n)+ n(m) 1 (mod mn). 2.9?m = pt1 1 ptr r qk1 1 qkl l ,n = uk1 1 ukj j qv1 1 qvl l ? 3 s = q1ql,(s) = (q1 1)(ql 1), (m) = m(1 1 p1 )(1 1 pr )(1 1 q1 )(1 1 ql ), (n) = n(1 1 u1 )(1 1 uj )(1 1 q1 )(1 1 ql ), ? (mn) (m)(n) = 1 (1 1 q1)(1 1 ql) = q1ql (q1 1)(ql 1) = s (s) 2.10 (1)?n = pt1 1 ptr r ,p1 p2 pr.?(n) = n(1 1 p1 )(1 1 pr ),? (n) = 1 2n r Y i=1 (1 1 pi ) = 1 2 r = 1,?p1= 2 n = 2t1? (2)?(1),(n) = 1 3n r Y i=1 (1 1 pi ) = 1 3 r = 2,p1= 2,p2= 3 n = 2t1 3t2? 2.11?x,y?3x2+ 2 2 (mod 3)?y2 0,1 (mod 3)? 2.12 p?p|Ci p,0 i p ? (a + b)p ap+ C1 pa p1b + + Cp1 p abp1+ bp, ap+ bp(mod p) 2.13?n = pt1 1 ptr r ? P d|n (d) = r P i=0(1) iCi r= 0 2.14?n = pt1 1 ptr r ,?(n) = n(1 1 p1 )(1 1 pr ),?p1 pr? (n)|n (p1 1)(pr 1)|p1pr n = 1,2t1 3t2,t 1,t2 0? 2.15?ap bp(mod p) a b (mod p) ap bp(mod p2) 2.16 (1 + ap)p l2 = 1 + pl2 ap + C2 pl2(ap) 2 + + (ap)p l2 ?pl2|Ci pl2,i = 2, ,p l2 1 ?(1 + ap)p l2 1 + apl1(mod pl)? 2.17?(x 1)(x p + 1) = xp1+ s1xp2+ + sp2x + (p 1)!(1) ?(x 1)(x p + 1) xp1+ s1xp2+ + sp2x + (p 1) (mod p) ?xp1 (x1)(xp+1) (mod p),?p|(s1, ,sp2),?(1)?x = p? ?(p 1)! = pp1+ s1pp2+ + sp2p + (p 1)!? ?p2|sp2?sp2= p1 P i=1 (p 1)! i ? 2.18 13+23+(m1)3+m3 m3+(13+(m1)3)+ 0 (mod m)2 6 |m; ?m 2 ?3 (mod m)2|m ?2 6 |m?4|m? 2.19?n 0?a (mod pk)?n2 an (mod pk)?n 0 (mod pk)? ?n 6 0 (mod pk)?pk|n(n a) p|n a?p 6 |a p 6 |n?pk|n a? 4 ?n a (mod pk)? 2.20?j2 (m j)2(mod m)? 2.21 (1)?3k 1?3k 1? 3k 1 = s Q i=1(3k i+ 1)vi ?1 s Q i=1 1vi(mod 3),?2 0 (mod 3)? ?4k 1?4k 1? 4k 1 = s Q i=1(4k i 3)ui ?1 1 (mod 4)? ?6k 1?6k 1? 6k 1 = s Q i=1(6k i 5)ui ?1 1 (mod 6)? (2)?4k 1?t?4ki 1,i = 1, ,t? un= t Q i=1(4k i 1) t?; t Q i=1(4k i 1) (4k1 1) t? ? u 1 (mod 4) ?u = 4s+1?w = u2 = 4s1?(1)?w?4v1?4v1|u? ?4v 1|2?4v 1?4ki 1,i = 1,2, ,t? (3)?6k 1?t?6ki 1,i = 1, ,t? un= t Q i=1(6k i 1) t?; t Q i=1(6k i 1) (6k1 1) t? ? u 1 (mod 6) ?u = 6s+1?w = u2 = 6s1?(1)w?6v 1?6v1|u? ?6v 1|2?6v 1?6ki 1,i = 1,2, ,t? ? 3.11,1,1,1,1,1,1 3.3i) ? 5 227 ? = 1,?ii) ? 11 511 ? = 1,?iii)91 = 7 13, ?11 7 ? = ?6 7 ? = 1, ?11 13 ? = ?6 13 ? = 1?iv)6193 = 11 563, ? 5 11 ? = 1, ?14 11 ? = 1? 5 3.4i)p = 1 (mod 5) ii)p = 1,3,7,9 (mod 20) 3.5?p?0?x?p? ?ax + b? p1 P x=0 ?ax + b p ? = 0? 3.6?xp 1 (x 1)(x 2)(x p + 1) (mod p)?(p 1)! 1 (mod p)?Q = 12 22 ? p1 2 ?2 = (1) p1 2(p 1)! (1) p+1 2 (mod p)? 3.7 ?2 p ? = ?1 p ? ?2 p ? = (1) p1 2 (1) p21 8 = 1p 1,3 (mod 8); 1p 5,7 (mod 8) 3.812 32 52 (p 2)2= 1 (1 p) 3 (3 p) (p 2) (2) (1) p1 2 (p 1)! (mod p) (1) p+1 2 (mod p) 3.9?a? 3.10?a = 2s?s? ? = 0? ? a 4ac b ? = ?b a ? (1) a1 2 1b 2 = ?b a ? (1) a1 2 1b 2 = ?a b ? (1) a1 2 1b 2 +a1 2 b1 2 = ?a b ? ? a 4ac b ? = ? 2 4ac b ? s 4ac b ? = (1) b21 8 (1) s1 2 1b 2 ?b s ? = (1) b21 8 (1) s1 2 1b 2 (1) s1 2 b1 2 ?s b ? = (1) b21 8 ?s b ? = ?2s b ? = ?a b ? ? 3.11?j?p j?1 j p1 2 ?3.2? ? 3.12?Legendre? ? 3 2n+ 1 ? = ?2n + 1 3 ? = ?2 3 ? = 1?3?2n+ 1? ?32 n 1 (mod 2n+ 1)?3?2n+ 1?3?2n+ 1 ?2k,k j? ?aij= e? 6.5 a,b G?aabb = abab = e?ab = ba? 6.6 a2= 10 01 , a4= 10 01 , ?a?4? b2= 11 10 , b3= 10 01 , ?b?3? ab = 11 01 , (ab)n= 1n 01 , ?ab? 6.7 (1)?o(a) = m,o(a1) = n,? e = (aa1)m= (a1)m e = (aa1)n= (a)n ?m n,n m?m = n? 8 (2)?o(ab) = m,o(ba) = n?e = (ab)m= a(ba)ma1 (ba)m= e?(ab)n= e? ?m n?n m?m = n? (3)?o(a) = m,o(cac1) = n?(cac1)m= camc1= e?e = (cac1)n= canc1? ?an= e?m n,n m?m = n. 6.8?m = nq + r?0 r n?e = am= anq+r= ar?r = 0?n|m? 6.9 o(ab) = 21? 6.10? 6.11? 6.12 (12),(13),(23) 6.13?t r?(123r)t?1?t+1?(123r)t6= (1)?(123r)r= (1), ?o(123r) = r? 6.14? 6.15?, G?(n) = n?1(n) = n?1(n) = n?1 G? ?G?Sn? 6.16?H G?|H| ? ? ?|G| ?|H| = 1?|H| = |G|?H = e?H = G? 6.17?x G?e 6= a N?xax1 N?xax1= e?x = e? ?xax1= a?xa = ax? 6.18 x G?x N?xN = Nx?x 6 N?G = N xN = N Nx? xN = Nx? 6.19?N H G?N G?NH G?a G?b NH?x N,y H ?b = xy?aba1= (axa1)(aya1) NH?NH G? 6.20?x G?a1Na G?G : a1Na = m?a1Na = N?N G? 6.21 1) x G,G?a G?axa1= (axa1x1)x G,G?G,G G? 2)?(ax)1(xa) = x1a1xa G,G?axG,G = xaG,G?aG,GxG,G = xG,G aG,G? 3)?G/N?a,b G?abN = baN?(ba)1(ab) = a1b1ab N? ?G,G N? 6.22 o(ar) = n (r,n) = n?(ar) = G? 6.23?a G?a 6= e?(a) = G? 6.24?G = (a)?G(m)= (ar)m|r Z?x,y G(m)?x = (ar1)m?y = (ar 2)m ? ?x1y = (ar2r1)m Gm?G(m) G? 6.25 (ab)pq= e?o(ab) = d?d|pq?bpd= (ab)pd= e?q|pd?(p,q) = 1 q|d? ?p|d?pq|d?d = pq? 9 6.26 G = (a),n = kr?H = (ar)?k? 6.27?G = (a)?(ar) = G o(ar) = o(a) = n n (r,n) = n (r,n) = 1? ?ar?(n)? 6.28 G = (a),H G?G/H = (aH)? 6.29?G/C(G) = (aC(G)?x,y G?c1,c2 C(G)?r1,r2? x = ar1c1,y = ar2c2?xy = (ar1c1)(ar2c2) = (ar2c2)(ar1c1) = yx? 6.30 |G| = |G/N| |N| 6.31? 6.32 : 4Z Z5?4Z5fZ Z5?f?f(4k) = k,(k) = k? Ker =Ker( f) = 20k|k Z? 6.33 f?Ker(f)=e?Ker(f) = e?f(x) = f(y)?f(xy1) = f(x)f(y)1= e xy Kerf x = y?f? ? 7.1? 7.2 p?0 i 1?F() : F = p?E = F()? 8.2 F() : F?E : F?m|n? 8.3 R?Q?C?R?2?R?Q?C?R? 11 ?C?Q? 8.4 F(u2) : F|F(u) : F?u2?F?F(u) : F = F(u2) : FF(u) : F(u2)?F(u) : F(u2) 2?F(u) : F = F(u2) : F?F(u) = F(u2)? 8.5?E? ?f(x) = n P i=0 aixi,a0,a1, ,an E?F(a0,a1, ,an) ?a0,a1, ,an?F?F(a0,a1, ,an) : F ? F(a0,a1, ,an)() : F = F(a0,a1, ,an)() : F(a0,a1, ,an) F(a0,a1, ,an)() : F ?F? 8.6 Ei= Q(2 1 3)(i) ?E1: Q(2 1 3) = 2 ?E1: Q= E1: Q(2 1 3)Q(2 1 3) : Q = 3 2 = 6; E2= Q(2 1 3)(3)(i) ?E2: Q(2 1 3) = E2: Q(2 1 3)(3)Q(2 1 3)(3) : Q(2 1 3)= 2 2 = 4; E2: Q = E2: Q(2 1 3)Q(2 1 3) : Q = 4 3 = 12 ? 8.7 K() : F = K() : KK : F= K() : F()F() : F?n|mK() : K? (m,n) = 1?n|K() : K?n K() : K?n = K() : K? 8