Bài tập | NEU OJ

Thuật toán lượng tử Grover cho phép tìm kiếm trong không gian $2^n$ phần tử chỉ với $O(2^{n/2})$ truy vấn, do đó làm giảm một nửa số bit an toàn của các sơ đồ dựa trên tìm kiếm khoá đối xứng hoặc tính kháng tiền ảnh (preimage resistance) của hàm băm. Đối với tính kháng va chạm (collision resistance) của hàm băm, thuật toán BHT (Brassard–Høyer–Tapp) đạt độ phức tạp $O(2^{n/3})$ truy vấn lượng tử, tức mức an toàn hậu lượng tử còn lại xấp xỉ $n/3$ bit thay vì $n/2$ bit như trong mô hình cổ điển (birthday bound).

Cho $T$ truy vấn, mỗi truy vấn gồm một ký tự loại S (khoá đối xứng hoặc kháng tiền ảnh hàm băm) hoặc C (kháng va chạm hàm băm) và một số nguyên $n$ là mức an toàn cổ điển (tính bằng bit). Hãy tính mức an toàn hậu lượng tử còn lại theo công thức:

Loại S: $\lfloor n/2 \rfloor$
Loại C: $\lfloor n/3 \rfloor$

Ví dụ

Input:

Output:

128
85
64

Định dạng đầu vào:
Dòng đầu tiên chứa số nguyên $T$ ( $T \ge 0$ ) — số truy vấn. $T$ dòng tiếp theo, mỗi dòng chứa một ký tự S hoặc C, theo sau là một số nguyên không âm $n$ , cách nhau bởi khoảng trắng.
Định dạng đầu ra:
In ra $T$ dòng, mỗi dòng là một số nguyên — mức an toàn hậu lượng tử còn lại tương ứng với truy vấn cùng thứ tự ở input.

solution

Đề bài: [An toàn thông tin] Ước lượng an toàn hậu lượng tử theo Grover/BHT