solution

Xét bản mã sinh bởi mật mã Vigenère với khóa có độ dài $m$. Nếu chia bản mã $C$ (đánh số ký tự từ 0) thành $m$ nhóm con, trong đó nhóm con thứ $j$ ($0 \le j < m$) gồm các ký tự ở vị trí $j, j+m, j+2m, \ldots$, thì mỗi nhóm con thực chất là kết quả của một phép dịch Caesar cố định trên bản rõ tiếng Anh. Do đó chỉ số trùng hợp (IC) trung bình của $m$ nhóm con sẽ gần với IC của tiếng Anh tự nhiên (khoảng 0.065) khi $m$ là (bội số của) độ dài khóa thật, và gần với IC của chuỗi ngẫu nhiên (khoảng $1/26 \approx 0.0385$) khi $m$ chọn sai.

Công thức IC của một chuỗi ký tự (độ dài $L$, số lần xuất hiện chữ $i$ là $f_i$): $IC = \dfrac{\sum_i f_i(f_i-1)}{L(L-1)}$ nếu $L \ge 2$; quy ước $IC = 0$ nếu $L < 2$.

Cho bản mã $C$ (chỉ gồm chữ in hoa $A \ldots Z$) và số nguyên $M$. Hãy xét mọi độ dài khóa ứng viên $m = 1, 2, \ldots, M$. Với mỗi $m$: chia $C$ thành $m$ nhóm con như mô tả trên, tính IC của từng nhóm, rồi tính IC trung bình (trung bình cộng của $m$ giá trị IC). Tìm $m^*$ có IC trung bình lớn nhất; nếu nhiều $m$ cùng đạt giá trị lớn nhất, chọn $m$ nhỏ nhất.

Ví dụ: với $C =$ BBBBBBBB và $M = 4$: mọi cách chia đều cho IC trung bình $= 1.0$ (vì chỉ có một chữ cái duy nhất), nên $m^* = 1$ (nhỏ nhất) được chọn, IC trung bình $= 1.000000$.