Đặt vấn đề: Có một khối lượng khổng lồ các tài liệu về các thuật toán phân tích thừa số. Tuy vậy, trong phần này chỉ đưa ra một cái nhìn khái quát bao gồm việc thảo luận sơ lược về các thuật toán phân tích thừa số tốt nhất hiện thời và cách sử dụng chúng trong thực tế. Ba thuật toán hiệu quả nhất trên các số thật lớn là: sàng bậc hai, thuật toán đường cong Elliptic và sàng trường số. Các thuật toán nổi tiếng khác bao gồm: phương pháp p và thuật toán (p – 1) của Pollard, thuật toán (p + 1) của Williams, thuật toán liên phân số và dĩ nhiên là cả phép chia thử.
Phương pháp Pollard Thuật toán (p – 1) của Pollard (đưa ra vào năm 1975) là một ví dụ về một thuật toán đơn giản khi được áp dụng đối với các số nguyên lớn. Inputs: n, số nguyên cần phân tích; và f(x), hàm tạo số giả ngẫu nhiên modulo n. Output: một nhân tử không tầm thường (khác 1 và n) của n, hoặc không thực hiện được. 11 x ← 2, y ← 2; d ← 1 While d = 1: x ← f(x) y ← f(f(y)) d ← GCD(|x − y|, n) If d = n, return không thực hiện được Else return d.
2: Thuật toán phân tích thừa số p - 1 Chú ý rằng thuật toán có thể không tìm thấy nhân tử và trả về kết quả không thực hiện được với một hợp số n. Trong trường hợp này sử dụng hàm f(x) khác và thử lại. Thuật toán cũng không làm việc khi n là số nguyên tố, trong trường hợp này d sẽ luôn là 1. Đối với hàm f, chúng ta chọn đa thức với hệ số nguyên.
một trong những dạng chung nhất đó là: f(x) = x2 + c mod n, c ≠ 0, -2. Ví dụ: Cho n = 8051 và f(x) = x2 + 1 mod 8051 i xi yi gcd(|xi – yi |, 8051) 1 5 26 1 2 26 7474 1 3 677 871 97 97 là một nhân tử không tầm thường của 8051. Nhân tử còn lại là thương của phép chia n cho 97 bằng 83. Thuật toán đường cong Elliptic Thuật toán đường cong Elliptic mạnh hơn (được Lenstra xây dựng vào những năm 80) trên thực tế là sự tổng quát hóa của phương pháp p - 1.
Ta sẽ không thảo luận về mặt lý thuyết ở đây mà chỉ nhấn mạnh rằng, thành công của phương pháp đường cong Elliptic tuỳ thuộc vào một tình huống tương tự: một số nguyên “gần 12 với” p chỉ có các thừa số nguyên tố bộ. Trong khi phương pháp p - 1 phụ thuộc vào quan hệ trong Zp thì phương pháp đường cong Elliptic phụ thuộc vào các Nhóm xác định trên các đường cong Elliptic theo modulo n. Thuật toán kiểu Las Vegas Thuật toán được xây dựng trên cơ sở một số nguyên tố nhất định liên quan tới các căn bậc hai của 1 theo modulo n, trong đó n = p * q là tích của hai số nguyên tố lẻ phân biệt. Chọn w là ngẫu nhiên và 1 w n – 1 2.
Nếu 1 < x < n thì thoát (thành công: x = p hoặc x = q) 4. Viết ab - 1 = 2s r, r lẻ 6. Tính v = wr mod n 7. Trong khi v 1 (mod n) thì thực hiện 9.
3: Thuật toán phân tích thừa số (cho trước số mũ giải mã 13 1. Thuật toán phân tích cổ điển Hiện nay người ta chưa có cách nào tính trực tiếp p, q hữu hiệu từ n trừ khi biết (n). Vì khi biết (n), ta có: p*q=n (n) = (p -1) * (q - 1) p + q = n - (n) +1 Dựa vào định lý Vi-ét p và q là nghiệm của phương trình: x 2 - (n - (n) +1) * x + n = 0 Giải phương trình này ta dễ dàng tìm được p và q. Ngoài ra theo cách cổ điển, sử dụng thuật toán : // Input: n // Output: p thoả mãn p | n // // 0 trong trường hợp ngược lại For (int i = 3; i <= sqrt (n); i+ = 2) if (n % i) return i; return 0; Hình 1.
4: Thuật toán phân tích cổ điển Trong thuật toán trên vòng lặp là (n1/ 2/ 2). Nếu n có 512 bit, giá trị lớn nhất của n là 2512. Nếu 1 máy tính thực hiện 106 chỉ lệnh trong 1 giây thì thời gian thực hiện là: T = n 1/ 2 / 2 2 1/2 * 512 / 2 = 2256 / 2 = 2255(giây) 2 238 (ngày) 2 230 năm. (1 ngày = 60 * 60 * 24 = 86400 giây 2 17 giây.
14 1 năm = 30 * 12 * 86400 giây = 31104000 giây 2 25 giây.) Nếu kẻ giả mạo muốn tìm p, q theo cách này thì đây là điều không tưởng. ĐỘ PHỨC TẠP TÍNH TOÁN 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 đờ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, đưa đến nhiều kết quả rất quan trọng và lý thú. Nhưng từ cái “tính được” một cách trừu tượng, hiểu theo nghĩa tiềm năng, đến việc tính được trong thực tế của khoa học tính toán bằng máy tính điện tử, là cả một khoảng cách rất lớn.
Vấn đề là do ở chỗ những đòi hỏi về không gian vật chất và về thời gian để thực hiện các tiến trình tính toán nhiều khi vượt quá xa những khả năng thực tế. Từ đó, vào khoảng giữa những năm 60 (của thế kỷ trước), một lý thuyết về độ phức tạp tính toán bắt đầu được hình thành và phát triển nhanh chóng, cung cấp cho chúng ta nhiều hiểu biết sâu sắc về bản chất phức tạp của các thuật toán và các bài 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ế. Sau đây giới thiệu sơ lược một số khái niệm cơ bản và vài kết quả sẽ được dùng đến của lý thuyết đó. Trước hết, hiểu độ phức tạp tính toán (về không gian hay về 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 thuật toán A trên bảng ký tự (tức có đầu vào là các từ trong ). Độ phức tạp tính toán của thuật toán A được hiểu là một hàm số fA(n) sao cho với mỗi số n, fA(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. 15 Về sau khi nói đến các bài toán, ta hiểu đó là các bài toán quyết định, mỗi bài toán P như vậy được xác định bởi: - Một tập các dữ liệu vào I (trong một bảng ký tự nào đó). - Một câu hỏi Q trên các dữ liệu vào, sao cho với mỗi dữ liệu vào x I, câu hỏi Q có một trả lời đúng hoặc sai. Bài toán quyết định 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ác bài toán, và cho kết quả đúng hoặc sai tùy theo câu hỏi Q trên dữ liệu đó có trả lời đúng hoặc sai.
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. Sau đây là vài ví dụ về các bài toán quyết định: Bài toán SATISFIABILYTY (viết tắt là SAT): - Mỗi dữ liệu vào là một công thức F của logic mệnh đề, được viết dưới dạng hội chuẩn tắc, tức dạng hội của một số các “clause”. - Câu hỏi là: công thức F có thỏa được hay không? Bài toán CLIQUE: - Mỗi dữ liệu vào là một graph G và một số nguyên k. - Mỗi câu hỏi là: Graph G có một clique với ≥ k đỉnh hay không? (một clique của G là một graph con đầy đủ của G).
Bài toán KNAPSACK: - Mỗi dữ liệu là một bộ n + 1 số nguyên dương I = (s1,. - Câu hỏi là: có hay không một vectơ Boole (x1, .,xn) sao cho i=1n xi-si = T? (vectơ Boole là vectơ có các thành phần là 0 hoặc 1) Bài toán thặng dư bậc hai: - Mỗi dữ liệu gồm hai số nguyên dương (a, n). - Câu hỏi là: a có là thặng dư bậc hai theo mod n hay không? 16 Bài toán hợp số: - Mỗi dữ liệu là một số nguyên dương N. - Câu hỏi: N là hợp số không? Tức có hay không hai số m, n >1 sao cho N = m.n? Tương tự, nếu đặt câu hỏi là “N là số nguyên tố hay không?” thì ta được bài toán số nguyên tố.
Đối với tất cả các bài toán kể trên, trừ bài toán hợp số và số nguyên tố, cho đến nay người ta đều chưa tìm được thuật toán giải chúng trong thời gian đa thức. Lớp phức tạp Xét một vài lớp các bài toán được xác định theo độ phức tạp tính toán của chúng. Trước hết, định nghĩa P là lớp tất cả các bài toán có thể giải được bởi thuật toán đơn định trong thời gian đa thức. Giả sử cho hai bài toán A và B với các tập dữ liệu trong hai bảng ký tự tương ứng là 1 và 2.
Một thuật toán f: *1 → *2 được gọi là một phép quy dẫn bài toán A về bài toán B, nếu nó biến mỗi dữ liệu x của bài toán A thành một dữ liệu f(x) của bài toán B, và sao cho câu hỏi của A trên x có trả lời đúng khi và chỉ khi câu hỏi của B trên f(x) cũng có trả lời đúng. Ta nói bài toán A quy dẫn được về bài toán B trong thời gian đa thức, và ký hiệu A B, nếu có thuật toán f với độ phức tạp thời gian đa thức qui dẫn bài toán A về bài toán B. Dễ thấy rằng, nếu A B và B P, thì cũng có A P.