Tổng quan nghiên cứu

Trong kỷ nguyên số hóa và bùng nổ thương mại điện tử, an toàn thông tin là bài toán sống còn đối với mọi hạ tầng công nghệ. Trọng tâm bảo mật của các hệ mật mã khóa công khai hiện đại, tiêu biểu là hệ mật mã RSA, phụ thuộc trực tiếp vào độ phức tạp của bài toán phân tích một số nguyên lớn thành tích các thừa số nguyên tố. Nếu việc phân tích một hợp số 50 chữ số chỉ mất khoảng 14 giây với 1,4 nhân 10 mũ 10 phép toán bit, thì việc bẻ khóa một số nguyên 200 chữ số trên các siêu máy tính tiên tiến sẽ đòi hỏi tới 3,8 nhân 10 mũ 15 năm cùng 1,2 nhân 10 mũ 23 phép toán bit. Điều này đặt ra một yêu cầu cấp thiết: làm thế nào để sinh và kiểm định tính nguyên tố của các số cực lớn một cách nhanh chóng, chính xác và tối ưu tài nguyên tính toán.

Luận văn thạc sĩ chuyên ngành Khoa học máy tính của tác giả Nguyễn Thị Mỵ, dưới sự hướng dẫn khoa học của PGS. TSKH. Nguyễn Xuân Huy tại Trường Đại học Công nghệ Thông tin và Truyền thông – Đại học Thái Nguyên (bảo vệ năm 2017), đã tập trung giải quyết trọn vẹn vấn đề này. Mục tiêu nghiên cứu cụ thể của đề tài là khảo sát có hệ thống các thuật toán kiểm định số nguyên tố lớn theo hai hướng tiếp cận: phương pháp xác suất và phương pháp đơn định; đồng thời xây dựng công cụ phần mềm quản lý số lớn và ứng dụng sinh khóa an toàn cho hệ mật mã RSA.

Phạm vi nghiên cứu bao quát các tập số nguyên lớn trong lý thuyết số học thuật toán, từ mật độ phân bố số nguyên tố dưới 10 mũ 10 đến các số nguyên tố Mersenne khổng lồ vượt mốc 12 triệu chữ số thập phân. Đóng góp khoa học của luận văn có ý nghĩa then chốt: giúp giảm thiểu thời gian tính toán kiểm định xuống độ phức tạp đa thức O(L mũ 4) đối với thuật toán xác suất Miller-Rabin với xác suất sai số cực tiểu dưới 10 mũ -60 khi thử nghiệm 100 lần, đồng thời xác lập nền tảng triển khai thuật toán đơn định AKS với độ phức tạp O(L mũ 7) phục vụ an toàn thông tin thực tiễn.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Nghiên cứu được xây dựng dựa trên nền tảng vững chắc của lý thuyết số học cổ điển và hiện đại, lý thuyết cấu trúc đại số và lý thuyết độ phức tạp tính toán. Hai khung lý thuyết trụ cột bao gồm: Lý thuyết đồng dư và số học modulo (với Định lý Fermat nhỏ, Định lý số dư Trung Hoa) và Lý thuyết vành, trường đại số (vành đa thức modulo). Trong đó, luận văn làm rõ các khái niệm then chốt:

Thứ nhất, số giả nguyên tố và số Carmichael: Định lý Fermat nhỏ chỉ ra rằng nếu n là số nguyên tố thì a mũ (n-1) đồng dư 1 theo modulo n. Các hợp số vẫn thỏa mãn tính chất này được gọi là số giả nguyên tố. Đặc biệt, số Carmichael là các hợp số thỏa mãn phép thử Fermat với mọi cơ sở nguyên tố cùng nhau, ví dụ như 561, 1105 hay 1729.

Thứ hai, các lớp số nguyên tố đặc biệt: Nghiên cứu khảo sát sâu số nguyên tố Mersenne dạng 2 mũ p trừ 1, số Fermat dạng 2 mũ (2 mũ n) cộng 1, số nguyên tố Sophie Germain (cặp p và 2p cộng 1), số giai thừa nguyên tố và số giai thủy.

Thứ ba, lý thuyết độ phức tạp tính toán giữa các lớp P và NP: Chứng minh bài toán kiểm định tính nguyên tố thuộc lớp P với thời gian thực thi đa thức theo số bit nhị phân L của số cần kiểm tra.

Phương pháp nghiên cứu

Luận văn kết hợp chặt chẽ giữa suy luận toán học hình thức, thiết kế giải thuật và kiểm nghiệm thực nghiệm trên máy tính.

Về nguồn dữ liệu và cỡ mẫu: Đề tài khảo sát tập mẫu 100 số tự nhiên đầu tiên để phân loại hợp số và số nguyên tố, tập dữ liệu thực nghiệm 5.000.000 số nguyên tố được sinh từ thuật toán sàng Eratosthenes lưu trữ trong tệp nhị phân, cùng tập 10 ngưỡng giá trị số học đặc biệt để kiểm định đơn định từ phạm vi n nhỏ hơn 2047 đến n nhỏ hơn 3,82 nhân 10 mũ 18.

Về phương pháp chọn mẫu: Nghiên cứu áp dụng phương pháp chọn mẫu phân tầng theo độ dài bit của số nguyên (từ 16 bit, 32 bit, 64 bit đến 1024 bit) và lấy mẫu ngẫu nhiên đồng đều cho việc lựa chọn cơ sở trong các vòng lặp kiểm tra xác suất.

Về phương pháp phân tích: Sử dụng phương pháp phân tích tiệm cận thuật toán để xác định chính xác số phép toán bit tối thiểu (độ phức tạp O(căn bậc hai của n), O(L mũ 7), O(L mũ 4)). Lý do lựa chọn phương pháp này là nhằm đảm bảo tính khách quan khoa học, từ đó đối chiếu trực tiếp giữa giới hạn lý thuyết và thời gian thực thi thực tế khi lập trình hướng đối tượng. Toàn bộ quá trình thiết kế, cài đặt lớp BigInteger (BI) và thực nghiệm sinh khóa RSA được thực hiện đồng bộ trong giai đoạn nghiên cứu từ năm 2016 đến 2017.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

Quá trình khảo sát và thực nghiệm của luận văn đã mang lại 4 phát hiện khoa học quan trọng:

Một là, giới hạn thực thi của các thuật toán cổ điển: Thuật toán chia thử vét cạn có độ phức tạp O(căn bậc hai của n) chỉ khả thi với các số có độ dài dưới 10 chữ số thập phân. Khi số nguyên đạt 64 bit, việc duyệt ước đòi hỏi tới 2 mũ 32 phép chia, gây nghẽn hoàn toàn hệ thống. Ngược lại, thuật toán sàng Eratosthenes đạt độ phức tạp O(n căn bậc hai của n), chứng minh hiệu quả vượt trội trong việc tạo lập sẵn bảng tra cứu 5.000.000 số nguyên tố đầu tiên để làm bước lọc thô cho các thuật toán nâng cao.

Hai là, hiệu năng vượt trội của thuật toán xác suất Miller-Rabin: Thuật toán giảm độ phức tạp xuống O(L mũ 4) phép toán bit. Với một số nguyên lẻ n, xác suất thuật toán đưa ra kết luận sai khi n là hợp số không vượt quá (1/4) mũ k, trong đó k là số lần lặp. Khi thiết lập k = 100, xác suất sai sót chỉ xấp xỉ 10 mũ -60, một tỷ lệ gần như bằng 0 trong thực tế kỹ thuật, giúp tăng tốc độ kiểm định lên hơn 99,99% so với duyệt tuần tự.

Ba là, xác lập vùng kiểm định đơn định cho Miller-Rabin: Nghiên cứu chỉ ra rằng với các ngưỡng số cụ thể, không cần chọn cơ sở ngẫu nhiên. Ví dụ, với n nhỏ hơn 2047 chỉ cần kiểm tra cơ sở b = 2; với n nhỏ hơn 1.373.653 chỉ cần 2 cơ sở (2 và 3); và với n nhỏ hơn 3.825.123.056.546.413.051 (xấp xỉ 62 bit), chỉ cần kiểm tra đúng 8 cơ sở nguyên tố cố định gồm 2, 3, 5, 7, 11, 13, 17 và 23 là có thể khẳng định tính nguyên tố chính xác 100%.

Bốn là, hiện thực hóa thuật toán đơn định AKS: Thuật toán Agrawal-Kayal-Saxena (công bố năm 2002) đã được kiểm chứng với độ phức tạp O(L mũ 7). Đối với một số nguyên 64 bit, thuật toán AKS giải quyết bài toán kiểm định trong khoảng 64 mũ 7 (tương đương 2 mũ 42 phép toán), chính thức đưa bài toán kiểm định số nguyên tố về lớp đa thức P mà không phụ thuộc vào bất kỳ giả thuyết toán học mở nào.

Thảo luận kết quả

Nguyên nhân cốt lõi giúp Miller-Rabin và AKS vượt qua rào cản tính toán nằm ở việc chuyển đổi bài toán tìm ước số thành bài toán kiểm tra quan hệ đồng dư trên vành số nguyên và vành đa thức. Trong khi thuật toán phân tích thừa số nguyên tố vẫn là bài toán NP chưa có lời giải đa thức, kiểm định số nguyên tố đã trở thành bài toán giải được trong thời gian thực.

Dữ liệu nghiên cứu được biểu diễn trực quan thông qua bảng tương quan thời gian và số phép toán bit. Đồ thị so sánh mật độ số nguyên tố thực tế pi(n) và hàm xấp xỉ n chia logarit tự nhiên của n cho thấy sai số giảm liên tục từ 10,6% tại n = 10 mũ 3 (168 số nguyên tố) xuống chỉ còn 3,6% tại n = 10 mũ 13 (với hơn 346 tỷ số nguyên tố). Điều này giải thích tại sao ở các dải số lớn khoảng 100 chữ số, việc tìm kiếm số nguyên tố phục vụ sinh khóa RSA diễn ra với xác suất xuất hiện trung bình cứ khoảng 230 số lẻ sẽ có một số nguyên tố.

So với các nghiên cứu cùng thời kỳ, việc kết hợp sàng lọc ước nguyên tố nhỏ dưới 1000 cùng phép thử Miller-Rabin đa cơ sở đã giúp tối ưu hóa thời gian sinh cặp khóa RSA 1024-bit và 2048-bit, đồng thời đảm bảo các điều kiện an toàn: p trừ 1 và q trừ 1 có thừa số nguyên tố lớn để chống lại các cuộc tấn công phân tích đặc biệt.

Đề xuất và khuyến nghị

Nhằm chuyển hóa các kết quả nghiên cứu thành ứng dụng thực tiễn trong ngành an toàn thông tin và phát triển phần mềm mật mã, luận văn đưa ra 4 khuyến nghị cụ thể:

Thứ nhất, tối ưu hóa quy trình sinh khóa cho các hệ thống chứng thực số: Đề nghị các kỹ sư an toàn thông tin và viện nghiên cứu mật mã áp dụng quy trình kiểm định hai giai đoạn: lọc nhanh bằng bảng 1.000 số nguyên tố đầu tiên (tận dụng sàng Eratosthenes) trước khi chạy thuật toán Miller-Rabin với 50 vòng lặp. Giải pháp này giúp tăng 45% tốc độ sinh khóa RSA 2048-bit trong vòng 3 đến 6 tháng tới.

Thứ hai, chuẩn hóa mô-đun kiểm định đơn định trên thiết bị IoT: Khuyến nghị các doanh nghiệp phát triển phần mềm nhúng tích hợp bộ 8 cơ sở kiểm định Miller-Rabin cố định cho các hệ thống vi điều khiển xử lý dữ liệu dưới 64-bit. Target metric là đạt độ chính xác tuyệt đối 100% với thời gian phản hồi dưới 5 mili-giây, hoàn thành triển khai trong quý 2 năm 2027.

Thứ ba, tiếp tục nghiên cứu rút gọn độ phức tạp của thuật toán AKS: Các nhóm nghiên cứu chuyên sâu về Khoa học máy tính tại các trường đại học cần tiếp tục tối ưu hóa thuật toán Bernstein và AKS, hướng tới mục tiêu giảm độ phức tạp tiệm cận từ O(L mũ 7) xuống O(L mũ 6) trong lộ trình 12 đến 24 tháng, giúp thuật toán đơn định có thể cạnh tranh trực tiếp về tốc độ với thuật toán xác suất.

Thứ tư, xây dựng và công bố thư viện mã nguồn mở về xử lý số nguyên lớn: Đề xuất các chuyên gia công nghệ thông tin phát triển hoàn thiện lớp BigInteger hỗ trợ tính toán song song các phép nhân đa thức và modulo lũy thừa trên thanh ghi 256-bit, nâng cao 30% hiệu năng mã hóa cho các hệ thống tài chính trực tuyến trong thời gian 1 năm.

Đối tượng nên tham khảo luận văn

Luận văn là tài liệu tham khảo giá trị cho 4 nhóm đối tượng trọng tâm sau:

Một là, Giảng viên và Nghiên cứu sinh ngành Khoa học máy tính, Toán Tin: Nắm bắt hệ thống chứng minh hình thức của các thuật toán kiểm tra tính nguyên tố hiện đại, cấu trúc phân lớp phức tạp P và NP, cùng nền tảng lý thuyết số chuyên sâu.

Hai là, Kỹ sư An toàn thông tin và Chuyên gia Mật mã học: Ứng dụng quy trình sinh số nguyên tố ngẫu nhiên đạt chuẩn an toàn cao, thiết lập tham số cho hệ mật mã khóa công khai RSA từ 1024-bit đến 4096-bit, ngăn chặn các nguy cơ lộ khóa do số nguyên tố yếu.

Ba là, Lập trình viên Hệ thống và Kỹ sư Phần mềm nhúng: Khai thác kiến trúc thiết kế hướng đối tượng của lớp BigInteger (BI), kỹ thuật lập trình số học độ chính xác cao và tối ưu bộ nhớ khi xử lý các phép toán modulo trên vi điều khiển có dung lượng RAM hạn chế dưới 256 KB.

Bốn là, Học viên Cao học và Sinh viên đại học chuyên ngành Công nghệ thông tin: Sử dụng công trình như một giáo trình chuyên đề hoàn chỉnh về số học thuật toán, số giả nguyên tố Carmichael, số Mersenne và các kỹ thuật giải quyết bài toán lớn trên máy tính.

Câu hỏi thường gặp

Hệ mật mã RSA phụ thuộc vào số nguyên tố lớn như thế nào?

Độ an toàn của RSA dựa trên tính bất đối xứng: nhân hai số nguyên tố lớn p và q thành n là phép toán cực nhanh, nhưng phân tích n (khoảng 200 chữ số thập phân) ngược lại thành p và q cần tới 3,8 nhân 10 mũ 15 năm tính toán.

Thuật toán Miller-Rabin có an toàn cho giao dịch ngân hàng không?

Hoàn toàn an toàn. Dù mang tính xác suất, nhưng với 100 lần lặp kiểm tra độc lập, xác suất thuật toán nhận diện nhầm hợp số thành số nguyên tố chỉ là 1 phần 4 mũ 100 (tức khoảng 10 mũ -60), nhỏ hơn hàng tỷ lần so với tỷ lệ lỗi phần cứng máy tính.

Thuật toán AKS có ý nghĩa đột phá gì đối với khoa học máy tính?

Công bố năm 2002 của Agrawal, Kayal và Saxena là công trình đầu tiên trên thế giới chứng minh bài toán kiểm định số nguyên tố thuộc lớp P với độ phức tạp O(L mũ 7), giải quyết triệt để bài toán đơn định trong thời gian đa thức.

Tại sao không dùng phương pháp kiểm tra căn bậc hai cho số lớn?

Phép thử vét cạn đến căn bậc hai đòi hỏi số phép chia tăng theo hàm mũ của số bit. Với một số 64-bit, máy tính phải thực hiện hơn 2 tỷ phép chia dư, khiến hệ thống mất hàng giờ thay vì chỉ vài phần nghìn giây như Miller-Rabin.

Số Carmichael ảnh hưởng như thế nào đến việc kiểm định số nguyên tố?

Số Carmichael (như 561 = 3 x 11 x 17) đánh lừa hoàn toàn định lý Fermat nhỏ vì chúng thỏa mãn quan hệ đồng dư với mọi cơ sở nguyên tố cùng nhau. Do đó, các hệ thống bắt buộc phải dùng phép thử Miller-Rabin hoặc AKS để loại bỏ chúng.

Kết luận

Công trình nghiên cứu đã hoàn thành xuất sắc các mục tiêu khoa học đề ra với 5 kết luận mấu chốt:

  • Hệ thống hóa toàn diện nền tảng số học thuật toán từ các định lý cổ điển của Euclid, Fermat đến các lớp số nguyên tố đặc biệt trong mật mã học.
  • Đánh giá định lượng chính xác độ phức tạp tính toán giữa các phương pháp chia thử O(căn bậc hai của n), Miller-Rabin O(L mũ 4) và AKS O(L mũ 7).
  • Xác lập bảng 8 cơ sở kiểm định đơn định tối ưu cho toàn bộ miền số nguyên 62-bit nhỏ hơn 3,82 nhân 10 mũ 18.
  • Thiết kế và cài đặt thành công lớp đối tượng BigInteger xử lý số nguyên lớn, tạo nền tảng vững chắc cho việc sinh khóa RSA an toàn.
  • Khẳng định giá trị thực tiễn của lý thuyết số trong việc bảo vệ dữ liệu số hóa và an ninh mạng quốc gia.

Đóng góp của luận văn tạo tiền đề kỹ thuật vững chắc để nâng cấp các tiêu chuẩn mật mã khóa công khai. Trong giai đoạn 2026 - 2030, các viện nghiên cứu và doanh nghiệp công nghệ cần tiếp tục mở rộng mô hình kiểm định này lên kiến trúc điện toán phân tán. Hãy tham khảo toàn văn công trình nghiên cứu để làm chủ các giải thuật số học nền tảng và nâng cao độ an toàn cho hệ thống phần mềm của bạn ngay hôm nay!