Boolean functions generated by the most significant bits of linear recurrent sequences.pdf В работе [1] изучались свойства булевых функций, построенных на основе последовательностей старших разрядов отмеченных линейных рекуррент над кольцом R = Z2n. Получены результаты, описывающие веса функций, степень их нелинейности, расстояние между функциями и мощность всего семейства. А. А. Нечаевым предложен к рассмотрению ещё один класс булевых функций, построенных на основе последовательностей старших разрядов, отличающийся другим упорядочиванием вектора значений функции. В настоящей работе приводятся результаты о степени нелинейности и алгебраической степени функций из данного класса. Пусть F(x) Е R[x] -унитарный (со старшим коэффициентом 1) реверсивный многочлен степени m, такой, что его период 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,k1} множества R назовём разрядным множеством кольца R (см., например, [2]), если элементы k0 и k1, рассматриваемые как целые числа, имеют различную чётность. Примером разрядного множества кольца R является двоичное разрядное множество K = {0,1}. Если K - разрядное множество кольца R, то каждый элемент a этого кольца однозначно представим в виде a = a0 + 2a1 + 22a2 + 23аз + ... + 2n-1 a„_b (1) где ai = (a) Е K для всех i = 0,1,... , n - 1. Элемент a^, участвующий в равенстве (1), будем называть i-м разрядом элемента a в разрядном множестве K. Сопоставим каждой ЛРП u E LR(F)* булеву функцию fU к(x1,... ,xm) по правилу Дк (0,..., 0) = xK.1(0)mod2, ' fU,K(uo(i),uo(i + 1),... ,uo(i + m - 1)) = x^^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) множество всех булевых функций fU к, соответствующих всем ЛРП u из множества LR(F)*. Оказывается, что для функций f U к E Bn(K, F) справедливы такие же оценки степени нелинейности и алгебраической степени, что и для функций из класса Bn(K,F) [1]. Теорема 1. Для коэффициентов Wf (a) Уолша - Адамара булевой функции f = = fa к при всех n ^ 2 имеет место оценка Следствие 1. При n = 2 и каждом чётном m класс Bn (K, F) состоит из бент-функций, а при n = 2 и каждом нечётном m класс Bn(K, F) состоит из платовидных функций порядка m - 1. Теорема 2. Пусть F(x) E R[x] -отмеченный многочлен степени m > |R| максимального периода над кольцом R, тогда для любой функции f E Bn(K, F) справедливо соотношение deg f = 2n-1.

Скачать электронную версию публикации