Класс булевых функций, построенных с использованием двоичных разрядных последовательностей линейных рекуррент над кольцом Z2n | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/23

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

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

Class of boolean functions constructed using significant bits of linear recurrences over the ring z2n.pdf Введение Пусть R = Z2n -кольцо вычетов по модулю 2n, F(х) -отмеченный многочлен степени m максимального периода T(F) = 2m - 1 над кольцом R [1]. Введём обозначения: P = Z2; F(x) -многочлен, полученный из F(х) приведением всех его коэффициентов по модулю 2. Тогда T(F) = 2m - 1 и F(x) является примитивным многочленом над полем P. Пусть ..., - линейно независимая система линейных рекуррентных последовательностей (ЛРП) над полем P с характеристическим многочленом F(x). Обозначим через Lr(F)* множество всех ЛРП u над кольцом R, у которых среди элементов u(0),... , u(m - 1) есть хотя бы один обратимый элемент кольца R. Рассмотрим функцию " : R -^ P, действующую на каждый элемент a Е R с двоичным представa лением ao + 2ai + 22a2 + ... + 2n 1an_i, ao, ai,... an-1 Е P по правилу "0(a) = an-i Ф an-2an-3 ...an-k, (1) где n ^ 3; k Е {3,... , n}. Для каждой ЛРП u Е LR(F)* рассмотрим булеву функцию f (xi,... , xm) = (xi,... , xm), определённую по следующему правилу: f (0,... , 0) = = "(0) и для всех i Е {0,..., 2m - 2} f Mi),...,^m(i))= "(U(i)). (2) Пусть x : R -> C* - аддитивный характер кольца R, определённый равенством Х(х) = e2nix/2n, х Е R. Группа всех аддитивных характеров кольца R имеет вид {x(ax) : a Е R}. Множество всех отображений из R в C* образует унитарное пространство со скалярным произведением, определённым для отображений g и h по правилу (g,h) = Е g(x)h(x). жея Система функций x(ax), a G R, образует ортогональный базис рассматриваемого пространства, поэтому найдутся однозначно определённые числа Vj - Vj(/) G C, такие, что (-ip) = E ^^X(jx), x G R. j jeR Vj - Е (-1)^(а)х(-aj). Они однозначно вычисляются по формуле 1 22 «ея 2m-1 - ^2 ln(2n-1) + (2n-1 - 1)2m/2-1 < Введём обозначение а(/) - £ |vj|. jeR 1. Свойства функций нового класса Для суммы модулей чисел Vj получим следующую оценку: Теорема 1. Пусть отображение / задано равенством (1) и k - 3, тогда 2 ) < - ln(2n-1) + 1. п Эта оценка позволяет доказать теорему: Теорема 2. Пусть f - функция, определённая равенством (2) и k - 3, тогда 1) вес f удовлетворяет неравенствам ^m-1 I 2 i^, (on-1\\ | 1 1 /on-1 1 \\om/2-1 ^ || < < 2m-1 + 0ln(2n-1) + (2n-1 - 1)2m/2-1; 2) если f - , g - и ЛРП не пропорциональны в R*, то расстояние Хэмминга p(f, g) между столбцами значений рассматриваемых функций удовлетворяет соотношениям 2m-1 - ^2 ln(2n-1) + (2n-1 - 1)2m/2-1 < p(f,g) < < 2m-1 + f2 ln(2n-1) + Л (2n-1 - 1)2m/2-1; чп 3) для нелинейности nl(f) верна оценка nl(f) ^ 2m-1 - ^2 ln(2n-1) + (2n-1 - 1)2m/2-1. Для произвольных значений k аналогичные результаты получить не удаётся. В общем виде справедливо Утверждение 1. Пусть -1(a) - an-1 Ф an-2 ...an-fc, -2(a) - an-1 Ф an-2 . . . an-fcan-k-1, где k G {3,..., n - 1}. Тогда для |vj(/2)| верна оценка (/ < 1 + 2n-1 sin(nj/2n)|vj (-1)| 1 j(/2)| < 2n sin(nj/2n)|cos(nj/2k+1)|. Это утверждение позволяет оценить модули чисел Vj (/2), зная аналогичные коэффициенты для отображения -1 . 2. Расстояние Хэмминга между функциями Изучим теперь для двух функций f и g из разных классов величину p(f, g). Утверждение 2. Пусть отображение задано равенством (1) и "2(a) = an-i, f = , g = . Тогда _ (2n - 1)(2n i - 1) 2m/2-k+2 < p(f g) < 2m-k+i + (2n - 1)(2n i - 1) 33 Обозначим через ei, e2 соответственно левую и правую части неравенства из утверждения 2. Утверждение 3. Пусть отображение задано равенством (1), "2(a) = an-i ф ф an-2 Ф an-з Ф ... Ф an-k, где k Е {3,... , n}, f = fu^, g = fu^. Тогда (2k-2 + 1)ei < p(f, g) < (2k-2 + 1)e2 для нечётного k; (2k-2 - 1)ei < p(f,g) < (2k-2 - 1)^2 для чётного k. Заключение В данной работе для класса булевых функций, построенных на основе двоичных разрядных последовательностей линейных рекуррент над кольцом Z2n, получены оценки для веса функций, нелинейности и расстояний между функциями. Отметим, что ранее в работах [2-4] аналогичные вопросы были рассмотрены только для случая, когда " - линейное отображение по всем двоичным разрядам.

Ключевые слова

булевы функции, линейные рекуррентные последовательности, двоичные разрядные последовательности, Boolean functions, linear recurrent sequences, significant bits sequences

Авторы

ФИООрганизацияДополнительноE-mail
Эрнандес Пилото Даниэль УмбертоООО «Центр сертификационных исследований»научный сотрудникdhhernandez2410@gmail.com
Всего: 1

Ссылки

Нечаев А. А. Цикловые типы линейных подстановок над конечными коммутативными кольцами // Математический сборник. 1993. Т. 184. №3. С. 21-56.
Былков Д. Н., Камловский О. В. Параметры булевых функций, построенных с использованием старших координатных последовательностей линейных рекуррент // Математические вопросы криптографии. 2012. Т. 3. №4. С. 25-53.
Камловский О. В. Нелинейность одного класса булевых функций, построенных с использованием двоичных разрядных последовательностей линейных рекуррент над кольцом Z2n // Математические вопросы криптографии. 2016. Т. 7. №3. С. 29-46.
Былков Д. Н. Об одном классе булевых функций, построенных с использованием старших разрядных последовательностей линейных рекуррент // Прикладная дискретная математика. Приложение. 2014. № 7. С. 59-60.
 Класс булевых функций, построенных с использованием двоичных разрядных последовательностей линейных рекуррент над кольцом Z2n | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/23

Класс булевых функций, построенных с использованием двоичных разрядных последовательностей линейных рекуррент над кольцом Z2n | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/23