Точные соотношения между нелинейностью и алгебраической иммунностью

Усилены некоторые нижние оценки нелинейности высоких порядков булевой функции через значения её алгебраической иммунности и получены новые точные оценки. Доказана универсальная точная нижняя оценка, позволяющая сводить проблему оценки нелинейности высоких порядков к проблеме поиска размерности некоторых линейных подпространств в пространстве булевых функций. Как простое следствие этого результата получены все ранее известные оценки в этой области. Для бесповторных полиномов поиск размерности упомянутых выше линейных подпространств в пространстве булевых функций сведён к простому комбинаторному анализу. Для булевой функции доказана точная нижняя оценка её нелинейности второго порядка через значение алгебраической иммунности. Табл. 1, библиогр. 9.