On the hamming distance between two bent functions.pdf Булевой функцией от n переменных называется отображение вида / : Fn м F2. Расстоянием Хэмминга dist(/, g) между двумя булевыми функциями / и g от n переменных называется количество значений аргументов, на которых значения функций различаются. Функция вида (a,x)®c, где а е Fn,c е F2 и (a,x) = a1x1 ®a2x2ф.. .®anxn, называется аффинной булевой функцией. Бент-функциями называются булевы функции от чётного числа переменных, находящиеся на максимально возможном расстоянии от множества всех аффинных функций. Они предложены О. Ротхаусом [1]. Бент-функции имеют приложения в алгебре, комбинаторике, теории кодирования, криптографии [2]. Обозначим через множество всех бент-функций от 2k переменных. В данной работе рассматривается расстояние Хэмминга между двумя бент-функ-циями и носитель их суммы. Исследование возможных носителей связано с гипотезой H. H. Токаревой [3] о том, что любую булеву функцию степени не больше k от 2k переменных можно представить в виде суммы двух бент-функций из B2k. Следующая лемма даёт общий критерий принадлежности функции на расстоянии |D| от бент-функции f к классу бент-функций. Лемма 1. Пусть f G B2k. Тогда f ф IndD G B2k, где D С F2k, тогда и только тогда, когда для всех y G F2k справедливо £ (-1)f(x)®

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