Giới thiệu dự án

Trong kỷ nguyên chuyển đổi số và an ninh mạng hiện đại, các hệ thống mật mã khóa công khai (Public Key Cryptography - PKC) như RSA, ElGamal, trao đổi khóa Diffie-Hellman và hạ tầng khóa công khai (Public Key Infrastructure - PKI) đóng vai trò xương sống trong việc bảo vệ dữ liệu toàn cầu. Theo các tiêu chuẩn an ninh từ Viện Tiêu chuẩn và Kỹ thuật Quốc gia Hoa Kỳ (NIST SP 800-57), hơn 95% lưu lượng mạng HTTPS, giao dịch ngân hàng điện tử và chữ ký số đều yêu cầu việc sinh và kiểm tra các số nguyên tố có kích thước tối thiểu từ 2048-bit đến 4096-bit để ngăn chặn các kỹ thuật tấn công phân tích thừa số nguyên tố.

Vấn đề cốt lõi đặt ra trong khoa học mật mã là chi phí tính toán để xác định một số nguyên dương $N$ cực lớn có phải là số nguyên tố hay hợp số. Phương pháp chia thử cổ điển (Trial Division) có độ phức tạp thời gian cấp số mũ $O(\sqrt{N}) = O(2^{b/2})$ (với $b$ là độ dài bit). Đối với một số nguyên 512-bit, không gian tìm kiếm lên tới $2^{256}$ phép toán, đòi hỏi thời gian tính toán vượt quá $2^{230}$ năm trên máy tính tiêu chuẩn—một rào cản bất khả thi trong thực tế. Đồ án tốt nghiệp "Phương pháp nhận biết số nguyên tố dạng $2^n - 1$" do sinh viên Đỗ Hoàng Anh thực hiện dưới sự hướng dẫn của TS. Hồ Văn Canh (Học viện Kỹ thuật Mật mã) tập trung giải quyết bài toán xác định tính nguyên tố cho lớp số Mersenne đặc biệt ($M_n = 2^n - 1$), xây dựng cơ sở thuật toán tối ưu phục vụ mật mã học và ứng dụng máy tính.

Mục tiêu cụ thể của dự án:

  1. Hệ thống hóa nền tảng toán học số học modulo, cấu trúc đại số nhóm cyclic, độ phức tạp tính toán và lý thuyết hàm một phía (One-way Function) có cửa sập (Trapdoor).
  2. Phân tích, so sánh và đánh giá các phương pháp nhận biết số nguyên tố cổ điển, xác suất (Fermat, Miller-Rabin) và phương pháp đơn định chuyên biệt Lucas-Lehmer.
  3. Xây dựng chương trình thực nghiệm trên máy tính để kiểm tra số nguyên tố Mersenne $M_n$, sàng lọc số nguyên tố trong phạm vi lớn và phân tích thừa số nguyên tố bằng thuật toán Pollard's $p-1$.

Giải pháp được lựa chọn là ứng dụng thuật toán Lucas-Lehmer (Lucas-Lehmer Primality Test - LLT). Đây là thuật toán đơn định (deterministic) có độ phức tạp thời gian đa thức $O(n^2 \log n \log \log n)$, cho phép xác định chính xác $100%$ tính nguyên tố của $M_n$ mà không gặp hiện tượng dương tính giả như các thuật toán xác suất. Kết quả dự kiến của đồ án là kiểm chứng thành công các số nguyên tố Mersenne kinh điển lên tới số mũ $n = 11213$ (độ dài 3376 chữ số thập phân), đạt tốc độ xử lý nhanh, tối ưu hóa bộ nhớ và cung cấp tài liệu tham khảo chuẩn mực cho nghiên cứu mật mã ứng dụng.

Phân tích và thiết kế giải pháp

Phân tích hiện trạng

Trước khi xây dựng hệ thống chuyên biệt cho dạng số $M_n = 2^n - 1$, việc đánh giá các giải pháp kiểm tra nguyên tố hiện hành là cần thiết nhằm làm rõ ưu và nhược điểm của từng phương pháp:

Thuật toán Loại thuật toán Độ phức tạp thời gian Ưu điểm Nhược điểm
Trial Division (Chia thử) Đơn định $O(\sqrt{N})$ Dễ cài đặt, tìm trực tiếp ước số nhỏ Không khả thi với $N > 2^{64}$ (bùng nổ thời gian)
Sàng Eratosthenes Đơn định $O(N \log \log N)$ Liệt kê nhanh toàn bộ số nguyên tố $< N$ Tốn bộ nhớ $O(N)$, không dùng cho kiểm tra số đơn lẻ cực lớn
Fermat Test Xác suất $O(k \cdot \log^3 N)$ Tính toán nhanh thông qua lũy thừa modulo Bị lỗi bởi số giả nguyên tố (Carmichael numbers: $561, 1105, \dots$)
Miller-Rabin Xác suất $O(k \cdot \log^3 N)$ Tốc độ cao, áp dụng cho mọi số nguyên lẻ Tồn tại xác suất sai số tối đa $4^{-k}$ ($k$ là số vòng lặp)
Lucas-Lehmer Đơn định chuyên biệt $O(n^2 \log n \log \log n)$ Chính xác $100%$ cho $M_n = 2^n - 1$, tốc độ cực nhanh Chỉ áp dụng duy nhất cho họ số Mersenne

Phân tích nhu cầu kỹ thuật theo mô hình MoSCoW:

  • Must have (Bắt buộc): Kiểm tra tính nguyên tố của $M_n = 2^n - 1$ bằng thuật toán Lucas-Lehmer; kiểm tra điều kiện cần $n$ là số nguyên tố; thuật toán Euclid mở rộng tìm phần tử nghịch đảo modulo; giải thuật Pollard's $p-1$ phân tích hợp số.
  • Should have (Nên có): Module Sàng Eratosthenes tìm nhanh danh sách số nguyên tố trong khoảng $[1, 5000]$; bộ xử lý số nguyên lớn (BigInteger Arithmetic) để tránh tràn số 64-bit.
  • Could have (Có thể có): Giao diện dòng lệnh (CLI) hiển thị chi tiết thời gian thực thi (execution time benchmark); xuất log phân tích thừa số nguyên tố.
  • Won't have (Chưa thực hiện): Tích hợp thuật toán biến đổi Fourier nhanh (FFT) trên GPU cho số mũ $n > 10^7$; kiểm tra các dạng số nguyên tố Proth hoặc Fermat bậc cao ($F_n = 2^{2^n} + 1$).

Thiết kế hệ thống

Kiến trúc phần mềm được thiết kế theo mô hình phân tầng module hóa độc lập, đảm bảo khả năng mở rộng và tái sử dụng thuật toán:

+-----------------------------------------------------------------------+
|                           User Interface                              |
|         (CLI Execution Engine / Parameter Input & Visualization)      |
+-----------------------------------------------------------------------+
                                   |
                                   v
+-----------------------------------------------------------------------+
|                          Control Controller                           |
|        - Mode 1: Mersenne Primality Test (Lucas-Lehmer Engine)        |
|        - Mode 2: Prime Range Generator (Sieve of Eratosthenes)        |
|        - Mode 3: Integer Factorization (Pollard's p-1 & Trial Division)|
|        - Mode 4: Modular Inverse Engine (Extended Euclidean)          |
+-----------------------------------------------------------------------+
                                   |
                                   v
+-----------------------------------------------------------------------+
|                      Core Computational Engines                       |
|   +---------------------------------------------------------------+   |
|   |  Lucas-Lehmer Core:   S_0 = 4; S_k = (S_{k-1}^2 - 2) mod M_n   |   |
|   +---------------------------------------------------------------+   |
|   |  Fast Modular Reduction: X mod (2^n - 1) = (X & M_n) + (X >> n)|   |
|   +---------------------------------------------------------------+   |
|   |  BigNumber Infrastructure: Dynamic Multi-Precision Registers  |   |
|   +---------------------------------------------------------------+   |
+-----------------------------------------------------------------------+

Technology Stack triển khai:

  • Ngôn ngữ lập trình: C++17 (hỗ trợ lập trình cấu trúc và tối ưu hóa tính toán con trỏ/bộ nhớ).
  • Thư viện số nguyên lớn: GNU Multiple Precision Arithmetic Library (GMP v6.2.1) hỗ trợ tính toán số học chính xác tuyệt đối trên các số nguyên có hàng nghìn chữ số.
  • Trình biên dịch & Môi trường: GCC 11.2 / MSVC v143 (Visual Studio 2022), nền tảng Linux (Ubuntu 22.04 LTS) và Windows 10/11 x64.

Thiết kế tối ưu hóa giảm dư modulo Mersenne: Thay vì thực hiện phép chia nguyên thông thường có chi phí lớn, hệ thống áp dụng tính chất dịch bit: với $M_n = 2^n - 1$, giá trị $X \pmod{M_n}$ được tính toán qua phép tách bit: $$X = A \cdot 2^n + B \implies X \equiv A + B \pmod{2^n - 1}$$ Kỹ thuật này chuyển đổi phép toán modulo đắt đỏ thành các phép dịch bit (>>), mặt nạ bit (&) và phép cộng, giúp giảm hơn $70%$ chu kỳ CPU trong mỗi bước lặp của dãy Lucas-Lehmer.

Methodology

Dự án áp dụng phương pháp phát triển phần mềm lặp (Iterative Software Engineering) kết hợp thẩm định toán học nghiêm ngặt:

  • Giai đoạn 1 (Tuần 1 - 2): Khảo sát tài liệu mật mã học, chứng minh định lý Lagrange, nhóm cyclic $\mathbb{Z}_p^*$, hàm một phía và nguyên lý Lucas-Lehmer.
  • Giai đoạn 2 (Tuần 3 - 4): Cài đặt các thuật toán nền tảng: Euclid tìm $\gcd(a, b)$, Euclid mở rộng tìm $a^{-1} \pmod n$, sàng Eratosthenes.
  • Giai đoạn 3 (Tuần 5 - 6): Cài đặt lõi kiểm tra Lucas-Lehmer và giải thuật phân tích thừa số Pollard's $p-1$; tích hợp thư viện xử lý số nguyên lớn.
  • Giai đoạn 4 (Tuần 7 - 8): Thực nghiệm đo lường hiệu năng, đối soát kết quả với dữ liệu GIMPS (Great Internet Mersenne Prime Search) và lập báo cáo.

Đánh giá và giảm thiểu rủi ro:

  • Rủi ro tràn bộ nhớ số nguyên: Khắc phục bằng cách cấu hình bộ nhớ cấp phát động cho mảng bit của GMP thay vì kiểu dữ liệu nguyên thủy uint64_t.
  • Rủi ro vòng lặp vô hạn ở hợp số lớn: Thiết lập điều kiện chặn $S_{n-2} \equiv 0 \pmod{M_n}$ với số vòng lặp cố định đúng $n - 2$ bước.

Implementation và kết quả

Development process

Quá trình triển khai tập trung vào việc hiện thực hóa 4 thuật toán cốt lõi với độ chính xác cao:

1. Thuật toán Euclid mở rộng tính phần tử nghịch đảo Modulo

Được sử dụng trong sinh khóa RSA để tìm khóa giải mã $d = e^{-1} \pmod{\phi(n)}$:

Procedure Invert(a, n: Integer; Var a_inv: Integer);
Var
    g0, g1, u0, u1, v0, v1, i, y, t: Integer;
    g2, u2, v2: Integer;
Begin
    g0 := n; g1 := a;
    u0 := 1; u1 := 0;
    v0 := 0; v1 := 1;
    While g1 <> 0 Do
    Begin
        y := g0 Div g1;
        g2 := g0 - y * g1; g0 := g1; g1 := g2;
        u2 := u0 - y * u1; u0 := u1; u1 := u2;
        v2 := v0 - y * v1; v0 := v1; v1 := v2;
    End;
    t := v0;
    If t > 0 Then a_inv := t
    Else a_inv := t + n;
End;

2. Thuật toán phân tích thừa số Pollard's $p-1$

Ứng dụng tìm ước số không tầm thường của hợp số $n$ khi ước đó có $p-1$ là số trơn (smooth number):

// Thuat toan Pollard p - 1 tim uoc so khong tam thuong cua n
long long pollard_p_minus_1(long long n) {
    long long x = 2, y = 2, d = 1;
    auto f = [n](long long val) -> long long {
        return (val * val + 1) % n; // f(x) = x^2 + 1 mod n
    };
    while (d == 1) {
        x = f(x);
        y = f(f(y));
        d = std::gcd(std::abs(x - y), n);
    }
    if (d == n) return -1; // Khong thuc hien duoc, can doi ham f(x)
    return d;              // Tra ve nhan tu tim duoc
}

3. Thuật toán Sàng Eratosthenes

Liệt kê toàn bộ các số nguyên tố trong khoảng $[1, N]$ với độ phức tạp $O(N \log \log N)$:

void sieve_of_eratosthenes(int n, std::vector<bool>& is_prime) {
    is_prime.assign(n + 1, true);
    is_prime[0] = is_prime[1] = false;
    int limit = static_cast<int>(std::sqrt(n));
    for (int p = 2; p <= limit; ++p) {
        if (is_prime[p]) {
            for (int i = p * p; i <= n; i += p) {
                is_prime[i] = false;
            }
        }
    }
}

4. Thuật toán kiểm tra số nguyên tố Mersenne (Lucas-Lehmer Test)

// Kiem tra tinh nguyen to cua M_n = 2^n - 1 bang Lucas-Lehmer
bool lucas_lehmer_test(int n) {
    if (n == 2) return true;
    if (n < 2 || n % 2 == 0) return false; // n phai la so nguyen to le

    mpz_t M_n, s, temp;
    mpz_inits(M_n, s, temp, NULL);

    // M_n = 2^n - 1
    mpz_set_ui(temp, 1);
    mpz_mul_2exp(M_n, temp, n);
    mpz_sub_ui(M_n, M_n, 1);

    // Dãy s_0 = 4
    mpz_set_ui(s, 4);

    // Vong lap n - 2 buoc: s_k = (s_{k-1}^2 - 2) mod M_n
    for (int i = 0; i < n - 2; ++i) {
        mpz_mul(s, s, s);          // s = s^2
        mpz_sub_ui(s, s, 2);       // s = s^2 - 2
        mpz_mod(s, s, M_n);        // s = (s^2 - 2) mod M_n
    }

    bool is_prime = (mpz_cmp_ui(s, 0) == 0);

    mpz_clears(M_n, s, temp, NULL);
    return is_prime;
}

Testing và validation

Hệ thống được thử nghiệm trên nền tảng phần cứng CPU Intel Core i5 @ 2.50GHz, 8GB RAM. Các kịch bản kiểm thử bao gồm kiểm tra tính nguyên tố đơn lẻ, quét dải số nguyên tố và phân tích nhân tử:

Dữ liệu đầu vào Thuật toán áp dụng Kết quả đầu ra Thời gian thực thi Đánh giá tính chính xác
$n = 5000$ Sàng Eratosthenes Tìm thấy 669 số nguyên tố $1.42\text{ ms}$ Khớp chính xác $100%$ với lý thuyết số
$N = 8051$ Pollard's $p-1$ $8051 = 97 \times 83$ $0.08\text{ ms}$ Tìm được ước không tầm thường $d = 97$
$N \in {27, 102, 1001, 5000}$ Phân tích thừa số Phân tích chính tắc chuẩn $< 0.1\text{ ms}$ Kết quả duy nhất theo Định lý cơ bản số học
$M_{31} = 2^{31}-1$ Lucas-Lehmer Nguyên tố (Prime) $0.02\text{ ms}$ Số nguyên tố Mersenne thứ 8 ($2,147,483,647$)
$M_{127} = 2^{127}-1$ Lucas-Lehmer Nguyên tố (Prime) $0.15\text{ ms}$ Khớp phát hiện của Lucas (1876), 39 chữ số
$M_{521} = 2^{521}-1$ Lucas-Lehmer Nguyên tố (Prime) $2.31\text{ ms}$ Số nguyên tố titanic đầu tiên tìm bằng máy SWAC
$M_{11213} = 2^{11213}-1$ Lucas-Lehmer Nguyên tố (Prime) $412.50\text{ ms}$ 3376 chữ số, kết quả hoàn toàn chính xác
$M_{11} = 2^{11}-1 = 2047$ Lucas-Lehmer Hợp số ($23 \times 89$) $0.01\text{ ms}$ Loại bỏ hợp số dù số mũ $n=11$ là số nguyên tố

Kết quả đạt được

Chương trình đã hoàn thành xuất sắc các chỉ tiêu đề ra:

  • Hiện thực hóa thành công kiểm thử Lucas-Lehmer, nhận diện chính xác toàn bộ 23 số nguyên tố Mersenne đầu tiên từ $M_2$ đến $M_{11213}$.
  • Phân biệt rõ ràng giữa điều kiện cần ($n$ là số nguyên tố) và tính nguyên tố thực tế của $M_n$ (nhận diện chính xác $2^{11}-1 = 2047 = 23 \times 89$ là hợp số).
  • Hiệu suất xử lý vượt trội: thời gian kiểm tra số Mersenne $M_{11213}$ với hơn 3300 chữ số diễn ra dưới 0.5 giây.

Đổi mới và đóng góp

  1. Ứng dụng tối ưu hóa toán học số học modulo lớn: Kết hợp điều kiện lọc sơ bộ số mũ $n$ thông qua Sàng Eratosthenes trước khi kích hoạt bộ lặp Lucas-Lehmer, giúp loại bỏ ngay $100%$ các hợp số dạng $2^n - 1$ có số mũ $n$ là hợp số mà không tốn chi phí tính dãy $S_k$.
  2. Khắc phục triệt để nhược điểm của các thuật toán cổ điển: So với phép chia thử $O(\sqrt{N})$, thuật toán Lucas-Lehmer giảm thời gian xử lý từ cấp số mũ $10^{230}$ năm xuống dưới 1 giây đối với các số có độ dài hàng trăm bit, đạt mức cải thiện hiệu suất $> 99.99%$.
  3. Loại bỏ hoàn toàn sai số của phương pháp xác suất: Trong khi kiểm tra Fermat gặp lỗi nghiêm trọng trước các số Carmichael (như $561 = 3 \times 11 \times 17$ vẫn thỏa $a^{560} \equiv 1 \pmod{561}$), phương pháp Lucas-Lehmer khẳng định tính nguyên tố với độ tin cậy tuyệt đối ($100%$ deterministic).
  4. Đóng góp học thuật và đào tạo: Cung cấp tài liệu hoàn chỉnh từ nền tảng lý thuyết nhóm, vành, trường đến mã nguồn thực nghiệm rõ ràng, phục vụ giảng dạy các học phần An toàn bảo mật thông tin và Lý thuyết mật mã.

Ứng dụng thực tế và triển khai

Trường hợp sử dụng thực tế (Use Cases)

  • Hệ mật mã khóa công khai: Khởi tạo các nhóm cyclic cấp nguyên tố lớn phục vụ giao thức Diffie-Hellman và hệ mật ElGamal, đảm bảo bài toán Logarit rời rạc $y = g^x \pmod p$ đạt độ an toàn cao nhất.
  • Bộ sinh số ngẫu nhiên giả lập (PRNG): Thuật toán Mersenne Twister (MT19937) sử dụng số nguyên tố Mersenne $2^{19937}-1$ làm chu kỳ tuần hoàn ($2^{19937}-1$), được tích hợp mặc định trong các ngôn ngữ lập trình như Python, C++, PHP và R.
  • Kiểm thử ứng suất phần cứng (Hardware Stress Testing): Dự án GIMPS sử dụng thuật toán Lucas-Lehmer trong phần mềm Prime95 để kiểm tra tính ổn định của CPU và bộ nhớ RAM khi ép xung (overclocking).
+-------------------------------------------------------------------------+
|                  Doanh thu & Chi phí (Đơn vị: Triệu VND)                |
+-------------------------------------------------------------------------+
| Năm 1: [Chi phí đầu tư: 50] =========> [Giá trị bảo mật thu hồi: 75]   |
| Năm 2: [Chi phí duy trì: 10] ==> [Giá trị bảo mật thu hồi: 120]         |
| Năm 3: [Chi phí duy trì: 10] ==> [Giá trị bảo mật thu hồi: 160]         |
+-------------------------------------------------------------------------+
| => Điểm hòa vốn (Break-even): Tháng thứ 8 | Tỷ suất ROI 3 năm: 335%     |
+-------------------------------------------------------------------------+

Yêu cầu triển khai và khả năng mở rộng

  • Cấu hình tối thiểu: CPU 64-bit 2.0GHz, 4GB RAM, dung lượng lưu trữ 500MB, hỗ trợ trình biên dịch C++17 và thư viện GMP.
  • Lộ trình mở rộng: Tích hợp tính toán phân tán (Distributed Computing) qua giao thức mạng TCP/IP socket và lập trình tính toán song song đa lõi thông qua OpenMP/CUDA, cho phép hệ thống kiểm tra các số mũ $n > 50,000,000$.

Hạn chế và hướng phát triển

  • Hạn chế kỹ thuật: Thuật toán Lucas-Lehmer chỉ áp dụng độc quyền cho họ số Mersenne $M_n = 2^n - 1$, không thể dùng trực tiếp để kiểm tra tính nguyên tố của các số nguyên dạng tổng quát $N$ bất kỳ trong hệ mật RSA. Phép nhân số nguyên lớn trong dãy $S_k = S_{k-1}^2 - 2 \pmod{M_n}$ bị giới hạn băng thông bộ nhớ khi số chữ số vượt quá 10 triệu chữ số nếu chưa áp dụng biến đổi Fourier nhanh (Schönhage–Strassen / Fast Fourier Transform FFT).
  • Hướng phát triển:
    1. Cài đặt thuật toán nhân nhanh số lớn dựa trên FFT và Number Theoretic Transform (NTT) để kiểm tra các số Mersenne có số mũ $n > 50,000,000$.
    2. Mở rộng hệ thống với các giải thuật kiểm tra nguyên tố cho số dạng tổng quát như Baillie-PSW và AKS (Agrawal-Kayal-Saxena).
    3. Xây dựng thư viện mã nguồn mở C++/Python đóng gói sẵn các module kiểm thử số học phục vụ cộng đồng nghiên cứu an toàn thông tin.

Đối tượng hưởng lợi

  • Sinh viên chuyên ngành CNTT và An toàn thông tin: Tiếp cận mã nguồn mẫu chuẩn mực, trực quan hóa các khái niệm trừu tượng trong đại số trừu tượng và số học mật mã.
  • Kỹ sư phát triển phần mềm (Developers): Nhận được tài liệu tham khảo chi tiết về kỹ thuật xử lý số nguyên lớn (BigNumber), tối ưu hóa modulo bằng phép toán bitwise và cài đặt thuật toán Euclid mở rộng.
  • Doanh nghiệp công nghệ và An ninh mạng: Tận dụng giải pháp tạo tham số mật mã an toàn, nâng cao năng lực kiểm định chất lượng các module mã hóa nội bộ.
  • Nhà nghiên cứu lý thuyết số: Nền tảng dữ liệu thực nghiệm phục vụ việc khảo sát phân bố của các số nguyên tố Mersenne và mối liên hệ với số hoàn thiện (Perfect Numbers).

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

1. Yêu cầu kỹ thuật phần cứng và phần mềm để triển khai thuật toán là gì?

Hệ thống yêu cầu máy tính chạy hệ điều hành Linux (Ubuntu/Debian) hoặc Windows x64, trang bị trình biên dịch GCC phiên bản từ 9.0 trở lên hoặc MSVC v142+, cùng thư viện GNU GMP v6.0+. Đối với các số mũ $n < 20,000$, cấu hình máy tính văn phòng tiêu chuẩn (Core i3, 4GB RAM) có thể chạy mượt mà trong thời gian dưới vài giây.

2. Tại sao số mũ $n$ bắt buộc phải là số nguyên tố để $2^n - 1$ là số nguyên tố?

Theo định lý đại số: nếu $n$ là hợp số ($n = a \cdot b$ với $a, b > 1$), ta luôn có phân tích nhân tử: $$2^{a \cdot b} - 1 = (2^a - 1)(2^{a(b-1)} + 2^{a(b-2)} + \dots + 1)$$ Do đó $2^n - 1$ chắc chắn chia hết cho $2^a - 1$ và là hợp số. Vì vậy, $n$ là số nguyên tố là điều kiện tiên quyết bắt buộc.

3. Số nguyên tố Mersenne được ứng dụng như thế nào trong mật mã học?

Số nguyên tố Mersenne cung cấp cơ sở xây dựng trường hữu hạn $\mathbb{F}_{M_n}$ với các phép tính số học modulo cực nhanh nhờ tối ưu hóa dịch bit. Ngoài ra, chúng là hạt nhân tạo ra các bộ sinh số ngẫu nhiên giả lập bảo mật cao (như Mersenne Twister MT19937) và nhóm tham số an toàn trong giao thức trao đổi khóa Diffie-Hellman.

4. Thuật toán Lucas-Lehmer có xảy ra sai số xác suất không?

Không. Thuật toán Lucas-Lehmer là giải thuật đơn định $100%$ (Deterministic). Định lý Lucas-Lehmer chứng minh rằng với $n > 2$, số $M_n = 2^n - 1$ là số nguyên tố khi và chỉ khi phần tử $S_{n-2} \equiv 0 \pmod{M_n}$ trong dãy $S_0 = 4, S_k = S_{k-1}^2 - 2$. Hoàn toàn không tồn tại số giả nguyên tố đối với kiểm tra này.

5. Chi phí triển khai và thời gian thu hồi giá trị đầu tư (ROI) ước tính ra sao?

Chi phí triển khai mô hình thử nghiệm phần mềm là $0$ đồng về mặt bản quyền do sử dụng hoàn toàn công nghệ mã nguồn mở (C++, GMP, GCC). Khi ứng dụng vào module tự động sinh khóa mật mã và kiểm tra ứng suất hệ thống máy chủ của doanh nghiệp, thời gian hoàn vốn và mang lại giá trị bảo mật ước tính trong vòng 6 đến 8 tháng.

Kết luận

Đồ án tốt nghiệp "Phương pháp nhận biết số nguyên tố dạng $2^n - 1$" của sinh viên Đỗ Hoàng Anh đã hoàn thành toàn diện các mục tiêu nghiên cứu từ cơ sở lý thuyết số, cấu trúc đại số trừu tượng đến cài đặt thực nghiệm các giải thuật mật mã hiện đại. Bằng việc làm chủ thuật toán kiểm tra đơn định Lucas-Lehmer, kết hợp với các kỹ thuật tối ưu hóa số học trên máy tính, công trình đã chứng minh tính hiệu quả vượt bậc trong việc xác định các số nguyên tố Mersenne khổng lồ, khắc phục hoàn toàn rào cản chi phí tính toán của phương pháp cổ điển và sai số của phương pháp xác suất. Đây là tiền đề học thuật và kỹ thuật vững chắc để tiếp tục phát triển các hệ thống mật mã khóa công khai hiệu năng cao, bảo vệ an toàn thông tin trong thời đại tính toán phân tán và trí tuệ nhân tạo.