CH NG 1ƯƠ
C B N V Đ I SƠ Ả Ề Ạ Ố TR U T NGỪ ƯỢ
Các thu t toán ậm t mã th c hi n bi n đ i tin t c d i d ng các s ho c các ph n t trong khôngậ ự ệ ế ổ ứ ướ ạ ố ặ ầ ử
gian h u h n. Khi đó các phép mã và gi i mã, th c hi n bi n đ i tin t c t m t d ng này sang m tữ ạ ả ự ệ ế ổ ứ ừ ộ ạ ộ
d ng khác c n ph i có đ c tính đóng (closure property) trong không gian h u h n. Tuy nhiên các toánạ ầ ả ặ ữ ạ
t s h c thông th ng trên các s – phép c ng, tr , nhân, chia – không có các đ c tính này. Vì lý doử ố ọ ườ ố ộ ừ ặ
này, các thu t toán m t mã ho t đ ng trong không gian h u h n đ bi n đ i tin t c, nh đã bi t,ậ ậ ạ ộ ữ ạ ể ế ổ ứ ư ế
không ch d n t i các toán t s h c thông th ng. Mà chúng làm vi c trong không gian có các c uỉ ẫ ớ ử ố ọ ườ ệ ấ
trúc đ i s riêng bi t, đ b o đ m đ c tính đóng.ạ ố ệ ể ả ả ặ
Trong ch ng này, s kh o sát v đ i s tr u t ng (abstract algebra), nó là m t ngành ươ ẽ ả ề ạ ố ừ ượ ộ toán h cọ
liên quan đ n vi c nghiên c u các ế ệ ứ c u trúc đ i sấ ạ ố nh ưnhóm, vành, tr ngườ , hay các c u trúc t ng quátấ ổ
khác và nó có vai trò quan tr ng trong m t mã hi n đ i.ọ ậ ệ ạ
1.1 NHÓM
1.1.1 Nhóm
Đ nh nghĩa 1.1ị .1 (Nhóm)
Nhóm (G, °) là m t ột p h pậ ợ G cùng v i m t ớ ộ phép toán hai ngôi, ký hi u ệ° (là m tộ ánh x t t p ạ ừ ậ G ×
G → G) th a mãn các ỏtiên đề sau:
G1. Tính đóng: N u ếa, b ∈ G, thì a ° b ∈ G.
G2. Tính k t h pế ợ : (a ° b) ° c = a ° (b ° c), v iớ ∀a, b, c ∈ G.
G3. Ph n t đ n v (trung hòaầ ử ơ ị ): Trong G t n t i m t ph n t đ c g i là ph n t đ n v ồ ạ ộ ầ ử ượ ọ ầ ử ơ ị e sao cho
v i ớ∀a ∈ G thì a ° e = e ° a = a.
G4. Ph n t ầ ử ngh ch đ o: V i m i ph n t ị ả ớ ỗ ầ ử a ∈ G t n t i m t ph n t ồ ạ ộ ầ ử a-1, g i là ph n t ngh chọ ầ ử ị
đ o c a ả ủ a, sao cho: a-1 ° a = a ° a-1 = e.
Chú ý: toán tử ° là ký hi u chung và có th đ i di n cho toán t c ng, nhân ho c các toán t toánệ ể ạ ệ ử ộ ặ ử
h c khác. ọ
Đ nh lý 1.1ị.1: V i ớ∀a ∈ G, a -1 ° a = e.
Ch ng minhứ: Khai tri n ểa -1 ° a, có:
oa -1 ° a = a -1 ° a ° e (theo G3)
oa -1 ° a ° e = a -1 ° a ° (a -1 ° (a -1) -1) (theo G4, a -1 có m t ngh ch đ o ký hi u làộ ị ả ệ (a -1) -1)
oa -1 ° a ° (a -1 ° (a -1) -1) = a -1 ° (a ° a -1) ° (a -1) -1 = a -1 ° e ° (a -1) -1 (theo G2 và G4)
oa -1 ° e ° (a -1) -1 = a -1 ° (a -1) -1 = e (theo G3 và G4)
⇒ a -1 ° a = e
Đ nh lý 1.ị1.2: V i ớ∀a ∈ G, e ° a = a.
Ch ng minhứ: Khai tri n ểe ° a, có:
oe ° a = (a ° a -1) ° a (theo G4)
1
o(a ° a -1) ° a = a ° (a -1 ° a) = a ° e (theo G2 và đ nh lý ị1.1.1)
oa ° e = a (theo G3)
⇒ e ° a = a
Đ nh lý 1.ị1.3: V i ớ∀a, b ∈ G, t n t i duy nh t ồ ạ ấ x ∈ G sao cho a ° x = b.
Ch ng minhứ: Ch c ch n, t n t i ít nh t m t ph n t ắ ắ ồ ạ ấ ộ ầ ử x nh v y, ch ng h n đ t ư ậ ẳ ạ ặ x = a -1 ° b, thì x ∈
G (theo G1) và do đó:
oa ° x = a ° (a -1 ° b) (th ếx)
oa ° (a -1 ° b) = (a ° a -1) ° b (theo G2).
o(a ° a -1) ° b= e ° b = b (theo G3).
Nh v y ư ậ x này luôn t n t i và th a mãn ồ ạ ỏ a ° x = b.
Đ ch ra tính duy nh t, n u ể ỉ ấ ế a ° x = b, thì:
ox = e ° x
oe ° x = (a -1 ° a) ° x
o(a -1 ° a) ° x = a -1 ° (a ° x)
oa -1 ° (a ° x) = a -1 ° b
⇒ x = a -1 ° b
Đ nh lý 1.ị1.4: Ph n t đ n v c a m t nhóm (ầ ử ơ ị ủ ộ G, °) là duy nh tấ.
Ch ng minhứ: Gi s ả ử G có hai ph n t đ n vầ ử ơ ị là e và f. V yậ thì e ° f = e (theo G3), nh ng cũng có ưe
° f = f (theo đ nh lý ị1.1.2) ⇒ e = f. Nh v y, có th nói ư ậ ể ph n t đ n vầ ử ơ ị c a (ủG, ° ) thay vì m tộ ph n tầ ử
đ n v . Khi đ c p nh ng nhóm khác nhau, s th ng ký hi u ơ ị ề ậ ữ ẽ ườ ệ eG cho ph n t đ n v c a nhóm (ầ ử ơ ị ủ G, °).
Đ nh lý 1.ị1.5: Ph n t ngh ch đ o c a m i ph n t thu c (ầ ử ị ả ủ ỗ ầ ử ộ G, °) là duy nh t, hay v i ấ ớ ∀a ∈ G, a ° x
= e n u và ch n u ế ỉ ế x = a -1.
Ch ng minhứ: Gi s m t ph n t ả ử ộ ầ ử g ∈ G có hai ph n t ngh ch đ o, ầ ử ị ả h và k. Thì h = h ° e = h ° (g ° k)
= (h ° g) ° k = e ° k = k (các đ ng th c nh n đ c theo G3, G4, G2, đ nh lý 1.1.1 và đ nh lý 1.1.2, theo thẳ ứ ậ ượ ị ị ứ
t ). Nh v y, có th nói ự ư ậ ể ph n t ngh ch đ oầ ử ị ả c a m t ph n t ủ ộ ầ ử x, thay vì m tộ ph n t ngh ch đ o.ầ ử ị ả
Đ nh lý 1.ị1.6: V i ớ∀a ∈ (G, °), (a -1) -1 = a.
Ch ng minhứ: Ta có a -1 ° a = e, đi đ nế k t lu n d a vào đ nh lý ế ậ ự ị 1.1.4.
Đ nh lý 1.ị1.7: V i ớ∀a, b∈ (G, °), (a ° b)-1 = b -1 ° a -1.
Ch ng minhứ: Ta có (a ° b) ° (b -1 ° a -1) = a ° (b ° b -1) ° a -1 = a ° e ° a -1 = a * a -1 = e, có k t lu n d a vàoế ậ ự
đ nh lý 1.4. ị
Đ nh lý 1.ị1.8: V i ớ∀a, x, y ∈ (G, °), n u ếa ° x = a ° y, thì x = y và n uế x ° a = y ° a, thì x = y.
Ch ng minhứ:
N u ếa ° x = a ° y thì:
oa -1 ° (a ° x) = a -1 ° (a ° y)
o(a -1 ° a) ° x = (a -1 ° a) ° y
oe ° x = e ° y
⇒ x = y
2
N u ếx ° a = y ° a thì
o(x ° a) ° a -1 = (y ° a) ° a -1
ox ° (a ° a -1) = y ° (a ° a -1)
ox ° e = y ° e
⇒ x = y
Ví d 1.1ụ.1 (Nhóm)
1. T p ậs th cố ự (R) là m t nhóm d i phép c ng (+):ộ ướ ộ
a. T ng c a hai s th c b t kỳ là m t s th c (tính đóng).ổ ủ ố ự ấ ộ ố ự
b. V i ớ
∀
a, b, c
∈
R: (a + b) + c = a + (b + c) (tính k t h pế ợ ).
c. V i ớ
∀
a
∈
R: a + 0 = a (0 là ph n t đ n vầ ử ơ ị).
d. V i ớ
∀
a
∈
R: –a + a = 0 (t n t i ph n t đ i l pồ ạ ầ ử ố ậ ).
2. T p ậs th cố ự khác không (R#) là m t nhóm d i phép nhân (*):ộ ướ
a. Tích c a hai s th c luôn là m t s th c (tính đóng).ủ ố ự ộ ố ự
b. V i ớ
∀
a, b, c
∈
R: (a * b) * c = a * (b * c) (tính k t h pế ợ ).
c. V i ớ
∀
a
∈
R: a * 1 = a (1 là ph n t đ n vầ ử ơ ị).
d. V i ớ
∀
a
∈
R: a * a -1 = 1 (t n t i ph n t đ i l pồ ạ ầ ử ố ậ ).
3. T p ậZ5 = {0, 1, 2, 3, 4} là m t nhóm theo ộphép c ng modulo 5ộ. Vì theo b ng tính toán d i đây,ả ướ
nó hoàn toàn th a mãn 4 tiên đ c a nhóm.ỏ ề ủ
+ 0 1 2 3 4
0 0 1 2 3 4
1 1 2 3 4 0
2 2 3 4 0 1
3 3 4 0 1 2
4 4 0 1 2 3
4. T ngươ t có th ch ng minh r ng t p ự ể ứ ằ ậ Zn = {0, 1, 2, 3, …, n – 1} là nhóm đ i v i phép c ngố ớ ộ
theo modulo n, ký hi u ệ
+
n
Z
.
Đ nh nghĩa 1.ị 1. 2 (Nhóm h u h n và vô h n)ữ ạ ạ
Nhóm G g i làọ h u h n n u nh t p ữ ạ ế ư ậ G có s l ng ph n t h u h n, và tr ng h p ng c l iố ượ ầ ử ữ ạ ườ ợ ượ ạ
g i là vô h n.ọ ạ
Đ nh nghĩa 1.ị 1.3 (Nhóm abel hay nhóm giao hoán)
Nhóm G g i là giao hoán n u nh v i ọ ế ư ớ ∀a, b ∈ G thì a ° b = b ° a.
Nói cách khác, nhóm abel là nhóm giao hoán. Sau này s không kh o sát các nhóm không giao hoán,ẽ ả
vì v y m i nhóm đ u là nhóm abel, cho nên thu t ng “abel” th ng b qua.ậ ọ ề ậ ữ ườ ỏ
Ví d 1.ụ1.2
1. T p ậh pợ c a các s nguyên ủ ố Z là nhóm đ i v i toán t (ố ớ ử +), t c là c p (ứ ặ G, +) – là nhóm, đây ởe
= 0 và a–1 = – a. Đây là nhóm c ng, vô h n và abel. (Theo G4: aộ ạ -1 + a = 0 → a-1 = -a).
3
T p h p c a các s h u t ậ ợ ủ ố ữ ỷ Q, t p h p c a các s th c ậ ợ ủ ố ự R, t p h p c a các s ph c ậ ợ ủ ố ứ C cũng là
nhóm c ng và vô h n, trong đó ph n t đ n v và ng c đ c xác đ nh theo cùng quy t c.ộ ạ ầ ử ơ ị ượ ượ ị ắ
2. Các ph n t khác không c a t p h p ầ ử ủ ậ ợ Q , R và C đ i v i phép nhân – là các nhóm, trong đó ố ớ e =
1 và a–1 là ph n t ngh ch đ o, đ c xác đ nh theo quy t c thông th ng. Ký hi u các nhómầ ử ị ả ượ ị ắ ườ ệ
này là (Q, * ), (R, *) và (C, *). Các nhóm này đ c g i là các nhóm nhân và vô h n.ượ ọ ạ
3. Đ i v i s nguyên b t kỳ ố ớ ố ấ n ≥ 1, t p h p các s nguyên theo modulo ậ ợ ố n hình thành lên nhóm h uữ
h n, bao g m t ạ ồ ừ n ph n t . Ph n t đ n v c a nhóm này là s 0, đ i v i ph n t ầ ử ầ ử ơ ị ủ ố ố ớ ầ ử a b t kỳ sấ ẽ
th c hi n đi u ki n ự ệ ề ệ a–1 = n – a. Nhóm này đ c ký hi u là ượ ệ Zn và ký hi u đ y đ c a nhóm nàyệ ầ ủ ủ
là (Zn, + (mod n)). (Theo G4: a-1 + a = 0 mod n → a–1 = n – a).
Đ nh nghĩa 1.ị 1. 4 (B c c a nhóm) ậ ủ
S l ng ph n t c a t p h u h n ố ượ ầ ử ủ ậ ữ ạ G đ c g i là b c c a ượ ọ ậ ủ G, đ c kí hi u làượ ệ #G.
1.1.2 Nhóm con
Đ nh nghĩa 1.ị 1. 5 (Nhóm con)
M t ột p conậ H c a ủG đ c g i là m t ượ ọ ộ nhóm con c a m t nhóm (ủ ộ G, °) n u ếH th a mãn các tiên đỏ ề
v nhómề và s d ngử ụ cùng các toán t ử°. Nh v y, n u ư ậ ế H là m t nhóm con c a (ộ ủ G, °), thì (H, °) cũng là
m t nhóm, và đ ng th i th a mãn các đ nh lý trên. Kí hi u ộ ồ ờ ỏ ị ệ
GH ⊆
.
Ví d 1.ụ1.3 (Nhóm con)
1. Đ i v i phép c ngố ớ ộ
CRQZ ⊆⊆⊆
.
2. T p ậ
{ }
e
là nhóm con c a m i nhóm.ủ ọ
3. T t c các nhóm con c a ấ ả ủ
+
6
Z
là {0}, {0, 3}, {0, 2, 4} và chính nó. Các nhóm {0, 1}, {0, 5}
không là nhóm con c a ủ
+
6
Z
. Vì (xem ti p sau) ph n t 1, 5 là ph n t sinh c a ế ầ ử ầ ử ủ
+
6
Z
, chúng
th a mãn c toán t không ph i c a nhóm. Đó là toán t : 1, 5 = a ỏ ả ử ả ủ ử ° a °…° a (i l n) = i . a.ầ
Đ nh nghĩa ị 1 . 1.6 (Nhóm con tách bi tệ và nhóm con không t m th ng) ầ ườ
M t ộnhóm con tách bi tệ c a m t nhóm ủ ộ G là m t nhóm con khác ộG (H ≠ G), ký hi u H ệ⊂ G. M tộ
nhóm con không t m th ngầ ườ c a ủG là b t kỳ nhóm con ấtách bi tệ nào c a ủG ch a m t ph n t khác ứ ộ ầ ử e.
Đ nh lý 1.ị1.9: N u ếH là m t nhóm con c a (ộ ủ G, °), thì ph n t đ n v ầ ử ơ ị eH c a ủH gi ng v i ph n tố ớ ầ ử
đ n v ơ ị e c a nhóm (ủG, °).
Ch ng minhứ: N u ếh ∈ H, thì h ° eH = h; vì h cũng ph i thu c ả ộ G, h ° e = h; do đó theo đ nh lý 1.1.4,ị
eH = e.
Đ nh lý 1.ị1.10: N u ếH là m t nhóm con c a ộ ủ G, và h là m t ph n t c a ộ ầ ử ủ H, thì ngh ch đ o c a ị ả ủ h
trong H gi ng v i ngh ch đ o c a ố ớ ị ả ủ h trong G.
Ch ng minhứ: G i ọh và k là các ph n t c a ầ ử ủ H, sao cho h ° k = e, b i vì ởh cũng thu c ộG, h ° h -1 = e
do đó theo đ nh lý 1.1.5, ịk = h -1.
Đ nh lý 1.ị1.11: N u ếS là m t t p con không r ng c a ộ ậ ỗ ủ G, thì S là m t nhóm con c a ộ ủ G n u và chế ỉ
n u v i ế ớ ∀a, b ∈ S, a ° b -1 ∈ S.
Ch ng minhứ:
4
1. N u v i ế ớ ∀a, b ∈ S, a ° b -1 cũng thu c ộS, thì
oe ∈ S, vì a ° a -1 = e ∈ S.
oV i ớ∀a ∈ S, e ° a -1 = a -1 ∈ S
oV i ớ∀a, b ∈ S, a ° b = a ° (b -1) -1 ∈ S
Do đó, các tiên đ v tính đóng, ph n t đ n v , ph n t ngh ch đ o, và tính k t h p đ c k th aề ề ầ ử ơ ị ầ ử ị ả ế ợ ượ ế ừ
do đó S là m t nhóm con. ộ
2. Ng c l i, n u ượ ạ ế S là m t nhóm con c a ộ ủ G, thì nó tuân theo các tiên đ v nhóm. ề ề
oNh đã nói, ph n t đ n v c a ư ầ ử ơ ị ủ S chính là ph n t đ n v ầ ử ơ ị e c a ủG.
oTheo G4, v i ớ∀b ∈ S, b -1 ∈ S
oTheo G1, a ° b -1 ∈ S.
Đ nh lý ị1.1.12: Giao c a các nhóm con c a nhóm ủ ủ G là m t nhóm con.ộ
Ch ng minhứ:
1. G i {ọHi} là m t t p các nhóm con c a ộ ậ ủ G, và K = ∩{Hi}.
2. e là ph n t c a m i ầ ử ủ ọ Hi theo đ nh lý ị1.1.9, do đó K không r ng. ỗ
3. N u ếh và k là các ph n t c a ầ ử ủ K, thì v i ớ∀i, có:
oh và k ∈ Hi.
oTheo đ nh lý tr c, ị ướ h ° k -1 ∈ Hi
oDo đó, h ° k -1 ∈ ∩{Hi}.
oDo đó v i ớ∀h, k ∈ K, h ° k -1 ∈ K.
o⇒ K = ∩{Hi} là m t nhóm con c a ộ ủ G và h n n a ơ ữ K là m t nhóm con c a m i ộ ủ ỗ Hi.
Đ nh lý ị1.1.13: G i ọa là m t ph n t c a m t nhóm (ộ ầ ử ủ ộ G, °), khi đó t p h p {ậ ợ an: n nguyên} là m tộ
nhóm con c a ủG.
Đ nh nghĩa 1.ị 1.7 (Liên t p, hay li n k ) ậ ề ề
Cho G là nhóm abel, H ⊆ G và
Ga ∈
thì
t p h p ậ ợ {a ° hh ∈ H} g i là liên t p trái (left coset) c a nhóm con ọ ậ ủ H trong G và ký hi u là ệa ° H, và
t p h p ậ ợ {h ° ah ∈ H} g i là liên t p ph i (right coset) c a nhóm con ọ ậ ả ủ H trong G và ký hi u là ệH ° a
Đ nh lý 1.ị1.14: N u ếH là m t nhóm con c a ộ ủ G, và x, y là các ph n t c a ầ ử ủ G, thì x ° H = y ° H, ho cặ
x ° H và y ° H không giao nhau.
Đ nh lý 1.ị1.15: N u ếH là m t nhóm con c a ộ ủ G, thì m i ọliên t pậ trái (ph i) c a ả ủ H trong G ch aứ
cùng s ph n t .ố ầ ử
Đ nh lý 1.ị1.16: N u ếH là m t nhóm con c a ộ ủ G, thì s ốliên t pậ trái phân bi t c a ệ ủ H b ng v i s ằ ớ ố liên
t pậ ph i phân bi t c a ả ệ ủ H.
Đ nh lý Lịagrange: N u ếH là m t nhóm con c a m t nhóm h u h n ộ ủ ộ ữ ạ G, thì
GH |##
, t c là sứ ố
l ng ph n t c a ượ ầ ử ủ H là c s c a ướ ố ủ #G.
Ch ng minhứ: Gi s ả ử G là nhóm h u h n và ữ ạ H là nhóm con c a nó. N u ủ ế G = H, thì đi u c n ch ngề ầ ứ
minh là hi n nhiên đúng. ể
5