Lý thuyết số nâng cao
Baby-Step Giant-Step (BSGS)
ID: #135
Xem trên trang chủ
Thời gian (Time)
O(sqrt(P))
Không gian (Space)
O(sqrt(P))
Mô tả nguyên lý
Giải bài toán logarit rời rạc $g^x \equiv h \pmod p$ trong thời gian căn bậc hai.
Cài đặt mẫu (Implementation)
// Sử dụng bảng băm lưu trữ các giá trị bước nhỏ (baby steps) để khớp với bước lớn (giant steps).