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
Tiªu ®Ò
Header
IDEA
International Data Encryption
Algorithm
ThuËt to¸n m· hãa d÷ liÖu
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
Register
Thanh ghi håi tiÕp tuyÕn tÝnh
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
BCNN (a , b) =
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
⎟⎟ K ⎜⎜1 −
Φ (n ) = n⎜⎜1 − ⎟⎟ ⎜⎜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
(e2 , f2 )
(ek , fk )
K pmin
th× − CLN(a , b) = p1min (e1 , f1 ) p min
2
k
Ch−¬ng 1: Bæ tóc vÒ lý thuyÕt sè
13
(e2 ,f2 )
(ek ,fk )
vμ BCNN (a , b) = p1max (e1 ,f1 ) pmax
K pmax
.
2
k
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:
x=
k
∑a N M
i
i
i
mod n
i =1
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
(1)
Z*n
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
b = α i mod n còng lμ mét phÇn tö sinh cña
(i, Φ(n )) = 1 . Tõ ®ã ta rót ra r»ng nÕu Z*n
tö sinh lμ Φ(Φ(n )) .
Z*n
Z*n ,
khi ®ã
nÕu vμ chØ nÕu
lμ cyclic th× sè c¸c phÇ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)
2
vμ Q p =
(p − 1) , tøc lμ mét nöa sè phÇn tö trong
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
vµ Qn =
3(p − 1)(q − 1)
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 − r
(a + b)mod n = ⎧⎨
a+b 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
k i 2 i trong ®ã mçi k i ∈ {0,1} khi ®ã
∑
i =0
a k 2 i = (a 2
∏
i =0
t
a =
k
i
0
) (a ) K (a )
k0
21
k1
2t
kt
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:
k=
t
k i 2i
∑
i =0
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)
a-1 mod n
0((lgn)2)
ak mod n, k < n
0((lgn)3)
NghÞch ®¶o modulo
Lòy thõa modulo
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?
- Xem thêm -