Điểm:1

Ký hiệu đa thức của LFSR

lá cờ se

Tôi đã theo dõi cùng với Bài giảng của Christof Paar về Thanh ghi dịch chuyển phản hồi tuyến tính. Anh ấy giải thích cấu trúc một cách mạch lạc như một tập hợp các flip flop trong đó các 'lần chạm' được xác định bởi một vectơ bit (0 cho việc không chạm vào flip flop đó, 1 cho một lần chạm vào flip flop đó). Nó có ý nghĩa tuyệt vời với tôi.

Nhưng sau đó, anh ấy đưa ra quan điểm rằng mọi người mô tả LFSR không phải là một tập hợp các dép xỏ ngón và một vectơ bit để xác định các vòi, mà là một phương trình đa thức.

Tôi không hiểu biểu diễn đa thức này đang cố gắng làm gì.

P(x) = x^4 + x + 1 sẽ đại diện cho một mạng gồm 4 flip flop, hai cái ngoài cùng bên phải được 'khai thác' để XOR vào bit mới.

Giá trị là gì p(x) đáng lẽ là? Trong thực tế, tôi thậm chí không chắc những gì x giá trị là. Những điều bí ẩn khác đối với tôi: (1) flip flop ngoài cùng bên phải được biểu thị bằng 1. Đây có phải là cách viết tắt của x^0 ? (2) các x^4 thuật ngữ.... bốn flip-flop được dán nhãn 0,1,2,3. Vậy tại sao một thuật ngữ sức mạnh bốn?

Làm cho tôi tự hỏi liệu 'phương trình' này không thực sự là một phương trình mà bạn mong muốn tạo ra một giá trị để sử dụng, mà là một cách lượn sóng thủ công nào đó để chỉ mô tả kiến ​​trúc của LFSR?

kelalaka avatar
lá cờ in
[Hướng dẫn trực quan](https://crypto.stackexchange.com/a/89829/18298) và $P(x) = 0$ như thường lệ!
Fractalice avatar
lá cờ in
Nhân tiện, các hàm tạo trong tổ hợp dựa trên cùng một ý tưởng.
Điểm:3
lá cờ ng

Giá trị là gì $P(x)$ đáng lẽ là?

Không. chúng tôi quan tâm đến hệ số của đa thức $P(x)$, được giới hạn trong Booleans $\{0,1\}$. Các hệ số này phản ánh hệ thống dây điện của LFSR. Đối với các đa thức khác, chúng có thể phản ánh trạng thái của LFSR. Ít khi ta cần đánh giá đa thức đó $P(x)$hoặc các đa thức khác mà chúng tôi sử dụng, cho một giá trị cụ thể của $x$, hoặc thậm chí chỉ định tập hợp $x$ thuộc về. nghĩ về $x$ như một biến không xác định, có thể là số nguyên $\mathbb Z$, hợp lý $\mathbb Q$, số thực $\mathbb R$, phức hợp $\mathbb C$, như bạn thấy phù hợp; và tự tin thực hiện phép tính trên các đa thức đó theo các quy tắc chuẩn của đại số, được sửa đổi bởi $1+1=0$ (tương đương, bằng cách giảm tất cả các hệ số của đa thức modulo $2$).

Flip flop ngoài cùng bên phải được biểu thị bằng $1$. Đây có phải là cách viết tắt của $x^0$?

Đúng. Một lý do khác chúng tôi viết $1$ là để tránh phải xác định $0^0$.

Bốn chiếc dép xỏ ngón được dán nhãn $0,1,2,3$. Vậy tại sao một thuật ngữ sức mạnh bốn?

Thuật ngữ cấp bốn chỉ có trong $P(x)$, đại diện cho hệ thống dây điện của LFSR, không phải trạng thái của nó. Khi xử lý trạng thái, nó sẽ được biểu diễn bằng một đa thức $S(x)$ bằng cấp nhiều nhất là ba.

Ngoài ra: khi chúng ta giảm bất kỳ modulo đa thức nào, đa thức $P(x)$, Phần còn lại $S(x)$ có mức độ nghiêm ngặt thấp hơn mà $P(x)$, do đó, hệ số của nó (thường là trạng thái mới của LFSR) phù hợp với bốn flip-flop.

Tuy nhiên, một cách khác để xem nó là thuật ngữ $x^4$ Trong $P(x)$ tương ứng với bit thoát ra khỏi thanh ghi dịch chuyển khi chúng ta dịch chuyển một bit (tương đương, nhân trạng thái với $x$), trong khi các bit khác tương ứng với sự điều chỉnh các trạng thái mới của mỗi flip-flop.

Làm cho tôi tự hỏi liệu 'phương trình' này không thực sự là một phương trình mà bạn mong muốn tạo ra một giá trị để sử dụng, mà là một cách lượn sóng thủ công nào đó để chỉ mô tả kiến ​​trúc của LFSR?

Thực vậy, $P(x)$ là về kiến ​​trúc của LFSR. Biểu diễn dưới dạng đa thức $P(x)$ cho kiến ​​trúc và $S(x)$ đối với trạng thái rất hữu ích để thiết lập các thuộc tính của LFSR. Đặc biệt, đối với LFSR ở dạng Galois, trạng thái tiến hóa theo $S_{i+1}(x)=S_i(x)\,x\bmod P(x)$, từ đó nó theo sau $S_i(x)=S_0(x)\,x^i\bmod P(x)$.

Lưu ý: ở đây, $\bmod$ mang lại phần còn lại cho mỗi phép chia đa thức, một lần nữa với các hệ số trong Booleans.


¹ Ngoại lệ: đánh giá $P(x)$ tại $x=1$ trong Booleans, hoặc $x=2$ đối với các số nguyên, đôi khi mang lại các giá trị thú vị.

Đăng câu trả lời

Hầu hết mọi người không hiểu rằng việc đặt nhiều câu hỏi sẽ mở ra cơ hội học hỏi và cải thiện mối quan hệ giữa các cá nhân. Ví dụ, trong các nghiên cứu của Alison, mặc dù mọi người có thể nhớ chính xác có bao nhiêu câu hỏi đã được đặt ra trong các cuộc trò chuyện của họ, nhưng họ không trực giác nhận ra mối liên hệ giữa câu hỏi và sự yêu thích. Qua bốn nghiên cứu, trong đó những người tham gia tự tham gia vào các cuộc trò chuyện hoặc đọc bản ghi lại các cuộc trò chuyện của người khác, mọi người có xu hướng không nhận ra rằng việc đặt câu hỏi sẽ ảnh hưởng—hoặc đã ảnh hưởng—mức độ thân thiện giữa những người đối thoại.