TT CNTT HN Wednesday, April 25, 2012
CCIT/RIPT 1
VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN
TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ
TS. Phạm Việt Hà
MẬT MÃ HÓA HIỆN ĐẠI
Chương 2: Cơsởtoán học
MẬT MÃ HÓA HIỆN ĐẠI
Chương 2: Cơsởtoán học
Trang 2© 2009 | CCIT/RIPT
VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN
TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ
2.1.Một sốkiếnthứctoánhọc2.1.Một sốkiếnthứctoánhọc
Cấutrúcđạisố
Sốhọc modulo
TT CNTT HN Wednesday, April 25, 2012
CCIT/RIPT 2
Trang 3© 2009 | CCIT/RIPT
VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN
TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ
Cấutrúcđạisố:
•Định nghĩa nhóm. TậphợpG đóvới phép toán .đã
cho đượcgọilànhóm, nếunóthỏa mãn các tính
chấtsauvớimọiphầntửa, b, c thuộcG:
–Tính kếthợp (a.b).c = a.(b.c)
–Có đơn vị e: e.a = a.e = a
–Có nghịch đảo a-1: a.a-1 = e
–Nếu có thêm tính giao hoán a.b = b.a, thì gọi là nhóm
Aben hay nhóm giao hoán.
2.2. Cấutrúcđạisố2.2. Cấutrúcđạisố
Trang 4© 2009 | CCIT/RIPT
VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN
TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ
2.2. Cấutrúcđạisố2.2. Cấutrúcđạisố
•Định nghĩa nhóm xyclic.
–Định nghĩalũythừanhưlà việcápdụng lặp phép toán:
Ví dụ: a3= a.a.a
–Và đơnvịe=a0
–Một nhóm đượcgọi là xyclic nếumọiphầntửđềulàlũy
thừacủamộtphầntửcốđịnh nào đó. Chẳng hạnb = a
k
đốivớia cốđịnh và mỗi b trong nhóm. Khi đóa được
gọilàphầntửsinh của nhóm.
TT CNTT HN Wednesday, April 25, 2012
CCIT/RIPT 3
Trang 5© 2009 | CCIT/RIPT
VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN
TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ
2.2. Cấutrúcđạisố2.2. Cấutrúcđạisố
•Vành: Cho mộttập R các “số” với hai phép toán đượcgọilàcộng và
nhân. Ở đây “số” đượchiểulàphầntửcủatậphợp và hai phép toán trên
xác định trên tậphợpđó. Tậpvới hai phép toán trên đượcgọilàvành,
nếu hai phép toán thoảmãn các tính chấtsau:
–Với phép cộng, R là nhóm Aben
–Với phép nhân, có:
–tính đóng và
–tính kếthợp
–tính phân phốiđốivới phép cộng a(b+c) = ab + ac
–Nếu phép nhân có tính giao hoán thì tạo thành vành giao hoán.
–Nếu phép nhân có nghịch đảo và không có thương 0 (tức là không có hai
phần khác 0 mà tích của chúng lạibằng 0), thì nó tạo thành miền nguyên
Trang 6© 2009 | CCIT/RIPT
VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN
TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ
2.2. Cấutrúcđạisố2.2. Cấutrúcđạisố
•Trường là mộttậphợpF với hai phép toán cộng và nhân, thoảmãn tính chấtsau:
–Với phép cộng F là nhóm Aben
–Với phép nhân F trừphầntử0 là nhóm Aben.
–F là mộtvành
Có thểnói là có các phép toán cộng, trừ, nhân, chia sốkhác 0. Phép trừđượccoi
nhưlà cộng vớisốđốicủa phép cộng và phép chia là nhân vớisốđốicủa phép
nhân:
a– b = a + (-b)
a / b = a.b-1
•Ví dụ: Dễdàng thấy, với phép cộng và nhân thông thường:
–Tậpsốnguyên Z là nhóm Aben với phép cộng
–Tậpsốnguyên Z là vành giao hoán.
–TậpsốhữutỉQ là trường.
–Tậpsốthực R là trường.
–Tậpsốphức C là trường với phép cộng và nhân hai sốphức.
TT CNTT HN Wednesday, April 25, 2012
CCIT/RIPT 4
Trang 7© 2009 | CCIT/RIPT
VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN
TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ
2.3. Sốhọc Modulo2.3. Sốhọc Modulo
•Cho sốtựnhiên n và sốnguyên a. Ta định nghĩa: a mod n là
phầndưdương khi chia a cho n.
•Định nghĩa quan hệtương đương trên tậpsốnguyên a ≡ b mod
n khi và chỉkhi a và b có phầndưnhưnhau khi chia cho n.
Trang 8© 2009 | CCIT/RIPT
VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN
TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ
2.3. Sốhọc Modulo2.3. Sốhọc Modulo
•Ví dụ: 100 mod 11 = 1; 34 mod 11 = 1, nên 100 ≡ 34 mod 11
•Sốb đượcgọilàđạidiệncủaa, nếua ≡ b mod n (a = qn + b) và
0 <= b < n.
•Ví dụ: -12 mod 7 ≡ -5 mod 7 ≡ 2 mod 7 ≡ 9 mod 7. Ở đây 2 là đạidiện
của –12, -5, 2 và 9.
•Trong Modulo 7 ta có các lớptuơng đương viết trên các hàng nhưsau:
–
–Các phầntửcùng cột là có quan hệđồng dư
với nhau.
–Tậpcácđạidiệncủacácsốnguyên theo
Modulo n gồmn phầntửký hiệunhưsau:
Zn = { 0, 1, 2, 3, …, n-1 }.
TT CNTT HN Wednesday, April 25, 2012
CCIT/RIPT 5
Trang 9© 2009 | CCIT/RIPT
VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN
TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ
2.3. Sốhọc Modulo2.3. Sốhọc Modulo
Ướcsố
•Sốb không âm đượcgọilàướcsốcủaa, nếucósốm sao cho: a = mb
trong đóa, b, m đều nguyên.
•Tức là a chia hết cho b, ký hiệulà b|a
•Ví dụ: 1, 2, 3, 4, 6, 8, 12, 24 là các ướcsốcủa24
Trang 10 © 2009 | CCIT/RIPT
VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN
TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ
2.3 Các phép toán sốhọc trên Modulo2.3 Các phép toán sốhọc trên Modulo
•Cho trướcmộtsốn. Ta muốnthựchiện các phép toán theo Modulo của
n. Ta có thểthựchiệncácphéptoántrêncácsốnguyên nhưcác phép
cộng, nhân các sốnguyên thông thường sau đórútgọnlạibằng phép lấy
Modulo hoặccũng có thểvừa tính toán, kếthợpvớirútgọntạibấtcứ
thờiđiểmnào:
(a+b) mod n = [a mod n + b mod n] mod n (*)
(a.b) mod n = [a mod n . b mod n] mod n (**)
•Như vậy khi thực hiện các phép toán ta có thể thay các số bằng các số
tương đương theo Modulo n đó hoặc đơn giản hơn có thể thực hiện các
phép toán trên các đại diện của nó: Zn = { 0, 1, 2, 3, …, n-1 }.