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

Введение. Булевы функции нескольких переменных играют важную роль в криптографии и теории кодирования. Композиции этих функций используются в ряде симметрических криптосистем; с их помощью могут быть определены некоторые помехоустойчивые коды, например, коды Рида-Маллера, коды Кердока, а также построены новые декодеры, работающие за пределом половины кодового расстояния. В работе рассматривается задача восстановления булевой функции по ее производной, названная задачей интегрирования булевых функций. При восстановлении булевой функции вектор, в направлении которого вычислена производная, полагается неизвестным.

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

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

Introduction. Boolean functions of several variables are of paramount importance in the coding theory and cryptography. The compositions of these functions are used in a set of the symmetric cryptosystems; therewith, some error-control codes, such as ReedMuller codes, Kerdock codes, can be defined; as well as some new decoders operating beyond half of the code distance can be constructed. The task of restoring a Boolean function from its derivative which is called a Boolean function integration problem is considered. A Boolean function being restored, the vector towards which the derivative is calculated is supposed unknown. Materials and Methods . The results are obtained on the basis of the following methodology: theory of Boolean functions, theory of finite fields and polynomial rings, linear algebra. The space of Boolean functions is considered a certain isomorphic factor-ring that allows reducing the task to finding solutions to a polynomial set of equations of a special form. The constructed isomorphism enables to check whether the integration problem is decidable, and also to offer a new method of its solution.

Research Results. The algorithm of searching preimage by the full enumeration method is formally constructed; and its algorithmic complexity is calculated. The theorem of necessary and sufficient conditions for the existence of an arbitrary Boolean function preimage regarded as the directional derivative value is proved. The provided proofs are constructive. On the basis of the established facts, the algorithms of checking the preimage existence for the specified Boolean function and of building the preimage are developed. In the proposed version, the algorithm forms only one of the possible preimages under the condition of its existence. The proposed algorithm of the preimage generation is significantly efficient from the standpoint of the algorithmic complexity compared to the full enumeration method. Time estimates of the complexity of the basic formal algorithms developed for solving the formulated problems are given. The comparison of their operation complexity to the algorithm of сложности их работы со сложностью алгоритма интегрирования булевых функций методом полного перебора. Обсуждение и заключения. Выполненная работа может быть полезна для специальных разделов криптографии и теории кодирования, в которых используются булевы функции нескольких переменных.

Boolean functions integration complexity by the complete enumeration method is described.

Discussion and Conclusions. The research performed can be useful for special sections of the coding theory and cryptography where Boolean functions of several variables are used.

Введение . Булевы функции нескольких переменных играют важную роль в криптографии и теории кодирования. Например, композиции этих функций используются в ряде симметрических криптосистем [1]; с их помощью могут быть определены, например, помехоустойчивые коды Рида-Маллера и коды Кердока [2, 3] и построены новые декодеры помехоустойчивых кодов, работающие за пределом половины кодового расстояния [3, 4, 5, 6]. Различные вопросы дифференциального исчисления булевых функций рассмотрены в [7, 8, 9]. В теории булевых функций естественным образом возникает понятие производной по направлению, представляющей собой оператор, действующий на пространстве булевых функций. Актуальной является задача исследования свойств данного оператора. В работе рассматривается задача восстановления булевой функции по ее производной по некоторому направлению, определены условия существования прообраза производной булевой функции, описан способ восстановления функции по ее прообразу и даны временные оценки сложности предложенных методов.

Формулировка задачи интегрирования булевых функций. Булевой функцией, согласно [1], назовем отображение f : F 2 ⁿ ^ F 2 , где F 2 ⁿ — векторное пространство размерности n над конечным полем F 2 . Множество булевых функций от n переменных обозначим Ф _n . Известно, что ф _n | = 2 2 . Будем считать, что элементы множеств Ф _n и F 2 упорядочены некоторым образом, например, лексикографически. Производной булевой функции f ( X ) по направлению и , где и * 0 , u е F 2 , называется ( D u f )( X ) еФ _n :

( D u f )( X ) = f ( X + u ) + f ( X ). (1) Функцию f назовем прообразом производной D _u f .

Сформулируем задачу восстановления булевой функции по ее производной, которую далее будем называть задачей интегрирования. Дана булева функция f еФ _n, необходимо найти хотя бы одну функцию g еФ _n, такую, чтобы выполнялось равенство f = D_ug для некоторого U * 0 , U е F ^ .

Необходимые предварительные сведения и результаты. В [1, стр. 69] сформулирована теорема, о том, что каждая функция f е Ф _n может быть единственным образом представлена в виде полинома из кольца полиномов F ₂[ x ₁, x ₂,..., x_n ] , при этом степень полинома по каждой переменной не превосходит 1. Такое представление называется алгебраической нормальной формой (АНФ) булевой функции f .

Утверждение 1. Кольцо Ф _n изоморфно факторкольцу F 2 [х ₁, х 2 ,...,x_n ]/ 1, то есть Ф _n = F 2 [ x₁ , х 2 ,...,x_n ]/ 1, где I =< x² + x₁ , x 2 + x 2 ,...,X 2 + x_n >c F ₂[ x₁ , x 2 ,...,x_n ] — идеал в кольце F 2 [ x₁ , x 2 ,...,x_n ].

Утверждение 1 легко доказать , используя теорему из [1, стр . 69], и тот факт , что F₂[x₁, x₂,..., x_n]/I — факторкольцо , в котором представителями классов смежности являются полиномы , степень которых по каждой переменной не превосходит 1.

Пусть [a] — класс смежности по модулю идеала I в кольце F₂[x₁, x₂,..., x_n] . Тогда из утверждения 1 следует , что [ a ] соответствует некоторой булевой функции f еФ _n . Будем записывать булеву функцию f еФ _n в виде полинома , являющегося представителем класса смежности [a] :

^{f (} x 1 , x 2 ,..., x n ) = a о +E П = 1 a i 1 ^X 1 ₊£ _{l s} 1 <  i 2 _s n a i 1 i 2 ^X 1 x i 2 + ... + ⁽²⁾

Для f , заданной в виде (2) определим биективное отображение у : Ф _n ^ F 2 ² :

Y ⁽ f ) = ⁽ a 0 , ^a 1 ^,-^{, a} 12... n )-                                                              (3)

Обозначим S A все возможные k -элементные подмножества множества A , где k е Z > ₀ -

По аналогии с к -м элементарным симметрическим многочленом [10] определим отображение О к : F 2 [X 1 , x 2 ,---, X r , u 1 , u 2 ,---, U_v ] ^ F 2 [ X 1 , x 2 ,---, X r , U 1 , U 2 ,---, U v ],

^ k ( x 1 , x 2 ^,---^, x r , u 1 , u 2 ^,---^, u v ) = I k                 У 1 У 2 --- У к ,

{y 1 ,y2 ,---,yk }еS{x। ,x2 ,---,xr ,u। ,u2 ,---,uv } где k = 1,r , r, v е N - Положим, что a 0(x,u) = 1, а при k г 1,r, a k(x,u) = 0 -

Теорема 1 (об АНФ производной булевой функции). Для любого f ( x ) еФ _п и u * 0 , u е F , справедливо

⁽ D u f ^{)( x} ) = I k = 1 I 1 < i₁ < i₂ <-< i_k < n a i₁i₂---i_k ^{[ a} k ^{( x}i , ^xi₂ ^, ---, ^xi_k , ^ui 1 ^ ₂ ^, ---, ^u _k ) +                                 ⁽⁴⁾

+x. xi 2 --- xik ' Il j < kxijuijC k-2(x.   x - xij+1 -■■ xik , ui1   j , u. -■■ uik H , где (Duf)(x) еФ n -

Доказательство- Согласно (1) получаем

⁽ D u f ^{)( x} ) = f ^{( x + u} ) + f ^{( x} ) = f ^{( x} 1 + ^u 1 , ^x 2 + ^u 2 ^{,---, x}n + ^un ) + f ^{( x} 1 , ^x 2 ^{,---, x}n ) ^-

Из (2) следует, что f(x1 + u 1,x2 + u2,---, xn + un ) = a0 + I,,=i ai a1 (xi, , ui, ) + 11  11

+Ек,- (a₂( x, , x_f , u,- , u ,- ) + x_f u_f + x_f u, ) + ... +

1 < q <  i 2 <  n q i 2 2 i 1 i 2 i 1 i 2 i 1 i 1 i 2 i 2

+I 1 < i 1 <  i ₂ < --- < i_k <  n a i₁i₂---i_k ^[ ° k ^{( x}i ₁ , ^xi ₂ ^, ---, ^xi_k , ^ui₁ , ^ui ₂ ^, ---, ^ui_k ) ⁺

I 1 < j < k^xi_f^ui,ak - 2 ^{( x}i, ^, ---, ^xi_f , , ^xi_i+ , ^,---, ^xi_k , ^ui, ^, ---, ^ui_f ,, ^ui_i+ , ^,---, ^ui_k ^{)] +} --- ⁺ fl I j I j + 1            k I j I       j + 1            k

+ a 12--- n [ a n ( x 1 , x 2 ,---, x , , u 1 , u 2 ,---, u , ) + Z 1 < j < n xj^ j ^ n - 2 < x 1 ,---, x j ₄, x j+_v ---, x , u 1 ,---, u j ₄, u j + 1 ,---, u , )] -

Суммируя полученное выражение с f ( x 1 , x ₂,---, x_n ), доказываем (4)- •

Установление связи коэффициентов исходной булевой функции и ее производной по направлению.

[ { x е N | m <  x <  n}, m <  n

Пусть [ m -- n ] = <                       , где m , n е N , N — множество натуральных чисел- Обозначим

[       0, n < m через 2A множество всех подмножеств множества A - Пусть

с[m,,n] = {i1---ik I ij е [m--n],i1 <... < ik,k = m,n, j = 1,k} c N -(5)

Обозначим для удобства C _{[0-- n} ] = {0} и C [1 _n ] - Заметим, что C _{[0-- n} ] c Z > ₀, где Z > ₀ — множество целых неотрицательных чисел- Тогда, очевидным образом, можно упорядочить множество C [ _{0 n} ] , используя естественное упорядочение на множестве Z _{> 0} - Пусть

X : C[0--,] ^ N(6)

сопоставляет элементу C [ ₀ , ] его порядковый номер согласно введенному упорядочению (5)- Очевидно, что X является инъективным отображением-

Определим отображение т : 2 ^{[1-- n ]} ^ ^C [1-- , ] ,

T({i1, i 2,---, ik}) = j ij 2--ik, где {/1,i2,---,ik} = {ij- 1,ij2,..., j}; ij 1 < ij2 < ... < j - Очевидно, что т — биекция-

Пусть f еФ _n задана формулой (2), а ( D_uf )( x ) представлена формулой (4)- Упорядочим мономы ( D_uf )( x ) по степеням переменных x 1 , x ₂, ... , x_n :

(Dnf)(x) = [I, FijUj +I a^ujuj + --- + Zk,<,<      a u^u, --juf +... + u i1 =1 i1 i1 ^^1

+ a12---,^u 1^u 2---^u,^{] + I},j1=1^[1,1е[1--п ]\{j1} a T({j1, ij) ^u1^+Ii^^{2 е[1--П Nj1}}, a т({ j1, i1,i₂}) ^u_k^ui₂⁺--- ⁺

• ¹    i^1,i/;x, ⁱ^_I^е[^{1--n ]}\^{j}a т({ j1, i1,---, ik-1}) ^u1 ^ui2--^uik-1 ⁺--- ⁺a12---n^u1^u 2--- ^uj 1-1 ^uj1+1--- ^un^]xj 1 ⁺--- ⁺ 1 <2 <^---<^lk-1

^+I{ j 1, j 2,---, jl }е S [1--, ]^[I'1е[1--n ]\{j1, j₂,---j_;} a т({ j1, j₂,---, j_;, ip) ^u1^+I[^ ² 2^е[1--n^]'^{{j 11 j2},^---jl}, a т({ j1, j 2,---, j_;, Ц, i 2}) ^u1 ^ui 2 ^{+ --- +}

^+-V; i₂<,Ж[¹" ”^]\^{j ^^ j^l}, a T({ h, j 2,-Ji, ^, ik -l}) u1 u 2- uk - l⁺ - ^{+ +}a12-”^Пj е[1..” ]\{ j1, j 2,-Ji} uj^]xj 1 xjVxjl⁺ - ⁺

Согласно теореме 1 (Duf)(x) может быть представлена в виде:

(Duf)(x) = b о + - ” =1 b1 x1 +Z,< _ц<2<_nb_i1i2х_цх₂ +... + -1<i,<i₂<...<k< nb₁i₂...ik^x₁, x₂... xk + ... + ^b12... n^x1^x 2... xn .

Сравним коэффициенты при соответствующих мономах и получим полиномиальную систему, состоящую из уравнений вида:

• ^—Ле[1..”]\{J1,j2,...,ji} at({j1,j2,...,j,,i"1})ui⁺... ^{+ —}i1<²2^e[1..”^]\^{j^1,j^2,...^,j^^,at({j 1,j2,...,j,,i1,i2}ui ui2 ⁺ ^ ^{+ (8)} ■ - i1 '^^ 1..”        ’...’^jl}a t({j1 j j,, i1 ,...,ik -l} ui ui. ...uik -l⁺... ⁺

+a12... ” П j е[1.. ” ]\{ j 1, j 2,..., j,} uj = bj 1 j 2... j; , где {j1, j2,..., ji} ■ 2[1..”]. Пусть 0c 2[1"”] соответствует b0. Очевидно, что b12 n = 0 . Таким образом, система, состоящая из уравнений (8), связывает коэффициенты исходной булевой функции и ее производной по направлению.

Пример. Рассмотрим Ф₂. Тогда система уравнений (8) принимает вид:

a1 и 1 + a₂u₂+ a₁₂u1 u₂= b₀, < a_n u₂= b1, ^a12 ^u 1 = ^b 2,

• .0 = b₁₂.

Рассмотрим Ф₃. Тогда система уравнений (8) принимает вид:

a1 u 1 + a 2 u 2 + a 3 u 3 + a12 u 1 u 2 + a13 u 1 u 3 + a 23 u 2 u 3 + a123 u 1 u 2 u 3 — b0,

• ^a12 u 2 + ^a13 u 3 + ^a123 ^u 2 ^u 3 = ^b1, ^a12 u 1 + ^a 23 u 3 + ^a123 ^u 1^u 3 = ^b 2, ^a13 ^u 1 ^{+ a} 23^u 2 ^{+ a}123 ^u1^u 2 = ^b 3, ^a123^u 3 = ^b12, ^a123 ^u 2 = ^b13, ^a123 ^u1 = ^b 23, .0 = b123.

Далее матрицу системы уравнений вида (8) относительно коэффициентов ai обозначим A е M2n_х(₂n -1) (F₂). Расширенную матрицу системы обозначим через A е M2n_х2n (F₂). Определим условия совместности системы из уравнений вида (8) при любом фиксированном u = (u 1,u₂,...,un) е F₂”. Из теоремы Кронекера-Капелли [10] известно, что СЛАУ совместна тогда и только тогда, когда ранг матрицы системы равен рангу расширенной матрицы. Следовательно, необходимо выбрать подходящие значения коэффициентов bi в (8), чтобы rank(A) = rank(A ). Далее, определив значения bi и aj, построим булеву функцию g и вектор y : Dyg = Duf. Согласно определению производной по направлению из рассмотрения можно исключить случай, когда u = 0 .

Построение множества векторов, имеющих прообразы. Элементы векторного пространства F₂², взаимно однозначно соответствующие булевым функциям пространства Ф _n, для которых существует прообраз, назовем «разрешёнными».           Множество           «разрешённых»           векторов обозначим

Allowed = {у е F₂²| 3f е Ф_n,u * 0 е F₂” : Duf = у^-1(y)}, где у — биекция (3). Множество «запрещенных» векторов пространства булевых функций Ф_n обозначим NotAllowed = F₂²\ Allowed. Очевидно, что Ф” = Allowed и NotAllowed , Allowed о NotAllowed = 0 .

Построим множества разрешенных и запрещенных векторов для Ф1: Allowed = {(0,0), (1,0)}, NotAllowed = {(0,1),(1,1)}. Действительно,

• ^(D (u 1)^f)(x1) = ^a 0 ^{+ a}1^(x1 ^{+ u} 1)^{+ a} 0 ^{+ a}1 ^x1 = ^a1 ^u1.

Положим, что n > 1. Будем последовательно строить множество «разрешённых» векторов пространства булевых функций Ф_n. Построим «разрешённые» векторы при и = (1,0,...,0). Тогда система, состоящая из уравнений (8), содержит следующие уравнения:

ai = b 0,

• 0 = bi,

• a¹ji...jk = bji...jk ,

0=b ,

• 1    j₁... j_k

где 2 < j1 <... < jk < n , 1 < k < n-1. Таким образом, при u = (1,0,...,0) множество «разрешённых» векторов A1, состоит из у е F : V{j1,..., jk} c 2[1"n ]\{1}, где 1 < k < n-1, yX(t({1, j 1,..., jk })) = 0, где X определено формулой (6), т — формулой (7).

При u = (0,...,0,1 i,0,...,0), где i = 1,n , множество «разрешённых» векторов Ai, состоит из у еF22 : V{j1,..., jk} c 2[1.n]\{i}, где 1 < k < n-1, yX(t({i, j 1,..., jk})) = 0 .

Рассмотрим теперь вектор u , который имеет l ненулевых координат и^, ui2, ... , Uj, где 1 < i₁< i₂<... < il< n , 1 < I< n . Положим, что I = {i_bi₂,...,il}. Тогда из системы уравнений вида (8) после подстановки такого и получаем систему, которая будет состоять из уравнений следующего вида:

(9.1)

(9.2)

(9.3)

(9.4)

^Sk =^{1 S{j}1>^j2,..., ^jk^}cSI a^t({j1^,...^^jk^{})      0},

St— |Sf/ Vk a                     = Ь , k =1 ^{j1,J2 ,...,jk }cSI\{i^. , .,ih} t({i1,i2 ,...,ih ,j1,j2 ,...,jk })        т({/1,12 ,...,ih })

0 = b ■ ■ ■ „, t({i1,12,...,il,j1,j2,...,jh }) ’

St- Ski i k к V- a ' к к к к     .■                = Ь ' .' к к к к ,

К =¹^;^j,^j2 ,...,^jk^}cS_|i1,i2,...,d_}^t({i1 ,i2 ,...,id ,j1,j2 ,...,jv ,j1,j2 ,...,jk^{})        t({}i1,i2 ,...,id ,j1,j2 ,...,jv^})

где   {i1,i2,...,ih} c 21,   h = 1,l-1;   {jb j2,..., jh} c 2[1.n]X 1,   h = 1,n-1;   {ц,i2,...,id} c Ud=0SI,   {j1, j2,..., jv} c 2[1.n]X 1, v = 1, n -1.

Строка матрицы A системы уравнений вида (8), соответствующая уравнению вида (9.1), является линейно независимой относительно остальных строк матрицы. Строки, соответствующие уравнениям вида (9.3), являются нулевыми. Выделим среди строк матрицы A, соответствующих уравнениям вида (9.2), линейно зависимые. Для линейной зависимости двух векторов, соответствующие уравнениям вида (9.2), необходимо и достаточно, чтобы в левой части уравнения стояли одинаковые неизвестные. Следовательно, для таких уравнений число фиксированных координат, фигурирующих при индексе свободных членов, должно быть одинаково.

Рассмотрим два уравнения, соответствующие линейно зависимым строкам:

^SkJ ^S{ jf¹), j 0),..., j<¹>}cS^k_{m m} m^a_T(lii i i (1) /1) ,-(1) ,-(1) ,-(1) ,-(1)< 1 = b_T( н (1) ,-(1) ,-(1))V

• ¹    ,J2 ,,J^kI\,i(¹⁾i(1) ipv ^t({i1,i2 ,...,iz ,iz+1,iz+2 ,...,ih ,^j 1 ,^j2 ,...,^jk^{}) т({i}1 ,i2 ,...,ih^}) 1 ,2 ,..., h

l h ^sk =1 ^s{j(²⁾,j(²⁾,...,j(²⁾}cS^k                 a                (2)/(2) /2) ,-(2) .-(2) /2) = b (2) -(2) -(2) ,

• ^{1   ,}J2   ^,,J k   *     i\{ i(²⁾i⁽²⁾   i (2L    ^т({i1, i 2,..., iz , iz+1, iz+2,..., ih   ,^j 1   ,^j 2   ,..., ^jk   ^{})        T({i}1   , i 2   ,..., ih   ^})

• 1    ,2 ,..., h

• (1)    (1) (1)        (2) (2) (2)       (1) (1)        (1)        (1) (1) (1) (2) (2) (2)

^{где {i}1, i 2,..., iz } = ^{i1  , i 2  ,..., ih } ^{n {i}1   , i 2  ,..., ih  }, ^{iz+1, iz+2,..., ih  } = ^{i1  , i 2  ,..., ih  ^}X{i1   , i 2  ,..., ih  } ^^ ,

Следовательно, в силу произвольности выбора элементов J® и j^²’, h = l -1. Таким образом, для того чтобы два вектора из матрицы A, соответствующих уравнениям вида (9.2), со свободными членами равными b₍₀ ,₍i) ,₀) и ^т({i , i 2 ,..., ih^})

b ,._{(2) (2)} -_(2)oбыли линейно зависимы необходимо и достаточно, чтобы выполнялись условия ^т({ii ,i2 ,...,ih^})

h = l -1,

• (1)    (1) (1) (2) (2) (2)

{i1 , i2 ,..., ih }A{i1 , i2 ,..., ih } = ii, J}, где I \{i1(), 12’,..., ih’} = {i}, I\{i1( ’, 12 ’,..., ih ’} = iJ}, а знак « A » обозначает симметрическую разность множеств.

=zd=2^ad zk-i z_{y<d)^jd) Jkd>_}cSi d) d)   da_T(_{ii ,i₂ ,...,iz,iz+■>_л+) ,...,ihd)jd)jd),...,jd)_}),

1 ,2 ,—, h где iiz+),iz+2,...,ihd’} = {iid’,i2d’,...,ihd)}\B, B = ii,i2,...,iz} = ПfU#d’,i2d’,...,ihd’}.

Рассмотрим некоторый

коэффициент из левой части равенства a ... . . ,(i) ,(i)   ,₍i) .(iv,. Так как h< n, то без

^т({ii, i 2,..., iz , iz+1, iz+2,..., ih , ^J1 ^})

нарушения общности aт({ii,i2,...,iz,£1,i^ ,...,ih”,jf1’})    Zd=2 aiat({ii,i2,...,iz,id,i(+2,...,ihd’,j(d’}) °

(d) ,•(d)      ,•(d) „(d)      ,

^т({ii, i 2,..., iz , iz+1 , iz +2,..., ih    , ri    ^}’

° a т({ ii, i 2,., iz, iz+i, iz+2,.., ih1’, Jf)}’ =zdi+22 a где 2к + 2 < g , к е Z>0, a т({ ii, i 2,...,iz, iz+i, iz+2,., ih1’, jC’}’ = a т({1, i 2,..., iz, iz+1’, iz+2,..., ihd ’, ri(d ’}’.

Из предыдущих рассуждений следует aт({ii,i2,...,iz,iz+i,iz+2,...,ih”,J(1)}) = aт({ii,i2,...,iz,iz+1’,iz+2,...,ihd’,ri(d’}’ °

;(1) _e(dd) /(d)      /(d)1 _r(i’ _e //(1) ;(1)       v(1)

° ^J1^{е {i}z+1, iz+2,...,ih^}, ^r1 ^е{iz+1,iz+2,...,ih^}, h = ^{z + j}.

Таким образом, верны равенства aт({ii,i2 ,...,iz ,-<+’ ,-)+1’}) aт({ii,i2 ,...,iz ,iz+1’,i-z+’i }) , где i = 1,2к +1. В проведенных рассуждениях элементы J1(1) и J1d’ выбраны произвольно, d = 2,2к + 2, h = l -1. Таким образом, доказана следующая лемма.

Лемма 1. Линейно зависимые строки матрицы A системы уравнений вида (8), соответствующие уравнениям вида (9.2), при подстановке вектора и с l ненулевыми координатами I = {u^, ui 2,..., u^}, где 1 < i₁< i₂<... < il< n ,

• 1    < l< n , имеют вид

a . . . = b . . т({ii,i2,...,il-1,J})        т({ii,i2,...,/_м}) ’

' '                '                           _                        ' '                '

где {ii,i2,...,il_i} c S¹; ^j; I\{ii,i2,...,i^} = {j}. •

Теперь выделим линейно зависимые строки матрицы A системы уравнений вида (8) среди соответствующих уравнениям (9.4). Легко увидеть, что уравнения (9.2) отличаются от уравнений (9.4), наличием в последних среди фиксированных индексов свободного члена и неизвестных элементов, не принадлежащих множеству I номеров позиций ненулевых координат вектора и , подставляемого в (8). Но суммирование в левой части обоих уравнений ведется по некоторому подмножеству I, которое является одинаковым для обоих видов уравнений (9.2) и (9.4). Таким образом, применяя рассуждения аналогичные рассуждениям для случая уравнений вида (9.2), можно убедиться, что верна

Лемма 2. Линейно зависимые строки матрицы A системы уравнений вида (8), соответствующие уравнениям вида (9.4), при подстановке и с l ненулевыми координатами I = {и^,ui2,...,uil}, где 1 < i1 < i2 <... < il < n, 1 < l < n , имеют вид a ' / / / / / = b ' / / / /     •'   ,

^т({ii , i 2 ,..., il-1 , ^J1 ,^J 2 ,..., ^Jv ,^{J})         т({}ii , i 2 ,..., il-1 , ^J1 ,^J 2 ,..., ^Jv^})

il-i} = ^{J}, ^{J1,^J ;■■•■ ^J'v^cS[1.. n ]\I^}, ¹< ^v< ^{n -}l. •

где {ij,i2,...,il-i} c SI^-1, I\{ij,i2

Таким образом, в общем случае, когда и имеет l ненулевых координат I = {u^,ui2,...,ul}, где 1 < i1< i₂<... < il< n , 1 < l< n , из лемм 1 и 2, а также формул (9.1)-(9.4) следует, что множество «разрешенных» векторов A,2 il состоит из векторов y е F , для коэффициентов которых выполняются следующие свойства:

• 1.    У                         = 0, V{ j _ь j₂,..., j _h} c 2^[1"ⁿ ]\I, h = 1, n -l;

Mt({i1, i 2,..., il, j1, J 2,..., Jh }))                   ^{1 J2 ,Jh}

• ' .'            .'                                                              1 -1

• ²    y Цт({ i1, i₂,..., /Д})) = y X(t({i|, i 2,..., il-1})) ^{: V{}i^b i^2,...^,il^-1}, {i^1,i^2,...^,il^{-1} c}SI^;

• 3.    ^Wi /'         /'   = У T / ^{: V{}i1’i2’-’il-1^}, ^{i1,i2,-,il-1^}■ SI ’ при фиксированном

• 4.    все элементы вектора y е F₂², не определенные свойствами 1-3, являются произвольными элементами поля F₂ .

' .' .'                                          ."                    l -1

^^(T(li1,i2 ,...,il-1, ^J1,j2 ,...,jv^}))         ^^(T(li1 ,i2 ,...,il-1, ^J1,j2 ,...,jv^}))

^{Л, j 2,-, ^jV^{} c}SV.. n ]\i,¹<^v< n^-1;

Теорема 2 (о существовании производной по направлению). Рассмотрим Ф_n. Пусть вектор и е F₂ⁿ содержит l ненулевых координат I = {и^, ui 2,..., u_t}, где 1 < i1< i₂<... < i_l< n , 1 < l< n . Положим, что Ai1 i 2 i_l — множество «разрешенных» векторов, определенных при подстановке в систему уравнений вида (8) вектора u . Для булевой функции g е Ф _n существует такая булева функция f, что

• ⁽Duf⁾⁽x) = g⁽x) ^ У⁽g)^еUiеC_[1.._n]Ai ,

где у — биекция (3); С[1.._n] определено (5).

Доказательство. Докажем, что Ui_еС[1 ] Ai = Allowed . Если это равенство верно, то утверждение теоремы будет выполняться в силу определения множества Allowed .

Очевидно, что в силу своего построения Ui_еС[1 ] Ai c Allowed . Множество Aii2 i_l содержит все возможные вектора свободных членов b , при которых система уравнений вида (8) совместна при подстановке вектора u . Пусть w е Ai-1 i2 i_l. При фиксировании w в качестве свободных членов системы (8) можно найти все возможные решения данной системы, которые определяют все булевы функции f еФ _n: Duf = y^-1(w). Поскольку при построении множеств Ai, i е С[1.._n], перебираются все вектора u е F₂ⁿ, кроме нулевого, то Allowed c Ui_еС[1 ] Ai . •

Алгоритм определения существования прообраза. Представим в краткой форме алгоритм, позволяющий определить существование для данной булевой функции прообраза. На вход алгоритма поступает булева функция g^еФn⁽ⁿ>1), на выходе алгоритм выдает значение true, если прообраз для входной функции существует, иначе, при отсутствии прообраза, алгоритм возвращает значение false . Будем рассматривать алгоритм в виде двух частей, которые обозначим как алгоритмы А и Б. Алгоритм А определяет возможное направление, по которому была взята производная и отправляет его на вход алгоритма Б, который проверяет существует ли прообраз для булевой функции, поступившей на вход алгоритма с учетом выбранного направления.

Рассмотрим работу алгоритмов. На вход алгоритма А поступает вектор у(g) = (g 1,..., g₂„) е F₂². Выполняется проверка значения коэффициента g₂n . Если этот коэффициент ненулевой, то согласно теореме 2 прообраза не существует, и алгоритм выдает false , иначе алгоритм продолжает работу. Далее алгоритм А формирует вектор u = (g-^n 1,gon о,...,gon ) е Fi , в направлении которого была предположительно взята производная, при условии, что 2 -1 2 -2       2 - n²

u * 0 . Объяснение этого предположения легко видеть из (8). Если u * 0 , то происходит вызов алгоритма Б, работа которого описана ниже, иначе, если u = 0 , в цикле происходит последовательный перебор всех ненулевых векторов, принадлежащих F₂ⁿ , которые подаются на вход алгоритма Б в качестве предполагаемого вектора, в направлении которого была взята производная. Если при выполнении алгоритма Б было установлено существование прообраза, то алгоритм А возвращает true .

Опишем работу алгоритма Б. На его вход которого поступают векторы у(g) е F22 и u е F2n. Алгоритм Б проверяет выполняются ли для входного вектора у(g) необходимые и достаточные условия существования прообраза по заданному направлению и , то есть определяет принадлежность вектора у(g) множеству Ai-1 i2 il , где i1 i2...il e C|| n], Wu = {ibi2,...,il}, множество Wu содержит номера ненулевых элементов вектора и . Для поиска ответа алгоритм последовательно проверяет выполнение свойств 1-3 (см. список перед теоремой 2) для заданного входного вектора. Если входной вектор удовлетворяет всем трем свойствам, то, согласно теореме 2, можно утверждать, что для булевой функции, взаимно однозначно соответствующей данному вектору, существует прообраз в заданном направлении, и, следовательно, алгоритм Б возвращает значение true, иначе, при невыполнении хотя бы одного из условий, алгоритм возвращает false .

Авторами получена оценка временной сложности алгоритма O(n + 2³n). Доказательства оценки сложности данного алгоритма и других алгоритмов, представленных ниже, в данной работе не приводится в связи с их громоздкостью.

Пример.

Рассмотрим Ф ₃. Пусть

Y⁽g⁽x1, x2, x3)) = ⁽g 1, g2, g3, g4, g5, g6.g7, g8 ) = (l,l,0,l,0,0,0,0) £ F^², g^(x1, x2,x3) = ^{1 + x}1 ⁺x3, где g(x_bx2,x3)eF2Vx_bx2,x3].

Поскольку g₈= 0 , то пока нет оснований утверждать, что прообраза не существует. Рассмотрим вектор й = (g₇, g₆, g₅) = (0,0,0) e F₂³. Следовательно, будем перебирать все ненулевые вектора F₂³в поисках подходящего направления. Упорядочим элементы F₂³следующим образом:

(0,0,0) < (1,0,0) < (0,1,0) < (0,0,1) < (1,1,0) < (1,0,1) < (0,1,1) < (1,1,1).

Пусть и = (1,0,0). Тогда Wu = {1}, 2^[1"^3]\Wu = {0,{2},{3},{2,3}}. Очевидно, что g_ад = g₂ = 1, то есть вектор и не удовлетворяет свойству 1 (см. список перед теоремой 2). Следовательно, алгоритм 1.2 возвращает значение false .

Пусть и = (0,1,0). Тогда Wu = {2}, 2^[1"^3]\Wu = {0,{1},{3},{1,3}}. Вектор и удовлетворяет свойству 1: gЦ2) = g3 = 0 , g_Х(12) = g5 = 0, g_M23) = g7 = 0 ^иgX(123) = g8 = 0 . Далее 5;0 = ^{0}, то есть нет необходимости проверять выполняется ли свойство 2. Проверим выполнение свойства 3 для вектора и . 5[*₁₃]\_W_ = {{1},{3}}, следовательно g_Х(1)= g₂= 1, g_Х(3)= g₄= 1. Далее 5_[2.._3]\W = {{1,3}}, следовательно g_Х(13)= g₆= 0, то есть вектор и удовлетворяет свойству 3. Поскольку вектор и удовлетворил всем трем свойствам, то согласно теореме 2 для g(x_b x₂, x₃) существует прообраз. Следовательно, алгоритм А, а затем и алгоритм Б, выдает на выход значение true. •

Способ поиска интеграла булевой функции. Опишем еще один подход к решению задачи интегрирования булевых функций. Положим, что для фиксированного вектора при помощи алгоритма существования прообраза установлено, что решение существует. Легко увидеть, что при работе этого алгоритма находится вектор, в направлении которого взята производная. Таким образом, из теоремы 2 следует, что система уравнений вида (8) при подстановке в нее найденного вектора совместна и неопределенна. То есть можно построить общее решение I10] для этой системы, приняв в качестве неизвестных a_i , где i e C_I1..n] , и выбрав в качестве неизвестного a₀ произвольный элемент поля F₂. Заметим, что ai являются коэффициентами прообраза булевой функции, поступившей на вход алгоритма поиска прообраза. Можно использовать любой прямой метод для решения данной СЛАУ. К примеру, если использовать метод Гаусса [10], сложность которого равна O(n³), где n — количество неизвестных, встречающихся в системе, то можно показать, что асимптотическая оценка сложности решения задачи интегрирования булевой функции (с использованием метода Гаусса для решения СЛАУ) составляет O(n + 2³n) + O(2³n) = O(n + 2³n). Авторами также установлено, что при использовании метода полного перебора для поиска прообраза, сложность решения задачи интегрирования булевой функции равна O(2²⁺²"^-2(3п +10) + 2³n + n). Таким образом, использование предложенных методов уменьшает алгоритмическую сложность поиска прообраза по сравнению с методом полного перебора примерно в O(2²ⁿ ) раз.

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