Сдвиговый регистр с обратной связью на основе большинства

Регистры сдвига с линейной обратной связью (LFSR) работать, взяв битовую строку фиксированной длины $b\in\{0,1\}^n$, а также фиксированные «отводы» (положения битов) и применение XOR к отводам, что дает один выходной бит, который добавляется в конец $b$ после его смещения.

Теперь XOR — это линейная функция.Естественная нелинейная функция, которую можно использовать на фиксированном наборе отводов, — это своего рода «голос большинства», который работает следующим образом: если большинство отводов $0$, то выводим $1$, наоборот. (Для этого лучше всего иметь нечетное количество нажатий.)

Можно найти простую реализацию регистра сдвига с обратной связью по мажоритарному принципу. здесь.

Конечно, применяя эту процедуру «большинства голосов» снова и снова, это в конечном итоге становится периодическим.

Вопрос. Учитывая фиксированную битовую длину $n$, какова нижняя граница максимальной длины периода, которая может быть достигнута при выборе подходящей начальной строки $b\in \{0,1\}^n$ и подходящий набор кранов?

Кроме того, мне не удалось выяснить, изучалась ли и где эта концепция.

Я бы не стал претендовать на лучшую нижнюю границу, чем 1.

Заметим, что для регистра сдвига с обратной связью по большинству голосов (далее MVFSR) при наличии $2k+1$ кранов, и если в какой-либо момент заполнение регистра имеет не более $к$ нулей (соответственно не более $к$ единицы), то регистр последовательно заполняется единицами (соответственно нулями) и достигает цикла 1.

Точно так же кажется, что есть много субстанциализма в том, что MVFSR с разреженными заполнениями с большим количеством нулей, вероятно, будет давать нулевую обратную связь, а плотные заполнения с большим количеством единиц, вероятно, будут давать одну обратную связь. Эвристически это приведет к уменьшению плотности заполнения от 1/2 к вышеуказанному вырождению.

Можно создавать MVFSR с отводами, установленными в арифметической прогрессии, которые вырождаются в чередование меньших регистров и, таким образом, достигают стабильных циклов длины, равной количеству меньших регистров, но это не кажется хорошей идеей.

Можно также отметить, что карта от заполнения к заполнению для MVFSR имеет много отображений два к одному, что дает плохую верхнюю границу конечной длины цикла. В общем заполняет где $к+1$ из первых $2k$ отводов ноль или один (т.е. там, где точно нет $к$ нули и $к$ те в первом $2k$ позиции касания) — это заполнения, в которых самый старый бит касания не имеет отношения к обратной связи, поэтому мы создаем два к одному.

Я написал некоторый код, чтобы просто перебрать конфигурации касаний и начальные значения для небольших размеров регистров. Так что у меня есть некоторые значения, а не аналитический результат.Конечно, результаты зависят от отсутствия ошибок в коде (https://github.com/bmm6o/MVFSR).

для ширины 4 максимальная длина цикла 8
для ширины 5 максимальная длина цикла 10
для ширины 6 максимальная длина цикла 12
для ширины 7 максимальная длина цикла 14
для ширины 8 максимальная длина цикла 48
для ширины 9 максимальная длина цикла 48
для ширины 10 максимальная длина цикла 80
для ширины 11 максимальная длина цикла 108
для ширины 12 максимальная длина цикла 140
для ширины 13 максимальная длина цикла 270
для ширины 14 максимальная длина цикла 270
для ширины 15 максимальная длина цикла 270
для ширины 16 максимальная длина цикла 480
для ширины 17 максимальная длина цикла 752
для ширины 18 максимальная длина цикла 1520

Обобщение малых значений может быть рискованным, но кажется, что оно примерно удваивается, когда ширина увеличивается на 2. Эта последовательность отсутствует в OEIS.

Вы, наверное, поняли это, но ваш MVFSR развивается таким образом, что у большинства состояний есть ровно 2 прообраза. Я не уверен, как использовать это для вероятностной оценки распределения длины цикла, но кажется, что это было бы полезно.

Для большинства криптографических целей установление нижней границы максимальной длины цикла не является самым важным вопросом. Гораздо важнее минимальная длина или, по крайней мере, способ охарактеризовать короткие циклы и избежать их. Таким образом, существует серьезная проблема с MVFSR. При оптимальном выборе ответвления имеются циклы длиной всего $2n$.