Bỏ qua tới nội dung chính
Toán học

Hướng dẫn học chủ đề

Lý thuyết số

Trung bìnhkhoảng 40 giờ6 bước

Chia hết, đồng dư, định lý Fermat – Euler, căn nguyên thủy, thặng dư bậc hai và ứng dụng vào mật mã RSA.

Bắt đầu học

Bạn sẽ học được gì

  • Dùng thuật toán Euclid mở rộng để tính ước chung lớn nhất, hệ số Bézout và nghịch đảo modulo
  • Chứng minh định lý cơ bản của số học và các kết quả về sự phân bố số nguyên tố ở mức sơ cấp
  • Giải phương trình và hệ phương trình đồng dư bằng định lý phần dư Trung Hoa
  • Áp dụng định lý Fermat nhỏ, định lý Euler và căn nguyên thủy để tính lũy thừa modulo và kiểm tra nguyên tố
  • Giải thích và cài đặt các hệ mật mã Diffie–Hellman và RSA, chỉ ra điểm yếu khi chọn tham số không an toàn
  • Xác định một số có phải thặng dư bậc hai hay không bằng ký hiệu Legendre và luật thuận nghịch bậc hai
  • Khai triển liên phân số của số hữu tỉ và số vô tỉ bậc hai, áp dụng vào phương trình Pell và bài toán tổng hai bình phương

Nên học trước

Giới thiệu

Lý thuyết số nghiên cứu các số nguyên: chia hết, số nguyên tố, đồng dư và các phương trình nghiệm nguyên. Đây là một trong những ngành cổ xưa nhất của toán học — thuật toán Euclid đã hơn hai nghìn năm tuổi — nhưng cũng là một trong những ngành ứng dụng nhiều nhất hôm nay: mỗi lần bạn mở một trang web qua HTTPS, trình duyệt đang thực hiện phép lũy thừa modulo và các thuật toán số học trên những số nguyên hàng trăm chữ số. Chủ đề này tương ứng với MIT 18.781 Theory of Numbers, Berkeley Math 115 và học phần Số học ở các khoa Toán Việt Nam.

Ba trụ cột

  1. Chia hết và số nguyên tố. Thuật toán Euclid (và dạng mở rộng) tính ước chung lớn nhất cùng các hệ số Bézout; từ đó suy ra định lý cơ bản của số học: mọi số nguyên lớn hơn 1 phân tích duy nhất thành tích các số nguyên tố. Có vô hạn số nguyên tố, và định lý số nguyên tố mô tả mật độ của chúng.
  2. Đồng dư. Viết a ≡ b (mod n) nghĩa là n chia hết a − b; các lớp đồng dư tạo thành vành ℤ/nℤ. Các kết quả nền tảng: định lý phần dư Trung Hoa (giải hệ đồng dư với mô-đun nguyên tố cùng nhau), định lý Fermat nhỏ aᵖ⁻¹ ≡ 1 (mod p), định lý Euler với hàm φ, và căn nguyên thủy — nhóm nhân (ℤ/pℤ)* luôn xyclic.
  3. Thặng dư bậc hai. Phương trình x² ≡ a (mod p) có nghiệm hay không? Ký hiệu Legendre, tiêu chuẩn Euler và luật thuận nghịch bậc hai của Gauss cho phép trả lời nhanh — một định lý có hàng trăm chứng minh khác nhau.

Tính toán là một phần của môn học

Khác với nhiều môn toán thuần túy, lý thuyết số hiện đại gắn chặt với thuật toán: lũy thừa nhanh theo modulo, tìm nghịch đảo modulo bằng Euclid mở rộng, kiểm tra nguyên tố xác suất (Miller–Rabin), phân tích số nguyên. Sách chính của lộ trình — Elementary Number Theory: Primes, Congruences, and Secrets của William Stein, đọc miễn phí từ trang tác giả với sự đồng ý của Springer — minh họa mọi khái niệm bằng tính toán trên máy (Sage) và dẫn thẳng tới mật mã: trao đổi khóa Diffie–Hellman, hệ mật mã RSA và cách tấn công RSA khi chọn tham số kém. Hãy cài Python hoặc dùng SageMathCell để thử mọi ví dụ: tự nhìn thấy các quy luật trên số liệu là cách tốt nhất để hiểu vì sao cần chứng minh chúng.

Xa hơn: liên phân số và đường cong elliptic

Nửa sau của sách Stein giới thiệu liên phân số (xấp xỉ số vô tỉ tốt nhất, phương trình Pell, định lý tổng hai bình phương) và đường cong elliptic — đối tượng đứng sau chứng minh định lý Fermat lớn, thuật toán phân tích số nguyên của Lenstra và mật mã đường cong elliptic đang được dùng rộng rãi.

Nên học thế nào

  • Nền tảng: kỹ năng chứng minh (quy nạp, phản chứng) từ học phần nhập môn chứng minh là đủ để bắt đầu. Nếu đã học lý thuyết nhóm, bạn sẽ thấy định lý Fermat – Euler chỉ là hệ quả của định lý Lagrange — nên học nhóm song song hoặc trước là rất có lợi.
  • Luyện tập: làm nhiều bài tập nhỏ tính tay trước khi dùng máy; sách của Niven – Zuckerman – Montgomery là kho bài tập kinh điển. Sách miễn phí của Shoup phù hợp nếu bạn thiên về khoa học máy tính: mọi kết quả đều đi kèm độ phức tạp thuật toán.
  • Tài liệu MIT: bài giảng và bài tập của MIT 18.781 Theory of Numbers có trên MIT OpenCourseWare để đối chiếu.

Lý thuyết số là cửa ngõ tự nhiên dẫn tới mật mã học, lý thuyết mã, đại số máy tính và lý thuyết số đại số.

Giáo trình & sách tham khảo

Xem tất cả trong tab Sách

Giáo trình chính

Miễn phíTrung bìnhTiếng Anh166 trang

Vì sao chọn: Sách của Springer (Undergraduate Texts in Mathematics) được đọc miễn phí hợp pháp từ trang tác giả với sự đồng ý của nhà xuất bản; được Viện Toán học Hoa Kỳ (AIM) giới thiệu. Chọn làm sách chính vì gắn lý thuyết với tính toán và mật mã, ngắn gọn, phủ đúng nội dung lộ trình.

Nên đọc: Chương 1–6 (số nguyên tố, vành ℤ/nℤ, mật mã khóa công khai, luật thuận nghịch bậc hai, liên phân số, đường cong elliptic)

An Introduction to the Theory of Numbers

Ivan Niven, Herbert S. Zuckerman, Hugh L. Montgomery · 1991 · Bản thứ 5

Có phíTrung bìnhTiếng Anh529 trang

Giáo trình kinh điển (Niven – Zuckerman – Montgomery), sách tham khảo của MIT 18.781 Theory of Numbers, với kho bài tập phong phú, trình bày chặt chẽ cả phần đồng dư, thặng dư bậc hai và phương trình Diophantine. Dùng để luyện bài tập và đọc sâu hơn; sách trả phí.

CC BY-NC-NDTrung bìnhTiếng Anh580 trang

Sách của Cambridge University Press, tác giả cho tải miễn phí bản PDF. Phù hợp với người thiên về khoa học máy tính: mọi kết quả đi kèm thuật toán và phân tích độ phức tạp.

Nên đọc: Chương 1–4 (số nguyên, đồng dư, tính toán với số lớn, thuật toán Euclid); Chương 10–12 (kiểm tra nguyên tố, logarit rời rạc, thặng dư bậc hai)

Các bước học

Đăng nhập để đánh dấu các bước đã hoàn thành.

  1. Bước 1: Chia hết, số nguyên tố và thuật toán Euclid

    khoảng 7 giờ

    Học phép chia có dư, ước chung lớn nhất, thuật toán Euclid mở rộng, định lý cơ bản của số học và sự phân bố số nguyên tố (vô hạn số nguyên tố, sàng Eratosthenes, định lý số nguyên tố). Cài đặt thuật toán Euclid mở rộng và sàng Eratosthenes, đếm số nguyên tố nhỏ hơn 10⁶ và so sánh với x/ln x.

  2. Bước 2: Đồng dư, định lý phần dư Trung Hoa, Fermat và Euler

    khoảng 8 giờ

    Học đồng dư, vành ℤ/nℤ, phương trình đồng dư tuyến tính, định lý phần dư Trung Hoa, hàm Euler, định lý Fermat nhỏ, định lý Euler và lũy thừa nhanh theo modulo. Giải bài toán “Hàn Tín điểm binh” (hệ ba đồng dư) bằng tay và tính 3¹⁰⁰⁰ mod 101 không cần máy.

  3. Bước 3: Căn nguyên thủy và kiểm tra nguyên tố

    khoảng 6 giờ

    Học cấu trúc nhóm nhân (ℤ/pℤ)*, căn nguyên thủy, logarit rời rạc, phép thử Fermat, số Carmichael và thuật toán Miller–Rabin. Cài đặt Miller–Rabin, kiểm tra với số Carmichael 561 và tìm căn nguyên thủy nhỏ nhất modulo các số nguyên tố dưới 100.

  4. Bước 4: Mật mã khóa công khai: Diffie–Hellman và RSA

    khoảng 6 giờ

    Học trao đổi khóa Diffie–Hellman, hệ mật mã RSA, chữ ký số và các tấn công RSA khi tham số yếu. Tự sinh khóa RSA với hai số nguyên tố khoảng 20 chữ số, mã hóa rồi giải mã một thông điệp, sau đó phá khóa khi p và q quá gần nhau bằng phương pháp phân tích Fermat. Đọc thêm tài liệu trên OpenER về mật mã học ứng dụng để thấy RSA được dùng ra sao trong bảo mật phần mềm.

  5. Bước 5: Thặng dư bậc hai và luật thuận nghịch bậc hai

    khoảng 7 giờ

    Học thặng dư bậc hai, ký hiệu Legendre và Jacobi, tiêu chuẩn Euler, bổ đề Gauss, luật thuận nghịch bậc hai và thuật toán tìm căn bậc hai modulo p. Dùng luật thuận nghịch tính ký hiệu Legendre (219/383) bằng tay rồi kiểm tra lại bằng máy.

  6. Bước 6: Liên phân số, tổng hai bình phương và đường cong elliptic

    khoảng 6 giờ

    Học liên phân số hữu hạn và vô hạn, số vô tỉ bậc hai, phương trình Pell, định lý tổng hai bình phương; nhóm điểm trên đường cong elliptic và ứng dụng trong phân tích số nguyên và mật mã. Tìm nghiệm nhỏ nhất của x² − 13y² = 1 bằng liên phân số của √13 và cộng vài điểm trên một đường cong elliptic modulo 17. Bài giảng MIT 18.781 trên MIT OpenCourseWare là nguồn đối chiếu tốt cho bước này.

Khái niệm chính

Thuật toán Euclid mở rộng
Tính ƯCLN(a, b) cùng các số nguyên x, y với ax + by = ƯCLN(a, b); dùng để tìm nghịch đảo modulo trong thời gian đa thức theo số chữ số.
Định lý cơ bản của số học
Mọi số nguyên lớn hơn 1 phân tích được thành tích các số nguyên tố, và phân tích đó là duy nhất nếu không kể thứ tự.
Đồng dư và vành ℤ/nℤ
a ≡ b (mod n) khi n chia hết a − b; các lớp đồng dư modulo n tạo thành vành ℤ/nℤ, với nhóm nhân (ℤ/nℤ)* gồm các lớp nguyên tố cùng nhau với n.
Định lý phần dư Trung Hoa
Hệ đồng dư với các mô-đun đôi một nguyên tố cùng nhau luôn có nghiệm duy nhất modulo tích các mô-đun.
Định lý Fermat nhỏ và định lý Euler
aᵖ⁻¹ ≡ 1 (mod p) khi p nguyên tố không chia a; tổng quát, a^φ(n) ≡ 1 (mod n) khi ƯCLN(a, n) = 1, với φ là hàm Euler.
Căn nguyên thủy (Primitive root)
Phần tử sinh của nhóm nhân (ℤ/pℤ)*; luôn tồn tại với p nguyên tố, là nền của bài toán logarit rời rạc.
Kiểm tra nguyên tố xác suất
Các thuật toán như Miller–Rabin kiểm tra một số lớn có là số nguyên tố với xác suất sai nhỏ tùy ý, nhanh hơn nhiều so với phân tích thừa số.
Hệ mật mã RSA
Khóa công khai (n, e) với n = pq; mã hóa m ↦ mᵉ mod n, giải mã bằng d với ed ≡ 1 (mod φ(n)); an toàn dựa trên độ khó của phân tích n.
Thặng dư bậc hai và ký hiệu Legendre
a là thặng dư bậc hai modulo p nếu x² ≡ a (mod p) có nghiệm; ký hiệu Legendre (a/p) bằng 1, −1 hoặc 0 ghi nhận điều đó, và (a/p) ≡ a^((p−1)/2) (mod p) theo tiêu chuẩn Euler.
Luật thuận nghịch bậc hai
Với p, q là hai số nguyên tố lẻ khác nhau, (p/q)(q/p) = (−1)^((p−1)(q−1)/4); cho phép tính ký hiệu Legendre nhanh như thuật toán Euclid.
Liên phân số
Biểu diễn số thực bằng dãy phân số lồng nhau; các giản phân cho xấp xỉ hữu tỉ tốt nhất và dùng để giải phương trình Pell x² − dy² = 1.
Đường cong elliptic
Đường cong y² = x³ + ax + b với 4a³ + 27b² ≠ 0; các điểm hữu tỉ hoặc modulo p, thêm điểm vô cực O, tạo thành một nhóm abel; dùng trong phân tích số nguyên (Lenstra) và mật mã ECC.

Học xong để làm gì

  • Mật mã khóa công khai: RSA, trao đổi khóa Diffie–Hellman, chữ ký số và mật mã đường cong elliptic trong HTTPS, ví điện tử, blockchain
  • Sinh số giả ngẫu nhiên và hàm băm dựa trên số học modulo
  • Mã kiểm tra lỗi: số ISBN, số tài khoản ngân hàng (IBAN), mã vạch dùng đồng dư để phát hiện lỗi nhập liệu
  • Thuật toán số học máy tính: nhân số lớn, tính toán theo modulo nhiều số nguyên tố (định lý phần dư Trung Hoa) trong đại số máy tính
  • Toán thi Olympic: số học là một trong bốn mảng chính của các kỳ thi học sinh giỏi và IMO

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

Lý thuyết số ở đây khác gì số học phổ thông chuyên?

Nhiều kết quả trùng nhau (đồng dư, Fermat, Euler), nhưng ở đây trọng tâm là chứng minh có hệ thống, cấu trúc nhóm – vành phía sau và thuật toán hiệu quả, dẫn tới mật mã và đường cong elliptic.

Có cần học lý thuyết nhóm trước không?

Không bắt buộc, chỉ cần kỹ năng chứng minh. Nhưng học nhóm trước hoặc song song giúp nhiều định lý (Fermat, Euler, căn nguyên thủy) trở thành hệ quả tự nhiên của định lý Lagrange.

Tại sao sách chính lại dùng máy tính nhiều như vậy?

Vì lý thuyết số hiện đại gắn với thuật toán: tính toán giúp phát hiện quy luật, kiểm tra giả thuyết và hiểu vì sao RSA an toàn khi số đủ lớn nhưng yếu khi chọn tham số kém.

Học xong có đủ để làm mật mã học không?

Đủ nền toán cho mật mã khóa công khai cơ bản; để làm mật mã thực tế cần thêm trường hữu hạn, xác suất, độ phức tạp tính toán và các chuẩn an toàn (padding, sinh khóa).

Chọn nguồn tự học

Chỉ cần kỹ năng chứng minh cơ bản; chọn nguồn có phần tính toán và mật mã để vừa học định lý vừa thử nghiệm trên máy (Python, SageMath).