Lý thuyết số / Mật mã

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

Lý thuyết số / Mật mã

Lenstra Elliptic Curve Factorization (ECM)

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

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ũ.