Giới thiệu
Hệ mã Merkle – Hellman thuộc nhóm Public key Cryptosystem, dựa vào bài toán Knapsack (bài toán xếp ba lô, hay bài toán người du lịch). Bài toán Knapsack ban đầu được phát biểu như sau:
Một kẻ trộm đột nhập vào một cửa hiệu tìm thấy có n mặt hàng có trọng lượng và giá trị khác nhau, nhưng hắn chỉ mang theo một cái túi có sức chứa về trọng lượng tối đa là M. Vậy kẻ trộm nên bỏ vào ba lô những món nào và số lượng bao nhiêu để đạt giá trị cao nhất trong khả năng mà hắn có thể mang đi được. Ta có n loại đồ vật, x0 tới xn-1. Mỗi đồ vật xi có một giá trị pi và một khối lượng wi. Khối lượng tối đa mà ta có thể mang trong ba lô là X. Ta cần cực đại hóa tổngpi * xisao chowi * xi < X.
Nhat Truong Blog 