Lý thuyết số

Danh sách đầy đủ các thuật toán trong nhóm (Tổng: 8)

Lý thuyết số

Euler Totient Function Sieve

Thời gian (Time) O(N log log N)
Không gian (Space) O(N)

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.
Lý thuyết số

Garner Algorithm

Thời gian (Time) O(N^2)
Không gian (Space) O(N)

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.
Lý thuyết số

Linear Diophantine Equation Solver

Thời gian (Time) O(log min(a, b))
Không gian (Space) O(1)

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.
Lý thuyết số

Mobius Inversion & Sieve

Thời gian (Time) O(N log log N)
Không gian (Space) O(N)

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).
Lý thuyết số

Pell Equation Solver

Thời gian (Time) O(sqrt(D))
Không gian (Space) O(1)

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.
Lý thuyết số

Primitive Root Finding

Thời gian (Time) O(sqrt(N) * log N)
Không gian (Space) O(1)

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.
Lý thuyết số

Quadratic Reciprocity & Legendre Symbol

Thời gian (Time) O(log P)
Không gian (Space) O(1)

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.
Lý thuyết số

Tonelli-Shanks Algorithm

Thời gian (Time) O(log^2 P)
Không gian (Space) O(1)

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.