Lý thuyết số / Mật mã
Lenstra Elliptic Curve Factorization (ECM)
ID: #149
Xem trên trang chủ
Thời gian (Time)
Tùy thuộc chữ số
Không gian (Space)
O(1)
Mô tả nguyên lý
Phân tích thừa số nguyên tố dựa trên đường cong elliptic trên trường hữu hạn.
Cài đặt mẫu (Implementation)
// Sử dụng phép cộng điểm trên đường cong elliptic modulo n để tìm ước số không tầm thường.
Lý thuyết số / Mật mã
Pollard p-1 Algorithm
ID: #137
Xem trên trang chủ
Thời gian (Time)
O(B log B log N)
Không gian (Space)
O(1)
Mô tả nguyên lý
Thuật toán phân tích thừa số nguyên tố hiệu quả khi các thừa số có đặc tính trơn (smooth numbers).
Cài đặt mẫu (Implementation)
// Tận dụng định lý nhỏ Fermat và tính chất bội số của giai thừa số mũ.