Вычисление минимальной степени многочлена над конечным полем для векторного булевого отображения, заданного полиномами Жегалкина
Authors: БЕЛОВ С.А. 
Published: January 2025

Рассматриваются векторные отображения над множеством из нуля и единицы, заданные множеством булевых функций. Булевы функции, входящие в отображение, в свою очередь, задаются полиномами Жегалкина. Зафиксировав правило, по которому двоичным векторам ставятся в соответствие элементы конечного поля характеристики два, получаем взаимно-однозначное соответствие между отображениями векторного пространства в себя и функциями над конечным полем. Конечное поле рассматривается как кольцо многочленов с операциями сложения и умножения по модулю выбранного неприводимого многочлена. Известно, что любую функцию над конечным полем можно записать в виде полинома. При этом для различных неприводимых многочленов полиномы над конечным полем, соответствующие заданному векторному отображению, в общем случае, могут быть различными и иметь различные степени. Рассматривается задача поиска такого неприводимого многочлена, чтобы степень полинома над конечным полем была минимальной, при условии, что соответствие между двоичными векторами и элементами конечного поля задаётся использованием полиномиального базиса конечного поля.  Для решения задачи булевы функции представляются своими трейс-формами. Из этого представления коэффициенты полинома над конечным полем выражаются через элементы дуального базиса конечного поля. Затем элементы дуального базиса выражаются через полиномиальный базис конечного поля и коэффициенты неприводимого многочлена. Таким образом, коэффициент полинома над конечным полем выражаются в полиномиальном базисе конечного поля. Полученные уравнения сводятся к системе булевых уравнений для коэффициентов неприводимого многочлена. Для решения системы булевых уравнений используется SAT-решатель. Приведены оценки сложности получения указанной системы булевых уравнений.

We consider vector mappings over the set of 0 and 1 given by the set of Boolean functions. Boolean functions included in the map are given in ANF. Having fixed the rule according to which the binary vectors are associated with the elements of a finite field of characteristic two, we obtain a one-to-one correspondence between the mappings of the vector space into itself and the functions over the finite field. The finite field is considered as a ring of polynomials with the operations of addition and multiplication modulo the selected irreducible polynomial. It is known that any function over a finite field can be written as a polynomial. Moreover, for various irreducible polynomials, the polynomials over a finite field, corresponding to a given vector map, may in general be different and have different properties. We consider the problem of finding an irreducible polynomial such that the degree of a polynomial over a finite field is minimal, provided that the correspondence between binary vectors and elements of a finite field is given by using a polynomial basis of a finite field. We present an algorithm to solve this problem. Firstly we rewrite Boolean functions in trace form and calculate expressions for finite field polynomial coefficients. Then we calculate elements of dual basis as an expression of polynomial basis. Using them we obtain system pf Boolean equations. Finally we solve system of Boolean equations by SAT-solver and filter reducible polynomials. We estimate of the complexity of obtaining the specified system of Boolean equations is bitwise operations.