solution

Trong triển khai Diffie–Hellman an toàn, người ta thường chọn $p$ là một số nguyên tố an toàn (safe prime), tức $p = 2q + 1$ với $q$ cũng là số nguyên tố. Khi đó nhóm nhân $\mathbb{Z}_p^{*}$ có cấp $p-1=2q$, chỉ chứa hai nhóm con thực sự không tầm thường: nhóm con cấp $2$ (gồm $\{1, p-1\}$) và nhóm con cấp $q$ (nhóm con lớn, dùng để sinh khóa).

Nếu không kiểm tra, kẻ tấn công có thể gửi một khóa công khai $B$ nằm trong nhóm con cấp $2$ (tấn công giam giữ nhóm con nhỏ — small subgroup confinement), khiến khóa chung chỉ nhận một trong hai giá trị, dễ dàng đoán được. Để phòng chống, bên nhận phải kiểm tra khóa công khai $B$ nhận được có thật sự nằm trong nhóm con cấp $q$ hay không, bằng điều kiện:

$1 < B < p - 1 \quad \text{và} \quad B^{q} \bmod p = 1$

Cho $p$ (đảm bảo là số nguyên tố an toàn, $q = (p-1)/2$) và $T$ giá trị $B$ cần kiểm tra, với mỗi giá trị hãy in ra VALID nếu $B$ thỏa cả hai điều kiện trên, ngược lại in ra INVALID.

Ví dụ: $p=23$ (nên $q=11$). Với $B=6$: $6^{11} \bmod 23 = 1$ và $1<6<22$, nên VALID. Với $B=22=p-1$: vi phạm điều kiện $B<p-1$, nên INVALID.