A new combinatorial construction of bent functions.pdf Бент-функции впервые были введены О. Ротхаусом [1]. В настоящее время ониактивно изучаются и имеют много приложений в теории кодирования, криптографии,цифровой сотовой связи и других областях (см. подробнее обзоры [2, 3]). Тем не менеев области бент-функций много открытых вопросов. Одними из основных являютсявопросы о конструкциях бент-функций и оценках их числа.В работе предложена новая итеративная конструкция бент-функций от n + 2 переменныхна основе бент-функций от n переменных. В дальнейшем представляетсяинтересным исследовать те нижние оценки числа бент-функций, которые следуют изэтой конструкции.Напомним, что преобразованием Уолша - Адамара булевой функции f от n переменныхназывается целочисленная функция Wf (y) = Е (-1)^x,y^+f(x). Булевафункция от n переменных (n четно), такая, что модуль каждого коэффициентаУолша - Адамара этой функции равен 2n/2, называется бент-функцией. С бент-функцией f часто связывают дуальную булеву функцию, которая определяется равенством2n/2(-1)^(y) = Wf (y). Функция f также является бент-функцией, f = f .Пусть булева функция g от n + 2 переменных определяется равенством#(аь а2,х) = f i (х ), где i = a + 2й2,и f 0, f 1, f 2 и f 3 - булевы функции от n переменных.Теорема 1. Пусть f 0, f 1, f 2 - бент-функции. Тогда g является бент-функцией отn + 2 переменных тогда и только тогда, когда функция f 0 + / 1 + f 2 - бент-функция.В этом случае f 3 также является бент-функцией, причем она однозначно определяетсяравенством fo + ,/1 + ./2 + Уз = 1.Пусть Bn - множество бент-функций от n переменных.Непосредственно из теоремы вытекаетСледствие 1. Для числа бент-функций от n переменных справедлива оценка|Bn| ^ Е Е | (Bn-2 + fo) П (Bn-2 + f 1) |.fo eBn_2 fi€Bn_2Например, несложно заметить, что при любых f 0, f 1 выполняется| (Bn-2 + fo) П (Bn-2 + f 1) | ^ 2n-1.Тогда из следствия сразу получается нижняя оценка вида 22"/2 (типа Мак-Фарланда)на число бент-функций от n переменных. Интересно найти более нетривиальные вариантыоценки из приведенного следствия.

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