Об одном классе булевых функций, построенных с использованием старших разрядных последовательностей линейных рекуррент

№7 ПРИЛОЖЕНИЕ Сентябрь 2014

Секция 3

ПСЕВДОСЛУЧАЙНЫЕ ГЕНЕРАТОРЫ

УДК 519.113.6

ОБ ОДНОМ КЛАССЕ БУЛЕВЫХ ФУНКЦИЙ, ПОСТРОЕННЫХ С ИСПОЛЬЗОВАНИЕМ СТАРШИХ РАЗРЯДНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ ЛИНЕЙНЫХ РЕКУРРЕНТ

Д. Н. Былков

Изучается семейство булевых функций, построенных на основе старших разрядных последовательностей линейных рекуррент над кольцом Z2« c отмеченным характеристическим многочленом. Для данного семейства изучаются степень нелинейности функций и алгебраическая степень. Показывается, что указанное семейство содержит функции, значительно удалённые от класса всех аффинных функций.

Ключевые слова: линейные рекуррентые последовательности, старшие разрядные последовательности, степень нелинейности булевой функции.

В работе [1] изучались свойства булевых функций, построенных на основе последовательностей старших разрядов отмеченных линейных рекуррент над кольцом R = Z2n. Получены результаты, описывающие веса функций, степень их нелинейности, расстояние между функциями и мощность всего семейства. А. А. Нечаевым предложен к рассмотрению ещё один класс булевых функций, построенных на основе последовательностей старших разрядов, отличающийся другим упорядочиванием вектора значений функции. В настоящей работе приводятся результаты о степени нелинейности и алгебраической степени функций из данного класса.

Пусть F(x) € R[x] —унитарный (со старшим коэффициентом 1) реверсивный многочлен степени т, такой, что его период T(F) удовлетворяет условию T(F) = = T(F mod 2) = 2m — 1. В этом случае будем говорить, что F(x) —отмеченный многочлен максимального периода. Обозначим Lr(F) множество всех линейных рекуррентных последовательностей (ЛРП) над кольцом R с характеристическим многочленом F(x) и Lr(F)* — множество всех ЛРП u € Lr(F), у которых в начальном векторе (u(0), u(1),..., u(m — 1)) есть хотя бы один обратимый элемент кольца R. Каждая последовательность u € Lr(F)* имеет период T(u) = T(F) = (2m — 1).

Подмножество K = {k0,kl} множества R назовём разрядным множеством кольца R (см., например, [2]), если элементы k0 и kl, рассматриваемые как целые числа, имеют различную чётность. Примером разрядного множества кольца R является двоичное разрядное множество K = {0,1}. Если K — разрядное множество кольца R, то каждый элемент а этого кольца однозначно представим в виде

а = ао + 2ai + 22а2 + 23аз + ... + 2n lan-i,

где а^ = (а) € K для всех i = 0,1,... ,n — 1. Элемент а^, участвующий в равен-

стве (1), будем называть i-м разрядом элемента а в разрядном множестве K.

Сопоставим каждой ЛРП u € Lr(F)* булеву функцию /U к(xl,... , xm) по правилу

/U,к(0,... , 0) = кП-1(0) mod 2

/U,K(uo(i),uo(i + 1),... ,uo(i + m — 1)) = KK-l(u(i)) mod 2,

где u0(i) = u(i) mod 2, 0 ^ i ^ 2m — 1.В силу выбора последовательности u вектор (u0(i), u0(i + 1),... ,u0(i + m — 1)) принимает все возможные значения из множества {0,1}m \ {(0,... , 0)}, поэтому функция определена на всех двоичных наборах {0,1}m. Обозначим Bn/;(K, F) множество всех булевых функций /Uk , соответствующих всем ЛРП u из множества Lr(F)*.

Оказывается, что для функций /U к € BI(K, F) справедливы такие же оценки степени нелинейности и алгебраической степени, что и для функций из класса

В(K,F) [1].

Теорема 1. Для коэффициентов Wf (a) Уолша — Адамара булевой функции / = = /и к при всех n ^ 2 имеет место оценка

+ 1^ (2n-1 — 1)2m/2.

Следствие 1. При n = 2 и каждом чётном m класс В (K, F) состоит из бент-функций, а при n = 2 и каждом нечётном m класс B/(K, F) состоит из платовидных функций порядка m — 1.

Теорема 2. Пусть F(x) € R[x] —отмеченный многочлен степени m > |R| максимального периода над кольцом R, тогда для любой функции / € BI(K, F) справедливо соотношение deg / = 2n-1.

ЛИТЕРАТУРА

1. Былков Д. Н., Камловский О. В. Параметры булевых функций, построенных с использованием старших координатных последовательностей линейных рекуррент // Матем. вопр. криптогр. 2012. Т. 3. №4. С.25-53.

2. Kurakin V.L., Kuzmin A. S., Mikhalev A. V., and Nechaev A. A. Linear recurring sequences over rings and modules // J. Math. Sci. (New York). 1995. V. 76. No. 6. P. 2793-2915.

УДК 519.6

ОЦЕНКИ ЭКСПОНЕНТОВ ПЕРЕМЕШИВАЮЩИХ ГРАФОВ НЕКОТОРЫХ МОДИФИКАЦИЙ АД ДИТИВНЫХ ГЕНЕРАТОРОВ

А. М. Дорохова

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

Ключевые слова: аддитивный генератор, перемешивающий граф преобразования, экспонент графа.