LFSR Fibonacci sinh chuỗi bit

Thanh ghi dịch phản hồi tuyến tính (LFSR) bậc $n$ có các hệ số phản hồi $c_1, c_2, \dots, c_n \in \{0,1\}$ . Trạng thái là $s_0 s_1 \dots s_{n-1}$ , trong đó $s_0$ là bit nằm ở đầu thanh ghi và được xuất ra ở mỗi bước.

Mỗi bước:

Xuất bit $s_0$ .
Tính bit phản hồi $f = (c_1 s_0 \oplus c_2 s_1 \oplus \dots \oplus c_n s_{n-1})$ .
Dịch trái: trạng thái mới là $s_1 s_2 \dots s_{n-1} f$ .

Hãy sinh $k$ bit đầu tiên của keystream.

Ví dụ

Với $n=3$ , taps $=1\,0\,1$ ( $c_1=1,c_2=0,c_3=1$ ), trạng thái đầu $0\,0\,1$ , $k=7$ : keystream là 0011101 (đây là một m-sequence chu kỳ 7).

Định dạng đầu vào:
Dòng 1: số nguyên $n$ . Dòng 2: $n$ số $c_1 \dots c_n$ (taps). Dòng 3: $n$ số $s_0 \dots s_{n-1}$ . Dòng 4: số nguyên $k$ .
Ràng buộc đầu vào:
$1 \le n \le 16$ , $1 \le k \le 100000$ , các bit $\in \{0,1\}$ .
Định dạng đầu ra:
Một dòng gồm $k$ ký tự 0/1 là keystream.

solution

Đề bài: [An toàn thông tin] LFSR Fibonacci: sinh chuỗi bit

LFSR Fibonacci sinh chuỗi bit

Ví dụ