В. Г. Никонов, А. В. Саранцев, “О сложности совместной реализации в базисе ДНФ регулярных систем булевых функций”, Матем. вопр. криптогр., 2010, том 1, выпуск 3,страницы 45

Эта публикация цитируется в 3 статьях

О сложности совместной реализации в базисе ДНФ регулярных систем булевых функций

В. Г. Никонов^a, А. В. Саранцев^b

^a Академия криптографии РФ, Москва
^b ООО "Центр сертификационных исследований", Москва

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

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

УДК: 510.52, 512.622

Получено 22.IV.2010

DOI: 10.4213/mvk15