solution

Xét thanh ghi dịch phản hồi tuyến tính (LFSR) Fibonacci độ dài $L$ như mô tả trong bài "Sinh dãy bit từ LFSR": trạng thái là $L$ bit ở các vị trí $1,\ldots,L$; mỗi bước, bit phản hồi mới $f$ = XOR các bit tại các vị trí tap của trạng thái hiện tại, sau đó dịch trái và chèn $f$ vào vị trí cuối.

Đề bài đảm bảo tập tap luôn chứa vị trí $1$. Khi đó phép chuyển trạng thái là một song ánh trên không gian $2^L$ trạng thái, do đó xuất phát từ seed khác không, dãy trạng thái chắc chắn sẽ quay trở lại đúng seed ban đầu sau một số bước hữu hạn.

Gọi $T$ là chu kỳ — số bước dịch nhỏ nhất để trạng thái quay lại đúng trạng thái ban đầu (seed). Hãy tính $T$.

Ví dụ: $L=4$, seed = 1000, tap $=\{4,1\}$ (đa thức nguyên thủy $x^4+x+1$) cho chu kỳ tối đại $T = 2^4 - 1 = 15$.