Chương 1: KHÁI NIỆM CƠ SỞ 1. KHÁI NIỆM CƠ SỞ VỀ TOÁN HỌC 1. Khái niệm về số đồng dư 1. Khái niệm Cho các số nguyên a, b, m (m > 0).
Ta nói rằng a và b “đồng dư” với nhau theo modulo m, nếu chia a và b cho m, ta nhận được cùng một số dư. Một số tính chất 1/ Quan hệ “đồng dư” là quan hệ tương đương trong Z: Với mọi số nguyên dương m ta có: a ≡ a (mod m) với mọi a Z; (tính chất phản xạ). 2/ Tổng hay hiệu các “đồng dư”: Có thể cộng hoặc trừ từng vế nhiều đồng dư thức theo cùng một modulo m, ta được một đồng dư thức theo cùng modulo m, tức là: k k Nếu ai ≡ bi (mod m), i = 1.k, thì ti ai tibi (mod m) với ti = ± 1. i 1 i 1 3/ Tích các “đồng dư”: Có thể nhân từng vế nhiều đồng dư thức theo cùng một modulo m, ta được một đồng dư thức theo cùng modulo m, tức là: k k Nếu ai ≡ bi (mod m) với i=1.k, thì ta có: ai bi (mod m) i 1 i 1 4/ Hệ quả: * Có thể cộng hoặc trừ cùng một số vào hai vế của một đồng dư thức.
* Có thể chuyển vế các số hạng của đồng dư thức bằng cách đổi dấu các số hạng đó. * Có thể cộng vào một vế của đồng dư thức một bội của modulo: LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 4 a ≡ b (mod m) → a+km ≡ b (mod m) với mọi k Z. * Có thể nhân hai vế của một đồng dư thức với cùng một số: a ≡ b (mod m) → ac ≡ bc (mod m) với mọi c Z. * Có thể nâng lên lũy thừa bậc nguyên không âm cho 2 vế của một đồng dư thức: a ≡ b (mod m) → an ≡ bn (mod m) với mọi n Z+ * Có thể chia 2 vế đồng dư thức cho một ước chung nguyên tố với modulo: c\a, c\b, (c, m) = 1, a ≡ b (mod m) a/c ≡ b/c (mod m) * Có thể nhân 2 vế đồng dư thức và modulo với cùng một số nguyên dương, Nếu a ≡ b (mod m), c >0 ac ≡ bc (mod mc) * Có thể chia 2 vế đồng dư thức và modulo cho cùng một số nguyên dương là ước chung của chúng: Nếu c\(a, b, m) a/c ≡ b/c (mod m/c) * a ≡ b (mod m) a ≡ b (mod k) với k\m * a ≡ b (mod m) gcd(a, m) = gcd(b, m) 1.
Khái niệm về độ phức tạp tính toán Lý thuyết thuật toán và các hàm số tính được ra dời từ những năm 30 của thế kỷ 20 đã đặt nền móng cho việc nghiên cứu các vấn đề “tính được”, ”giải được” trong toán học. Tuy nhiên, từ cái “tính được” đến việc tính toán trong thực tế là một khoảng cách rất lớn, có rất nhiều vấn đề chứng minh là có thể tính được nhưng không thể trong thực tế dù có sự hỗ trợ của máy tính. Vào những năm 1960 lý thuyết độ phức tạp tính toán được hình thành và phát triển nhanh chóng, cung cấp nhiều hiểu biết sâu sắc về bản chất phức tạp của các bài toán và thuật toán, cả những bài toán thuần túy lý thuyết đến những bài toán thường gặp trong thực tế. Độ phức tạp tính toán (về không gian hay thời gian) của một tiến trình tính toán là số ô nhớ được dùng hay số các phép toán sơ cấp được thực hiện trong tiến trình tính toán đó.
Dữ liệu đầu vào đối với một thuật toán thường được biểu diễn qua các từ trong một bảng ký tự nào đó. Độ dài của một từ là số ký tự trong từ đó. Cho một ký tự A trên bảng ký tự Z (tức là có các đầu vào là các từ trong Z). Độ phức tạp tính toán của thuật toán A được hiểu như một hàm số fa(n) sao cho với LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 5 mỗi số nfa(n) là số ô nhớ, hay số phép toán sơ cấp tối đa mà A cần để thực hiện tiến trình tính toán của mình trên các dữ liệu vào có độ dài n.
Ta nói thuật toán A có độ phức tạp thời gian đa thức, nếu có một đa thức P(n) sao cho với mọi n đủ lớn ta có fa(n) P(n), trong đó fa(n) là độ phức tạp tính toán theo thời gian của A [2]. Bài toán P là giải được nếu có thuật toán để giải nó, tức là thuật toán làm việc có kết thúc trên mọi dữ liệu vào của bài toán. Bài toán P là giải được trong thời gian đa thức nếu có thuật toán giải nó với độ phức tạp thời gian đa thức. Các thuật toán có độ phức tạp giống nhau được phân loại vào trong các lớp tương đương.
Ví dụ tất cả các thuật toán có độ phức tạp là n3 được phân vào trong lớp n3 và ký hiệu bởi 0(n3). Số nguyên tố 1. Khái niệm Số nguyên tố là số tự nhiên lớn hơn 1 và chỉ có hai ước là 1 và chính nó. Định lý về số nguyên tố 1/.
Định lý: về số nguyên dương > 1. Mọi số nguyên dương n > 1 đều có thể biểu diễn được duy nhất dưới dạng: n =P1n1.P nkk , trong đó: k, ni ( i =1,2,.,k) là các số tự nhiên, Pi là các số nguyên tố, từng đôi một khác nhau. Cho p = 2k -1, nếu p là số nguyên tố, thì k phải là số nguyên tố. Hàm Euler: Cho số nguyên dương n, số lượng các số nguyên dương bé hơn n và nguyên tố cùng nhau với n được ký hiệu (n) và gọi là hàm Euler.
Nhận xét: Nếu p là số nguyên tố, thì (p) = p-1 Định lý: về Hàm Euler. Nếu n là tích của hai số nguyên tố n = p. (n) = / Z n*/ LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Phương pháp kiểm tra tính nguyên tố Kiểm tra tính nguyên tố của một số nguyên dương là bài toán nảy sinh trong nhiều ứng dụng, đặc biệt là trong lý thuyết mật mã.
Năm 1975 Pratt đã chứng minh nó thuộc lớp NP và thuộc lớp co-NP NP, đây là bài toán “khó”. Phương pháp cổ điển. Kiểm tra tính nguyên tố của một số nguyên dương n theo định nghĩa: Thử lần lượt tìm các ước của n, từ 2 đến n/2. Nếu không tìm được ước nào thì kết luận n là nguyên tố.
Phương pháp “xác suất“. Trên cơ sở các định lý về số nguyên tố, hiện nay người ta có các phương pháp “xác suất” để kiểm tra tính nguyên tố của một số nguyên dương n. Ví dụ như các phương pháp: Solovay-Strassen, Lehmann-Peralta, Miller- Rabin. Định lý Ferma: Nếu p là số nguyên tố, a là số nguyên, thì a p ≡ a (mod p).
Nếu p không chia hết a, thì a p-1 ≡ 1 (mod p). Định lý Euler: Nếu gcd (a, m) = 1 thì a (m) ≡ 1 (mod m). Trường hợp m là số nguyên tố, ta có định lý Ferma. Hệ quả 1: Nếu gcd(c, m) = 1 và a ≡ b (mod (m)) với a, b là các số tự nhiên, thì ca ≡ cb (mod m) và suy ra ca mod m = ca mod (m) mod m.
Hệ quả 2: Nếu các số nguyên e, d thỏa mãn e. LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Tính toán đồng dư của “lũy thừa” lớn 1/. Trường hợp a > (m): Trong trường hợp a > (m), khi ấy b < a.
Người ta dùng Hệ quả 1 để tính “đồng dư” của “lũy thừa” lớn. Trường hợp (m) > a: Trong thực tế tính toán thường gặp m lớn, do đó (m) lớn, thậm chí > a, khi ấy người ta dùng kỹ thuật khác, ví dụ Phương pháp bình phương liên tiếp. * Định lý về Số dư (ĐL Trung Quốc): Cho tập số nguyên tố cùng nhau từng đôi một m1, m2,…mr. Với mỗi bộ số nguyên bất kỳ a1, a2,…ar , hệ phương trình đồng dư: x ≡ ai (mod mi), (i =1, 2, …, r), luôn có nghiệm duy nhất theo modulo m, m = m1.
Nghiệm này có thể tính theo công thức: x = a1m2 m3 … mr b1 + m1 a2 m3 … mr b2 + m1 m2 a3 m3 … mr b3 + …+ m1 m2 … mr-1 ar br (mod m1.m2…mr), Trong đó bi = (m1. m2…mi-1mi+1…mr)-1 (mod mi), với mọi i =1, 2, …, r. Mã hóa DES Quy trình lập mã và giải mã DES [2] 1. Qui trình lập mã DES Thuật toán DES tập trung thực hiện Giai đoạn 3 .của qui trình mã hóa.
Đó là chuyển đổi bản rõ số với 64 bit thành bản mã với 64 bit. Sơ đồ LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Sơ đồ mã hóa DES LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Thực hiện mã hóa DES theo Sơ đồ * Bản rõ là xâu x, Bản mã là xâu y, Khoá là xâu K, đều có độ dài 64 bit.
* Thuật toán mã hóa DES thực hiện qua 3 bước chính như sau: Bước 1: Bản rõ x được hoán vị theo phép hoán vị IP, thành IP (x). Bước 2: Thực hiện 16 vòng mã hoá với những phép toán giống nhau. Dữ liệu được kết hợp với khoá thông qua hàm f : L i = R i -1, R i = L i -1 f (R i -1, k i ), trong đó: là phép toán hoặc loại trừ của hai xâu bit (cộng theo modulo 2)., k16 là các khoá con (48 bit) được tính từ khóa gốc K. Bước 3: Thực hiện phép hoán vị ngược IP-1 cho xâu R16L16, thu được bản mã y.
(Lưu ý thứ tự bit R16 và L16) * Bảng hoán vị ban đầu IP : + bit 1 của IP(x) là bit 58 của x. + bit 2 của IP(x) là bit 50 của x. 8 0 2 4 6 8 0 0 2 4 6 8 0 2 2 4 6 8 0 2 4 4 6 8 0 2 4 6 7 9 1 3 5 7 9 1 3 5 7 9 1 1 3 5 7 9 1 3 3 5 7 9 1 3 5 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 10 * Bảng hoán vị cuối cùng IP-1: 40 8 48 16 56 24 64 32 39 7 47 15 55 23 63 31 38 6 46 14 54 22 62 30 37 5 45 13 53 21 61 29 36 4 44 12 52 20 60 28 35 3 43 11 51 19 59 27 34 2 42 10 50 18 58 26 33 1 41 9 49 17 57 25 1. Tính các khóa con Khóa con k1, k2, … , k16 từ khóa gốc K.