CƠ SỞ TOÁN HỌC

Trong phần này chúng ta sẽ nhắc lại tóm tắt một số kiến thức toán học, là cơ sở cho Lý thuyết mật mã được sử dụng xuyên suốt tài liệu này. Các kết quả quan trọng của Lý thuyết số cũng sẽ được trình bầy và có ví dụ cụ sở toán học bản đồ bao gồm những vấn đề: Tỷ lệ bản đồ, bố cục bản đồ, sai số, các phép chiếu bản đồ tỷ lệ nhỏ; các phép chiếu bản đồ tỷ lệ lớn | Chương CƠ SỞ TOÁN HỌC Trong phần này chúng ta sẽ nhắc lại tóm tắt một số kiến thức toán học là cơ sở cho Lý thuyết mật mã được sử dụng xuyên suốt tài liệu này. Các kết quả quan trọng của Lý thuyết số cũng sẽ được trình bầy và có ví dụ cụ thể. Nội dung chính I. Lý thuyết thông II. Lý thuyết về độ phức III. Lý thuyết Lý thuyết Mât mã và An toàn thông tin w r Á .1 . I. Lý thuyết thông tin 1. Entropy X là một biến ngẫu nhiên trong một tập các giá trị xác định x1 x2 . xn với xác suất P X Xị pi 0 pi 1 1 i n p 1 Cũng như vậy Y và Z cũng là các biến ngẫu nhiên. Entropy của X là một phép đo toán học khối lượng thông tin được cung cấp bởi một sự quan sát X. Tương đương nó là một sự không chắc chắn về kết quả trước một sự quan sát của X. Entropy cũng hữu dụng cho xấp xỉ số bit trung bình được yêu cầu để mã hóa yếu tố X. . Định nghĩa Entropy hoặc sự không chắc chắn của X được định nghĩa bởi n n 1 H X - Pi .lgPi -p- mà PilgPi Pilg 1 p 0 nếu Pi 0 . Tính chất của Entropy X là một biến ngẫu nhiên i 0 H X Ign ii H X 0 pi 1 và Pj 0 Ỵj i iii H X Ign pi 1 n và 1 i n . Định nghĩa Entropy kết hợp của X và Y được định nghĩa H X Y -yP X x Y y .lg P X x Y y x y Định nghĩa trên có thể được mở rộng tới bất kỳ số lượng biến ngẫu nhiên nào. Lê Thụy 2 Trường Đai hoc Dân lâp Hải Phòng . Định lý Nếu X và Y là các biến ngẫu nhiên thì H X Y H X H Y . Dấu xảy ra nếu X và Y là độc lập. . Định nghĩa Nếu X và Y là các biến ngẫu nhiên thì Entropy điều kiện của X được cho bởi Y y là H X Y y -yP X x Y y .lg P X x Y y x Entropy điều kiện của X được cho bởi Y cũng được gọi là sự lập lờ của Y về X H X Y ỵ P Y y .H X Y y y . Tính chất của Entropy điều kiện X và Y là các biến ngẫu nhiên i Số lượng H X Y đo khối lượng sự không chắc chắn duy trì về phía X sau khi Y được quan sát. ii H X Y 0 và H X X 0 iii H X Y H X H Y X H Y H X Y iv H X Y H X . Dấu xảy ra nếu X và Y là độc lâp. 2. Thông tin qua lại mutual information . Định nghĩa thông tin qua lại hoặc thông tin .