Thanh ghi thay đổi phản hồi dựa trên đa số

Các thanh ghi dịch chuyển phản hồi tuyến tính (LFSR's) hoạt động bằng cách lấy một chuỗi bit có độ dài cố định $b\in\{0,1\}^n$, cũng như cố định các "nhấn" (vị trí bit) và áp dụng XOR cho các vòi, tạo ra một bit đầu ra, bit này được thêm vào tại $b$ sau khi dịch chuyển nó.

Bây giờ XOR là một hàm tuyến tính.Một chức năng phi tuyến tính tự nhiên có thể được sử dụng trên tập hợp các vòi cố định là một loại "phiếu đa số", hoạt động như sau: nếu phần lớn các vòi là $0$, sau đó chúng tôi xuất $1$, và ngược lại. (Đối với điều này, tốt nhất là có số lần nhấn là số lẻ.)

Có thể tìm thấy một triển khai đơn giản của thanh ghi thay đổi phản hồi dựa trên đa số đây.

Tất nhiên, áp dụng đi áp dụng lại thủ tục "phiếu đa số" này, điều này cuối cùng sẽ trở nên định kỳ.

Câu hỏi. Với độ dài bit cố định $n$, giới hạn dưới của độ dài tối đa của khoảng thời gian có thể đạt được bằng cách chọn chuỗi bắt đầu phù hợp $b\in \{0,1\}^n$ và một bộ vòi phù hợp?

Ngoài ra, tôi không thể tìm hiểu xem liệu khái niệm này đã được nghiên cứu ở đâu và chưa.

Tôi sẽ ngần ngại yêu cầu giới hạn dưới tốt hơn 1.

Chúng tôi lưu ý rằng đối với thanh ghi thay đổi phản hồi đa số phiếu bầu (sau đây gọi là MVFSR) nếu có $2k+1$ vòi và nếu tại bất kỳ thời điểm nào, việc điền vào sổ đăng ký có nhiều nhất $k$ số không (tương ứng nhiều nhất $k$ những cái) thì thanh ghi sau đó sẽ lấp đầy những cái (tương ứng với số 0) và đạt chu kỳ 1.

Tương tự như vậy, người ta cảm thấy rằng có rất nhiều chủ nghĩa thực chất trong MVFSR đó với các lần lấp đầy thưa thớt với nhiều số không có khả năng tạo ra phản hồi bằng không và các lần lấp đầy dày đặc với nhiều số không có khả năng tạo ra một phản hồi. Về mặt kinh nghiệm, điều này sẽ đẩy mật độ lấp đầy ra khỏi 1/2 và hướng tới sự suy biến ở trên.

Có thể tạo MVFSR với các vòi được đặt theo cấp số cộng suy biến thành xen kẽ của các thanh ghi nhỏ hơn và do đó đạt được các chu kỳ ổn định có độ dài bằng với số lượng thanh ghi nhỏ hơn, nhưng điều này không phải là một ý tưởng hay.

Người ta cũng có thể lưu ý rằng bản đồ từ điền vào đến điền cho MVFSR có nhiều bản đồ hai đối một đặt giới hạn trên kém cho độ dài chu kỳ cuối cùng. Nói chung điền vào đâu $k+1$ của người đầu tiên $2k$ vòi bằng không hoặc một (nghĩa là không có chính xác $k$ số không và $k$ cái đầu tiên $2k$ các vị trí nhấn) là các lần lấp đầy trong đó bit nhấn cũ nhất không liên quan đến phản hồi và vì vậy chúng tôi tạo hai đối một.

Tôi đã viết một số mã để chỉ cấu hình chạm mạnh và bắt đầu các giá trị cho kích thước thanh ghi nhỏ. Vì vậy, tôi có một số giá trị, thay vì kết quả phân tích.Tất nhiên, kết quả có điều kiện là không có bất kỳ lỗi nào trong mã (https://github.com/bmm6o/MVFSR).

đối với chiều rộng 4, chiều dài chu kỳ tối đa là 8
đối với chiều rộng 5, chiều dài chu kỳ tối đa là 10
đối với chiều rộng 6, chiều dài chu kỳ tối đa là 12
đối với chiều rộng 7, chiều dài chu kỳ tối đa là 14
đối với chiều rộng 8, chiều dài chu kỳ tối đa là 48
đối với chiều rộng 9, chiều dài chu kỳ tối đa là 48
đối với chiều rộng 10, chiều dài chu kỳ tối đa là 80
đối với chiều rộng 11, chiều dài chu kỳ tối đa là 108
đối với chiều rộng 12, chiều dài chu kỳ tối đa là 140
đối với chiều rộng 13, chiều dài chu kỳ tối đa là 270
đối với chiều rộng 14, chiều dài chu kỳ tối đa là 270
đối với chiều rộng 15, chiều dài chu kỳ tối đa là 270
đối với chiều rộng 16, chiều dài chu kỳ tối đa là 480
đối với chiều rộng 17, chiều dài chu kỳ tối đa là 752
đối với chiều rộng 18, chiều dài chu kỳ tối đa là 1520

Có thể rủi ro khi khái quát hóa từ các giá trị nhỏ, nhưng nó dường như tăng gấp đôi khi chiều rộng tăng thêm 2. Trình tự này không có trong OEIS.

Bạn có thể đã nhận ra điều này, nhưng MVFSR của bạn phát triển theo cách mà hầu hết các trạng thái đều có chính xác 2 hình ảnh trước. Tôi không chắc cách sử dụng điều đó để ước tính xác suất phân phối độ dài chu kỳ, nhưng có vẻ như nó sẽ hữu ích.

Đối với hầu hết các mục đích mật mã, việc đặt giới hạn dưới cho độ dài chu kỳ tối đa không phải là câu hỏi quan trọng nhất. Điều quan trọng hơn nhiều là độ dài tối thiểu, hoặc ít nhất là một cách để mô tả và tránh các chu kỳ ngắn. Theo cách đó, có một vấn đề nghiêm trọng với MVFSR. Theo lựa chọn vòi tối ưu, có các chu kỳ độ dài chỉ $2n$.