Некоторые нижние оценки на алгебраическую иммунность функций, заданных своими след-формами

Показатель алгебраической иммунности булевой функции характеризует возможность ограничить эту функцию сверху или снизу булевой функцией низкой алгебраической степени, отличной от константы. получены нижние оценки алгебраической иммунности для класса функций, выраженных через операцию инвертирования в поле $GF(2^n)$, а также для более широких классов функций, заданных своими след-формами. в частности, для $n\geq 5$ алгебраическая иммунность функции $\mathrm{Tr}_n(x^{-1})$ имеет нижнюю оценку $\lfloor 2\sqrt{n+4}\rfloor-4$, которая достаточно близка к полученной ранее верхней оценке $\lfloor\sqrt{n}+\lceil n/\lfloor\sqrt{n}\rfloor\rceil-2$. Получен полиномиальный алгоритм, который по след-форме булевой функции $f$ вычисляет порождающие наборы функций степени $leq d$ для следующей пары пространств. каждая функция из первого (линейного) пространства ограничивает функцию $d$ снизу, а каждая функция из второго (аффинного) пространства ограничивает функцию $f$ сверху. При этом каждая функция из порождающих наборов представляется на выходе алгоритма как своей след-формой, так и многочленом от булевых переменных.