CLASS OF BOOLEAN FUNCTIONS CONSTRUCTED USING SIGNIFICANT BITS OF LINEAR RECURRENCES OVER THE RING ℤ2n

Abstract

In this work a class of functions is studied, which are built with the help of significant bits sequences on the ring ℤ2n. This class is built with use of a function ψ: ℤ2n → ℤ2. In public literature there are works in which ψ is a linear function. Here we will use a non-linear ψ function for this set. It is known that the period of a polynomial F in the ring ℤ2n is equal to T(mod 2)2α, where α∈ , n01- . The polynomials for which it is true that T(F) = T(F mod 2), in other words α = 0, are called marked polynomials. For our class we are going to use a polynomial with a maximum period as the characteristic polyomial. In the present work we show the bounds of the given class: non-linearity, the weight of the functions, the Hamming distance between functions. The Hamming distance between these functions and functions of other known classes is also given.

Full Text

Введение Система функций χ(ax), a  R, образует ортогональный n базис рассматриваемого пространства, поэтому найдутся од- Пусть R = ℤ2 n - кольцо вычетов по модулю 2 , F (x) - отнозначно определенные числа ν = ν (ψ)  ℂ такие, что меченный многочлен степени m максимального периода j j T (F ) = 2m - 1 над кольцом R[х]. Введем обозначения: P = ℤ ,   2 1 x  ν j  jx , x R. F $(x) - многочлен, полученный из F (x) приведением всех его коэффициентов по модулю 2. Тогда T(F $) = 2m - 1 и F $(x) является примитивным многочленом над полем P. Пусть jR Они однозначно вычисляются по формуле ω1, ... , ωm - линейно независимая система линейных ре- куррентных последовательностей (ЛРП) над полем P с ха-  j  image 1 n 1   a  aj . рактеристическим многочленом F $(x). Обозначим через LR (F)* множество всех ЛРП u над кольцом R у которых среди элементов u(0), ... , u(m - 1) есть хотя бы один обратимый 2 Введем обозначение aR элемент кольца R. Рассмотрим функцию ψ: R → P, действу- ющую на каждый элемент a  R с двоичным представле- нием    image j image. jR 0 1 2 a = a + 2a + 22a + ... + 2 по правилу n - 1 an - 1, a0, a1 ... an - 1  P Новый класс функций и его свойства Для суммы модулей чисел νj получим следующую оценку. ψ(a) = an - 1  an - 2an - 3 ... an - k, (1) image где n ≥ 3, k 3, n . Для каждой ЛРП u  LR (F)* рассмотрим Теорема 1. Пусть отображение ψ задано равенством (1) и k = 3, тогда   булеву функцию f (x1, ... , xm ) = fu, ψ(x1, ... , xm ), определенную image по правилу: f (0, ... , 0) = ψ(0) и для всех i 0,2m  2   2 ln 2  n  1  1. f [ω1(i ), ... , ωm(i )] = ψ[u(i )]. (2) Пусть χ: R → ℂ* - аддитивный характер кольца R, опреде- ленный равенством Доказательство. Сначала надо найти значения коэффици- image j ентов ν для любого j 0,2m  1 . По определению коэффици- ента νj мы имеем a   n  1 a j image  x   e2i x 2n  , x R.   1 j 2n  a0 , a1 , ... , an  1 1an  1  an  2an  3  0 image 2i e ... 2 2n n  1   a  ... 2n  2 a j Группа всех аддитивных характеров кольца R имеет вид {χ(ax): a  R}. Множество всех отображений из R в ℂ обра-  1 2n  1an  2an  3 0 image 2i e n  2 2n 1an  1 eijan  1 . зует унитарное пространство со скалярным произведением, a0 , a1 , ... , an  2 an  1 определенным для отображений g и h по правилу image imageg, himage   g  x h  x . xR Справедливо равенство 1an  1 eijan  1  1  eij  2. an  1 Следовательно, получим a  ...  2n  2 a j Теперь рассмотрим S2: j j 0 n  2 a i n  3     image 2  . image  1 .  1  a a n 2i e 2 image n e 2 1 1 2 3 1 image 2 3 1 2 2 2i   j 2n 1  n i aj n j 2 2  e 8      n n n  2 n  3  2 2 i S2  e  e  j j a0 , a1 , ... , an  2 a  0 a  0 2i i n n где Теперь преобразуем νj следующим образом: image   1 S S , j 2n  1 1 2 где Надо найти image image image   1 S j 2n  1 1 e image S2 image , 2  1 e 2  1 2 a  n  2 n  2 n  3  2 an  3 j S1   an  2 , an  3 1an  2an  3 e 2i 2n ; image  1    1  image image 2  i , image 2  i , j  1  8k; j  3  8k; a  ...  2n  4 a j S    image 0 n  4 1 S2   a0 , a1 , ... , an  4 2i e 2n .  1    1  2  i , image 2  i , j  5  8k; j  7  8k, Рассмотрим сумму S1: i j2 i j2 j 2  2  i image    2 2  2 , image   2 2  2 , j  1  8k j  3  8k или j = 7 + 8k; или j = 5 + 8k; n  3 n  2 n  2 n  3     S1  1  e 2n  1  e 2n  1  e image image 2n  1  j  1  e i j 4  e i j 2  e image i 3 j 4 . image image S  e 2i 8  1 . Нетрудно вычислить, что S1 = 0, если j - четное число. Для нечетных j имеем 2 Так как 2i j e 2n  1 image image   2  i 2 , j  1  8k; image image imageei   1image  cos   1  i sin  image 2  2cos   image image image  2 2   image image  2 2  2   i , j  3  8k;  2 2sin2  2 sin , i j  2 2 2 image image e 4    2  i 2 , j  5  8k; то отсюда получим  2 2 image image  image image  2  2  2  i 2 ,  7  8k; image image  , j  1  8k или j = 7 + 8k;  2 2  j  2 sin j  sin     image image imageS2 image  image   8     2n   2  i 2 , j  1  8k;  j  image image  2  2  sin  image  2 2  2n   ,  j  j  3  8k или j = 5 + 8k. image image  2 s n  3  2  i 2 , j  3  8k;   2n  i j  2 2 e 4    image image 2  i 2 , j  5  8k; Тогда  2 2 image image   2  i 2 ,  2 2 j  7  8k, 0, image  image image    2 2  2 2  2 j  , j - четное число; j - нечетное число; sin 2  n  j    n  image где k 0,2n  3  1, i j i, j  1  4k; 2  0,     j - четное число; 1 e 2   i, j  3  4k, image   2n  1 sin j  , j - нечетное число.   image где k 0,2n  2  1 .   2n  В итоге получим 1  image 2  i, j  1  8k; Заметим, что sin (πj/2 n) для любого j = 1, 3, 5, ... , 2 n - 1 всегда является положительным числом, тогда  1  S1   image 2  i, j  3  8k; 0, image image  image  j   j - четное число; 1 , j - нечетное число.   j 1  image 2  i, j  5  8k; 2n  1 image sin   1  image 2  i, j  7  8k,   2n  image где k 0,2n  3  1. Остается воспользоваться оценкой, которая доказана в работе [2]. Полученная оценка позволяет доказать следующий ре- зультат. Пусть a0  ...  2 n  k  2 an  k  2  2 n  k n  k a  ...  2 n  1 an  1 j 1 an  1 image 2 i n Теорема 2. Пусть f - функция, определенная равенством и k = 3, тогда вес f удовлетворяет неравенствам S1  n 1 e 2 M 2 ; a  ...  2n  k  1  ...  2n  1 a j 1  0 image  an  1  an  2 ... an  k 2i n  1  2n 2m  1   2 2n  1   1 2n  1 image image image 1 2m 21 f S2  n  1 e .  ln         2 M image  2m  1   2 ln2n  1   12n  1  12m 21 ; Пусть ψ3(a) = an - 1. Рассмотрим чему равна сумма S1:      a  ...  2n  k  2 a 2n  k a  ...  2n  1 a j 1 an  1 0 image 2i n  k  2 n n  k n  1 если f = fu, ψ, g = fν, ψ и ЛРП u, ν не пропорциональны в R*, то расстояние Хэмминга ρ(f, g) между столбцами S1  n 1 2 M e 2  2 a j n  k  1 n  k  1 значений рассматриваемых функций удовлетворяет соотношениям image 2i  e 2n a     nk1  j 3 . 2m  1   2 2 2n  1   1 2n 1 1 2m 21 f g 2n  k  1 a j 2i nk1 e 2n 2n  k  1 a j 2i nk1 e 2n  ln   image        ,     2  2m 1   2 ln2n  1   1 2n  1 1 2m 21 image an  k  1 an  k  1         ; Тогда для нелинейности nl (f) верна оценка  . j 3    image S1 2 ij k  1 image nl f   2m  1   2 ln2n  1   12n  1  12m 21. 1  e 2 image      Теперь аналогичным образом преобразуем S2: Доказательство. Пункты 1 и 2 непосредственно следу- ют из работы [3]. Пункт 3 следует из результатов работы [4]. 2ij image e 2 k  1 image S   2 2n  0 an  k  2  2 an  k  ...  2 an  1 j a  ...  2n  k  2 n  k n  1 Для произвольных значений k аналогичные результаты a a a 2i получить не удается. В общем виде справедлив следующий факт.  1 n  1  M n  2 , ... , n n  k e 2 . Утверждение 1. Пусть 1 a  an  1  an  2 ... an  k ; В итоге получим 2ij image j     e 2k  1    2 a  an  1  an  2 ... an  kan  k  1 , image где k 3, n  1 . Тогда для |νj (ψ2)| верна оценка image .  j 2   Нам надо найти 3 j 1 2 ij k  1 1  e 2 image image 1  2n  1 sin j     image image 2ij image  n  j 1     e 2k  1    image        image image     image image image  2  . image image     S  S  j 3 . j 1  j 3 j 1 j 2  j   j  j 2 1 2 2 ij 2 ij 2n sin  cos  k  1 1  e 2 k  1 1  e 2  2n   2k  1  Доказательство. По определению коэффициента νj мы имеем Заметим, что image image 2ij e k  1  image cos  image j  . a  ...  2n  1 a j 1 2 image 2       1 j 2 2n  a0 , a1 , ... , an  1 1an  1  an  2 ... an  k an  k  1 0 image 2i e n  1 2n .  2 Из [2] следует, что для нечетных j k  1  Согласно [4] νj (ψ2) = 0 для всех четных j. Будем рассма- image image     1 . тривать только нечетные значения j. Ведем обозначение j 3 n 1  j  2  sin  M = {a0, a1, ... , an - 1}an - k - 1, тогда a  ...  2n  1 a j  2n  image     1 j 2 2n  1an  1  an  2 ... an  k an  k  1 0 image 2i e n  1 2n  Следовательно получим  a   1 M image image  n  1  j    n k a  ...  2n  k  2 a 2n  k a  ...  2n  1 a j  1 2 image image     sin image  2n   j 1  . image  n  1 1an  1 e 0 image 2i n  k  2 2n n  k n  1 j 2  image 2n  j   j  image   2 M a0  ...  2 n  k  1  ...  2 n  1 an  1 j image   sin cos  2n   2k  1  image 2i  1 1an  1  an  2 ... an  k e 2 . Это утверждение позволяет оценить модули чисел ν (ψ ) image 2 n n  j 2 M зная аналогичные коэффициенты для отображения ψ1. Расстояние Хэмминга между функциями Изучим теперь для двух функций f и g из разных классов величину ρ( f, g). Доказательство. Пусть k нечетное. Рассмотрим когда ψ1(u(i)) ≠ ψ4(u(i)). Это происходит тогда и только тогда, когда un  2 i un  3 i  ... un  k i   un  2 i   un  3 i   Утверждение 2. Пусть отображение ψ1 задано равен-  ...  un  k i   u i imageun2 , ... , unk image - нечетное, или ством (1) и ψ3(a) = an - 1, f = fu, ψ , g = fu, ψ . Тогда u , ... , u   1, ... , 1|u , .... , u 0, 1  M, 1  n  n  1 2  m  k  n  2 nk n1 0 image 2m  k  1  2  1 2 3 image  1 2 2 2   f , g  где |M| = 2 n -1 + 2 n - k + 1. Аналогично предыдущему доказаimage n n  1 m тельству получим верхнюю оценку для ρ( f, g): 2  12  1  k  2  2m  k  1  2 2 . 3  2n  12n  1  1 m  n  1  image image    f , g   Nz u   z u  2 2 . 3 Доказательство. Заметим, что ψ1(u(i)) ≠ ψ3(u(i)) тогда и только тогда, когда zM zM   un  2 i un  3 i … un  k i   0  Так как z ≠ 0 получим   n  n  1  m  n  1  un  2 i   un  3 i  …  un  k i   1  image  f , g    2m  n  2  1 2  1 2 2   n  1  u i 2n  1u  2n  2  2n  3  ...  2n  k  zM   3  n  n  1   m  n  1  2n  k  1u image …  u u … u 0, 1  M,  2n  1  2n  k  1  2m  n  2  1 2  1 2 . n  k  1 0 n  1 0  image image 2  3  где |M| = 2n - k + 1. Тогда ρ(f, g) определяется равенством После преобразование последнего выражения получим  2n  12n  1  1 m  k  2   f , g   Nz u, zM  f , g  2 k  2  1 2  m  k  1 image image  2 2 . 3  где Nz(u) - количество появления элемента z  ℤ2 n на отрез- ке ЛРП u. Из [6, теорема 3.2] известна следующая оценка Аналогично доказывается нижняя оценка. Теперь для четного k множество M имеет следующий вид для Nz(u): 2n  12n  1  1 m  n  1 image M  un  2 image , ... , un  k  - нечетное и image image image image 3  n  2 , ... , n  k  image 1, ... , 1 n  1 , ... , u0 0, 1, Nz u  z u  2 2 , u u    u где 2m  n  1, z   u  m  n z  0; где |M| = 2 n -1 - 2 n - k + 1 и доказательство проводится анало- гично. 2 , z  0. Заключение Докажем верхнюю оценку для ρ(f, g): В данной работе для класса булевых функций, построен- ных на основе двоичных разрядных последовательностей  2n  12n  1  1 m  n  1  линейных рекуррент над кольцом ℤ , были получены оценimage image n  f , g   Nz u   z u  2 2   2 zM zM  3  ки для веса функций, нелинейности и расстояний между 2n  12n  1  1 m  k 2 функциями. Отметим, что ранее в работах [2-7] аналогичные image   z u  zM Так как z ≠ 0 получим  f , g  2m  k 1  3 2n  12n  1 3 image 2 2 . image  1 m  k 2 image 2 2 . вопросы были рассмотрены только для случая, когда ψ - линейное отображение по всем двоичным разрядам.