Decomposition of a boolean function into sum of bent functions.pdf Булева функция от чётного числа переменных, максимально удалённая от классавсех аффинных функций, называется бент-функцией. В работах [1, 2] исследованасвязь между вопросом о числе бент-функций и проблемой разложения произвольнойбулевой функции в сумму двух бент-функций. Была представлена серия гипотез, однаиз которых заключается в том, что каждую булеву функцию от n переменных степенине больше n/2 можно представить в виде суммы двух бент-функций от n переменных.В [2] с помощью компьютера гипотеза проверена для малых значений n ^ 6.В 2011 г. Л. Ку и С. Ли [3] разобрали случай малых n аналитически. В общем случаеони доказали, что в виде суммы двух бент-функций может быть представлена любаяквадратичная булева функция, любая бент-функция Мак-Фарланда, любая функциячастичного расщепления (partial spread function).В данной работе доказан ослабленный вариант гипотезы.Теорема 1. Любая булева функция от n переменных степени d, где d ^ n/2,n чётно, может быть представлена в виде суммы не более чем 2 ( b ) бент-функцийот n переменных, где b - наименьшее число, b ^ d, такое, что n делится на 2b.Заметим, что разложение, указанное в теореме, можно провести с помощью толькобент-функций Мак-Фарланда.

Скачать электронную версию публикации