Bối cảnh và vấn đề nghiên cứu

Trong lĩnh vực an toàn và bảo mật thông tin hiện đại, lý thuyết số học và đặc biệt là bài toán số nguyên tố lớn giữ vai trò nền tảng cốt lõi. Các hệ thống hạ tầng cơ sở khóa công khai, các giao thức mật mã bất đối xứng tiêu biểu như RSA, ElGamal, cũng như các cơ chế xác thực và chữ ký số đều phụ thuộc trực tiếp vào việc sinh và kiểm tra các số nguyên tố có kích thước lớn. Một vấn đề căn bản đặt ra trong thực tiễn tính toán là làm thế nào để khẳng định một số nguyên dương $N$ bất kỳ là số nguyên tố hay hợp số. Mặc dù ngoại trừ số 2, mọi số nguyên tố đều là số lẻ, nhưng một số lẻ chưa hẳn đã là số nguyên tố (ví dụ các số 9, 15, hoặc $2047 = 23 \times 89$ đều là hợp số lẻ). Khi kích thước dữ liệu tăng lên, việc kiểm tra bằng phương pháp thử thông thường đòi hỏi thời gian tính toán vượt xa giới hạn thực tế, đặt ra yêu cầu phải nghiên cứu các thuật toán chuyên biệt cho các họ số có cấu trúc toán học đặc biệt.

Từ yêu cầu thực tiễn đó, đồ án tốt nghiệp tập trung vào việc nghiên cứu họ số nguyên tố dạng $2^n - 1$ (số nguyên tố Mersenne). Nhiệm vụ nghiên cứu của đề tài được giao cụ thể gồm 3 nội dung:

  1. Tìm hiểu về vai trò của số nguyên tố trong an toàn bảo mật thông tin.
  2. Tìm hiểu các phương pháp nhận biết số nguyên tố dạng $2^n - 1$.
  3. Cài đặt chương trình thử nghiệm để kiểm chứng thuật toán.

Đối tượng nghiên cứu của đồ án là số nguyên tố, tập trung chuyên sâu vào số nguyên tố có dạng đặc biệt $2^n - 1$, cùng các cấu trúc đại số và thuật toán kiểm tra tính nguyên tố liên quan. Phạm vi không gian của nghiên cứu được thực hiện tại Khoa Công nghệ Thông tin, Trường Đại học Quản lý và Công nghệ Hải Phòng, phối hợp với quá trình thực tập chuyên môn tại Công ty Cổ phần Đầu tư Tài chính và Công nghệ Datatech, dưới sự hướng dẫn khoa học của giảng viên thuộc Học viện Kỹ thuật Mật mã (Cục Kỹ thuật Nghiệp vụ - CBA). Về mặt thời gian, đề tài được giao thực hiện từ ngày 17 tháng 4 năm 2023 và hoàn thành bảo vệ vào tháng 6 năm 2023.

Cơ sở lý thuyết và phương pháp

Cơ sở lý thuyết của đồ án được xây dựng trên nền tảng số học, đại số trừu tượng và lý thuyết độ phức tạp tính toán:

  • Khái niệm và cấu trúc số học - đại số: Văn bản sử dụng các khái niệm về quan hệ chia hết, ước số chung lớn nhất ($\gcd$), bội số chung nhỏ nhất ($\text{lcm}$), quan hệ đồng dư modulo, cấu trúc nhóm $(G, )$, nhóm con, nhóm cyclic, phần tử sinh, cấp của nhóm và cấp của một phần tử. Nhóm nhân các phần tử khả nghịch $\mathbb{Z}_n^$ và hàm phi Euler $\phi(n)$ được thiết lập để làm rõ định lý Lagrange và bài toán logarit rời rạc ($x = \log_\alpha \beta \pmod p$).
  • Lý thuyết độ phức tạp và mật mã học: Đồ án phân tích các lớp độ phức tạp tính toán gồm lớp $P$, lớp $NP$, khái niệm máy Turing tất định và không tất định, phép quy dẫn thời gian đa thức và bài toán $NP$-đầy đủ (SAT, CLIQUE, KNAPSACK, Thặng dư bậc hai, Hợp số, Số nguyên tố). Nghiên cứu định nghĩa hàm một phía (one-way function) và hàm cửa sập một phía (trapdoor one-way function), trong đó phép nhân hai số nguyên tố lớn là dễ nhưng bài toán phân tích ngược lại ra thừa số nguyên tố là rất khó trừ khi biết thông tin cửa sập $\phi(n) = (p-1)(q-1)$.
  • Quy luật phân bố số nguyên tố: Định lý số nguyên tố (Prime Number Theorem) biểu diễn hàm đếm $\pi(n) \approx n/\ln n$. Dựa trên định lý này, tỷ lệ số nguyên tố trong khoảng từ 5 tỷ đến 6 tỷ đạt khoảng 4,3% (trung bình cứ 23 số ngẫu nhiên thì có 1 số nguyên tố), tạo cơ sở xác suất cho việc sinh tham số mật mã.

Phương pháp nghiên cứu được triển khai bao gồm:

  • Phương pháp phân tích và tổng hợp lý thuyết: Khảo cứu tài liệu học thuật từ các công trình chuyên khảo về mật mã và số học của Hồ Văn Canh, Lê Danh Cường (2018), Phan Đình Diệu (2002), Trịnh Nhật Tiến (2003), Menezes, van Oorschot, Vanstone (1999), Neal Koblitz (2000), và Donald Knuth (2004).
  • Phương pháp toán học hình thức: Chứng minh các tính chất số học, điều kiện cần để $2^n - 1$ là số nguyên tố thì số mũ $n$ phải là số nguyên tố; phân tích định lý Euler, định lý Fermat nhỏ, và cấu trúc dãy số phục vụ kiểm tra Lucas-Lehmer.
  • Phương pháp thực nghiệm số trị: Cài đặt thuật toán, phân tích chi phí tính toán theo ký hiệu $O$ lớn và thực hiện kiểm thử trên dữ liệu số thực tế.

Nguồn dữ liệu sử dụng trong đồ án gồm bảng thống kê lịch sử 46 số nguyên tố Mersenne đã biết do tổ chức GIMPS (Great Internet Mersenne Prime Search) công bố, kết hợp các bộ dữ liệu số nguyên khảo sát trong phạm vi từ 1 đến 5000 và các số mũ $n$ lên đến 11213.

Thiết kế và triển khai

Căn cứ trên mục tiêu cài đặt chương trình thử nghiệm, phần kỹ thuật của đồ án bao gồm các thành phần sau:

  • Môi trường và cấu hình hệ thống: Thiết lập hệ thống máy tính cá nhân để biên dịch và thực thi chương trình kiểm thử các thuật toán số học đã nghiên cứu lý thuyết.
  • Các chức năng chính của chương trình:
    • Chức năng kiểm tra tính nguyên tố của các số tự nhiên đơn lẻ trong phạm vi từ 2 đến 5000.
    • Chức năng kiểm tra và nhận biết số nguyên tố Mersenne dạng $2^n - 1$ với các số mũ $n$ mở rộng từ 2 đến 11213.
    • Chức năng liệt kê toàn bộ các số nguyên tố trong một dải cho trước từ 1 đến 5000 dựa trên giải thuật sàng.
    • Chức năng phân tích số tự nhiên ra các thừa số nguyên tố cho các giá trị kiểm thử cụ thể gồm 27, 102, 1001 và 5000.
  • Cài đặt hệ thống: Chuyển đổi các mô tả giải thuật (sàng Eratosthenes, kiểm tra Lucas-Lehmer, thuật toán phân tích thừa số) thành các hàm xử lý tính toán số học, hiển thị kết quả kiểm tra trạng thái nguyên tố hoặc hợp số cùng thời gian thực thi tương ứng.

Nội dung chính theo từng chương

Chương I: Các khái niệm cơ bản

Chương 1 hệ thống hóa các kiến thức nền tảng về số học, đại số trừu tượng, thuật toán số học và lý thuyết độ phức tạp tính toán:

  • Số học và đại số: Trình bày định nghĩa chia hết, ước số chung lớn nhất ($\gcd$), đồng dư modulo. Trình bày cấu trúc nhóm, nhóm cyclic hữu hạn cấp $n$, định lý Lagrange và ứng dụng trong nhóm nhân $\mathbb{Z}_p^*$.
  • Thuật toán Euclid và Euclid mở rộng: Trình bày thuật toán tìm $\gcd(a, b)$ và thuật toán Euclid mở rộng để giải phương trình vô định $a \cdot x + b \cdot y = \gcd(a, b)$. Văn bản cung cấp ví dụ số trị tính toán từng bước với hai số $a = 4864$ và $b = 3458$:
Bước $a$ $b$ $q = a \text{ div } b$ $r = a \bmod b$ $x$ $y$ $x_1$ $x_2$ $y_1$ $y_2$
Khởi tạo 4864 3458 - - 0 1 1 0 - -
1 3458 1406 1 1406 1 -1 1 0 -1 1
2 1406 646 2 646 -2 3 -2 1 3 -1
3 646 114 2 114 5 -7 5 -2 -7 3
4 114 76 5 76 -27 38 -27 5 38 -7
5 76 38 1 38 32 -45 32 -27 -45 38
Kết thúc 38 0 2 0 -91 128 -91 32 128 -45

Kết quả thu được $\gcd(4864, 3458) = 38$ và cặp nghiệm thỏa mãn là $x = 32, y = -45$, tức $4864 \cdot 32 + 3458 \cdot (-45) = 38$.

  • Thuật toán nghịch đảo modulo: Thiết lập hàm Invert(a, n) dựa trên Euclid mở rộng để giải phương trình $a \cdot x \equiv 1 \pmod n$. Minh họa giải phương trình $3 \cdot x \equiv 1 \pmod 7$, cho kết quả phần tử nghịch đảo của 3 trong $\mathbb{Z}_7$ là $x = 5$.
  • Thuật toán phân tích thừa số: Trình bày tổng quan về các phương pháp sàng bậc hai (Quadratic Sieve), đường cong Elliptic của Lenstra, sàng trường số, và thuật toán kiểu Las Vegas. Khảo sát chi tiết phương pháp $p-1$ của Pollard với hàm ngẫu nhiên $f(x) = x^2 + c \pmod n$. Ví dụ với $n = 8051$ và $f(x) = x^2 + 1 \pmod{8051}$, thuật toán tìm ra nhân tử không tầm thường là 97 qua 3 bước lặp, từ đó xác định thừa số còn lại là $8051 / 97 = 83$.
  • Độ phức tạp thuật toán cổ điển: Đối với thuật toán chia thử tìm thừa số của $n$ đến $\sqrt{n}$, tác giả tính toán với khóa 512 bit ($n \approx 2^{512}$). Nếu máy tính thực hiện $10^6$ chỉ lệnh/giây, thời gian vét cạn cần thiết là $T = 2^{255} \text{ giây} \approx 2^{238} \text{ ngày} \approx 2^{230} \text{ năm}$, chứng minh tính bất khả thi về mặt thực tiễn.
  • Hàm một phía và cửa sập: Phân tích cơ chế an toàn của hàm $y = a^x \bmod p$ (bài toán logarit rời rạc) và hàm RSA $y = x^a \bmod n$, trong đó thông tin phân tích $n = p \cdot q$ cho phép xác định số mũ giải mã $b$ thông qua thuật toán Euclid mở rộng ($a \cdot b \equiv 1 \pmod{\phi(n)}$).

Chương II: Một số phương pháp kiểm tra số nguyên tố

Chương 2 đi sâu vào lý thuyết số nguyên tố, các họ số nguyên tố đặc biệt và các phương pháp kiểm tra tính nguyên tố:

  • Khái niệm và tính chất: Trình bày chứng minh ước tự nhiên khác 1 nhỏ nhất của một số là số nguyên tố; ước số dương bé nhất khác 1 của hợp số $a$ không vượt quá $\sqrt{a}$; chứng minh định lý Euclid về sự vô hạn của tập hợp số nguyên tố bằng phương pháp phản chứng thông qua biểu thức $P + 1 = (p_1 p_2 \dots p_r) + 1$.
  • Định lý cơ bản của số học: Mọi số tự nhiên lớn hơn 1 đều phân tích duy nhất thành tích thừa số nguyên tố dạng tiêu chuẩn $n = p_1^{k_1} p_2^{k_2} \dots p_m^{k_m}$, và số các ước số tự nhiên của $n$ được xác định bằng $(k_1 + 1)(k_2 + 1) \dots (k_m + 1)$ (ví dụ 300 có 18 ước tự nhiên).
  • Số nguyên tố Mersenne: Định nghĩa số Mersenne $M_n = 2^n - 1$. Chứng minh định lý: Nếu $M_n = 2^n - 1$ là số nguyên tố thì $n$ bắt buộc phải là số nguyên tố, dựa trên phép khai triển $2^{pr} - 1 = (2^p - 1)(2^{p(r-1)} + \dots + 1)$. Khẳng định mệnh đề đảo không đúng thông qua phản ví dụ $2^{11} - 1 = 2047 = 23 \times 89$. Phân tích mối liên hệ lịch sử với số hoàn thiện chẵn thông qua công thức Euclid-Euler $M(M+1)/2$.
  • Kiểm tra Lucas-Lehmer cho số Mersenne: Thiết lập dãy số tuần hoàn với $S_0 = 4$ và $S_k = S_{k-1}^2 - 2$. Với $n > 2$, $M_n = 2^n - 1$ là số nguyên tố khi và chỉ khi $S_{n-2} \equiv 0 \pmod{M_n}$.
  • Lịch sử và thống kê 46 số nguyên tố Mersenne: Đồ án lập bảng thống kê chi tiết 46 số nguyên tố Mersenne đã biết đến tháng 9/2008: từ 4 số đầu tiên biết từ thời cổ đại ($M_2, M_3, M_5, M_7$), các phát hiện của Cataldi (1588), Euler (1750), Lucas (1876), kỷ nguyên máy tính điện tử với máy SWAC do Robinson và Lehmer vận hành (1952 phát hiện $M_{521}$ và $M_{607}$), các siêu máy tính Cray-2 của Slowinski, cho đến dự án tính toán phân tán GIMPS. Số thứ 46 được ghi nhận là $M_{43112609} = 2^{43112609} - 1$ gồm 12.978.189 chữ số thập phân, tìm thấy ngày 23/8/2008 bởi Edson Smith.
  • Số Fermat: Định nghĩa $F_n = 2^{2^n} + 1$. Liệt kê 5 số Fermat đầu tiên đều là số nguyên tố ($F_0=3, F_1=5, F_2=17, F_3=257, F_4=65537$). Phân tích công thức truy hồi và các tính chất thừa số của $F_n$ với $n \ge 5$ là các hợp số.
  • Kiểm tra Lucas-Lehmer tổng quát: Kiểm tra tính nguyên tố khi biết phân tích $n-1$: nếu tồn tại $a$ thỏa mãn $a^{n-1} \equiv 1 \pmod n$ và $a^{(n-1)/q} \not\equiv 1 \pmod n$ với mọi ước nguyên tố $q$ của $n-1$. Đồ án minh họa với $n = 71$ ($n-1 = 70 = 2 \times 5 \times 7$), chọn $a = 11$, tính lũy thừa theo các ước cho thấy bậc của 11 mod 71 là 70, khẳng định 71 là số nguyên tố. Phân tích hệ mật mã LUC dựa trên dãy Lucas.
  • Các phương pháp kiểm tra số nguyên tố:
    • Phương pháp Trial Division (chia thử): Thuật toán vét cạn chia thử từ 2 đến $n-1$ có độ phức tạp $O(n)$. Thuật toán cải tiến chia thử cho các số đến $\lfloor\sqrt{n}\rfloor$ có chi phí tính toán tối đa là $\sqrt{n}$ phép toán, tương đương độ phức tạp thời gian $O(2^{t/2})$ với $t$ là độ dài bit.
    • Phương pháp Sàng Eratosthenes: Mô tả giải thuật sàng trên mảng từ 2 đến $n$ bằng việc loại trừ các bội số của từng số nguyên tố $p \le \sqrt{n}$. Độ phức tạp thời gian của giải thuật đạt $O(n \log \log n)$. Nhược điểm là yêu cầu lưu trữ toàn bộ mảng trong bộ nhớ, không khả thi với số nguyên lớn.
    • Phương pháp xác suất Fermat: Dựa trên định lý Fermat nhỏ $a^{p-1} \equiv 1 \pmod p$. Trình bày hiện tượng số giả nguyên tố (pseudoprime) cơ sở $a$, lấy ví dụ $n = 341$ là hợp số ($341 = 11 \times 31$) nhưng vẫn thỏa mãn $2^{340} \equiv 1 \pmod{341}$. Vì vậy phép thử Fermat chủ yếu được dùng để sàng lọc phát hiện hợp số.

Chương III: Ứng dụng của số nguyên tố và thử nghiệm chương trình

Chương 3 tập trung vào việc mô tả cấu hình, chức năng và kết quả chạy thử nghiệm của phần mềm xây dựng trong đồ án:

  • Trình bày giao diện và kết quả thực thi chức năng kiểm tra tính nguyên tố của các giá trị trong phạm vi từ 2 đến 5000 (Hình 3.3).
  • Kết quả nhận diện các số nguyên tố Mersenne $2^n - 1$ với các giá trị số mũ $n$ từ 2 đến 11213 (Hình 3.4).
  • Kết quả thực nghiệm liệt kê danh sách toàn bộ các số nguyên tố từ 1 đến 5000 bằng thuật toán sàng Eratosthenes (Hình 3.5).
  • Kết quả thực nghiệm chức năng phân tích thừa số nguyên tố đối với 4 số tự nhiên mẫu gồm: 27, 102, 1001, và 5000 (Hình 3.5b).

Kết quả và đóng góp

Nghiên cứu đạt được các kết quả cụ thể dựa trên số liệu thực tế được ghi nhận trong văn bản:

  • Kết quả tính toán thuật toán lý thuyết:
    • Thực hiện hoàn chỉnh thuật toán Euclid mở rộng cho cặp số $(4864, 3458)$, tìm ra $\gcd = 38$ và nghiệm phương trình vô định $(x, y) = (32, -45)$.
    • Tính toán thành công phần tử nghịch đảo của 3 trong trường $\mathbb{Z}_7$ bằng 5.
    • Áp dụng thuật toán Pollard $p-1$ phân tích thành công số 8051 thành hai nhân tử $97 \times 83$ chỉ sau 3 vòng lặp.
    • Xác lập bảng dữ liệu 46 số nguyên tố Mersenne, trong đó số nhỏ nhất là $M_2 = 3$ (1 chữ số) và số lớn nhất được ghi nhận là $M_{43112609}$ với 12.978.189 chữ số thập phân (được ước tính cần 3.461 trang in với định dạng 75 chữ số/dòng và 50 dòng/trang để biểu diễn).
  • Kết quả thực nghiệm phần mềm:
    • Cài đặt thành công mô-đun sàng số nguyên tố Eratosthenes liệt kê chính xác các số nguyên tố trong khoảng từ 1 đến 5000.
    • Triển khai thuật toán kiểm tra số nguyên tố Mersenne $2^n - 1$ thành công đối với dải số mũ kiểm thử lên tới $n = 11213$.
    • Phân tích chính xác thừa số nguyên tố cho các hợp số kiểm thử (27, 102, 1001, 5000).
  • Giải pháp và đề xuất của tác giả: Đề xuất việc áp dụng thuật toán kiểm tra chuyên biệt Lucas-Lehmer đối với các số có cấu trúc dạng Mersenne $2^n - 1$ thay vì dùng các phương pháp chia thử cổ điển hoặc sàng số học; kết hợp phép thử Fermat để loại nhanh các hợp số ngẫu nhiên trước khi thực hiện các phép kiểm tra xác định tốn kém chi phí tính toán.
  • Đóng góp của đồ án: Hệ thống hóa toàn diện cơ sở toán học số học và lý thuyết độ phức tạp phục vụ ngành an toàn thông tin; cung cấp chương trình thử nghiệm cụ thể hỗ trợ việc nhận biết và phân tích số nguyên tố Mersenne trên máy tính.

Hạn chế và hướng nghiên cứu tiếp

Văn bản nêu rõ các hạn chế kỹ thuật và phạm vi của đề tài:

  • Hạn chế được chỉ ra trong văn bản:
    • Thuật toán kiểm tra số Mersenne có nhược điểm cơ bản về hiệu suất tính toán, tốc độ xử lý chậm và tiêu tốn nhiều tài nguyên bộ nhớ khi kích thước số mũ $n$ tăng cao.
    • Thuật toán sàng Eratosthenes đòi hỏi phải cấp phát bộ nhớ mảng lưu trữ tất cả các số nhỏ hơn $n$, dẫn đến việc không khả thi khi kiểm tra các số nguyên có độ lớn thực sự phục vụ mật mã học.
    • Phương pháp chia thử thông thường có độ phức tạp hàm mũ $O(2^{t/2})$, hoàn toàn không khả thi trên miền khóa mật mã lớn; trong khi phép kiểm tra Fermat vướng phải các số giả nguyên tố (như 341) nên không thể đưa ra khẳng định chắc chắn về tính nguyên tố.
    • Chương trình thử nghiệm mới dừng lại ở việc kiểm thử các số nguyên trong phạm vi nhỏ ($\le 5000$) và dải số mũ Mersenne hạn chế ($n \le 11213$), chưa cập nhật kiểm thử các số nguyên tố Mersenne mới phát hiện sau năm 2008.
  • Hướng nghiên cứu tiếp: Cải tiến cấu trúc dữ liệu và giải thuật xử lý số nguyên lớn để tối ưu hiệu suất bộ nhớ; mở rộng chương trình kiểm thử với các số mũ Mersenne cao hơn và nghiên cứu các phương pháp kiểm tra xác suất tiên tiến hơn nhằm giảm thiểu thời gian tính toán.

Giá trị tham khảo

Đồ án là tài liệu tham khảo phù hợp cho:

  • Đối tượng: Sinh viên ngành Công nghệ thông tin, An toàn thông tin, Khoa học máy tính hoặc Toán tin ứng dụng đang học tập các học phần Mật mã học, An toàn mạng, Lý thuyết số học thuật toán, hoặc đang chuẩn bị thực hiện đồ án tốt nghiệp về mật mã khóa công khai.
  • Nội dung có giá trị tham khảo cao:
    • Quy trình từng bước tính toán chi tiết của thuật toán Euclid mở rộng, thuật toán tìm phần tử nghịch đảo modulo và thuật toán Pollard $p-1$.
    • Mã giải thuật cụ thể (viết theo cấu trúc thủ tục chuẩn) của phương pháp chia thử (Trial Division sơ khai và cải tiến) và sàng Eratosthenes.
    • Bảng tổng hợp chi tiết thông tin lịch sử 46 số nguyên tố Mersenne đầu tiên kèm số chữ số, năm phát hiện và tác giả phát hiện.

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

1. Điều kiện cần và điều kiện đủ để một số Mersenne $M_n = 2^n - 1$ là số nguyên tố là gì? Điều kiện cần để $M_n = 2^n - 1$ là số nguyên tố thì bản thân số mũ $n$ phải là một số nguyên tố (chứng minh dựa trên phép phân tích $2^{pr} - 1$ chia hết cho $2^p - 1$). Tuy nhiên, điều kiện này không phải là điều kiện đủ vì tồn tại các trường hợp $n$ là số nguyên tố nhưng $M_n$ lại là hợp số, điển hình là số $2^{11} - 1 = 2047 = 23 \times 89$.

2. Phép kiểm tra Lucas-Lehmer xác định tính nguyên tố của số Mersenne như thế nào? Với $n > 2$, số Mersenne $M_n = 2^n - 1$ là số nguyên tố khi và chỉ khi $M_n$ chia hết cho phần tử thứ $n-2$ của dãy số Lucas-Lehmer. Dãy này được định nghĩa đệ quy bởi: $S_0 = 4$ và $S_k = S_{k-1}^2 - 2$ với mọi $k > 0$. Điều kiện nguyên tố tương đương với biểu thức đồng dư: $S_{n-2} \equiv 0 \pmod{M_n}$.

3. Tại sao phương pháp chia thử cổ điển không thể dùng để phá vỡ khóa RSA 512 bit? Thuật toán chia thử cổ điển đến $\lfloor\sqrt{n}\rfloor$ đòi hỏi số vòng lặp tối đa là $\sqrt{n}/2$. Với số $n$ có kích thước 512 bit ($n \approx 2^{512}$), $\sqrt{n} \approx 2^{256}$. Nếu một máy tính thực hiện được $10^6$ chỉ lệnh trong mỗi giây, thời gian để hoàn thành tiến trình vét cạn phân tích số $n$ là $T = 2^{255} \text{ giây} \approx 2^{238} \text{ ngày} \approx 2^{230} \text{ năm}$, một khoảng thời gian hoàn toàn không thể thực hiện được trong thực tế.

4. Tại sao thuật toán Fermat không thể khẳng định chắc chắn một số là số nguyên tố? Thuật toán Fermat dựa trên định lý Fermat nhỏ: nếu $p$ là số nguyên tố và $\gcd(a, p) = 1$ thì $a^{p-1} \equiv 1 \pmod p$. Tuy nhiên, chiều ngược lại không đúng do sự tồn tại của các số giả nguyên tố (pseudoprime) cơ sở $a$. Ví dụ số $n = 341$ là hợp số ($341 = 11 \times 31$) nhưng vẫn thỏa mãn phương trình đồng dư $2^{340} \equiv 1 \pmod{341}$. Do đó, phép thử Fermat chỉ có giá trị khẳng định một số là hợp số, không thể khẳng định chắc chắn tính nguyên tố.

5. Số nguyên tố Mersenne lớn nhất được ghi nhận trong bảng dữ liệu của đồ án là số nào? Số nguyên tố Mersenne lớn nhất được ghi nhận trong tài liệu là số thứ 46: $M_{43112609} = 2^{43112609} - 1$. Số này có 12.978.189 chữ số thập phân, được tìm ra vào ngày 23 tháng 8 năm 2008 bởi Edson Smith thông qua dự án tính toán phân tán trên Internet (GIMPS).

Kết luận

Đồ án tốt nghiệp của sinh viên Đỗ Hoàng Anh đã hệ thống hóa toàn diện cơ sở toán học về số nguyên tố, tập trung làm rõ tính chất và các phương pháp nhận biết số nguyên tố Mersenne dạng $2^n - 1$ phục vụ an toàn thông tin. Tác giả đã phân tích sâu các thuật toán từ cổ điển (chia thử, sàng Eratosthenes) đến chuyên biệt (Lucas-Lehmer, Pollard $p-1$) và lý thuyết độ phức tạp tính toán hàm một phía. Kết quả nghiên cứu được kiểm chứng thông qua việc xây dựng chương trình thử nghiệm nhận biết số Mersenne với số mũ lên đến 11213 và phân tích thừa số nguyên tố, cung cấp tài liệu tham khảo có giá trị học thuật cho chuyên ngành Công nghệ thông tin.