Giới thiệu dự án

Trong kỷ nguyên chuyển đổi số và an ninh không gian mạng, mật mã học khóa công khai (Public Key Cryptography) đóng vai trò nền tảng để bảo vệ hơn 95% lưu lượng truyền tải dữ liệu toàn cầu thông qua các giao thức như TLS/HTTPS, SSH, IPsec và chữ ký số. Cốt lõi của các hệ mật mã phi đối xứng kinh điển như RSA, ElGamal, Trao đổi khóa Diffie-Hellman hay các hệ thống elliptic curve (ECC) đều dựa trên độ khó của các bài toán lý thuyết số: bài toán phân tích thừa số nguyên tố của số nguyên lớn (Integer Factorization Problem - IFP) và bài toán logarit rời rạc (Discrete Logarithm Problem - DLP).

Để thiết lập các tham số an toàn, hệ thống bắt buộc phải sinh và kiểm tra các số nguyên tố có kích thước hàng trăm đến hàng ngàn bit. Tuy nhiên, bài toán kiểm tra tính nguyên tố đối với một số nguyên tổng quát $N$ có kích thước lớn luôn đối mặt với nút thắt cổ chai về độ phức tạp tính toán. Phép thử chia cổ điển (Trial Division) với độ phức tạp $O(\sqrt{N})$ trở nên hoàn toàn bất khả thi trên các số nguyên lớn. Chẳng hạn, với một số $n$ có kích thước 512-bit ($N \approx 2^{512}$), việc duyệt ước số tới $\sqrt{N} = 2^{256}$ trên một máy tính xử lý $10^6$ chỉ lệnh/giây sẽ tiêu tốn khoảng $2^{255}$ giây (tương đương hơn $2^{230}$ năm).

Đồ án tốt nghiệp "Phương pháp nhận biết số nguyên tố dạng $2^n-1$" của tác giả Đỗ Hoàng Anh, dưới sự hướng dẫn của TS. Hồ Văn Canh tại Trường Đại học Quản lý và Công nghệ Hải Phòng (2023), tập trung giải quyết bài toán kiểm tra tính nguyên tố của các số dạng đặc biệt – số Mersenne $M_n = 2^n - 1$.

graph TD
    A["Số Mersenne Mn = 2^n - 1"] --> B{"Kiểm tra số mũ n"}
    B -- "n là hợp số" --> C["Mn chắc chắn là hợp số"]
    B -- "n là số nguyên tố" --> D["Khởi tạo kiểm tra Lucas-Lehmer"]
    D --> E["S0 = 4"]
    E --> F["Vòng lặp: Sk = (Sk-1^2 - 2) mod Mn (k từ 1 đến n-2)"]
    F --> G{"Sn-2 ≡ 0 (mod Mn)?"}
    G -- "Đúng" --> H["KẾT LUẬN: Mn LÀ SỐ NGUYÊN TỐ"]
    G -- "Sai" --> I["KẾT LUẬN: Mn LÀ HỢP SỐ"]

Mục tiêu cụ thể của đề tài bao gồm:

  1. Hệ thống hóa cơ sở lý thuyết số học và đại số trừu tượng: nhóm Cyclic $\mathbb{Z}_n^*$, cấp của phần tử, định lý Lagrange, hàm một phía (one-way functions) và hàm cửa sập (trapdoor one-way functions).
  2. Phân tích các thuật toán kiểm tra số nguyên tố và phân tích thừa số kinh điển: thuật toán Euclid mở rộng, thuật toán phân tích thừa số $p-1$ của Pollard, sàng Eratosthenes, kiểm tra xác suất Fermat.
  3. Nghiên cứu sâu cơ chế tất định của phép kiểm tra Lucas-Lehmer (Lucas-Lehmer Primality Test) dành riêng cho họ số nguyên Mersenne $M_n = 2^n - 1$.
  4. Thiết kế, cài đặt và đánh giá chương trình thực nghiệm trên máy tính, kiểm tra chính xác tính nguyên tố của các số Mersenne quy mô lớn (lên tới $n = 11213$) và phân tích thừa số nguyên tố cho dải dữ liệu thực tế.

Giải pháp mang lại kết quả kỳ vọng là một công cụ thực nghiệm đạt độ chính xác 100% đối với các số Mersenne khảo sát, tối ưu thời gian thực thi từ cấp số mũ $O(2^{n/2})$ xuống cấp độ đa thức $O(n^2 \log n \log \log n)$, tạo tiền đề cho các ứng dụng nghiên cứu an toàn bảo mật và giáo dục mật mã học.

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

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

Trước khi đi sâu vào số nguyên tố Mersenne, các giải pháp kiểm tra nguyên tố hiện hữu được phân chia thành hai nhóm: phương pháp tất định (deterministic) và phương pháp xác suất (probabilistic).

Phương pháp Loại thuật toán Độ phức tạp thời gian Độ chính xác Ưu điểm Nhược điểm
Trial Division (Chia thử) Tất định $O(\sqrt{N}) = O(2^{k/2})$ $100%$ Dễ cài đặt, hiệu quả với số cực nhỏ ($N < 10^6$). Độ phức tạp hàm mũ theo số bit $k$; bất khả thi với số lớn.
Sàng Eratosthenes Tất định (Dải số) $O(N \log \log N)$ $100%$ Liệt kê nhanh toàn bộ số nguyên tố trong đoạn $[1, N]$. Tiêu tốn bộ nhớ $O(N)$; không kiểm tra đơn lẻ số siêu lớn.
Fermat Primality Test Xác suất $O(k \cdot \log^3 N)$ Xác suất (Có thể sai) Tốc độ nhanh; dựa trên định lý nhỏ Fermat $a^{N-1} \equiv 1 \pmod N$. Bị đánh lừa bởi số giả nguyên tố (Fermat pseudoprimes) và số Carmichael.
Lucas-Lehmer (LLT) Tất định (Mersenne) $O(n^2 \cdot M(n))$ $100%$ Tối ưu tuyệt đối cho dạng $M_n = 2^n - 1$; tất định 100%. Chỉ áp dụng duy nhất cho các số có dạng $M_n = 2^n - 1$.

Yêu cầu người dùng đối với hệ thống được chuẩn hóa theo mô hình MoSCoW:

  • Must Have: Kiểm tra tất định số nguyên tố dạng $M_n = 2^n - 1$ bằng kiểm tra Lucas-Lehmer; thuật toán Sàng Eratosthenes cho dải $n \le 5000$; hỗ trợ xử lý số nguyên lớn (Arbitrary-precision arithmetic).
  • Should Have: Phân tích thừa số nguyên tố cho hợp số dạng tổng quát bằng phương pháp Pollard's $p-1$; tính phần tử nghịch đảo modulo $\mathbb{Z}_n$ qua Euclid mở rộng.
  • Could Have: Giao diện trực quan hóa quá trình tính toán và đo lường thời gian thực thi (benchmarking).
  • Won't Have: Tính toán song song quy mô lưới đa cụm GPU (được định hướng cho phiên bản mở rộng).

Thiết kế hệ thống

Kiến trúc phần mềm được tổ chức theo mô hình phân tầng module độc lập, tách biệt giữa tầng xử lý đại số số học và tầng tương tác:

graph LR
    subgraph UI_Layer ["Tầng Giao Diện"]
        CLI["CLI / Console Interface"]
        GUI["Module Thực Nghiệm & Đo Đạc"]
    end

    subgraph Service_Layer ["Tầng Dịch Vụ Nghiệp Vụ"]
        LLT_Engine["Lucas-Lehmer Service (Mn = 2^n - 1)"]
        Sieve_Engine["Eratosthenes Sieve Service"]
        Factor_Engine["Pollard p-1 Factorizer"]
        Mod_Engine["Extended Euclidean & Modular Inverse"]
    end

    subgraph Core_Math ["Tầng Cốt Lõi Tính Toán"]
        BigInt["BigInteger ALU (Arbitrary Precision)"]
        FastMod["Fast Mersenne Reduction (Shift/Add)"]
    end

    UI_Layer --> Service_Layer
    Service_Layer --> Core_Math
  • Công nghệ triển khai: Ngôn ngữ C++17 (GNU GCC 11.2) kết hợp thư viện toán học đa độ dài Boost.Multiprecision và GNU Multiple Precision Arithmetic Library (GMP v6.2.1) nhằm đảm bảo tốc độ tính toán số nguyên hàng ngàn chữ số.
  • Cơ chế an toàn & hiệu năng: Sử dụng kỹ thuật khử Modulo Mersenne tối ưu dựa trên phép dịch bit: phép chia modulo $M_n = 2^n - 1$ được tính thông qua biểu thức tương đương $X \equiv (X \bmod 2^n) + \lfloor X / 2^n \rfloor \pmod{2^n-1}$, giúp loại bỏ phép chia số lớn đắt đỏ và tăng tốc độ xử lý hơn $4.5$ lần.

Methodology

Quy trình phát triển đề tài áp dụng mô hình nghiên cứu lặp (Iterative Research-Driven Engineering) với 4 giai đoạn cụ thể:

  1. Giai đoạn 1 (Khảo sát lý thuyết): Nghiên cứu cấu trúc nhóm nhân $\mathbb{Z}_n^*$, cấp của phần tử, tính chất của số hoàn thiện (Perfect Numbers) $M(M+1)/2$ theo định lý Euclid-Euler, và các tính chất đồng dư đặc thù của dãy Lucas.
  2. Giai đoạn 2 (Thiết kế giải thuật cốt lõi): Chuẩn hóa thuật toán tìm nghịch đảo Euclid mở rộng, thuật toán Pollard $p-1$, và thuật toán sinh dãy hồi quy $S_k = S_{k-1}^2 - 2 \pmod{M_n}$.
  3. Giai đoạn 3 (Cài đặt & Tối ưu BigInteger): Xây dựng module tính toán số nguyên lớn, xử lý tràn bit khi bình phương các số có hàng ngàn bit nhị phân.
  4. Giai đoạn 4 (Kiểm thử & Đánh giá chuẩn): Chạy thực nghiệm trên bộ dữ liệu chuẩn từ dự án GIMPS (Great Internet Mersenne Prime Search), so sánh sai số và đo đạc thời gian tính toán.

Implementation và kết quả

Development process

Cốt lõi của đề tài là việc cài đặt chính xác các giải thuật số học nền tảng và kiểm tra Lucas-Lehmer.

1. Thuật toán kiểm tra Lucas-Lehmer cho số $M_n = 2^n - 1$

Định lý phát biểu: Với $n > 2$ là số nguyên tố, $M_n = 2^n - 1$ là số nguyên tố khi và chỉ khi $M_n$ chia hết cho $S_{n-2}$, trong đó dãy $S$ được xác định bởi: $S_0 = 4$ và $S_k = (S_{k-1}^2 - 2) \bmod M_n$.

#include <iostream>
#include <boost/multiprecision/cpp_int.hpp>

using namespace boost::multiprecision;

// Kiểm tra số nguyên tố Mersenne M_p = 2^p - 1
bool LucasLehmerTest(int p) {
    if (p == 2) return true;
    if (p < 2 || p % 2 == 0) return false;

    cpp_int Mp = (cpp_int(1) << p) - 1; // Mp = 2^p - 1
    cpp_int s = 4;

    for (int i = 0; i < p - 2; ++i) {
        s = (s * s - 2) % Mp;
    }

    return (s == 0);
}

2. Thuật toán Euclid mở rộng tìm nghịch đảo Modulo

Được sử dụng trong giải mã và tính phần tử nghịch đảo $a^{-1} \pmod n$ khi $\gcd(a, n) = 1$:

Procedure Extended_Euclid_Invert(a: Integer; n: Integer; var a_inv: Integer);
Var
    g0, g1, u0, u1, v0, v1, y, gi_next, ui_next, vi_next, t: Integer;
Begin
    g0 := n; g1 := a;
    u0 := 1; u1 := 0;
    v0 := 0; v1 := 1;
    While g1 <> 0 Do
    Begin
        y := g0 Div g1;
        gi_next := g0 - y * g1;
        ui_next := u0 - y * u1;
        vi_next := v0 - y * v1;
        
        g0 := g1; g1 := gi_next;
        u0 := u1; u1 := ui_next;
        v0 := v1; v1 := vi_next;
    End;
    t := v0;
    If t > 0 Then
        a_inv := t
    Else
        a_inv := t + n;
End;

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

Phương pháp hữu hiệu để tách nhân tử nguyên tố không tầm thường $d$ của hợp số $n$ khi $p-1$ chỉ có các ước nguyên tố nhỏ:

import math

def pollard_p_minus_1(n, max_iterations=1000):
    # Hàm sinh chuỗi ngẫu nhiên f(x) = (x^2 + 1) mod n
    def f(x):
        return (x * x + 1) % n

    x = 2
    y = 2
    d = 1

    while d == 1:
        x = f(x)           # Bước nhảy đơn
        y = f(f(y))        # Bước nhảy đôi (Tortoise and Hare)
        d = math.gcd(abs(x - y), n)

    if d == n:
        return "Không tìm thấy nhân tử (Thử lại với hàm f khác)"
    else:
        return d  # Nhân tử không tầm thường tìm được

Testing và validation

Chương trình được thực nghiệm trên máy tính thử nghiệm cấu hình chuẩn: Intel Core i5 @ 2.6 GHz, 8GB RAM, hệ điều hành Linux Ubuntu 22.04 LTS / Windows 10 64-bit.

========================================================================
KIỂM TRA TÍNH NGUYÊN TỐ CỦA CÁC SỐ MERSENNE M_n = 2^n - 1
========================================================================
[Test 1] n = 2      => M_2 = 3                  => PRIME (0.001 ms)
[Test 2] n = 3      => M_3 = 7                  => PRIME (0.001 ms)
[Test 3] n = 5      => M_5 = 31                 => PRIME (0.001 ms)
[Test 4] n = 7      => M_7 = 127                => PRIME (0.001 ms)
[Test 5] n = 11     => M_11 = 2047 (23 * 89)    => COMPOSITE (0.002 ms)
[Test 6] n = 13     => M_13 = 8191              => PRIME (0.002 ms)
[Test 7] n = 17     => M_17 = 131071            => PRIME (0.003 ms)
[Test 8] n = 19     => M_19 = 524287            => PRIME (0.003 ms)
[Test 9] n = 31     => M_31 = 2147483647        => PRIME (0.005 ms)
[Test 10] n = 61    => M_61 = 2305843009213693951 => PRIME (0.012 ms)
...
[Test 23] n = 11213 => M_11213 (3,376 chữ số)   => PRIME (1420.45 ms)
========================================================================
Số mũ $n$ Giá trị $M_n = 2^n - 1$ Số chữ số thập phân Kết quả Lucas-Lehmer Thời gian LLT (ms) Thời gian Trial Division
$n = 5$ $31$ 2 Số nguyên tố 0.001 < 0.001 ms
$n = 11$ $2047$ ($23 \times 89$) 4 Hợp số 0.002 < 0.001 ms
$n = 31$ $2,147,483,647$ 10 Số nguyên tố 0.005 0.42 ms
$n = 61$ $\approx 2.3058 \times 10^{18}$ 19 Số nguyên tố 0.012 1,480.20 ms
$n = 521$ $\approx 6.8647 \times 10^{156}$ 157 Số nguyên tố 4.85 Vượt quá thời gian (> 100 năm)
$n = 1279$ $\approx 1.0407 \times 10^{385}$ 386 Số nguyên tố 28.30 Bất khả thi
$n = 4253$ $\approx 1.9079 \times 10^{1280}$ 1,281 Số nguyên tố (Titanic) 245.10 Bất khả thi
$n = 11213$ $\approx 2.8141 \times 10^{3375}$ 3,376 Số nguyên tố (Gigantic) 1,420.45 Bất khả thi

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

  1. Khả năng kiểm định chính xác: Kiểm chứng thành công toàn bộ danh sách 23 số nguyên tố Mersenne đầu tiên trong lịch sử toán học điện toán (từ $M_2$ đến $M_{11213}$), đảm bảo độ hội tụ $100%$ không xảy ra lỗi sai số logic.
  2. Liệt kê & Sàng lọc dữ liệu: Ứng dụng thuật toán Sàng Eratosthenes liệt kê chính xác $669$ số nguyên tố trong dải từ $1 \to 5000$ chỉ trong $1.82\text{ ms}$, làm bộ lọc điều kiện cần ($n$ phải là số nguyên tố) trước khi đưa vào kiểm tra Lucas-Lehmer.
  3. Phân tích nhân tử: Thực nghiệm thành công giải thuật Pollard's $p-1$ trên các số thử nghiệm như $8051 = 97 \times 83$, $1001 = 7 \times 11 \times 13$, và các hợp số Mersenne như $M_{11} = 2047 = 23 \times 89$.

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

  1. Ứng dụng tối ưu toán tử dịch bit (Bitwise Optimization): Bằng việc khai thác đặc tính nhị phân của $M_n = 2^n - 1$ (chuỗi gồm $n$ bit 1 liên tiếp), phép tính modulo lớn $(s^2 - 2) \bmod M_n$ được thực thi thông qua các phép toán dịch bit (>>, <<) và phép cộng logic (&, +), giúp cải thiện tốc độ nhân modulo hơn $350%$ so với việc gọi hàm mod tổng quát của các thư viện lớn.
  2. So sánh với giải pháp trước đây: So với phương pháp kiểm tra chia thử $O(\sqrt{N})$, Lucas-Lehmer giảm độ phức tạp thời gian từ cấp số mũ sang đa thức. So với kiểm tra xác suất Fermat/Miller-Rabin, Lucas-Lehmer cung cấp lời khẳng định tất định $100%$ mà không cần kiểm tra lặp nhiều vòng cơ sở (witness loops).
  3. Đóng góp học thuật: Đồ án tổng hợp hoàn chỉnh từ nền tảng lý thuyết số học trừu tượng (nhóm, vành, trường đồng dư, tính nguyên thủy) đến thực thi phần mềm cụ thể, cung cấp tài liệu tham khảo và mã nguồn mẫu cho sinh viên chuyên ngành Mật mã học và An toàn thông tin.

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

graph TD
    A["Thuật toán & Cơ sở lý thuyết số nguyên tố Mersenne"] --> B["An toàn thông tin & Mật mã học"]
    A --> C["Kiểm thử phần cứng (Hardware Stress Test)"]
    A --> D["Bộ sinh số giả ngẫu nhiên (PRNG)"]

    B --> B1["Sinh khóa an toàn cho RSA, ElGamal, ECC"]
    B --> B2["Ứng dụng trong hệ mật mã Lucas (LUC)"]

    C --> C1["Kiểm tra tính ổn định của CPU/FPU (Prime95)"]
    C --> C2["Phát hiện lỗi phần cứng trong siêu máy tính"]

    D --> D1["Mersenne Twister Algorithm (MT19937)"]
    D --> D2["Mô phỏng Monte Carlo & Game Engine"]
  1. Khởi tạo tham số hệ mật mã: Cung cấp nguồn số nguyên tố siêu lớn phục vụ nghiên cứu các giao thức trao đổi khóa Diffie-Hellman và hệ mật mã dựa trên dãy Lucas (hệ LUC, LUCELG, LUCDIF).
  2. Kiểm thử ổn định phần cứng (Hardware Benchmarking): Phép lặp Lucas-Lehmer liên tục trên các số nguyên lớn là công cụ tiêu chuẩn để kiểm tra tính ổn định, tản nhiệt và phát hiện lỗi tính toán dấu phẩy động/số học nguyên của các dòng vi xử lý mới (như phương thức Prime95 thực hiện).
  3. Bộ tạo số ngẫu nhiên chất lượng cao: Nền tảng số Mersenne $2^{19937}-1$ là nền móng của thuật toán Mersenne Twister (MT19937) – bộ sinh số giả ngẫu nhiên được tích hợp mặc định trong hầu hết các ngôn ngữ lập trình như Python, C++, PHP, R.

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

  • Hạn chế kỹ thuật: Chương trình hiện đang thực thi trên môi trường xử lý đơn luồng (single-thread CPU). Khi số mũ $n > 50000$ (kích thước vượt quá $15000$ chữ số thập phân), thuật toán nhân BigInt trường hợp xấu $O(k^2)$ bắt đầu xuất hiện độ trễ đáng kể do chưa tích hợp giải thuật nhân nhanh biến đổi Fourier rời rạc (FFT / Schönhage-Strassen).
  • Hướng phát triển:
    1. Tích hợp thư viện nhân nhanh đa thức nhiều biến dựa trên biến đổi số học NTT/FFT để hỗ trợ kiểm tra các số Mersenne có hàng triệu chữ số ($n > 10,000,000$).
    2. Song song hóa tính toán thông qua OpenMP/MPI và tận dụng hàng ngàn nhân xử lý trên GPU qua CUDA.
    3. Mở rộng phần mềm sang các thuật toán kiểm tra tính nguyên tố tổng quát như APR-CL (Adleman-Pomerance-Rumely) và AKS (Agrawal-Kayal-Saxena).

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

  • Sinh viên & Học viên: Cung cấp tài liệu trực quan, dễ hiểu kèm mã nguồn mẫu minh họa về mối liên hệ giữa lý thuyết số và khoa học máy tính ứng dụng.
  • Lập trình viên & Kỹ sư an toàn thông tin: Nắm vững cấu trúc đại số và kỹ thuật tối ưu hóa phép toán modulo lớn, phục vụ cài đặt các giao thức mã hóa tự phát triển.
  • Nhà nghiên cứu lý thuyết số: Sử dụng công cụ để thực nghiệm nhanh các giả thuyết về số hoàn thiện, số Fermat, phân phối số nguyên tố theo Định lý Prime Number Theorem.

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

1. Cấu hình hệ thống tối thiểu để triển khai chương trình là gì?

Chương trình yêu cầu môi trường hệ điều hành Linux (Ubuntu 18.04+) hoặc Windows 10/11 64-bit, trình biên dịch hỗ trợ chuẩn C++17 (GCC 9+, MSVC 2019+), RAM tối thiểu 2GB và bộ nhớ trống 100MB.

2. Giới hạn độ dài số mũ mà chương trình có thể kiểm tra trong thời gian chấp nhận được?

Với phiên bản tối ưu bitwise hiện tại trên CPU cá nhân, chương trình xử lý mượt mà và trả kết quả dưới 2 giây cho các số mũ $n \le 11213$ (khoảng $3376$ chữ số thập phân). Với $n > 50000$, thời gian thực thi sẽ tăng dần nếu không kích hoạt thuật toán nhân FFT.

3. Tại sao không dùng thuật toán chia thử (Trial Division) cho mọi bài toán kiểm tra nguyên tố?

Thuật toán chia thử có độ phức tạp hàm mũ $O(\sqrt{N})$. Với một số có 100 chữ số, số phép chia thử cần thực hiện lớn hơn tổng số nguyên tử trong vũ trụ quan sát được, làm cho việc tính toán bị nghẽn vô hạn.

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

Không. Lucas-Lehmer là thuật toán tất định 100% (Deterministic). Nếu $S_{n-2} \equiv 0 \pmod{M_n}$, số $M_n$ chắc chắn là số nguyên tố, loại bỏ hoàn toàn hiện tượng "số giả nguyên tố" (Pseudoprimes).

5. Chi phí triển khai và khả năng tái sử dụng mã nguồn như thế nào?

Mã nguồn được viết hoàn toàn trên các công nghệ mã nguồn mở (C++, Boost, GCC), không tốn chi phí bản quyền thương mại và có thể đóng gói thành thư viện liên kết động (.dll/.so) phục vụ tích hợp vào các dự án phần mềm khác.

Kết luận

Đề tài "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 đã giải quyết trọn vẹn bài toán kiểm tra tính nguyên tố cho họ số Mersenne bằng việc hiện thực hóa thuật toán kiểm tra tất định Lucas-Lehmer kết hợp kỹ thuật tối ưu hóa số học modulo trên hệ nhị phân. Đồ án không chỉ củng cố bức tranh toàn cảnh về lý thuyết đại số nhóm đồng dư, các hàm cửa sập trong mật mã hóa mà còn mang lại một sản phẩm phần mềm thực nghiệm có độ tin cậy và hiệu năng cao. Đây là nền tảng vững chắc cho các hướng phát triển chuyên sâu về tính toán hiệu năng cao (HPC) và công nghệ an toàn bảo mật thông tin trong tương lai.