TỔNG QUAN VỀ MÃ MẠNG 9
Chương 1 của luận án trình bày các kiến thức lý thuyết cơ bản, phục vụ cho các nghiên cứu tiếp theo Nội dung chương này bao gồm tổng quan về lý thuyết thông tin và mã hóa, cùng với định nghĩa, mô hình, phương pháp thực hiện và những lợi ích của mã mạng.
1 1 TỔNG QUAN CHUNG VỀ LÝ THUYẾT THÔNG TIN VÀ MÃ HÓA
Người khởi xướng lý thuyết thông tin là Hartley R V L, người đã giới thiệu khái niệm đo lượng thông tin vào năm 1928, cho phép so sánh định lượng các hệ thống truyền tin Năm 1933, V A Kachenhicov đã chứng minh nhiều luận điểm quan trọng của lý thuyết thông tin trong bài báo về khả năng thông qua của không trung và dây dẫn trong hệ thống liên lạc điện Tiếp theo, vào năm 1935, D V Ageev phát triển công trình "Lý thuyết tách tuyến tính", nêu ra các nguyên tắc cơ bản về tách tín hiệu Đến năm 1946, V A Kachenhicov tiếp tục công bố các nghiên cứu liên quan đến lý thuyết thông tin.
“Lý thuyết thế chống nhiễu’ đánh dấu một bước phát triển rất quan trọng của lý thuyết thông tin
Trong giai đoạn 1948 - 1949, Shanon C E đã công bố nhiều công trình quan trọng, đánh dấu bước tiến vượt bậc trong sự phát triển của lý thuyết thông tin Ông đã giới thiệu khái niệm lượng thông tin và phân tích cấu trúc thống kê của tin, từ đó chứng minh các định lý về khả năng truyền tải của kênh thông tin trong điều kiện nhiễu, cũng như các định lý mã hóa Những công trình này đã tạo nền tảng vững chắc cho lý thuyết thông tin.
Ngày nay, lý thuyết thông tin phát triển theo hai hướng chủ yếu sau:
Lý thuyết thông tin toán học xây dựng các luận điểm và cơ sở toán học vững chắc, đóng vai trò quan trọng trong lĩnh vực lý thuyết thông tin Những đóng góp nổi bật đến từ các nhà bác học lỗi lạc như N Wiener, A Feinstain, C.E Shannon, A.N Kolmogorov và A.J.A Khinchin.
Lý thuyết thông tin ứng dụng, hay lý thuyết truyền tin, tập trung vào việc giải quyết các vấn đề thực tiễn quan trọng liên quan đến kỹ thuật liên lạc, đặc biệt là chống nhiễu và nâng cao độ tin cậy trong truyền tin Nhiều nhà khoa học nổi tiếng như C.E Shannon, S.O Rice, D Middleton, W Peterson, A.A Khakevich và V Kachenhicov đã có những đóng góp đáng kể cho lĩnh vực này.
Thông tin là các đặc tính xác định của vật chất mà con người hoặc hệ thống kỹ thuật thu nhận từ thế giới bên ngoài hoặc từ các quá trình diễn ra bên trong chính nó.
Theo định nghĩa, mọi ngành khoa học đều khám phá cấu trúc thông qua việc thu thập và xử lý thông tin Ở đây, "thông tin" được hiểu là một danh từ, không phải hành động giữa hai đối tượng Trong triết học, thông tin được coi là một thuộc tính của thế giới vật chất, tương tự như năng lượng và khối lượng Thông tin không được tạo ra mà chỉ được hệ thụ cảm sử dụng, và tồn tại một cách khách quan, không phụ thuộc vào hệ thụ cảm Trong nghĩa tổng quát, thông tin thể hiện sự đa dạng, có thể hiểu theo nhiều khía cạnh như tính ngẫu nhiên và mức độ tổ chức.
Tin là một dạng vật chất cụ thể dùng để biểu diễn hoặc thể hiện thông tin, bao gồm hai loại chính: tin rời rạc và tin liên tục Ví dụ về tin rời rạc có thể là tấm ảnh, bản nhạc, bảng số liệu và bài nói.
- Tín hiệu: Tín hiệu là các đại lượng vật lý biến thiên, phản ánh tin cần truyền
Nguồn tin là nơi sản sinh ra thông tin, được chia thành hai loại: nguồn rời rạc và nguồn liên tục Nguồn rời rạc có tập tin hữu hạn, trong khi nguồn liên tục có tập tin vô hạn Hai tính chất chính của nguồn tin là tính thống kê và tính hàm ý Tính thống kê ở nguồn rời rạc thể hiện qua xác suất xuất hiện khác nhau của các tin, trong khi tính hàm ý cho thấy xác suất xuất hiện của một tin cụ thể sau một chuỗi tin khác cũng khác nhau.
Máy phát là thiết bị chuyển đổi tập tin thành tín hiệu tương ứng, sử dụng phép biến đổi đơn trị hai chiều để đảm bảo tín hiệu có thể được tái tạo chính xác ở bên thu Trong cấu trúc tổng quát, máy phát bao gồm hai khối chính.
Thiết bị mã hoá sử dụng tổ hợp các ký hiệu đã chọn để mã hóa thông tin, từ đó tăng mật độ dữ liệu, nâng cao khả năng chống nhiễu và cải thiện tốc độ truyền tin.
Khối điều chế là thiết bị chuyển đổi tập tin (có thể mã hóa hoặc không) thành tín hiệu để phát ra sóng điện từ cao tần Mọi máy phát đều trang bị khối điều chế này để thực hiện chức năng phát sóng.
Đường truyền tin là môi trường vật lý cho phép tín hiệu được truyền từ máy phát đến máy thu Tuy nhiên, trong quá trình truyền tải, tín hiệu có thể bị ảnh hưởng bởi các tác động bên ngoài, dẫn đến việc mất năng lượng và thông tin.
Máy thu là thiết bị có chức năng lập lại thông tin từ tín hiệu nhận được, thực hiện phép biến đổi ngược lại với máy phát Nó chuyển đổi tập tín hiệu thu được thành tập tin tương ứng Máy thu bao gồm hai khối chính: Giải điều chế, giúp biến đổi tín hiệu nhận được thành tin đã mã hóa, và Giải mã, chuyển đổi các tin đã mã hóa thành các tin tương ứng ban đầu từ nguồn gửi đi.
Nhận tin có ba chức năng chính: ghi giữ tin, biểu thị tin và xử lý tin Ghi giữ tin tương tự như bộ nhớ của máy tính, băng ghi âm hay ghi hình Biểu thị tin giúp các giác quan của con người hoặc các bộ cảm biến nhận diện và xử lý thông tin, ví dụ như băng âm thanh, chữ số và hình ảnh Cuối cùng, xử lý tin là quá trình biến đổi thông tin thành dạng dễ sử dụng, có thể thực hiện bởi con người hoặc máy móc.
- Kênh truyền tin: là tập hợp các thiết bị kỹ thuật phục vụ cho việc truyền tin từ nguồn đến nơi nhận tin
ĐỀ XUẤT XÂY DỰNG MÃ MẠNG TRÊN MỘT SỐ CẤU TRÚC ĐẠI SỐ 27
MỘT SỐ CẤU TRÚC ĐẠI SỐ
Chương 2 cung cấp kiến thức cơ bản về số học modulo và các cấu trúc đại số liên quan Từ nền tảng này, NCS tập trung nghiên cứu và đề xuất các phương pháp mã hóa mạng thông qua các phép toán cộng, nhân trên số học hoặc đa thức, cùng với cấu trúc đại số nhóm cộng các điểm trên đường cong elliptic.
Các kết quả nghiên cứu ở chương 2 đã được công bố trên các bài báo:
Bài báo 1: (2018) , Nguyễn Bình, Ngô Đức Thiện, Nguyễn Lê
Cường, “Mã mạng trên một số cấu trúc đại số”, Tạp chí Nghiên cứu Khoa học và công nghệ Quân sự, trang 125-132, No 54, 4/2018)
Bài báo 2: (2019) Au Pham Long, Thien Ngo Duc and Binh Nguyen, "About
Some Methods of Implementing Network Coding based on Polynomial Rings and
Polynomial Fields," 2019 25th Asia-Pacific Conference on Communications
(APCC), Ho Chi Minh City, Vietnam, 2019, pp 507-510, doi:
10 1109/APCC47188 2019 9026530; (PoD) ISSN: 2163-0771, IEEE Xplore
Bài báo 3: (2019) Pham Long Au, Nguyen Minh Trung, Nguyen Le Cuong,
“About Some Methods of Implementation Network Coding over Number Rings”,
Proceedings of the 12th international conference on advanced technologies for communication, page 371-374, ATC 10/2019; ISSN: 2162-1039 IEEE Xplore;
Bài báo 4: (2019) Pham Long Au, Ngo Duc Thien, “About one method of
Implementation Network Coding based on point additive operation on Elliptic curve” Journal of Science and Technology on Information and Communications,
2 1 MÔT SỐ PHƯƠNG PHÁP XÂY DỰNG MÃ MẠNG TRÊN VÀNH SỐ
Cho �, � Z∈ , � là ước của � nếu ∃� ∈ ℤ: � = � � Ký hiệu: �|�
Các tính chất chia hết
+ Nếu �|� và �|� thì �|(�� + ��) với ∀�, � ∈ ℤ + Nếu �|� và �|� thì � = ± � Định nghĩa 2 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 � ≥ 1 thì � = �� + �, 0 ≤ � < �, � và � là duy nhất
Phần dư của phép chia a và b được ký hiệu � mod � = �
Thương của phép chia a và b được ký hiệu � div � = �
� = 73, � = 17 → 73div17 = 4, 73mod17 = 5 Định nghĩa 2 3: Ước chung c là ước chung của a và b nếu �|� & �|� Định nghĩa 2 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 � = (�, �)) nếu:
- d là ước chung của a và b
Như vậy (�, �) 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 Định nghĩa 2 5: Bội chung nhỏ nhất (BCNN)
Số nguyên dương d là bội chung nhỏ nhất (BCNN) của các số nguyên a và b
Như vậy d là số nguyên dương nhỏ nhất là bội của cả a và b
Hai số nguyên dương a và b được gọi là nguyên tố cùng nhau nếu ước chung lớn nhất của chúng là 1, ký hiệu là (a, b) = 1 Số nguyên p ≥ 2 được gọi là số nguyên tố khi các ước dương của nó chỉ có 1 và p, trong khi nếu không thỏa mãn điều kiện này, p được gọi là hợp số Định lý cơ bản của số học khẳng định tầm quan trọng của các số nguyên tố trong cấu trúc của các số tự nhiên.
Với mỗi số nguyê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ố
Trong đó �� là các số nguyên tố khác nhau và �� là các số nguyên dương Hơn nữa phân tích trên là duy nhất
Với � ≥ 2, hàm �(�) được xác định là số các số nguyên trong khoảng [1, �] nguyên tố cùng nhau với �
Các tính chất của hàm � ( � )
Nếu p là số nguyên tố thì �(�) = � − 1
Cho � và � là các số nguyên không âm và nhỏ hơn hoặc bằng � × � = � × �
Số bit trong biểu diễn nhị phân của n là [lg n] + 1, xấp xỉ bằng lgn Số phép toán bit cho bốn phép toán cơ bản: cộng, trừ, nhân và chia được thực hiện theo các thuật toán cổ điển Các kỹ thuật tinh vi hơn cho phép toán nhân và chia có thể đạt độ phức tạp thấp hơn Độ phức tạp bit của các phép toán cơ bản trong ℤ có thể được tính theo định lý liên quan đến ƯCLN của hai số nguyên a và b.
Phép toán Độ phức tạp bit
0(lg� + lg�) = 0(lg�) 0(lg� + lg�) = 0(lg�) 0((lg�) (lg�)) = 0((lg�) ) 2
Nếu � = �1 1 �2 2 … �� � là phân tích ra thừa số nguyên tố của n thì:
� � � � � � min(� 1 ,� 1 ) min(� 2 ,� 2 ) max(� 1 ,� 1 ) max(� 2 ,� 2 ) min(� � ,� � ) max(� � ,� � )
Ví dụ : Cho � = 4864 = 28 19, � = 3458 = 2 7 13 19 Khi đó: ƯCLN(�, �) = (4864, 3458) = 2 19 = 38
����(�, �) = (4864, 3458) = 28 7 13 19 = 442624 Định lý 2 3: Nếu � và � là các số nguyên dương với � > � thì:
Thuật toán Euclid 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ố a) Thuật toán Euclid
Thuật toán Euclid là phương pháp hiệu quả để tính ước chung lớn nhất (ƯCLN) của hai số nguyên dương Thuật toán bắt đầu với cặp số ban đầu và tạo ra cặp số mới bằng cách lấy số nhỏ hơn và phần dư của phép chia hai số đó Quá trình này tiếp tục cho đến khi hai số trong cặp trở nên bằng nhau, lúc này giá trị đó chính là ƯCLN Nguyên lý chính của thuật toán là ƯCLN không thay đổi khi hiệu của hai số trong cặp được tính Bằng cách giảm giá trị của số lớn hơn, thuật toán cho phép tạo ra các số ngày càng nhỏ cho đến khi kết thúc, khi cặp số còn lại trở thành bằng nhau.
VÀO: Hai số nguyên không âm a và b với � > �
(2) Return (a) Định lý 2 2: Nếu � = �1 1 �2 2 … �� � , � = �1 1 �2 2 … �� � trong đó �� ≥ 0, �� ≥ 0
Thuật toán trên có thời gian chạy chừng O(2 log2 �) các phép toán bit
Ví d ụ: Cho � = 4864 và � = 3458, các bước của thuật toán Euclid khi tính ƯCLN (�, �) như sau:
Thuật toán Euclid mở rộng không chỉ cho phép tính ƯCLN của hai số nguyên a và b, mà còn tìm ra các số nguyên x và y sao cho ax + by = ƯCLN(a, b).
Giải thuật Euclid mở rộng được sử dụng để giải một phương trình vô định nguyên (còn được gọi là phương trình Đi-ô-phăng) có dạng: �� + �� = �
Để phương trình có nghiệm nguyên, điều kiện cần và đủ là ƯCLN(a, b) phải là ước của c, trong đó a, b, c là các hệ số nguyên và x, y là các ẩn nhận giá trị nguyên.
� Khẳng định này dựa trên một mệnh đề sau:
Nếu d = ƯCLN(a, b) thì tồn tại các số nguyên x, y sao cho �� + �� = �
VÀO : Hai số nguyên không âm a và b với � > �
RA : � = CLN(Ư �, �) và các số nguyên x và y thoả mãn
Thuật toán trên có thời gian chạy cỡ 0((lg�)2) các phép toán bit
Ví d ụ: Bảng sau chỉ ra các bước của thuật toán trên với các giá trị vào � = 4864 và � = 3458
Bảng 2 1 Ví dụ thuật toán Euclid mở rộng
Bởi vậy ta có: ƯCLN(4864, 3458) = 38 và (4864)(32) + (3458)(-45) = 38
2 1 1 3 Các số nguyên modulo n Định nghĩa 2 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à � ≡ �mod�) nếu �|(� − �)
Số nguyên n được gọi là modulo đồng dư
Các tính chất Đối với �, �1, �, �1, � ∈ ℤ ta có:
(1) � ≡ �mod� nếu và chỉ nếu a và b cũng có phần dư khi chia cho n
(3) Tính đối xứng: Nếu � ≡ �(mod�) thì � ≡ �(mod�)
Tính bắc cầu: Nếu � ≡ �(mod�) và � ≡ �(mod�) thì � ≡ �(mod�)
(4) Nếu � ≡ �1(mod�) và � ≡ �1(mod�) thì
Lớp tương đương của một số nguyên \( a \) là tập hợp các số nguyên đồng dư với \( a \) theo modulo \( n \) Dựa vào các tính chất đã nêu, ta có thể thấy rằng với mỗi \( n \) cố định, quan hệ đồng dư theo modulo \( n \) sẽ phân hoạch tập hợp số nguyên ℤ thành các lớp tương đương Nếu \( a = kn + r \) với \( 0 \leq r < n \), thì \( a \equiv r \,(\text{mod } n) \).
Mỗi số nguyên a có một thặng dư tối thiểu duy nhất trong khoảng từ 0 đến n-1 khi xét theo modulo n.
Các số nguyên modulo n, ký hiệu ℤ_n, là tập hợp các lớp tương đương của các số nguyên từ 0 đến n-1 Trong ℤ_n, các phép toán cộng, trừ và nhân được thực hiện theo quy tắc modulo n.
Tương tự 13 16 = 8 trong ℤ25 Định nghĩa 2 11: Phần tử nghịch đảo
Cho � ∈ ℤ�, phần tử nghịch đảo (ngược theo phép nhân) của � mod � là một số nguyên � ∈ ℤ� sao cho: � � ≡ 1(mod�)
Nếu x tồn tại thì nó là duy nhất, � được gọi là khả nghịch Phần tử nghịch đảo của � được ký hiệu là �−1 Định nghĩa 2 12:
Phép chia của với � cho � mod � là tích của a và �−1mod� tích này được xác định nếu b là phần tử khả nghịch Định lý 2 4:
Cho � ∈ ℤ�, khi đó a là khả nghịch nếu và chỉ nếu: (�, �) = 1
Các phần tử khả nghịch trong ℤ9 là 1, 2, 4, 5, 7 và 8 Chẳng hạn 4−1 = 7 vì
Cho \( a = (a, n) \), phương trình đồng dư \( ax \equiv 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 trong khoảng từ 0 đến \( n - 1 \) Những nghiệm này là tất cả các đồng dư theo modulo \( n/d \).
Nếu các số nguyên �1, �2, … , �� 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 modn 1 x a 2 modn 2 x a k modn k sẽ có nghiệm duy nhất theo modulo �(� = �1, �2, … , �� )
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:
Các tính toán này có thể được thực hiện trong 0((lg�)2) các phép toán trên bit
Ví d ụ: Cặp phương trình đồng dư � ≡ 3(mod7), � ≡ 7(mod13) có nghiệm duy nhất � ≡ 59(mod91) Định lý 2 7: Nếu (�1, �2) = 1 thì cặp phương trình đồng dư
Trong lý thuyết số, nếu có hai phương trình đồng dư là \( x \equiv a \,(\text{mod } m_1) \) và \( x \equiv b \,(\text{mod } m_2) \), thì tồn tại một nghiệm duy nhất \( x \equiv c \,(\text{mod } m_1, m_2) \) Nhóm nhân của \( \mathbb{Z}_n \) được ký hiệu là \( \mathbb{Z}_n^* = \{ k \in \mathbb{Z}_n \,|\, (k, n) = 1 \} \) Đặc biệt, nếu \( n \) là số nguyên tố, thì \( \mathbb{Z}_n^* = \{ k \,|\, 1 \leq k \leq n - 1 \} \) Cấp của nhóm \( \mathbb{Z}_n^* \) được định nghĩa là số lượng phần tử trong \( \mathbb{Z}_n^* \) và được ký hiệu là \( |\mathbb{Z}_n^*| \).
Theo định nghĩa của hàm Phi-Euler ta thấy:
Chú ý: nếu � ∈ ℤ∗� và � Z∈ �∗ thì �, � ∈ ℤ∗� và bởi vậy ℤ∗� là đóng đối với phép nhân Định lý 2 8: Cho p là một số nguyên tố:
(1) Định lý Euler: Nếu � ∈ ℤ∗� thì �� (�) ≡ 1(mod�)
(2) Nếu n là tích của các số nguyên khác nhau và nếu � ≡ �(mod�(�)) thì
�� ≡ � � (mod�) đố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 �(�) Định lý 2 9:
Cho p là một số nguyên tố:
(1) Định lý Ferma: Nếu (�, �) = 1 thì ��−1 ≡ 1(mod�)
Nếu \( a \equiv b \,(\text{mod} \, p - 1) \), thì \( a^n \equiv b^n \,(\text{mod} \, p) \) đối với mọi số nguyên \( n \) Điều này có nghĩa là khi làm việc với modulo của một số nguyên tố \( p \), các luỹ thừa có thể được rút gọn theo modulo \( p - 1 \).
(3) Đặc biệt �� ≡ �(mod�) với mọi số nguyên � Định nghĩa 2 15:
Cho � ∈ ℤ∗� Cấp của a (ký hiệu là ���(�)) là số nguyên dương nhỏ nhất t sao cho �� ≡ 1(mod�) Định nghĩa 2 16:
Cho � ∈ ℤ∗� , ���(�) = � và � � ≡ 1(mod�) khi đó t là ước của s Đặc biệt �|�(�)
Theo định nghĩa 2.17, cho \( G \in \mathbb{Z}^* \), nếu cấp của \( G \) là \( n \), thì \( \alpha \) được gọi là phần tử sinh hay phần tử nguyên thủy của \( \mathbb{Z}^* \) Nếu \( \mathbb{Z}^* \) có một phần tử sinh, thì \( \mathbb{Z}^* \) được gọi là nhóm cyclic.
Các tính chất của các phần tử sinh của � ∗ �
Ví dụ: Cho � = 21, khi đó Z21 = {1, 2, 3, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20}
Chú ý rằng �(21) = �(7) �(3) = 12 = |Z21| Cấp của các phần tử trong ℤ21∗
Nhóm nhân ℤ∗p có phần tử sinh khi và chỉ khi p = 2, 4, hoặc p = 2^k với k ≥ 1, trong đó p là một số nguyên tố lẻ Đặc biệt, nếu p là một số nguyên tố, thì ℤ∗p luôn có phần tử sinh.
(2) Nếu α là một phần tử sinh của ℤ∗� thì:
Giả sử rằng \( g \) là một phần tử sinh của \( \mathbb{Z}^*_n \), thì \( g^k \mod n \) cũng là một phần tử sinh của \( \mathbb{Z}^*_n \) nếu và chỉ nếu \( \gcd(k, \varphi(n)) = 1 \) Từ đó, có thể kết luận rằng nếu \( \mathbb{Z}^*_n \) là một nhóm cyclic, số lượng các phần tử sinh trong nhóm này sẽ là \( \varphi(\varphi(n)) \).
(4) � ∈ ℤ∗� là một phần tử sinh của ℤ∗� nếu và chỉ nếu � �(�)/� ≠ 1(mod�) đối với mỗi nguyên tố p của �(�)
(Chú ý rằng 21 không thoả mãn điều kiện (1) ở trên)