Просмотр кода страницы Участник:One/Алгоритм распределения булевых функций на гиперсфере

Автор - Бартель Артем.

Одним из самых интересных свойств булевых функций, часто используемых в криптографии, является нелинейность. Для булевых функций, зависящих от четного количества переменных существует точная формула для подсчета нелинейности, а вот с функциями, зависящими от нечетного числа переменных такой формулы нет. Конечно же, существует общая формула вычисления нелинейности, но при достаточно больших <math>n</math> (количество переменных) ей практически невозможно пользоваться, так как она подразумевает перебор всех возможных векторов длины <math>n</math>. Именно поэтому хочется попытаться расширить используемый математический аппарат, чтобы получить более удобное решение поставленной проблемы. В данной статье будет рассматриваться метод распределения булевых функций на гиперсфере. На основе этого метода будут предприняты попытки нахождения закономерностей и связей между степенью нелинейности булевой функции и ее расположением на гиперсфере в евклидовом пространстве.

== Свойства и структура алгоритма ==
 
=== Общее описание алгоритма ===
 
Объекты, с которыми работает данный алгоритм - булевы функции. Фактически, при задании <math>n</math> - количество переменных, от которых зависит функция - будет выполнен полный перебор всех возможных векторов длины <math>2^{n}</math> (это вектора, которые соответствуют значениям, которые функция принимает на всевозможных лексико-графически упорядоченных наборах длины <math>n</math>), количество коих равно <math>2^{2^{n}}</math>. Для каждого такого вектора будет подсчитана нужная характеристика - спектр Уолша, на основе которой будет составляться вектор так называемой функции-сектора, которая отвечает за то, в каком секторе гиперсферы находится исследуемая функция. На основе полученного распределения булевых функций на гиперсфере будут предприняты попытки нахождения зависимостей между функцией-сектором данной булевой функции и ее показателем нелинейности. Конечно же, особое внимание уделяется функциям, зависящим от нечетного числа переменных.

=== Математическое описание алгоритма ===

Через <math>V_{n}</math> обозначим множество всевозможных двоичных векторов длины <math>n</math>. Тогда отображение <math>f: V_{n} → V_{n}</math> - булева функция. Коэффициентом Уолша заданной функции на векторе <math>u</math> называется величина <math>W_{f}(u)</math>, определяемая формулой: <center><math>W_{f}(u) = Σ_{x\in V_{n}} (-1)^{f(x)+<u,x>}</math>,</center> где <math><u,x></math> - скалярное произведение соответствующих векторов: <math><u,x> = Σ_{i=1}^{n}x_{i}u_{i}</math>, где <math>Σ</math> - сложение по модулю 2. Соответственно спектром Уолша данной функции называется вектор вида <math>(W_{f}(0^{n}), ..., W_{f}(1^{n}))</math>. 
На основе данного вектора составляется вектор значений функции-сектора <math>g(x)</math> по правилу:
<center><math>W_{f}(x)>0 → g(x) = 0; W_{f}(x)<0 → g(x) = 1</math></center>
Таким образом, мы получаем вектор значений функции, которая 'нумерует' определенную секцию гиперсферы. Легко видеть, что для булевых функций, у которых существует хотя бы один нулевой коэффициент Уолша, невозможно точно и однозначно определить секцию, в которой они лежат, то есть они находятся на стыке двух секторов. 
В дальнейшем будут исследоваться свойства полученных функций-секторов и их взаимосвязь с исходными булевыми функциями.

=== Вычислительное ядро алгоритма ===

=== Макроструктура алгоритма ===

=== Схема реализации последовательного алгоритма ===

=== Последовательная сложность алгоритма ===

=== Информационный граф ===

=== Ресурс параллелелизма алгоритма ===

=== Входные и выходные данные алгоритма ===

=== Свойства алгоритма ===

== Программная реализация алгоритма ==

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

=== Масштабируемость алгоритма и его реализации ===

=== Динамические характеристики и эффективность реализации алгоритма ===

=== Выводы для классов архитектур ===

=== Существующие реализации алгоритма ===


== Литература ==

# ↑ О.А. Логачев, С.Н. Федоров, В.В. Ященко. Булевы функции как точки гиперсферы в евклидовом пространстве // Общероссийский математический портал Math-Net.ru. 2018, том 30, выпуск 1, стр. 39-55
# ↑ О.А. Логачев, А.А. Сальников, С.В. Смышляев, В.В. Ященко. Булевы функции в теории кодирования и криптологии. 2012.
# ↑ Tomas Cusick, Pantelimon Stanica. Cryptographic Boolean Functions and Applications. 2009.