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

Số nguyên tố đóng vai trò nền tảng trong lĩnh vực an toàn và bảo mật thông tin hiện đại. Chúng là thành phần cốt lõi trong việc thiết lập hạ tầng khóa công khai (PKI), xây dựng các hệ mật mã bất đối xứng tiêu biểu như RSA, ElGamal, cũng như các giao thức chữ ký số và cơ chế xác thực điện tử. Trong kỹ thuật mật mã, độ an toàn của hệ thống phụ thuộc chặt chẽ vào độ lớn của các số nguyên tố được sử dụng; số nguyên tố càng lớn thì độ phức tạp tính toán để giải mã hoặc phá khóa càng cao. Tuy nhiên, việc xác định một số nguyên dương $N$ có kích thước lớn là số nguyên tố hay hợp số luôn là một bài toán tính toán phức tạp. Ngoại trừ số 2, mọi số nguyên tố đều là số lẻ, song điều ngược lại không đúng vì có rất nhiều số lẻ là hợp số (chẳng hạn 9, 15, hay $2047 = 23 \times 89$). Do đó, việc nghiên cứu các thuật toán hiệu quả nhằm nhận biết và kiểm tra tính nguyên tố—đặc biệt là với các họ số nguyên tố có cấu trúc đặc biệt—trở thành một yêu cầu thiết yếu trong khoa học máy tính và mật mã học.

Khóa luận tốt nghiệp của sinh viên Đỗ Hoàng Anh (ngành Công nghệ thông tin, Trường Đại học Quản lý và Công nghệ Hải Phòng, dưới sự hướng dẫn của TS. Hồ Văn Canh) tập trung giải quyết vấn đề nhận biết số nguyên tố với đối tượng trọng tâm là các số có dạng $2^n - 1$ (số Mersenne). Đồ án xác định rõ 3 nhiệm vụ nghiên cứu chính:

  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.

Về đối tượng và phạm vi, đề tài tập trung vào lý thuyết số học modulo, cấu trúc đại số trừu tượng (đặc biệt là nhóm cyclic), lý thuyết độ phức tạp tính toán và các giải thuật kiểm tra tính nguyên tố (chia thử, sàng Eratosthenes, kiểm tra xác suất Fermat, kiểm tra Lucas-Lehmer). Phạm vi thực nghiệm của đồ án được triển khai trên máy tính cá nhân, thực hiện kiểm tra và liệt kê số nguyên tố trong phạm vi từ 1 đến 5000 đối với số tự nhiên thông thường và kiểm tra tính nguyên tố của các số Mersenne với số mũ $n$ từ 2 đến 11213. Quá trình nghiên cứu và thực tập tốt nghiệp được thực hiện tại Công ty Cổ phần Đầu tư Tài chính và Công nghệ Datatech trong thời gian từ tháng 4 năm 2023 đến tháng 6 năm 2023.

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

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

  • Số học và đại số trừu tượng: Đồ án sử dụng các khái niệm về quan hệ chia hết ($b | a$), ước số chung lớn nhất ($\gcd$), bội số chung nhỏ nhất ($\text{lcm}$), quan hệ đồng dư modulo và các tính chất đại số trên vành số nguyên. Tác giả vận dụng cấu trúc nhóm $(G, )$, nhóm con, nhóm cyclic, cấp của nhóm và cấp của phần tử. Trong đó, tập thặng dư thu gọn $\mathbb{Z}_n^$ cùng hàm số Euler $\phi(n)$, Định lý Lagrange, Định lý Euler tổng quát ($b^{\phi(n)} \equiv 1 \pmod n$) và Định lý nhỏ Fermat ($b^{p-1} \equiv 1 \pmod p$) là cơ sở trực tiếp cho các phép thử tính nguyên tố và bài toán logarit rời rạc ($x = \log_g y \pmod p$).
  • Lý thuyết độ phức tạp tính toán: Khóa luận áp dụng mô hình máy Turing tất định và không tất định để định nghĩa các lớp độ phức tạp: lớp P (các bài toán giải được bằng thuật toán đơn định trong thời gian đa thức) và lớp NP (các bài toán giải được bằng thuật toán không đơn định trong thời gian đa thức), quan hệ quy dẫn đa thức và lớp bài toán NP-đầy đủ (như SAT, CLIQUE, KNAPSACK). Trên cơ sở này, đồ án xác lập cơ chế bảo mật thông qua khái niệm hàm một phía (one-way function) và hàm cửa sập một phía (trapdoor one-way function).
  • Phương pháp nghiên cứu: Tác giả sử dụng phương pháp phân tích - tổng hợp lý thuyết từ các giáo trình chuyên khảo trong và ngoài nước về mật mã và lý thuyết số tính toán; phương pháp chứng minh toán học quy nạp và phản chứng; phương pháp phân tích độ phức tạp thuật toán (ký pháp $\mathcal{O}$); và phương pháp thực nghiệm lập trình nhằm mô phỏng, đo lường kết quả thực thi của các giải thuật trên các tập dữ liệu số cụ thể.
  • Nguồn dữ liệu: Dữ liệu nghiên cứu bao gồm các công thức giải tích toán học, các mốc dữ liệu lịch sử về 46 số nguyên tố Mersenne được công bố bởi dự án tính toán phân tán GIMPS (Great Internet Mersenne Prime Search) tính đến năm 2008, cùng dữ liệu thử nghiệm số học được sinh trực tiếp trong chương trình máy tính.

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

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

Chương 1 thiết lập toàn bộ nền tảng toán học và độ phức tạp tính toán phục vụ cho việc nghiên cứu thuật toán nhận biết số nguyên tố:

  • Số học và cấu trúc đại số: Tác giả hệ thống hóa các định nghĩa về quan hệ chia hết, ước chung lớn nhất, đồng dư thức modulo và các tính chất nhân/cộng modulo. Phần đại số trình bày chi tiết về cấu trúc nhóm, nhóm con, và đặc biệt là nhóm cyclic sinh bởi phần tử nguyên thủy $g$. Đồ án chứng minh định lý Lagrange (cấp của phần tử là ước của cấp của nhóm), xác định tính chất của nhóm $\mathbb{Z}_n^$ và nhóm cyclic $\mathbb{Z}_p^$ (khi $p$ nguyên tố), đồng thời giải thích bài toán logarit rời rạc.
  • Các thuật toán số học nền tảng:
    • Thuật toán Euclid và Euclid mở rộng: Trình bày giải thuật chia lấy dư liên tiếp để tìm $\gcd(a, b)$. Tác giả minh họa quá trình tính toán tìm $\gcd(4864, 3458) = 38$ và áp dụng thuật toán Euclid mở rộng để giải phương trình vô định $4864x + 3458y = 38$, cho ra nghiệm nguyên $(x, y) = (32, -45)$.
    • Thuật toán tính phần tử nghịch đảo modulo: Sử dụng thuật toán Euclid mở rộng để tính $a^{-1} \pmod n$ với điều kiện $\gcd(a, n) = 1$. Ví dụ tính toán cụ thể tìm được nghịch đảo của 3 trong $\mathbb{Z}_7$ là 5 (do $3 \times 5 \equiv 15 \equiv 1 \pmod 7$).
    • Các thuật toán phân tích thừa số nguyên tố: Khái quát các giải thuật hiện đại như sàng bậc hai (Quadratic Sieve), đường cong Elliptic của Lenstra và sàng trường số. Đồ án trình bày chi tiết thuật toán phân tích $(p - 1)$ của Pollard (1975) dựa trên hàm giả ngẫu nhiên $f(x) = x^2 + c \pmod n$; với dữ liệu thực nghiệm $n = 8051$ và $f(x) = x^2 + 1 \pmod{8051}$, thuật toán tìm ra ước số không tầm thường là 97 và thương số là 83.
    • Phân tích độ phức tạp của phương pháp cổ điển: Đồ án phân tích thuật toán chia thử tìm ước lẻ đến $\sqrt{n}$ với số vòng lặp $\mathcal{O}(\sqrt{n}/2)$. Tác giả tính toán định lượng: nếu số $n$ có kích thước 512 bit ($n \approx 2^{512}$), trên một 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 \approx 2^{255}$ giây, tương đương hơn $2^{230}$ năm (với 1 năm $\approx 2^{25}$ giây), chứng minh việc phân tích khóa bằng phương pháp cổ điển là hoàn toàn bất khả thi.
  • Lý thuyết độ phức tạp và mật mã học: Trình bày định nghĩa hình thức về bài toán quyết định, lớp P, lớp NP, và các bài toán NP-đầy đủ. Tác giả phân tích mô hình hàm một phía (như phép lũy thừa modulo $y = a^x \pmod p$) và hàm cửa sập một phía (như hàm mã hóa RSA $y = x^a \pmod n$, trong đó việc biết các thừa số nguyên tố $p, q$ đóng vai trò là "cửa sập" $z$ cho phép tính $\phi(n) = (p-1)(q-1)$ để giải mã dễ dàng).

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

Chương 2 là phần trọng tâm về mặt lý thuyết của khóa luận, đi sâu vào các dạng số nguyên tố đặc thù và các thuật toán kiểm tra tính nguyên tố:

  • Tính chất và sự phân bố số nguyên tố: Trình bày các định lý cơ bản: ước tự nhiên nhỏ nhất khác 1 là số nguyên tố; ước dương bé nhất khác 1 của hợp số $a$ không vượt quá $\sqrt{a}$; chứng minh phản chứng tính vô hạn của tập hợp số nguyên tố; định lý phân tích duy nhất ra thừa số nguyên tố. Đồ án giới thiệu Định lý số nguyên tố (Prime Number Theorem): $\lim_{n \to \infty} \frac{\pi(n)}{n / \ln n} = 1$. Dựa vào đó, tác giả tính toán trong khoảng từ 5 tỉ đến 6 tỉ có khoảng $4{,}3%$ số là số nguyên tố, nghĩa là trung bình cứ 23 số ngẫu nhiên thì có 1 số nguyên tố (nếu chỉ xét số lẻ thì tỉ lệ cần kiểm tra giảm một nửa).
  • Số nguyên tố dạng đặc biệt:
    • Số nguyên tố Mersenne ($M_n = 2^n - 1$): Đồ án chứng minh định lý: Điều kiện cần để $M_n$ là số nguyên tố là bản thân $n$ phải là số nguyên tố, dựa trên hằng đẳng thức $2^{ab} - 1 = (2^a - 1)(1 + 2^a + 2^{2a} + \dots + 2^{(b-1)a})$. Tác giả chỉ rõ chiều ngược lại không đúng thông qua phản ví dụ $M_{11} = 2^{11} - 1 = 2047 = 23 \times 89$ (là hợp số mặc dù 11 là số nguyên tố). Khóa luận trình bày mối quan hệ giữa số Mersenne và số hoàn thiện chẵn thông qua định lý Euclid-Euler: số $M(M+1)/2$ là số hoàn thiện khi $M$ là số nguyên tố Mersenne.
    • Lịch sử khám phá số Mersenne: Khảo sát các mốc tìm kiếm từ thời Hy Lạp cổ đại ($M_2, M_3, M_5, M_7$), Cataldi năm 1588 ($M_{17}, M_{19}$), Euler năm 1750 ($M_{31}$), Lucas năm 1876 ($M_{127}$), đến bước ngoặt sử dụng máy tính điện tử SWAC năm 1952 của Lehmer và Robinson ($M_{521}, M_{607}$), và mạng lưới tính toán phân tán GIMPS. Bảng dưới đây tổng hợp các mốc số nguyên tố Mersenne tiêu biểu được trích xuất từ văn bản:
Thứ tự Số mũ $n$ Số nguyên tố Mersenne $M_n$ Số chữ số trong $M_n$ Năm tìm ra Người / Dự án tìm ra
1 2 3 1 Cổ đại Hy Lạp cổ đại
2 3 7 1 Cổ đại Hy Lạp cổ đại
3 5 31 2 Cổ đại Hy Lạp cổ đại
4 7 127 3 Cổ đại Hy Lạp cổ đại
5 13 8191 4 1456 Khuyết danh
6 17 131071 6 1588 Cataldi
7 19 524287 6 1588 Cataldi
8 31 2147483647 10 1750 Euler
12 127 $1{,}7014 \times 10^{38}$ 39 1876 Lucas
13 521 $6{,}8647 \times 10^{156}$ 157 1952 Robinson (máy SWAC)
19 4253 $1{,}9079 \times 10^{1280}$ 1281 1961 Hurwitz (số titanic)
27 44497 $8{,}5450 \times 10^{13394}$ 13395 1979 Nelson & Slowinski (gigantic)
46* 43112609 $3{,}1647 \times 10^{12978188}$ 12978189 2008 GIMPS / Edson Smith
  • Thuật toán Lucas-Lehmer: Trình bày phép thử chuyên biệt cho số Mersenne: Với $n > 2$, số $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 định nghĩa truy hồi: $S_0 = 4$ và $S_k = S_{k-1}^2 - 2$. Đồ án cũng giới thiệu phép thử Lucas-Lehmer tổng quát (minh họa kiểm tra số 71 với cơ sở $a=11$) và ứng dụng của dãy Lucas trong hệ mật mã LUC (LUCELG, LUCDIF, LUCRSA).
  • Số nguyên tố Fermat: Giới thiệu số Fermat $F_n = 2^{2^n} + 1$. Phỏng đoán của Fermat về tính nguyên tố của mọi $F_n$ chỉ đúng với $n \in {0, 1, 2, 3, 4}$; mọi số Fermat được kiểm tra từ $n=5$ đến 32 đều là hợp số (được chứng minh bằng phương pháp chia thử và phép thử Pépin).
  • Các phương pháp kiểm tra tính nguyên tố thông dụng:
    • Phương pháp cổ điển: Thuật toán Trial Division cơ bản duyệt từ 2 đến $n-1$ có độ phức tạp $\mathcal{O}(n)$; thuật toán cải tiến chỉ duyệt các ước đến $\lfloor\sqrt{n}\rfloor$ có độ phức tạp $\mathcal{O}(\sqrt{n}) = \mathcal{O}(2^{t/2})$ với $t = \log_2 n$. Thuật toán Sàng Eratosthenes loại trừ các bội số của số nguyên tố với chi phí thời gian $\mathcal{O}(n \log \log n)$, nhưng bị hạn chế lớn về bộ nhớ khi số $n$ tăng cao.
    • Phương pháp xác suất: Thuật toán Fermat dựa trên đẳng thức $a^{n-1} \equiv 1 \pmod n$. Đồ án chỉ rõ thuật toán này không tuyệt đối chính xác vì tồn tại các số giả nguyên tố (chẳng hạn số $n = 341$ là hợp số vì $341 = 11 \times 31$ nhưng vẫn thỏa mãn $2^{340} \equiv 1 \pmod{341}$). Do đó, kiểm tra Fermat chủ yếu có giá trị khẳng định một số là hợp số.

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

Chương 3 mô tả việc hiện thực hóa các giải thuật lý thuyết thành các chức năng tính toán trên máy tính:

  • Cấu hình và cài đặt hệ thống: Chương trình được xây dựng nhằm mục đích thử nghiệm, kiểm chứng các thuật toán đã nghiên cứu trong Chương 1 và Chương 2.
  • Các chức năng chính đã triển khai:
    1. Kiểm tra số nguyên tố đơn lẻ: Thử nghiệm kiểm tra tính nguyên tố của các số trong dải từ 2 đến 5000 (Hình 3.3).
    2. Kiểm tra số nguyên tố dạng Mersenne ($2^n - 1$): Cài đặt chương trình kiểm tra tính nguyên tố của số Mersenne với dải số mũ $n$ từ 2 đến 11213 (Hình 3.4).
    3. Liệt kê số nguyên tố: Cài đặt thuật toán sàng nhằm liệt kê danh sách toàn bộ các số nguyên tố trong phạm vi từ 1 đến 5000 (Hình 3.5).
    4. Phân tích thừa số nguyên tố: Chương trình thực hiện phân tích các hợp số đầu vào thành tích các thừa số nguyên tố, với các trường hợp thử nghiệm cụ thể được báo cáo là 27, 102, 1001 và 5000 (Hình 3.5/3.6).

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

Khóa luận đạt được các kết quả cụ thể sau:

  • Hệ thống hóa lý thuyết số và độ phức tạp: Đã tổng hợp toàn diện các cơ sở lý thuyết số học, đại số trừu tượng và lý thuyết độ phức tạp tính toán gắn liền với mật mã học, phân tích rõ cơ chế hoạt động của hàm một phía và hàm cửa sập trong hệ mật mã khóa công khai.
  • Tổng hợp dữ liệu lịch sử về số nguyên tố Mersenne: Khóa luận xây dựng bảng thống kê chi tiết 46 số nguyên tố Mersenne được nhân loại tìm thấy từ thời cổ đại đến tháng 9 năm 2008, trong đó số lớn nhất tại thời điểm tài liệu ghi nhận là $M_{43112609}$ chứa 12.978.189 chữ số thập phân (cần tới 3.461 trang giấy để in hết các chữ số).
  • Định lượng chi phí tính toán của các thuật toán: Chứng minh toán học về sự bất khả thi của thuật toán chia thử cổ điển khi phá khóa 512 bit (đòi hỏi $2^{230}$ năm tính toán); so sánh hiệu năng giữa thuật toán Trial Division cải tiến ($\mathcal{O}(\sqrt{n})$), Sàng Eratosthenes ($\mathcal{O}(n \log \log n)$), và thuật toán phân tích thừa số $(p-1)$ của Pollard.
  • Xây dựng chương trình thử nghiệm: Cài đặt hoàn chỉnh chương trình với 4 nhóm chức năng thực tế: kiểm tra số nguyên tố từ 2 đến 5000; kiểm tra số Mersenne dạng $2^n - 1$ với $n$ lên tới 11213; liệt kê số nguyên tố từ 1 đến 5000; và phân tích thừa số nguyên tố cho các số tự nhiên (27, 102, 1001, 5000).
  • Đề xuất giải pháp: Khẳng định việc sử dụng thuật toán Lucas-Lehmer là giải pháp tối ưu và chính xác nhất để nhận biết các số nguyên tố dạng $2^n - 1$, thay thế hoàn toàn các phương pháp chia thử vét cạn hay kiểm tra xác suất dễ mắc lỗi số giả nguyên tố.

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

  • Hạn chế được văn bản đề cập:
    • Về mặt thuật toán: Thuật toán kiểm tra số Mersenne và Sàng Eratosthenes có nhược điểm cơ bản về hiệu suất khi số cần kiểm tra tăng lên quá lớn (tốc độ xử lý chậm và đòi hỏi dung lượng bộ nhớ lớn).
    • Về mặt thử nghiệm: Chương trình mới chỉ dừng lại ở việc kiểm thử trên các phạm vi dữ liệu nhỏ (liệt kê và kiểm tra đến 5000; kiểm tra số Mersenne với số mũ $n$ đến 11213 theo danh mục đã biết); chưa cài đặt các giải thuật phân tích hiện đại cho số cực lớn như thuật toán đường cong Elliptic hay sàng trường số.
  • Hướng nghiên cứu tiếp:
    • Nghiên cứu tối ưu hóa giải thuật và cấu trúc dữ liệu nhằm tiết kiệm bộ nhớ khi thực hiện kiểm tra các số Mersenne có kích thước lớn hơn.
    • Mở rộng chương trình để cài đặt các thuật toán kiểm tra tính nguyên tố hiện đại khác (như thuật toán ngẫu nhiên Miller-Rabin hoặc thuật toán kiểm tra tất định trong thời gian đa thức).
    • Nghiên cứu mô hình tính toán phân tán trên mạng Internet (tương tự kiến trúc của dự án GIMPS) để nâng cao năng lực tính toán tìm kiếm số nguyên tố lớn.

Giá trị tham khảo

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

  • Đối tượng hưởng lợi: Sinh viên, học viên chuyên ngành Công nghệ thông tin, An toàn thông tin, Mật mã học và Toán tin ứng dụng đang học tập hoặc làm đồ án tốt nghiệp về lý thuyết số và bảo mật dữ liệu.
  • Các nội dung có giá trị tham khảo cao:
    • Phần trình bày súc tích, hệ thống về các cấu trúc đại số trừu tượng (nhóm cyclic, vành thặng dư $\mathbb{Z}_n^*$, hàm Euler) và mô hình hàm cửa sập ứng dụng trong mật mã học tại Chương 1.
    • Các giải thuật số học có kèm ví dụ tính toán từng bước chi tiết: 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 phân tích $(p-1)$ của Pollard.
    • Chuyên đề nghiên cứu chuyên sâu về số nguyên tố Mersenne, phương pháp kiểm tra Lucas-Lehmer và bảng tư liệu 46 số nguyên tố Mersenne tại Chương 2.

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

1. Tại sao điều kiện số mũ $n$ là số nguyên tố chỉ là điều kiện cần chứ chưa phải điều kiện đủ để số Mersenne $M_n = 2^n - 1$ là số nguyên tố? Theo đẳng thức đại số $2^{ab} - 1 = (2^a - 1)(1 + 2^a + 2^{2a} + \dots + 2^{(b-1)a})$, nếu số mũ $n$ là hợp số ($n = ab$ với $a, b > 1$) thì $M_n$ luôn chia hết cho $2^a - 1$, do đó $M_n$ bắt buộc phải là hợp số. Vì vậy, $n$ bắt buộc phải là số nguyên tố để $M_n$ có cơ hội là số nguyên tố. Tuy nhiên, chiều ngược lại không đúng vì khi $n$ là số nguyên tố thì $M_n$ vẫn có thể là hợp số; ví dụ cụ thể trong đồ án là $n = 11$ (11 là số nguyên tố), nhưng $M_{11} = 2^{11} - 1 = 2047 = 23 \times 89$ (là hợp số).

2. Thuật toán kiểm tra Lucas-Lehmer đối với số nguyên tố Mersenne được thực hiện dựa trên quy tắc dãy số nào? Thuật toán Lucas-Lehmer xác định tính nguyên tố của số Mersenne $M_n = 2^n - 1$ (với $n > 2$) dựa trên việc tính toán một dãy số truy hồi bắt đầu từ $S_0 = 4$ và công thức lặp $S_k = S_{k-1}^2 - 2$ (với $k > 0$). Số $M_n$ 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ố này, nghĩa là $S_{n-2} \equiv 0 \pmod{M_n}$.

3. Tại sao không thể sử dụng thuật toán chia thử cổ điển để tìm các thừa số nguyên tố của một khóa bí mật 512 bit? Thuật toán chia thử cổ điển kiểm tra các ước số lẻ từ 3 đến $\sqrt{n}$ với số bước lặp là $\mathcal{O}(\sqrt{n}/2)$. Khi số $n$ có kích thước 512 bit ($n \approx 2^{512}$), vòng lặp phải thực hiện xấp xỉ $2^{255}$ phép toán. Ngay cả khi sử dụng máy tính có tốc độ thực thi $10^6$ chỉ lệnh mỗi giây, thời gian hoàn thành phép toán tính toán được lên tới khoảng $2^{230}$ năm (trong khi 1 năm chỉ có khoảng $2^{25}$ giây), khiến phương pháp này hoàn toàn bất khả thi trong thực tế.

4. Vì 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ý nhỏ Fermat: nếu $p$ là số nguyên tố thì $a^{p-1} \equiv 1 \pmod p$ với mọi $\gcd(a, p) = 1$. Tuy nhiên, mệnh đề đảo không hoàn toàn đúng do sự tồn tại của các số giả nguyên tố (pseudoprimes)—tức là các hợp số $n$ nhưng vẫn thỏa mãn đẳng thức $a^{n-1} \equiv 1 \pmod n$ với một cơ số $a$ nhất định. Ví dụ được đồ án nêu ra là số $n = 341$ ($341 = 11 \times 31$ là hợp số), nhưng vẫn thỏa mãn $2^{340} \equiv 1 \pmod{341}$. Do đó, phép thử Fermat chỉ có thể khẳng định chắc chắn một số là hợp số khi đẳng thức không thỏa mãn, chứ không thể dùng để kết luận một số là số nguyên tố.

5. Thuật toán Pollard $(p-1)$ phân tích số $n = 8051$ ra thừa số nguyên tố như thế nào trong ví dụ của đồ án? Thuật toán Pollard $(p-1)$ sử dụng hàm sinh số giả ngẫu nhiên $f(x) = x^2 + 1 \pmod{8051}$ với các giá trị khởi tạo $x_0 = 2, y_0 = 2$. Tại mỗi bước lặp, thuật toán tính $x \leftarrow f(x)$, $y \leftarrow f(f(y))$ và tìm ước số bằng công thức $d = \gcd(|x - y|, n)$. Tại bước lặp thứ 3, giá trị thu được là $x_3 = 677$ và $y_3 = 871$; khi đó $\gcd(|677 - 871|, 8051) = \gcd(194, 8051) = 97$. Số 97 là một ước số không tầm thường của 8051, và thừa số còn lại được tìm ra thông qua phép chia $8051 / 97 = 83$.

Kết luận

Đồ án tốt nghiệp của sinh viên Đỗ Hoàng Anh đã nghiên cứu toàn diện cơ sở toán học và độ phức tạp tính toán của bài toán nhận biết số nguyên tố trong an toàn thông tin, tập trung chuyên sâu vào họ số nguyên tố Mersenne có dạng $2^n - 1$. Tác giả đã làm rõ các tính chất đại số, phân tích hiệu năng của các giải thuật kiểm tra tính nguyên tố kinh điển và hệ thống hóa lịch sử khám phá 46 số nguyên tố Mersenne từ thời cổ đại đến hiện đại. Kết quả thử nghiệm chương trình đã hiện thực hóa thành công việc kiểm tra tính nguyên tố, xác nhận số Mersenne và phân tích hợp số ra thừa số nguyên tố, cung cấp nguồn tư liệu học thuật hữu ích cho sinh viên và người nghiên cứu trong lĩnh vực công nghệ thông tin và mật mã học.