Биективные отображения, порождаемые фильтрующим генератором

Прикладная дискретная математика. 2014. № 1(23). С. 27–39.

Рожков М. И.

Рассматриваются методы построения биективных отображений  Bf,L:(F2)n®(F2)n, Вf,L(x)=(f(x),f(d(x)),…,f(dn-1(x)), xÎ(F2)n, набор координатных функций которых  (f(x),f(d(x)),…,f(dn-1(x)) задается преобразованием d=dL регистра сдвига большой длины n с функцией обратной связи L и  нелинейной функцией съема f=f(x1,x2,…,xk)  от небольшого числа k аргументов (k<<n). При этом биективность отображения  Bf,L равносильна ортогональности системы его координатных функций. В работе развивается метод, который  сводит исходную задачу проверки биективности отображения Вf,L при больших значениях длины регистра n к проверке биективности соответствующих отображений применительно к регистрам сдвига ограниченной длины n<n0, что позволяет эффективно использовать для ее решения вычислительную технику. На основе данного метода в настоящей работе построены новые бесконечные классы биективных отображений Bf,L для случая нелинейной функции f, зависящей от k<=6 переменных. Ранее аналогичные результаты были известны для случая, когда функция f зависит от трех аргументов. Полученные результаты могут быть полезны при построении и обосновании статистических свойств датчиков случайных последовательностей на основе фильтрующих генераторов. При этом особое значение имеет выбор пар (f,L), при которых одновременно обеспечивается биективность  отображения Bf,L и максимальность периода отображения dL.

Ключевые слова: ортогональные системы функций, регистр сдвига, orthogonal system of Boolean functions, feedback shift register, filter generator, restrictive multitude, фильтрующий генератор, понижающие множества