Number Theory Algorithms

Thực hiện các thuật toán Lý thuyết số & các phép tính số học cho các số rất lớn

Máy tính:

Cộng hai số nguyên lớn

Trừ hai số nguyên lớn

Nhân hai số nguyên lớn

Chia hai số nguyên lớn

Lũy thừa của một số nguyên lớn

Căn của một số nguyên lớn

Ước chung lớn nhất (ƯCLN) của hai số nguyên lớn

Bội chung nhỏ nhất (ƯCLN) của hai số nguyên lớn

Môđun của hai số nguyên lớn

Môđun nghịch đảo của hai số nguyên lớn

Môđun lũy thừa

Kiểm tra xem một số nguyên lớn có phải là số nguyên tố không

Hàm phi Euler

Giai thừa

Số nguyên tố tiếp theo của một số nguyên lớn

Cặp nguyên tố sinh đôi tiếp theo của một số nguyên lớn

Thuật toán:

Dạng bậc hai đơn giản. Giải tìm x, y sao cho bxy + dx + ey = f với b, d, e, f, x, y thuộc Z.

Thuật toán Euclid. Tính Ước chung lớn nhất (ƯCLN) của hai số a và b.

Thuật toán Euclid mở rộng. Giải tìm x, y sao cho ax + by = gcd(a, b).

Phương trình Diophantine tuyến tính hai ẩn. Giải tìm x, y sao cho ax + by = c.

Đồng dạng tuyến tính trong một ẩn. Giải tìm x, một đồng dạng có dạng ax ≡ b (mod m).

Đồng dạng tuyến tính trong hai ẩn. Giải tìm x, y, một đồng dạng có dạng ax + by ≡ c (mod m).

Thuật toán Tonelli-Shanks. Tính thặng dư bậc hai theo modulo. Giải tìm x, một đồng dạng có dạng x² ≡ a (mod p) với p là số nguyên tố.

Mod thừa số. Tính các thừa số khả dĩ theo modulo của một số cho trước và một modulo. Tìm n ≡ bc (mod a) với (ax + c)(ay + b) = a(axy + bx + cy) + bc = n.

Danh sách số nguyên tố. Danh sách các số nguyên tố được sắp xếp theo cột.

Lưu ý: Hiệu suất dựa trên thiết bị.