Giáo trình Lý thuyết số

mục chọn trong dữ liệu đầu vào. Ví dụ: (về kích cỡ của một vài đối tượng) (i) Số các bit trong mô tả nhị phân của 1 số nguyên dương n là 1 + ⎣ln(n)⎦. Để đơn giản, cỡ của n sẽ ≈ lg(n) (ii) Nếu f là 1 đa thức bậc k, mỗi hệ số là 1 số nguyên không âm n thì cỡ của f là (k+1)lg(n) bit (iii) Nếu A là 1 ma trận với r hàng, s cột, và với các mục nhập n nguyên không âm thì cỡ của A là r.s.lgn bit 1.3. Định nghĩa Thời gian chạy thực (running time) của một thuật toán với một đầu vào cụ thể là số các thao tác nguyên thủy hoặc các bước thực hiện. Thường một bước cần đến 1 bít thao tác. Nhưng đối với một vài giải thuật, sẽ thuận tiện hơn khi trải qua các bước như: so sánh, chỉ dẫn cơ khí, một chu kì đồng hồ cơ khí, một phép nhân module 1.4. Định nghĩa Trường hợp chậm nhất (worst-case) của thời gian chạy thực của một thuật toán là một cận trên (upper bound) thời gian chạy thực đối với bất kỳ đầu vào nào, được diễn tả như là một hàm của dữ liệu đầu vào. Lê Thụy 6 Trường Đại học Dân lập Hải Phòng 1.5. Định nghĩa Trường hợp trung bình (average-case) của thời gian chạy thực của 1 thuật toán là mức trung bình của thời gian trên tất cả các đầu vào của các cỡ cố định, được diễn tả như là một hàm của dữ liệu đầu vào. 2. Ký hiệu tiệm cận (asymptotic notation) Thường rất khó để nhận biết được thời gian chạy thực của một thuật toán. Trong trường hợp như vậy, một hàm xấp xỉ sẽ được dùng thay thế, nhưng chỉ thu được gần sát với thời gian chạy thực. Chính vì vậy, sẽ tìm hiểu cách mà thời gian chạy thực của một thuật toán tăng như cỡ của bộ dữ liệu đầu vào tăng mà không cần có sự ràng buộc nào. Với những gì dưới đây, các hàm được định nghĩa trên các số nguyên dương và các giá trị thực dương, f và g là hai hàm như vậy. 2.1. Định nghĩa (order notation –sắp xếp kí hiệu ) (i) Cận trên tiệm cận (asymptotic upper bound) : f(n) = O(g(n)) nếu tồn tại một hằng số dương c và 1 số nguyên dương n0 để 0 ≤ f(n) ≤ cg(n) với n ≥ n0. (ii) Cận dưới tiệm cận (asymptotic lower bound) : f(n) = Ω(g(n)) nếu tồn tại một hằng số dương c và 1 số nguyên dương n0 để 0 ≤ cg(n) ≤ f(n) với n ≥ n0. (iii) Cận sát theo tiệm cận (asymptotic tight bound) : f(n) = (g(n)) nếu tồn tại hằng số dương c1 và c2 và 1 số nguyên dương n0 để c1g(n) ≤ f(n) ≤ c2g(n) với n ≥ n0. (iv) Kí hiệu o (o- notation): f(n) = o(g(n)) nếu đối với bất kỳ hằng số c > 0 nào đều tồn tại một hằng n0 > 0 để 0 ≤ f(n) ≤ cg(n) với n ≥ n0. Lê Thụy 7 Lý thuyết Mật mã và An toàn thông tin 2.2. Tính chất của sắp xếp kí hiệu Đối với các hàm bất kì: f(n), g(n), h(n), l(n) thì các điều sau là đúng: * f(n) = O(g(n)) ⇔ g(n) = Ω(f(n)) * f(n) = (g(n)) ⇔ f(n) = O(g(n)) và f(n) = Ω(g(n)) * Nếu f(n) = O(h(n)) và g(n) = O(h(n)) thì (f + g)(n) = O(h(n)) * Nếu f(n) = O(h(n)) và g(n) = O(l(n)) thì (f.g)(n) = O(h(n)l(n)) * f(n) = O(f(n)) * Nếu f(n) = O(g(n)) và g(n) = O(h(n)) thì f(n) = O(h(n)) 2.3. Định lý (sự xấp xỉ của 1 vài hàm phổ biến) (i) Hàm đa thức (polynomial function): Nếu f(n) là một đa thức bậc k với các số hạng dương thì f(n) = (nk). (ii) Với mọi hằng số c > 0 thì logc(n) = (lgn) (iii) Công thức Stirling: Với mọi số nguyên n ≥ 1 thì: ) n12 1(nn ) e n(n2!n) e n(n2 +≤≤ ππ Do đó: n! = )) n 1(1() e n(n2 n θπ + , n! = o(nn) và n! = Ω(2n) (iv) Ta có: lg(n!) = (nlgn) Ví dụ: (so sánh tỉ lệ tăng của 1 vài hàm) ε và c là các hằng số tùy ý với 0 < ε < 1 < c. Các hàm sau được liệt kê theo thứ tự tăng dần của tỉ lệ tăng tiệm cận: 1< ln ln n < lnn < exp ( ln ln lnn n ) < < nεn c < nln n < cn < nn < ncc Lê Thụy 8 Trường Đại học Dân lập Hải Phòng 3. Lớp phức tạp 3.1. Định nghĩa: Một thuật toán thời gian đa thức là một thuật toán mà hàm thời gian chạy thử trường hợp tồi nhất (worst-case running time function) của nó có dạng O(nk), trong đó n là cỡ dữ liệu đầu vào (input) và k là hằng số. Với bất kì thuật toán nào mà thời gian chạy thực của nó không thể bị giới hạn (bound) được gọi là một thuật toán thời gian theo số mũ (exponential- time algorithm) Nói một cách tổng quát, thuật toán thời gian đa thức có thể ngang bằng với các thuật toán tốt hoặc hiệu quả, trong khi thuật toán thời gian theo số mũ lại bị xem là không hiệu quả. Tuy nhiên, đối với một vài tình huống thực tế thì nét riêng biệt này lại không phù hợp. Khi xem xét độ phức tạp của thời gian đa thức (polynomial- time), bậc của đa thức rất quan trọng, thậm chí dù một thuật toán với một thời gian chạy thực của O(nln ln n), n là cỡ của dữ liệu đầu vào (input), thì chậm hơn so với thuật toán có thời gian chạy thực của O(n100). Thuật toán trước có thể nhanh hơn trong thực tế đối với các giá trị n nhỏ hơn, đặc biệt nếu các hằng số bị ẩn bởi kí hiệu O-lớn là nhỏ hơn. Hơn thế nữa, trong mật mã học, độ phức tạp trung bình thì quan trọng hơn nhiều độ phức tạp trong trường hợp tồi nhất (worst-case) - một điều kiện cần thiết cho một lược đồ mã hóa (encryption scheme) để được coi như là an toàn. Mà bài toán giải mã tương ứng thì khó trên trung bình (hoặc chính xác hơn là luôn luôn khó), và không chỉ đối với một vài trường hợp riêng biệt. 3.2. Định nghĩa Một thuật toán thời gian chạy thử số mũ con (subexponential- time algorithm) là một thuật toán mà hàm thời gian chạy thử tồi nhất có dạng eO(n), trong đó n là cỡ của của bộ dữ liệu đầu vào. Lê Thụy 9 Lý thuyết Mật mã và An toàn thông tin Ví dụ: (về thời gian chạy thử số mũ con) A là một thuật toán mà dữ liệu đầu vào hoặc là các phần tử của một trường xác định Fq hoặc là 1 số nguyên q. Nếu thời gian chạy thử được mong chờ của A có dạng: Lq[α, c] = O(exp((c + o(1)(lnq)α(ln ln q)1-α)) trong đó: c là hằng số dương, α = 1 là hằng số thỏa mãn 0 < α < 1 thì A là một thuật toán thời gian chạy thử số mũ con. Quan sát thấy rằng khi α = 0 thì Lq[0, c] là một đa thức trong lnq, trong khi α =1 thì Lq[1, c] là một đa thức trong q. Do đó nên đầy đủ lũy thừa trong lnq. Để đơn giản, lý thuyết độ phức tạp tính toán hạn chế sự chú ý của nó tới các bài toán quyết định (decision problems), ví dụ: Các bài toán mà có câu trả lời YES hoặc NO. Điều này không quá hạn chế trong thực tiễn, vì tất cả các bài toán tính toán sẽ bị bắt gặp (encounter) ở đây có thể là cụm từ như các bài toán quyết định theo một cách như vậy, mà một thuật toán hiệu quả đối với các bài toán quyết định mang lại một thuật toán hiệu quả cho bài toán tính toán và ngược lại. 3.3. Định nghĩa Lớp phức tạp P là tập của tất cả các bài toán quyết định mà có thể giải được trong thời gian đa thức. 3.4. Định nghĩa Lớp phức tạp NP là tập của tất cả các bài toán quyết định cho một câu trả lời YES, có thể được xác minh trong thời gian đa thức bằng cách đưa ra một vài thông tin thêm, gọi là một chứng nhận. Lê Thụy 10 Trường Đại học Dân lập Hải Phòng 3.5. Định nghĩa Lớp phức tạp co-NP là tập của tất cả các bài toán quyết định cho một câu trả lời NO, có thể được xác minh trong thời gian đa thức bằng cách sử dụng một chứng nhận phù hợp. Phải nhấn mạnh rằng nếu một bài toán quyết định trong NP, nó có thể không thuộc trường hợp mà chứng nhận của một câu trả lời YES có thể dễ dàng đạt được. Cái được xác nhận là cái mà giống như một chứng nhận tồn tại và nếu được biết, thì có thể được dùng để xác nhận 1 cách hiệu quả câu trả lời YES. Điều tương tự cũng đúng đối với câu trả lời NO của các bài toán trong co-NP Ví dụ: (bài toán trong NP ). Xem xét một bài toán quyết định sau: Giả thiết: Cho một số nguyên dương n Câu hỏi: n có phải là hợp tử hay không? Nghĩa là, có hai số nguyên a,b >1 để n = a.b không? Hợp tử (composite) thuộc NP bởi vì nếu một số nguyên n là hợp tử thì sự kiện này có thể được kiểm chứng trong thời gian đa thức nếu a là số chia của n, khi 1< a < n (việc chứng nhận trong trường hợp này bao gồm cả số chia a). Điều này cũng đúng trong trường hợp mà hợp tử thuộc về co-NP, nhưng cũng vẫn chưa xác định được là hợp tử có thuộc P hay không? 3.6. Định lý P ⊆ NP và P co-NP ⊆ Dưới đây là các câu hỏi chưa được giải quyết xung quanh vấn đề lý thuyết độ phức tạp: 1. P = NP ? 2. P = co-Np ? 3. P = NP∩ co-NP ? Lê Thụy 11 Lý thuyết Mật mã và An toàn thông tin Hầu hết các chuyên gia đều có ý kiến rằng câu trả lời cho 3 câu hỏi trên là không, mặc dù không có gì chứng minh. Ý kiến về sự qui về được là hữu ích khi so sánh mối tương quan về độ khó của các bài toán. 3.7. Định nghĩa Cho L1 và L2 là 2 bài toán quyết định. L1 là ‘polytime reduce’ đối với L2 và được viết : L1 ≤ p.L2 nếu có một thuật toán giải L1 mà dùng một thuật toán để giải L2 như một thường trình con, và chạy trong thời gian đa thức nếu thuật toán cho L2 được dùng. Nếu L1 ≤ p.L2 thì L2 ít nhất cũng khó như L1 hoặc tương đương. L1 không khó hơn L2 3.10. Định nghĩa L1 và L2 là 2 bài toán quyết định. Nếu L1 ≤ pL2 và L2 ≤ pL1 thì L1 và L2 được coi là tương đương nhau về mặt tính toán (computationally equivalent). 3.11. Tính chất L1 , L2 , L3 là 3 bài toán quyết định (i) Nếu L1 ≤ pL2 và L2 ≤ pL3 thì L1 ≤ pL3 (ii) Nếu L1 ≤ pL2 và L2∈P thì L1∈P 3.12. Định nghĩa Một bài toán quyết định L được nói là NP- trọn vẹn (NP- complete) nếu: (i) L∈NP và (ii) L1 ≤ pL với mọi L1∈ NP Lớp của tất cả các bài toán NP- trọn vẹn được kí hiệu là NPC, Lê Thụy 12 Trường Đại học Dân lập Hải Phòng (iii) Các bài toán NP- trọn vẹn là các bài toán khó nhất trong NP, ít nhất thì cũng khó như bất kì bài toán nào trong NP. Có hàng nghìn bài toán đa dạng như: kết hợp, lý thuyết số, logic, được biết đến như là NP- trọn vẹn. Ví dụ: ( bài toán tổng tập con - subset sum problem ) Cho một tập các số nguyên dương {a1, a2 , , an} và một số nguyên dương s, thì liệu rằng có một tập con của ai là tổng của s hay không ? Bài toán này là NP- trọn vẹn. 3.13. Hệ quả L1 và L2 là 2 bài toán quyết định (i) Nếu L1 là NP- trọn vẹn và L1∈P thì P = NP (ii) Nếu L1∈ NP, L2 là NP- trọn vẹn và L2 ≤ pL1 thì L1 cũng là NP- trọn vẹn (iii) Nếu L1 là NP- trọn vẹn và L1∈ co-NP thì NP = co-NP Theo (1): Nếu một thuật toán thời gian đa thức được áp dụng cho bất kì bài toán NP- trọn vẹn đơn lẻ nào thì đó là trường hợp mà P= NP, một kết quả cực kì đáng ngạc nhiên. Hình 2 sẽ chứng minh mối quan hệ giữa các lớp phức tạp P, NP, co-NP, NPC. Theo (2): Chỉ ra rằng tiến trình dưới đây chứng minh bài toán quyết định L1 là NP- trọn vẹn. (hình 2 – Phỏng đoán mối quan hệ giữa các lớp phức tạp P, NP, co-NP, NPC) Lê Thụy 13 Lý thuyết Mật mã và An toàn thông tin 3.14. Định nghĩa Một bài toán là NP- khó (hard) nếu tồn tại một vài bài toán NP- trọn vẹn mà polytime rút gọn (reduce) tới nó. Chú ý rằng việc phân loại NP- khó thì không hạn chế tới các bài toán quyết định. Quan sát thấy rằng một bài toán NP- trọn vẹn cũng là NP- khó. Ví dụ: (bài toán NP- khó) Cho các số nguyên dương a1, a2 , , an và một số nguyên dương s. Phiên bản của bài toán tổng tập con sẽ yêu cầu tìm ra một tập con của ai mà tính tổng bằng s, được cho như một tập con tồn tại. Bài toán này là NP- khó. 4. Thuật toán ngẫu nhiên (Randomized algorithm) Thuật toán được nghiên cứu trong phần này đã được tiền định trước (deterministic), như các giải thuật có cùng số chuỗi thao tác, số bước thực hiện với cùng dữ liệu đầu vào. Tuy vậy, một giải thuật ngẫu nhiên tạo ra các quyết định ngẫu nhiên tại mỗi thời điểm trong lúc thực thi. Hơn nữa, chuỗi thao tác thực thi của chúng có thể khác so với mỗi thời điểm mà chúng làm việc với cùng dữ liệu đầu vào. Các quyết định ngẫu nhiên được dựa trên các kết quả của số phần tử sinh (generator) ngẫu nhiên. Có nhiều bài toán dành cho các thuật toán ngẫu nhiên mà chúng được biết đến hiệu quả hơn, cả về thời gian và không gian, hơn là các thuật toán tiền định. Thuật toán ngẫu nhiên dành cho các bài toán quyết định có thể được phân lớp theo xác suất mà chúng quay trở lại câu trả đúng. Lê Thụy 14 Trường Đại học Dân lập Hải Phòng 4.1. Định nghĩa A là một thuật toán ngẫu nhiên dành cho bài toán quyết định L A có 0- sided error nếu P(A xuất YES | Câu trả lời của I là YES) = 1 Và P(A xuất YES | Câu trả lời của I là NO) = 0. A có 1- sided error nếu P(A xuất YES | Câu trả lời của I là YES) ≥ 1 2 Và P(A xuất YES | Câu trả lời của I là NO) = 0 A có 2- sided error nếu P(A xuất YES | Câu trả lời của I là YES) 2 3 ≥ Và P(A xuất YES | Câu trả lời của I là NO) 1 3 ≤ Số 1 2 trong định nghĩa 1- sided error là một cái gì đó bất kì và có thể được thay thế bởi bất kì hằng số dương nào. Tương tự, số 2 3 và 1 3 trong định nghĩa. 2-sided error có thể được thay thế lần lượt bằng 1 2 ε+ và 1 2 ε− với bất kì hằng số ε sao cho 10 2 ε< < 4.2. Định nghĩa Thời gian chạy thực được mong chờ của thuật toán ngẫu nhiên là một cận trên (upper bound) thời gian chạy được mong chờ đối với mỗi dữ liệu đầu vào việc mong chờ trên tất cả dữ liệu đầu ra của số phần tử sinh (generator) ngẫu nhiên được dùng bởi thuật toán, được diễn tả như một hàm độ lớn của đầu vào. Lê Thụy 15 Lý thuyết Mật mã và An toàn thông tin 4.3. Định nghĩa. Lớp phức tạp ZPP (zero- sided probabilistic polynomial time) là tập của tất cả các bài toán ngẫu nhiên với 0- sided error, chạy trong thời gian đa thức mong đợi. Lớp phức tạp RP (randomized polynomial time) là tập của tất cả các bài toán quyết định mà có một thuật toán ngẫu nhiên với 1-sided error, chạy trong thời gian đa thức tồi nhất (worst-case). Lớp phức tạp BPP (bounded error probabilistic polynomial time) là tập của tất cả các bài toán quyết định mà có một thuật toán ngẫu nhiên với 2-sided error, chạy trong thời gian đa thức tồi nhất (worst-case). 4.4. Tính chất P ⊆ ZPP ⊆ RP ⊆ BPP và RP ⊆ NP. Lê Thụy 16 Trường Đại học Dân lập Hải Phòng III. Lý thuyết số 1. Số nguyên. Gọi là tập các số nguyên { -2 -1 0 1 2 } ] Và +] là tập các số nguyên không âm {0 1 2 3 } 1.1. Định nghĩa Cho a, b ∈ . Ta nói a chia hết cho b, nếu tồn tại một số nguyên c sao cho a = b.c và ký hiệu là b|a ] 1.2. Tính chất a, b, c ∈ ] (i) a|a. (ii) a|b , b|c, ⇒ a|c. (iii) a|b , a|c ⇒ a|(bx + cy) ∀ x, y ∈ ] . (iv) a|b , b|a ⇒ a = ±b. 1.3. Định nghĩa Cho hai số nguyên bất kì a và b với b>1. Thực hiện phép chía a cho b ta sẽ được hai số q (phần nguyên) và r (phần dư) như sau : a = b.q + r, 0 ≤ r < b trong đó q và r là duy nhất. Phần nguyên (số thương) được ký hiệu là a div b. Phần dư được ký hiệu là a mod b Ta có a, b ∈ ] , b ≠ 0 thì a div b = ⎣a/b⎦, a mod b = a – b⎣a/b⎦ Ví dụ: a = 73, b = 17, thì q = 4 và r = 5, do đó 73 mod 17 = 5 và 73 div 17 = 4. 1.4. Định nghĩa Một số nguyên c được gọi là ước số chung của a và b nếu c|a và c|b 1.5. Định nghĩa Một số không âm d được gọi là ước số chung lớn nhất (greatest common divisor) của a và b, ký hiệu d = gcd(a, b), nếu (i) d là ước số chung của a, b, và (ii) mọi c|a , c|b ⇒ c|d. Có thể nói gcd(a, b) là số lớn nhất mà a và b cùng chia hết. Ta có gcd(0, 0) = 0 Lê Thụy 17 Lý thuyết Mật mã và An toàn thông tin Ví dụ Tập các ước số của 12 và 18 là {±1, ±2, ±3, ±6}, và gcd(12, 18) = 6. 1.6. Định nghĩa Một số không âm d được gọi là bội số chung nhỏ nhất (least common multiple) của hai số a và b, ký hiệu d = lcm(a, b), nếu (i) a|d , b|d, và (ii) mọi a|c , b|c ⇒ d|c. Có thể nói lcm(a, b) là số nhỏ nhất có thể chia hết cả a và b. 1.7. Tính chất Nếu a và b là hai số nguyên xác định thì lcm(a, b) = a.b/gcd(a, b). Ví dụ Ta có gcd(12, 18) = 6, do đó lcm(12, 18) = 12.18/6 = 36 1.8. Định nghĩa Hai số nguyên a và b được gọi là nguyên tố cùng nhau, nếu gcd(a, b) = 1. 1.9. Định nghĩa Một số nguyên p ≥ 2 được gọi là số nguyên tố nếu nó chỉ chia hết cho 1 và p. Ngược lại p được gọi là hợp số. 1.20. Tính chất (i) Nếu p là số nguyên tố và p|a.b thì ta có p|a hoặc p|b hoặc cả hai đều chia hết cho p (ii) Có vô số số nguyên tố. 1.21. Định lý Đặt π(x) là tập các số nguyên tố ≤ x, ( )lim 1. / ln( )x x x x π →∞ = Nghĩa là với một giá trị x lớn, thì π(x) sẽ xấp xỉ bằng biểu thức x/ln(x). Ví dụ, khi x = 1010, π(x) = 455.052.511, và ⎣x/ln(x)⎦ = 434.294.481 1.22. Hệ quả Đặt π(n) là tập các số nguyên tố ≤ n, với n ≥ 17 π(n) > ln( ) n n Với n > 1 π(n) < 1.25506 ln( ) n n Lê Thụy 18 Trường Đại học Dân lập Hải Phòng 1.23. Định lý Mọi số nguyên n ≥ 2 đều có thể phân tích thành tích các luỹ thừa cơ số nguyên tố như sau: n = 1 21 2 ... k ee e kp p p , trong đó pi là các số nguyên tố, ei là các số nguyên dương. Nếu không kể thứ tự các thừa số nguyên tố thì dạng biểu diễn đó là duy nhất, ta gọi đó là dạng khai triển chính tắc của n. Ví dụ, dạng khai triển chính tắc của 1800 = 233252 1.24. Hệ quả Nếu a = 1 21 2 ... k ee e kp p p , b = 1 21 2 ... k ff f kp p p , ei ≥ 0, fi ≥ 0 thì gcd(a, b) = lcm(a, b) = 1 1 2 2 min( , )min( , ) min( , ) 1 2 ... k k e fe f e f kp p p 1 1 2 2 max( , )max( , ) max( , ) 1 2 ... k k e fe f e f kp p p Ví dụ: a = 4864 = 28.19, b = 3458 = 2.7.13.19 khi đó ta có gcd(4864, 3458) = 2.19 = 38 và lcm(4864, 3458) = 28.7.13.19 = 442624. 1.25. Định nghĩa Với n ≥ 1, đặt φ(n) là số các số nguyên trong khoảng [1, n] và nguyên tố cùng nhau với n. Hàm φ như thế được gọi là hàm phi- Euler. 1.26. Tính chất (i) Nếu p là số nguyên tố, thì φ(p) = p – 1 (ii) Nếu gcd(n, m) = 1, thì φ(n.m) = φ(n).φ(m) (iii) Nếu n = 1 21 2 ... k ee e kp p p , dạng khai triển chính tắc của n, thì φ(n) = 1 2 1 11 1 ... 1 k n 1 p p p ⎛ ⎞⎛ ⎞⎛ ⎞− − −⎜ ⎟⎜ ⎟⎜ ⎟⎝ ⎠⎝ ⎠ ⎝ ⎠ 1.27. Định lý Nếu b ≥ 0 và b|a thì gcd(a, b) = b Nếu a = b.q + r thì gcd(a, b) = gcd(b, r) Thuật toán Thuật toán Euclide, tính ước số chung lớn nhất của hai số. INPUT: Hai số nguyên không âm a và b sao cho a ≥ b. OUTPUT: Ước số chung lớn nhất của a và b. Lê Thụy 19 Lý thuyết Mật mã và An toàn thông tin 1. Trong khi b ≠ 0, thực hiện 1.1 Đặt r ← a mod b, a ← b, b ← r. 2. Kết_quả(a) Ví dụ (Euclidean algorithm) Tính gcd(4864, 3458) = 38: 4864 = 1.3458 + 1406 3458 = 2.1406 + 646 1406 = 2.646 + 114 646 = 5.114 + 76 114 = 1.76 + 38 76 = 2.38 + 0. Thuật toán Euclidean có thể được mở rộng để không chỉ tính được ước số chung d của hai số nguyên a và b, mà còn có thể tính được hai số nguyên x, y thoả mãn ax + by = d Thuật toán Euclidean mở rộng: INPUT: Hai số nguyên không âm a và b với a ≥ b. OUTPUT: d = gcd(a, b) và hai số x, y thoả mãn ax + by = d. 1. Nếu b = 0, đặt d←a , x←1, y←0, Kết_quả(d, x, y). 2. Đặt x2←1, x1←0 , y2 ←0 , y1←1. 3. Trong khi còn b > 0, thực hiện: 3.1 q←⎣a/b⎦, r←a–q.b, x←x2–q.x1, y←y2–q.y1 3.2 a←b, b←r, x2←x1, x1←x, y2←y1, y1←y 4. Đặt d←a, x←x2 , y←y2 , Kết_quả(d, x, y). Lê Thụy 20 Trường Đại học Dân lập Hải Phòng Ví dụ Bảng dưới đây mô tả các bước thực hiện của thuật toán Euclidean mở rộng với đầu vào là a =4864, b = 3458, và nhận được kết quả: gcd(4864, 3458) = 38 và (4864)(32) + (3458)(−45) = 38. q r x y a b x2 x1 y2 y1 − − − − 4864 3458 1 0 0 1 1 1406 1 −1 3458 1406 0 1 1 −1 2 646 −2 3 1406 646 1 −2 −1 3 2 114 5 −7 646 114 −2 5 3 −7 5 76 −27 38 114 76 5 −27 −7 38 1 38 32 −45 76 38 −27 32 38 −45 2 0 −91 128 38 0 32 −91 −45 128 2. Số nguyên Modulo n Cho n là một số nguyên dương. 2.1 Định nghĩa Nếu a và b là hai số nguyên, khi đó a được gọi là đồng dư với b theo modulo n, được viết a ≡ b (mod n) nếu n chia hết (a – b), và n được gọi là modulus của đồng dư. Ví dụ: (i) 24 ≡ 9 (mod 5) vì 24 − 9 = 3.5. (ii) −11 ≡ 17 (mod 7) vì −11 − 17 = −4.7. 2.2. Tính chất (một số tính chất của đồng dư) (i) a ≡ b (mod n), nếu và chỉ nếu a và b đều trả số dư như nhau khi đem chia chúng cho n. (ii) a ≡ a (mod n) (tính phản xạ) (iii) Nếu a ≡ b (mod n) thì b ≡ a (mod n) (tính đối xứng) (iv) Nếu a ≡ b (mod n) và b ≡ c (mod n) thì a ≡ c (mod n) (tính bắc cầu) (v) Nếu a ≡ a1 (mod n) và b ≡ b1 (mod n) thì a + b ≡ a1 + b1 (mod n) và a.b ≡ a1.b1 (mod n) Giờ đây ta có khái niệm lớp tương đương của một sô nguyên a là tập các số nguyên đồng dư với a theo modulo n. Theo các tính chât (ii), Lê Thụy 21 Lý thuyết Mật mã và An toàn thông tin (iii), (iv) trên, có thể thấy với mỗi n, quan hệ đồng dư modulo n chia tập thành các lớp tương đương (phân hoạch). ] 2.3. Định nghĩa Những số nguyên theo modulo n, được ký hiệu là ] n là tập (lớp tương đương của) các số nguyên {0, 1, 2,..., n-1}. Tập ] n có thể được coi là tập hợp tất cả các lớp tương đương theo modulo n. trên tập ] n xác định các phép cộng, trừ, nhân theo modulo n. Ví dụ: ] 25 = {0, 1, 2, , 24}. Trong ] 25, 13 + 16 = 4, vì 13 + 16 = 29 ≡ 4 (mod 25). Tương tự, 13.16 = 8 trong ] 25. 2.4. Định nghĩa Cho a ∈ ] n, số nghịch đảo của a theo modulo n là một số nguyên x ∈ ] n, nếu a.x ≡ 1 (mod n). Nếu tồn tại x như vậy, thì nó là duy nhất và a được gọi là khả nghịch, nghịch đảo của a được ký hiệu là a-1. 2.5. Định nghĩa Cho a, b ∈ ] n, a/b (mod n) = a.b-1 (mod n) được xác định chỉ khi b là khả nghịch theo modulo n. 2.6. Tính chất a ∈ ] n, a là khả nghịch khi và chỉ khi gcd(a, n) = 1. Ví dụ: Các phần tử khả nghịch trong ] 9 là 1, 2, 4, 5, 7, và 8. cho ví dụ, 4−1 = 7 vì 4.7 ≡ 1 (mod 9). 2.7. Hệ quả Cho d = gcd(a, n). Khi đó phương trình đồng dư có dạng a.x ≡ b (mod n) sẽ có nghiệm x khi và chỉ khi d chia hết cho b. Thuật toán Tính phần tử nghịch đảo trên ] n INPUT: a ∈ ] n OUTPUT: a-1 mod n, nếu tồn tại. 1. Sử dụng thuật toán Euclidean mở rộng, tìm x và y để ax + ny = d, trong đó d = gcd(a, n). 2. Nếu d > 1, thì a-1 mod n không tồn tại, Ngược lại Kết_quả(x) 2.8. Định nghĩa Nhóm nhân (phép nhân) của tập ] n là tập = {a ∈ ] *n ] n | gcd(a, n) = 1}, điều đặc biệt là nếu n là một sô nguyên tố thì tập = {a | 1 ≤ a ≤ n−1}. ] *n Lê Thụy 22 Trường Đại học Dân lập Hải Phòng Tập lập thành một nhóm con đối với phép nhân của ] *n ] n vì trong phép chia theo modulo n bao giờ cũng thực hiện được. ] *n 2.9. Định nghĩa Cấp của được định nghĩa là số phần tử trong ] , (| |). Theo định nghĩa hàm phi-Euler ta có |] | = φ(n). ] *n *n ] *n *n 2.10. Định lý (Euler) n ≥ 2, a ∈ thì a] *n φ(n) ≡ 1 (mod n) 2.11. Định lý (Fermat) p nguyên tố, gcd(a, p) = 1 thì ap-1 ≡ 1 (mod p) 2.12. Định nghĩa Cho a ∈ , khi đó cấp của a, ký hiệu ord(a) là số nguyên dương t nhỏ nhất sao cho a ] *n t ≡ 1 (mod n) trong ] . *n Ví dụ: Cho n = 21, = {1 ,2,4,5,8,10,11,13,16,17,19,20}. *21] a ∈ *21] 1 2 4 5 8 10 11 13 16 17 19 20 Cấp của a 1 6 3 6 2 6 6 2 3 6 6 2 2.13. Định nghĩa Cho α ∈ , nếu cấp của α là φ(n), khi đó α được gọi là phần tử sinh hay phần tử nguyên thủy của , Và nếu có một phần tử sinh, thì được gọi là nhóm cyclic. (chú ý nếu n là số nguyên tố thì φ(n) = n–1) ] *n ] *n ] *n ] *n 2.14. Tính chất (phần tử sinh của ) ] *n (i) Nếu α là phần tử sinh của , thì ] = {α ] *n * n i mod n | 0 ≤ i ≤ φ(n) –1} (ii) Giả sử α một là phần tử sinh của , khi đó b = α] *n i mod n cũng là một phần tử sinh của khi và chỉ khi gcd(i, φ(n)) = 1. Và sau đó nếu là nhóm cyclic thì số phần tử sinh sẽ là φ(φ(n)). ] *n ] *n (iii) α ∈ là phần tử sinh của khi và chỉ khi α] *n ] *n φ(n)/p !≡ 1 (mod n) với mỗi số chia nguyên tố của φ(n). Lê Thụy 23 Lý thuyết Mật mã và An toàn thông tin (iv) có phần tử sinh khi và chỉ khi n = 2, 4, p] *n k hay 2pk khi p là số nguyên tố lẻ và k ≥ 1. Còn nếu p là số nguyên tố thì chắc chắn có phần tử sinh. ] *n Ví dụ: ] không phải là nhóm cyclic vì không phần tử nào của có cấp là φ(21) = 12 (xem ví dụ trên), chú ý là 21 không thoả mãn bất cứ một điều kiện nào theo tính chất của phần tử sinh trên. Trong khi đó là nhóm cyclic và có phần tử sinh α = 2. * 21 ] *21 ] *13 Thật vậy: 20 mod 13 = 1 21 mod 13 = 2 22 mod 13 = 4 23 mod 13 = 8 24 mod 13 = 3 25 mod 13 = 6 26 mod 13 = 12 27 mod 13 = 11 28 mod 13 = 9 29 mod 13 = 5 210 mod 13 = 10 211 mod 13 = 7 phần tử 2i là sinh khi và chỉ khi gcd(i, 12) = 1 nghĩa là khi và chỉ khi i = 1, 5, 7 hoặc 11. Vậy các phần sinh của là 2, 6, 7 và 11. ] *13 2.15. Định nghĩa Cho a ∈ , a được gọi là thặng dư bậc hai theo modulo n, nếu tồn tại một x ∈ , sao cho x ] *n ] *n 2 ≡ a (mod n), và nếu không tồn tại x như vậy thì a được gọi là bất thặng dư bậc hai theo modulo n. Tập các thăng dư bậc hai ký hiệu là và tập các bất thặng dư bậc hai ký hiệu là nQ nQ . 2.16. Tính chất Cho p là số nguyên tố lẻ và α là phần tử sinh của , thì a ∈ là thặng dư bậc hai modulo p khi và chỉ khi a = α ] *p ] *p i mod p. Thuật toán Tính luỹ thừa theo modulo n trong ] n INPUT: a ∈ ] n, số nguyên 0 ≤ k ≤ n trong đó k biểu diễn dạng nhị phân. k = ∑ 0 2ik t i i= OUTPUT: ak mod n. 1. Đặt b ← 1, nếu k = 0 thì Kết_quả(b). 2. Đặt A ← a. 3. Nếu k0 = 1, thì đặt b ← a. Lê Thụy 24 Trường Đại học Dân lập Hải Phòng 4. Với mỗi i từ 1 đến t, thực hiện như sau: 4.1 Đặt A ← A2 mod n. 4.2 Nếu ki = 1, thì b ← A.b mod n. 5. Kết_quả(b). Ví dụ: Bảng dưới