Giáo trình Mật mã học: Phần 1– HV Bưu chính Viễn thông

Chia sẻ: Thư Minh | Ngày: | Loại File: PDF | Số trang:157

Thêm vào BST

Báo xấu

179
lượt xem 49
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Phần 1 của giáo trình "Mật mã học" trình bày các kiến thức bổ túc về lý thuyết số, đại số trừ tượng, mật mã cổ điển, mật mã khóa công khai. Hi vọng giáo trình sẽ đáp ứng nhu cầu tìm hiểu về mật mã học, là tài liệu tham khảo hữu ích cho giảng viên, sinh viên các trường đại học về kỹ thuật và công nghệ. Mời các bạn cùng tham khảo nội dung chi tiết.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Giáo trình Mật mã học: Phần 1– HV Bưu chính Viễn thông

Lêi nãi ®Çu Trong sù ph¸t triÓn cña x· héi loµi ng−êi, kÓ tõ khi cã sù trao ®æi th«ng tin, an toµn th«ng tin trë thµnh mét nhu cÇu g¾n liÒn víi nã nh− h×nh víi bãng. Tõ thña s¬ khai, an toµn th«ng tin ®−îc hiÓu ®¬n gi¶n lµ gi÷ ®−îc bÝ mËt vµ ®iÒu nµy ®−îc xem nh− mét nghÖ thuËt chø ch−a ph¶i lµ mét ngµnh khoa häc. Víi sù ph¸t triÓn cña khoa häc kü thuËt vµ c«ng nghÖ, cïng víi c¸c nhu cÇu ®Æc biÖt cã liªn quan tíi an toµn th«ng tin, ngµy nay c¸c kü thuËt chÝnh trong an toµn th«ng tin bao gåm: Kü thuËt mËt m· (Cryptography), Kü thuËt nguþ trang (Steganography), Kü thuËt t¹o bãng mê (Watermarking - hay x¨m ®iÖn tö). Kü thuËt mËt m· nh»m ®¶m b¶o ba dÞch vô an toµn c¬ b¶n:BÝ mËt (Confidential), X¸c thùc (Authentication), §¶m b¶o tÝnh toµn vÑn (Integrity). Cã thÓ thÊy r»ng mËt m· häc lµ mét lÜnh vùc khoa häc réng lín cã liªn quan rÊt nhiÒu ®Õn to¸n häc nh−: §¹i sè tuyÕn tÝnh, Lý thuyÕt th«ng tin, Lý thuyÕt ®é phøc t¹p tÝnh to¸n…. N¾m b¾t ®−îc nhu cÇu t×m hiÓu vÒ mËt m· häc, Häc viÖn C«ng nghÖ B−u chÝnh ViÔn th«ng phèi hîp víi Nhµ xuÊt b¶n B−u ®iÖn xuÊt b¶n cuèn gi¸o tr×nh "MËt m· häc" do PGS.TS NguyÔn B×nh chñ biªn. Cuèn gi¸o tr×nh nµy sÏ giíi thiÖu víi b¹n ®äc vÒ c¸c kiÕn thøc to¸n häc c¬ b¶n nh−: lý thuyÕt sè, c¸c cÊu tróc ®¹i sè nh− vµnh nhãm, tr−êng...; mét sè thuËt to¸n mËt m· cæ ®iÓn vµ hiÖn ®¹i; c¸c thñ tôc vµ c¸c chuÈn øng dông trong thùc tÕ. Víi nhiÒu vÝ dô cô thÓ, cuèn s¸ch gióp cho b¹n ®äc thuËn tiÖn trong qu¸ tr×nh häc tËp nghiªn cøu ®Ó n©ng cao kiÕn thøc vÒ mËt m· häc. §©y lµ gi¸o tr×nh phôc vô ®µo t¹o t¹i Häc viÖn C«ng nghÖ B−u chÝnh ViÔn th«ng.
Hy väng cuèn s¸ch sÏ lµ tµi liÖu tham kh¶o h÷u Ých cho gi¶ng viªn, sinh viªn c¸c tr−êng ®¹i häc vÒ kü thuËt vµ c«ng nghÖ. Xin tr©n träng giíi thiÖu cïng b¹n ®äc. Hµ Néi, ngµy 23 th¸ng 10 n¨m 2003 Häc viÖn c«ng nghÖ b−u chÝnh viÔn th«ng
thuËt ng÷ viÕt t¾t DES Data Encryption Standard ChuÈn m· d÷ liÖu LAN Local Area Network M¹ng côc bé MDV M· dÞch vßng MTT M· thay thÕ MHV M· ho¸n vÞ ECB Electronic Code Book ChÕ ®é quyÓn m· ®iÖn tö CFB Cripher Feedback ChÕ ®é ph¶n håi m· CBC Cripher Block Chaining ChÕ ®é liªn kÕt khèi m· RSA Rivest - Shamir - Adleman MAC Message Authentication Code M· x¸c thùc th«ng b¸o OWHF Oneway Hash Funtion Hµm b¨m mét chiÒu CRHF Collision Resistant hash function Hµm b¨m khã va ch¹m MDC Manipulation Detection Code M· ph¸t hiÖn sù söa ®æi LSB Least Signification Bit Bit thÊp nhÊt (cã gi¸ trÞ nhá nhÊt Header Tiªu ®Ò IDEA International Data Encryption ThuËt to¸n m· hãa d÷ liÖu Algorithm quèc tÕ PGP Pretty Good Privacy ThuËt to¸n m· hãa PGP SET Secure Electronic Transaction Giao dÞch ®iÖn tö an toµn LFSR Linear Feedback Sequence Thanh ghi håi tiÕp tuyÕn tÝnh Register Firewall Bøc t−êng löa Server M¸y chñ Router Bé ®Þnh tuyÕn
PhÇn I C¸c kiÕn thøc to¸n häc phô trî
bæ tóc vÒ lý thuyÕt sè 1.1. Sè nguyªn TËp c¸c sè nguyªn {K, − 3, − 2, − 1, 0,1, 2, 3,K}= Z. 1.1.1. §Þnh nghÜa 1.1 Cho a, b ∈ Ζ a lμ −íc cña b nÕu ∃c ∈ Z : b = a.c. Ký hiÖu lμ a b. 1.1.2. C¸c tÝnh chÊt chia hÕt ∀ a, b, c ∈ Ζ ta cã: (i) a a. (ii) NÕu a b vμ b c th× a c. (iii) NÕu a b vμ a c th× a (bx + cy ) víi ∀x, y ∈ Z. (iv) NÕu a b vμ b a th× a = ± b. 1.1.3. §Þnh nghÜa 1.2 (ThuËt to¸n chia ®èi víi c¸c sè nguyªn) NÕu a vμ b lμ c¸c sè nguyªn víi b ≥ 1 th× a = qb + r; 0 ≤ r < b q vμ r lμ nh÷ng gi¸ trÞ duy nhÊt.
10 Gi¸o tr×nh MËt m· häc PhÇn d− cña phÐp chia a vμ b ®−îc ký hiÖu a mod b = r Th−¬ng cña phÐp chia a vμ b ®−îc ký hiÖu a div b = q ⎡a ⎤ ⎡a ⎤ Ta cã a div b = ⎢ ⎥, a mod b = a − b⎢ ⎥. ⎣b⎦ ⎣b⎦ VÝ dô: a = 73, b = 17. 73 div 17 = 4, 73 mod 17 = 5. 1.1.4. §Þnh nghÜa 1.3 (¦íc chung) c lμ −íc chung cña a vμ b nÕu c a & c b. 1.1.5. §Þnh nghÜa 1.4 (¦íc chung lín nhÊt (¦CLN)) Sè nguyªn d−¬ng d lμ ¦CLN cña c¸c sè nguyªn a vμ b (Ký hiÖu d = (a, b)) nÕu: (i) d lμ −íc chung cña a vμ b. (ii) NÕu cã c a vμ c b th× c d . Nh− vËy (a,b) lμ sè nguyªn d−¬ng lín nhÊt −íc cña c¶ a vμ b kh«ng kÓ (0,0) = 0. VÝ dô: C¸c −íc chung cña 12 vμ 18 lμ {± 1, ± 2, ± 3, ± 6} (12,18) = 6 1.1.6. §Þnh nghÜa 1.5 (Béi chung nhá nhÊt (BCNN)) Sè nguyªn d−¬ng d lμ BCNN cña c¸c sè nguyªn a vμ b (Ký hiÖu d = BCNN (a,b)) nÕu: (i) a d, b d. (ii) NÕu cã a c, b c th× d c. Nh− vËy d lμ sè nguyªn d−¬ng nhá nhÊt lμ béi cña c¶ a vμ b.
Ch−¬ng 1: Bæ tóc vÒ lý thuyÕt sè 11 1.1.7. TÝnh chÊt a.b BCNN (a , b) = (a , b) VÝ dô: (12 ,18 ) = 6 ⇒ BCNN(12 ,18 ) = 12 .18 = 36 . 6 1.1.8. §Þnh nghÜa 1.6 Hai sè nguyªn d−¬ng a vμ b ®−îc gäi lμ nguyªn tè cïng nhau nÕu: (a,b) = 1. 1.1.9. §Þnh nghÜa 1.7 Sè nguyªn p ≥ 2 ®−îc gäi lμ sè nguyªn tè nÕu c¸c −íc d−¬ng cña nã chØ lμ 1 vμ p. Ng−îc l¹i p ®−îc gäi lμ hîp sè. 1.1.10. §Þnh lý c¬ b¶n cña sè häc Víi mçi sè nguyªn n ≥ 2 ta lu«n ph©n tÝch ®−îc d−íi d¹ng tÝch cña luü thõa cña c¸c sè nguyªn tè. n = p1e1 pe22 K pekk Trong ®ã pi lμ c¸c sè nguyªn tè kh¸c nhau vμ ei lμ c¸c sè nguyªn d−¬ng. H¬n n÷a ph©n tÝch trªn lμ duy nhÊt. 1.1.11. §Þnh nghÜa 1.8 Víi n ≥ 2, hμm Φ(n ) ®−îc x¸c ®Þnh lμ sè c¸c sè nguyªn trong kho¶ng [1 , n ] nguyªn tè cïng nhau víi n. 1.1.12. C¸c tÝnh chÊt cña hμm Φ(n) (i) NÕu p lμ c¸c sè nguyªn tè th× Φ(p) = p – 1. (ii) NÕu (m, n) = 1 th× Φ(m.n) = Φ(m). Φ(n).
12 Gi¸o tr×nh MËt m· häc (iii) NÕu n = p1e1 pe22 K pekk lμ ph©n tÝch ra thõa sè nguyªn tè cña n th×: ⎛ 1 ⎞⎛ 1 ⎞ ⎛ 1 ⎞ Φ (n ) = n⎜⎜1 − ⎟⎟ ⎜⎜1 − ⎟⎟ K ⎜⎜1 − ⎟⎟ . ⎝ p1 ⎠ ⎝ p2 ⎠ ⎝ pk ⎠ 1.1.13. §Þnh lý 1.1 Víi ∀n ≥ 5 th× Φ (n ) > n 6 ln (ln n ) 1.2. c¸c thuËt to¸n trong z Cho a vμ b lμ c¸c sè nguyªn kh«ng ©m vμ nhá h¬n hoÆc b»ng n. CÇn chó ý r»ng sè c¸c bit trong biÓu diÔn nhÞ ph©n cña n lμ [lgn] + 1 vμ sè nμy xÊp xØ b»ng lgn. Sè c¸c phÐp to¸n bit ®èi víi bèn phÐp to¸n c¬ b¶n trªn c¸c sè lμ céng, trõ, nh©n vμ chia sö dông c¸c thuËt to¸n kinh ®iÓn ®−îc tãm l−îc trªn b¶ng 1.1. C¸c kü thuËt tinh tÕ h¬n ®èi víi c¸c phÐp to¸n nh©n vμ chia sÏ cã ®é phøc t¹p nhá h¬n. B¶ng 1.1: §é phøc t¹p bit cña c¸c phÐp to¸n c¬ b¶n trong Z PhÐp to¸n §é phøc t¹p bit Céng a+b 0(lga + lgb) = 0(lgn) Trõ a–b 0(lga + lgb) = 0(lgn) Nh©n a.b 0((lga).(lgb)) = 0((lgn)2) Chia a = qb + r 0((lga).(lgb)) = 0((lgn)2) ¦CLN cña 2 sè nguyªn a vμ b cã thÓ ®−îc tÝnh theo ®Þnh lý sau: 1.2.1. §Þnh lý 1.2 NÕu a = p1e1 pe22 K pekk , b = p1f1 p2f2 ...p fkk trong ®ã e i ≥ 0, fi ≥ 0 th× − CLN(a , b) = p1min (e1 , f1 ) p min 2 (e2 , f2 ) K pmin k (ek , fk )
Ch−¬ng 1: Bæ tóc vÒ lý thuyÕt sè 13 vμ BCNN (a , b) = p1max (e1 ,f1 ) pmax 2 (e2 ,f2 ) K pmax k (ek ,fk ) . VÝ dô: Cho a = 4864 = 28.19; b = 3458 = 2.7.13.19. Khi ®ã: − CLN(a , b) = (4864, 3458 ) = 2.19 = 38 BCNN(a , b) = (4864, 3458 ) = 28.7.13.19 = 442624 . 1.2.2. §Þnh lý 1.3 NÕu a vμ b lμ c¸c sè nguyªn d−¬ng víi a > b th× ¦CLN(a,b) = ¦CLN (b,a mod b). ThuËt to¸n Euclide sau sÏ cho ta c¸ch tÝnh ¦CLN rÊt hiÖu qu¶ mμ kh«ng cÇn ph¶i ph©n tÝch ra thõa sè nguyªn tè. 1.2.3. ThuËt to¸n Euclide TÝnh ¦CLN cña 2 sè nguyªn Vμo : Hai sè nguyªn kh«ng ©m a vμ b víi a > b Ra : ¦CLN cña a vμ b. (1) While b ≠ 0 do r ← a mod b, a ← b, b ← r (2) Return (a). 1.2.4. §Þnh lý 1.4 ThuËt to¸n trªn cã thêi gian ch¹y chõng 0 ( (lg n ) ) c¸c phÐp 2 to¸n bit. VÝ dô: Sau ®©y lμ c¸c b−íc chia cña thuËt to¸n trªn khi tÝnh: (4864, 3458 ) = 38 4864 = 1.3458 + 1406 3458 = 2.1406 + 646 1406 = 2.646 + 76 646 = 5.114 + 38 76 = 2.38 + 0
14 Gi¸o tr×nh MËt m· häc ThuËt to¸n trªn cã thÓ ®−îc më réng ®Ó kh«ng nh÷ng chØ tÝnh ®−îc ¦CLN cña 2 sè nguyªn a vμ b mμ cßn tÝnh ®−îc c¸c sè nguyªn x vμ y tho¶ m·n ax + by = d . 1.2.5. ThuËt to¸n Euclide më réng Vμo : Hai sè nguyªn kh«ng ©m a vμ b víi a ≥ b Ra : d = ¦CLN(a,b) vμ c¸c sè nguyªn x vμ y tháa m·n ax + by = d . (1) NÕu b= 0 th× ®Æt d ← a , x ← 1 , y ← 0 vμ return (d, x, y) (2) §Æt x 2 ← 1, x1 ← 0, y 2 ← 0 , y1 ← 1 (3) While b > 0 do (3.1) q ← ⎣a / b⎦ , r ← a − qb , x ← x 2 − qx1 , y ← y 2 − qy1 (3.2) a ← b, b ← r, x 2 ← x1 , x1 ← x, y 2 ← y1 , y1 ← y (4) §Æt d ← a, x ← x 2 , y ← y 2 vμ vμ return (d, x, y). 1.2.6. §Þnh lý 1.5 ThuËt to¸n trªn cã thêi gian ch¹y cì 0((lgn)2) c¸c phÐp to¸n bit. VÝ dô: B¶ng 1.2 sau chØ ra c¸c b−íc cña thuËt to¸n trªn víi c¸c gi¸ trÞ vμo a = 4864 vμ b = 3458 B¶ng 1.2: ThuËt to¸n Euclide më réng Q r x y a b x2 x1 y2 y1 − − − − 4864 3458 1 0 0 1 1 1406 1 −1 3458 1406 0 1 1 −1 2 646 −2 3 1406 646 1 −2 −1 3 2 114 5 −7 646 114 −2 5 3 7 5 76 −27 38 114 76 5 −27 −7 38 1 38 32 −45 76 38 −27 32 38 −45 2 0 −91 128 38 0 32 −91 −45 128
Ch−¬ng 1: Bæ tóc vÒ lý thuyÕt sè 15 Víi c¸c ®Çu vμo a = 4864 vμ b = 3458 Bëi vËy ta cã: ¦CLN(4864,3458) = 38 vμ (4864)(32) + (3458)(-45) = 38. 1.3. C¸c sè nguyªn modulo n 1.3.1. §Þnh nghÜa 1.9 NÕu a vμ b lμ c¸c sè nguyªn th× a ®−îc gäi lμ ®ång d− víi b theo modulo (ký hiÖu lμ a = b mod n) nÕu n (a − b) . Sè nguyªn n ®−îc gäi lμ modulo ®ång d−. VÝ dô: 24 ≡ 9 mod 5 v× 24 – 9 = 3.5 − 11 ≡ 17 mod 7 v× − 11 − 17 = −4.7 . 1.3.2. C¸c tÝnh chÊt §èi víi a, a1 , b, b1 , c ∈ Ζ ta cã: (1) a ≡ b(mod n ) nÕu vμ chØ nÕu a vμ b còng cã phÇn d− khi chia cho n. (2) TÝnh ph¶n x¹: a ≡ a(mod n ) . (3) TÝnh ®èi xøng: NÕu a ≡ b(mod n ) th× b ≡ a(mod n ) (4) TÝnh b¾c cÇu: NÕu a ≡ b(mod n ) vμ b ≡ c(mod n ) th× a ≡ c(mod n ) (5) NÕu a ≡ a1 (mod n ) vμ b ≡ b1 (mod n ) th× a + b ≡ a1 + b1 (mod n ) vμ a.b ≡ a1 .b1 (mod n ) Líp t−¬ng ®−¬ng cña mét sè nguyªn a lμ tËp c¸c sè nguyªn ®ång d− víi a modulo n. Tõ c¸c tÝnh chÊt (2), (3) vμ (5) ë trªn ta cã thÓ thÊy r»ng ®èi víi n cè ®Þnh, quan hÖ ®ång d− theo modulo n sÏ ph©n ho¹ch Z thμnh c¸c líp t−¬ng ®−¬ng.
16 Gi¸o tr×nh MËt m· häc NÕu a = qn + r víi 0 ≤ r ≤ n th× a ≡ r(mod n ) . Bëi vËy mçi sè nguyªn a lμ ®ång d− theo modulo n víi mét sè nguyªn duy nhÊt n»m trong kho¶ng tõ 0 tíi n - 1, sè nμy ®−îc gäi lμ thÆng d− tèi thiÓu cña a mod n. Nh− vËy a vμ r cã thÓ ®−îc dïng ®Ó biÓu thÞ cho líp t−¬ng ®−¬ng nμy. 1.3.3. §Þnh nghÜa 1.10 C¸c sè nguyªn modulo n (ký hiÖu Zn) lμ tËp (c¸c líp t−¬ng ®−¬ng) cña c¸c sè nguyªn {0,1, 2,K, n − 1}. C¸c phÐp céng, trõ, nh©n trong Zn ®−îc thùc hiÖn theo modulo n. VÝ dô: Z25 = {0,1,K, 24}. Trong Z 25 ta cã: 13 + 16 = 4 v× 13 + 16 = 29 ≡ 4 (mod 25 ) T−¬ng tù 13.16 = 8 trong Z25. 1.3.4. §Þnh nghÜa 1.11 (PhÇn tö nghÞch ®¶o) Cho a ∈ Z n , PhÇn tö nghÞch ®¶o (ng−îc theo phÐp nh©n) cña a mod n lμ mét sè nguyªn x ∈ Z n sao cho: ax ≡ 1(mod n ) NÕu x tån t¹i th× nã lμ duy nhÊt, a ®−îc gäi lμ kh¶ nghÞch. PhÇn tö nghÞch ®¶o cña a ®−îc ký hiÖu lμ a−1. 1.3.5. §Þnh nghÜa 1.12 PhÐp chia cña a cho b mod n lμ tÝch cña a vμ b−1 mod n tÝch nμy ®−îc x¸c ®Þnh nÕu b lμ phÇn tö kh¶ nghÞch 1.3.6. §Þnh lý 1.6 Cho a ∈ Z n , khi ®ã a lμ kh¶ nghÞch nÕu vμ chØ nÕu: (a, n ) = 1 VÝ dô: C¸c phÇn tö kh¶ nghÞch trong Z9 lμ 1, 2, 3, 4, 5, 7 vμ 8. Ch¼ng h¹n 4 − 1 = 7 v× 4 . 7 ≡ 1 (mod 9 ) .
Ch−¬ng 1: Bæ tóc vÒ lý thuyÕt sè 17 1.3.7. §Þnh lý 1.7 Cho d = (a,n). Ph−¬ng tr×nh ®ång d− ax ≡ b(mod n ) cã nghiÖm x nÕu vμ chØ nÕu d b , trong tr−êng hîp nμy cã ®óng d nghiÖm n»m gi÷a 0 vμ n - 1, nh÷ng nghiÖm nμy lμ tÊt c¶ c¸c ®ång d− theo modulo n d . 1.3.8. §Þnh lý 1.8 (PhÇn d− China) NÕu c¸c sè nguyªn n1 , n 2 ,K, n k lμ nguyªn tè cïng nhau tõng ®«i mét th× hÖ c¸c ph−¬ng tr×nh ®ång d−: x ≡ a 1 (mod n 1 ) x ≡ a 2 (mod n 2 ) .......... .......... .... x ≡ a k (mod n k ) sÏ cã nghiÖm duy nhÊt theo modulo n (n = n 1 . n 2 K n k ) . 1.3.9. ThuËt to¸n Gausse NghiÖm x cña hÖ ph−¬ng tr×nh ®ång d− trong ®Þnh lý phÇn d− China cã thÓ ®−îc tÝnh b»ng: k x= ∑a N M i =1 i i i mod n Trong ®ã: N i = n / n i vμ M i = N i− 1 mod n i C¸c tÝnh to¸n nμy cã thÓ ®−îc thùc hiÖn trong 0 ( (lg n ) ) c¸c 2 phÐp to¸n trªn bit. VÝ dô: CÆp ph−¬ng tr×nh ®ång d− x ≡ 3 (mod 7 ), x ≡ 7 (mod 13 ) cã nghiÖm duy nhÊt x ≡ 59 (mod 91 ) .
18 Gi¸o tr×nh MËt m· häc 1.3.10. §Þnh lý 1.9 NÕu (n1 , n 2 ) = 1 th× cÆp ph−¬ng tr×nh ®ång d−. x ≡ a (mod n 1 ) , x ≡ a (mod n 2 ) cã mét nghiÖm duy nhÊt x ≡ a (mod n 1 , n 2 ) . 1.3.11. §Þnh nghÜa 1.13 Nhãm nh©n cña Z n lμ Z *n = {a ∈ Z n (a, n ) = 1} §Æc biÖt, nÕu n lμ sè nguyªn tè th× Z *n = {a 1 ≤ a ≤ n − 1}. 1.3.12. §Þnh nghÜa 1.14 CÊp cña Z *n lμ sè c¸c phÇn tö trong Z *n (ký hiÖu Z *n ) Theo ®Þnh nghÜa cña hμm Phi-Euler ta thÊy: Z *n = Φ(n ) CÇn ®Ó ý r»ng nÕu a ∈ Z *n vμ b ∈ Z *n th× a, b ∈ Z *n vμ bëi vËy Z *n lμ ®ãng ®èi víi phÐp nh©n. 1.3.13. §Þnh lý 1.10 Cho p lμ mét sè nguyªn tè: (1) §Þnh lý Euler: NÕu a ∈ Z *n th× a Φ (n ) ≡ 1 (mod n ) . (2) NÕu n lμ tÝch cña c¸c sè nguyªn kh¸c nhau vμ nÕu r ≡ s (mod Φ (n )) th× a r ≡ as (mod n ) ®èi víi mäi sè nguyªn a. Nãi mét c¸ch kh¸c khi lμm viÖc víi modulo n th× c¸c sè mò cã thÓ ®−îc rót gän theo modulo Φ(n ).
Ch−¬ng 1: Bæ tóc vÒ lý thuyÕt sè 19 1.3.14. §Þnh lý 1.11 Cho p lμ mét sè nguyªn tè: (1) §Þnh lý Ferma: NÕu (a, p) = 1 th× a p −1 ≡ 1 (mod p ) . (2) NÕu r ≡ s (mod p − 1 ) th× a r ≡ a s (mod p ) ®èi víi mäi sè nguyªn a. Nãi mét c¸ch kh¸c khi lμm viÖc víi modulo cña mét sè nguyªn tè p th× c¸c luü thõa cã thÓ ®−îc rót gän theo modulo p - 1. (3) §Æc biÖt a p ≡ a (mod p ) víi mäi sè nguyªn a. 1.3.15. §Þnh nghÜa 1.15 Cho a ∈ Z *n . CÊp cña a (ký hiÖu lμ ord(a ) ) lμ sè nguyªn d−¬ng nhá nhÊt t sao cho a t ≡ 1 (mod n ) . 1.3.16. §Þnh nghÜa 1.16 Cho a ∈ Z *n , ord(a ) = t vμ a s ≡ 1 (mod n ) khi ®ã t lμ −íc cña s. §Æc biÖt t Φ (n ) . VÝ dô: Cho n = 21, khi ®ã Z *21 = {1, 2, 4 , 5, 8 , 10 , 11 , 13 , 16 , 17 , 19 , 20 } Chó ý r»ng Φ (21 ) = Φ (7 ) Φ (3 ) = 12 = Z *21 . CÊp cña c¸c phÇn tö trong Z *21 ®−îc nªu trong b¶ng sau: B¶ng 13: CÊp cña c¸c phÇn tö trong Z *21 a ∈ Z 21 * 1 2 4 5 8 10 11 13 16 17 19 20 Ord(a) 1 6 3 6 2 6 6 2 3 6 6 2
20 Gi¸o tr×nh MËt m· häc 1.3.17. §Þnh nghÜa 1.17 Cho α ∈ Z *n . NÕu cÊp cña α lμ Φ(n ) th× α ®−îc gäi lμ phÇn tö sinh hay phÇn tö nguyªn thñy cña Z *n . NÕu Z *n cã mét phÇn tö sinh th× Z *n ®−îc gäi lμ cyclic. 1.3.18. C¸c tÝnh chÊt cña c¸c phÇn tö sinh cña Z*n (1) Z*n cã phÇn tö sinh nÕu vμ chØ nÕu n = 2, 4, p k hoÆc lμ 2p k , trong ®ã p lμ mét sè nguyªn tè lÎ vμ k ≥ 1 . §Æc biÖt, nÕu p lμ * mét sè nguyªn tè th× Z n cã phÇn tö sinh. * (2) NÕu α lμ mét phÇn tö sinh cña Z n th×: Z *n = { α i mod n 0 ≤ i ≤ Φ(n ) − 1 } (3) Gi¶ sö r»ng α lμ mét phÇn tö sinh cña Z*n , khi ®ã b = α i mod n còng lμ mét phÇn tö sinh cña Z*n nÕu vμ chØ nÕu (i, Φ(n )) = 1 . Tõ ®ã ta rót ra r»ng nÕu Z*n lμ cyclic th× sè c¸c phÇn tö sinh lμ Φ(Φ(n )) . (4) α ∈ Zn lμ mét phÇn tö sinh cña Z n nÕu vμ chØ nÕu * * α Φ (n ) / p ≠ 1(mod n ) ®èi víi mçi nguyªn tè p cña Φ(n ) . VÝ dô: Z*21 kh«ng lμ cyclic v× nã kh«ng chøa mét phÇn tö cã cÊp Φ(21) = 12 (Chó ý r»ng 21 kh«ng tháa m·n ®iÒu kiÖn (1) ë trªn). Z *25 lμ cyclic vμ cã mét phÇn tö sinh α = 2 .
Ch−¬ng 1: Bæ tóc vÒ lý thuyÕt sè 21 1.3.19. §Þnh nghÜa 1.18 Cho a ∈ Z*n , a ®−îc gäi lμ thÆng d− bËc hai modulo n (hay b×nh ph−¬ng cña modulo n) nÕu tån t¹i x ∈ Z*n sao cho x 2 ≡ a(mod n ) . NÕu kh«ng tån t¹i x nh− vËy th× a ®−îc gäi lμ thÆng d− kh«ng bËc hai mod n. TËp tÊt c¶ c¸c thÆng d− bËc hai modulo n ®−îc ký hiÖu lμ Qn, cßn tËp tÊt c¶ c¸c thÆng d− kh«ng bËc hai ®−îc ký hiÖu lμ Q n . CÇn chó ý r»ng theo ®Þnh nghÜa 0 ∉ Z*n . Bëi vËy 0 ∉ Q n vμ 0 ∉ Qn . 1.3.20. §Þnh lý 1.12 Cho p lμ mét sè nguyªn tè lÎ vμ α lμ mét phÇn tö sinh cña Z*p . Khi ®ã a ∈ Z*p lμ mét thÆng d− bËc hai modulo p nÕu vμ chØ nÕu a = α i mod p , trong ®ã i lμ mét sè nguyªn ch½n. Tõ ®ã rót ra r»ng Q p = (p − 1) vμ Q p = (p − 1) , tøc lμ mét nöa sè phÇn tö trong 2 2 Z*p lμ c¸c thÆng d− bËc hai vμ nöa cßn l¹i thÆng d− kh«ng bËc hai. * VÝ dô: α = 6 lμ mét phÇn tö sinh cña Z13 . C¸c lòy thõa cña α ®−îc liÖt kª ë b¶ng sau: i 0 1 2 3 4 5 6 7 8 9 10 11 αi mod 13 1 6 10 8 9 2 12 7 3 5 4 11 Bëi vËy Q13 = { 1, 3, 4, 9, 10,12 }, Q13 = { 2, 5, 6, 7, 8,11 } . 1.3.21. §Þnh lý 1.13 Cho n lμ tÝch cña hai sè nguyªn tè lÎ kh¸c nhau q vμ p, n = p.q, khi ®ã a ∈ Z*n lμ mét thÆng d− bËc hai modulo n nÕu vμ chØ nÕu a ∈ Q p vμ a ∈ Q p . §iÒu ®ã dÉn tíi Q n = Q q . Q p = (p − 1)(q − 1) 4
22 Gi¸o tr×nh MËt m· häc 3(p − 1)(q − 1) vµ Qn = 4 VÝ dô: Cho n = 21. Khi ®ã Q 21 = { 1, 4,16 } Q 21 = {2,5, 8,10,11,13,17,19, 20} 1.3.22. §Þnh nghÜa 1.19 Cho a ∈ Q n . NÕu x ∈ Z*n tháa m·n x 2 ≡ a(mod n ) th× x ®−îc gäi lμ c¨n bËc hai cña a mod n. 1.3.23. §Þnh lý 1.14 (Sè c¸c c¨n bËc hai) (1) NÕu p lμ mét sè nguyªn tè lÎ vμ a ∈ Q n th× a ®−îc gäi lμ c¨n bËc hai theo modulo p. (2) Tæng qu¸t h¬n, cho n = p1e1 pe22 K pekk , trong ®ã pi lμ c¸c sè nguyªn tè lÎ ph©n biÖt vμ e i ≥ 1 . NÕu a ∈ Q n th× cã ®óng 2k c¨n bËc hai kh¸c nhau theo modulo n. VÝ dô: C¸c c¨n bËc 2 cña 12 mod 37 lμ 7 vμ 30. C¸c c¨n bËc 2 cña 121 mod 315 lμ 11, 74, 101, 151, 164, 214, 241 vμ 304. 1.4. C¸c thuËt to¸n trong Zn Cho n lμ mét sè nguyªn d−¬ng. C¸c phÇn tö cña Zn sÏ ®−îc biÓu thÞ bëi c¸c sè nguyªn Q 21 = {0,1, 2,..., n − 1}. Ta thÊy r»ng, nÕu a, b ∈ Z n th× a+b a+b
Ch−¬ng 1: Bæ tóc vÒ lý thuyÕt sè 23 phÇn d− cña kÕt qu¶ sau khi chia cho n. C¸c phÇn tö nghÞch ®¶o trong Zn cã thÓ ®−îc tÝnh b»ng c¸ch dïng thuËt to¸n Euclide më réng ®−îc m« t¶ d−íi ®©y: 1.4.1. ThuËt to¸n (TÝnh c¸c nghÞch ®¶o trong Zn) Vμo : a ∈ Zn . Ra : a −1 mod n (nÕu tån t¹i). (1) Dïng thuËt to¸n Euclide më réng ®Ó t×m c¸c sè nguyªn x vμ y sao cho ax + ny = d trong ®ã d = (a,n). (2) NÕu d > 1 th× a−1 mod n kh«ng tån t¹i. Ng−îc l¹i return (x). PhÐp lòy thõa theo modulo cã thÓ ®−îc thùc hiÖn cã hiÖu qu¶ b»ng thuËt to¸n nh©n vμ b×nh ph−¬ng cã lÆp. §©y lμ mét thuËt to¸n rÊt quan träng trong nhiÒu thñ tôc mËt m·. Cho biÓu diÔn nhÞ ph©n cña k lμ: t ∑ i =0 k i 2 i trong ®ã mçi k i ∈ {0,1} khi ®ã a k 2 i = (a 2 ) (a ) K (a ) t ∏ 0 k0 k1 kt 21 2t a = k i i =0 1.4.2. ThuËt to¸n nh©n vμ b×nh ph−¬ng cã lÆp ®Ó lÊy luü thõa trong Zn Vμo: a ∈ Z n vμ sè nguyªn k, (0 ≤ k < n ) cã biÓu diÔn nhÞ ph©n: t k= ∑ i =0 k i 2i Ra: ak mod n. (1) §Æt b ← 1 . NÕu k = 0 th× return (b). (2) §Æt A ← a .
24 Gi¸o tr×nh MËt m· häc (3) NÕu k0 = 1 th× ®Æt b ← a . (4) For i from 1 to t do (4.1) §Æt A ← A 2 mod n (4.2) NÕu k i = 1 th× ®Æt b ← A.b mod n (5) Return (b). VÝ dô: B¶ng 1.4 sau chØ ra c¸c b−íc tÝnh to¸n 5596 mod 1234 = 1013 B¶ng 1.4: TÝnh 5596 mod 1234 i 0 1 2 3 4 5 6 7 8 9 ki 0 0 1 0 1 0 1 0 0 1 A 5 25 625 681 1011 369 421 779 947 925 b 1 1 625 625 67 67 1059 1059 1059 1013 Sè c¸c phÐp to¸n bit ®èi víi phÐp to¸n c¬ b¶n trong Zn ®−îc tãm l−îc trong b¶ng 1.5. B¶ng 1.5: §é phøc t¹p bit cña c¸c phÐp to¸n c¬ b¶n trong Zn PhÐp to¸n §é phøc t¹p bit Céng modulo a+b 0(lgn) Trõ modulo a-b 0(lgn) Nh©n modulo a.b 0((lgn)2) NghÞch ®¶o modulo a-1 mod n 0((lgn)2) Lòy thõa modulo ak mod n, k < n 0((lgn)3) 1.5. c¸c ký hiÖu legendre vμ jacobi Ký hiÖu Legendre lμ mét c«ng cô h÷u Ých ®Ó xem xÐt liÖu mét sè nguyªn a cã lμ mét thÆng d− bËc hai theo modulo cña mét sè nguyªn tè p hay kh«ng?