Euler Totient Function Sieve
Mô tả nguyên lý
Tính hàm phi Euler cho tất cả các số từ 1 đến N bằng phương pháp sàng.
Cài đặt mẫu (Implementation)
// Cập nhật giá trị phi cho các bội số nguyên tố tương tự sàng Eratosthenes.
Garner Algorithm
Mô tả nguyên lý
Giải hệ thặng dư Trung Hoa với các số module không nguyên tố cùng nhau đôi một.
Cài đặt mẫu (Implementation)
// Sử dụng biểu diễn hệ cơ số hỗn hợp (mixed radix representation) để khôi phục nghiệm.
Linear Diophantine Equation Solver
Mô tả nguyên lý
Giải phương trình nghiệm nguyên tuyến tính dạng $ax + by = c$.
Cài đặt mẫu (Implementation)
// Sử dụng thuật toán Euclid mở rộng để tìm nghiệm cơ sở và sinh họ nghiệm tổng quát.
Mobius Inversion & Sieve
Mô tả nguyên lý
Ứng dụng hàm Möbius và sàng nguyên tố để giải các bài toán đếm ước số và coprime.
Cài đặt mẫu (Implementation)
// Sàng lọc giá trị hàm Möbius kết hợp kỹ thuật chia đoạn (block division).
Pell Equation Solver
Mô tả nguyên lý
Giải phương trình dạng nghiệm nguyên $x^2 - D y^2 = 1$ sử dụng phân số liên tục.
Cài đặt mẫu (Implementation)
// Triển khai khai triển phân số liên tục của căn bậc hai D để tìm nghiệm cơ bản.
Primitive Root Finding
Mô tả nguyên lý
Tìm căn nguyên thủy (primitive root) modulo n phục vụ mã hóa và biến đổi số học.
Cài đặt mẫu (Implementation)
// Kiểm tra tính phân tích các ước số của phi(n) để tìm số sinh thỏa mãn cấp nhân.
Quadratic Reciprocity & Legendre Symbol
Mô tả nguyên lý
Xác định xem một số có phải là thặng dư chính phương modulo p hay không.
Cài đặt mẫu (Implementation)
// Áp dụng định luật tương ấp bậc hai (Law of Quadratic Reciprocity) để đảo ngược ký hiệu.
Tonelli-Shanks Algorithm
Mô tả nguyên lý
Tìm căn bậc hai modulo số nguyên tố ($x^2 \equiv n \pmod p$).
Cài đặt mẫu (Implementation)
// Phân rã p-1 thành $q \cdot 2^s$ và tìm phần tử không chính phương để điều chỉnh nghiệm.