RUS  ENG
Полная версия
ЖУРНАЛЫ // Прикладная дискретная математика // Архив

ПДМ, 2011, номер 1(11), страницы 26–33 (Mi pdm266)

Теоретические основы прикладной дискретной математики

О числе совершенно уравновешенных булевых функций с барьером длины $3$

С. В. Смышляев

Московский государственный университет им. М. В. Ломоносова, г. Москва, Россия

Аннотация: Рассматривается класс булевых функций с барьером длины $3$, вложенный в множество совершенно уравновешенных булевых функций. Получены нижняя и верхняя оценки для мощности класса булевых функций с правым барьером длины $3$, существенно зависящих от последней переменной, а также новая нижняя оценка логарифма числа совершенно уравновешенных булевых функций $n$ переменных, существенно и нелинейно зависящих от крайних переменных: $2^{n-2}\left(1+\dfrac{\log_25}4-\mathrm O(1/\sqrt n)\right)$.

Ключевые слова: совершенно уравновешенные функции, барьеры булевых функций, криптография.

УДК: 519.7



© МИАН, 2024