RUS  ENG
Полная версия
ЖУРНАЛЫ // Математические вопросы криптографии // Архив

Матем. вопр. криптогр., 2011, том 2, выпуск 4, страницы 37–47 (Mi mvk42)

О числе существенных переменных равновероятной булевой функции с фиксированным количеством элементарных конъюнкций в ДНФ

В. Г. Никонов

Академия криптографии Российской Федерации, Москва

Аннотация: Получены верхние и нижние оценки числа $n(k)$ существенных переменных равновероятной булевой функции, заданной в виде ДНФ с помощью $k$ элементарных конъюнкций. Ограниченность числа $n(k)$ для любого $k$ была доказана автором ранее. Равновероятные булевы функции представляют первостепенный интерес для криптографических приложений, а их представлению в виде ДНФ соответствует реализация на современной элементной базе, в частности, с помощью программируемых логических матриц.

Ключевые слова: булева функция, дизъюнктивная нормальная форма, числа Фибоначчи.

УДК: 519.714.83

Получено 23.VI.2010

DOI: 10.4213/mvk42



© МИАН, 2024