Làm thế nào bạn có thể tìm thấy đa thức cho một LFSR đã bị xóa?

Question

Tôi biết rằng nếu bạn quyết định chuỗi được tạo ra bởi thanh ghi thay đổi phản hồi tuyến tính, bạn sẽ nhận được một chuỗi mới và một đa thức mới. Ví dụ: nếu bạn lấy mẫu mỗi phần tử thứ năm trong chuỗi được tạo bởi LFSR với đa thức x + x + 1, bạn sẽ nhận được chuỗi được tạo bởi x + x + 1. Tôi có thể tìm thấy đa thức thứ hai (x + x + 1) bằng sức mạnh vũ phu, điều này tốt cho các đa thức bậc thấp. Tuy nhiên, đối với các đa thức bậc cao, thời gian cần thiết cho sức mạnh vũ phu là không hợp lý.

Vì vậy, câu hỏi đặt ra là: liệu có thể tìm thấy phân tích đa thức được phân tích không?

Answer 1

Gần đây đọc bài viết này và nghĩ đến nó khi nhìn thấy câu hỏi của bạn, hy vọng nó sẽ giúp ..: OTH

Cho một đa thức nguyên thủy trên GF (q), người ta có thể có được một đa thức nguyên thủy bởi decimating một chuỗi LFSR thu được từ đa thức ban đầu. Điều này được thể hiện trong đoạn mã dưới đây.

K: = GF (7); C: = PrimitivePolynomial (K, 2); C; D^2 + 6 * D + 3 Để tạo chuỗi LFSR, trước tiên chúng ta phải nhân đa thức này với hằng số phù hợp để hệ số theo sau trở thành 1.

C: = C * Coefficient (C, 0)^- 1; C; 5 * D^2 + 2 * D + 1 Bây giờ chúng ta có thể tạo chuỗi LFSR có độ dài 72 - 1. Trạng thái ban đầu có thể là bất kỳ thứ gì khác hơn [0, 0].

t: = LFSRSequence (C, [K | 1,1], 48); t; [1, 1, 0, 2, 3, 5, 3, 4, 5, 5, 0, 3, 1, 4, 1, 6, 4, 4, 0, 1, 5, 6, 5, 2, 6, 6, 0, 5, 4, 2, 4, 3, 2, 2, 0, 4, 6, 3, 6, 1, 3, 3, 0, 6, 2, 1, 2, 5] Chúng tôi phân tích chuỗi theo giá trị d có gcd thuộc tính (d, 48) = 1.

t: = Decimation (t, 1, 5); t; [1, 5, 0, 6, 5, 6, 4, 4, 3, 1, 0, 4, 1, 4, 5, 5, 2, 3, 0, 5, 3, 5, 1, 1, 6, 2, 0, 1, 2, 1, 3, 3, 4, 6, 0, 3, 6, 3, 2, 2, 5, 4, 0, 2, 4, 2, 6, 6] B: = BerlekampMassey (t); B; 3 * D^2 + 5 * D + 1 Để có được đa thức nguyên thủy tương ứng, chúng ta nhân với hằng số để làm cho nó đơn sắc.

B: = B * Hệ số (B, 2)^- 1; B; D^2 + 4 * D + 5 IsPrimitive (B); true