Алгоритм быстрого умножения элементов в 2-группах на основе полиномов Жегалкина

Проектирование сети многопроцессорной вычислительной системы или дата-центра представляет собой важную проблему, в рамках которой осуществляется поиск моделей графов, обладающих привлекательными топологическими свойствами и позволяющих применять эффективные алгоритмы маршрутизации. Указанными свойствами, в частности такими, как высокая симметрия, иерархическая структура, рекурсивная конструкция, высокая связность и отказоустойчивость, обладают графы Кэли. Например, такие базовые топологии сети, как «кольцо», «гиперкуб» и «тор», являются графами Кэли. Определение графа Кэли подразумевает, что вершины графа являются элементами некоторой алгебраической группы. Выбор группы и ее порождающих элементов позволяет получить граф, отвечающий необходимым требованиям по диаметру, степени вершин, количеству узлов и т. д. Решению данной задачи посвящено большое количество научных статей и монографий. Для исследования графов Кэли, в первую очередь, необходимо разработать быстрые алгоритмы умножения элементов в данных группах. Такие алгоритмы помогают осуществлять эффективную маршрутизацию на соответствующих графах Кэли. Цель настоящей работы - создать алгоритм быстрого умножения элементов в конечных 2-группах, т. е. в группах периода 2n. В первом разделе статьи дано теоретическое обоснование алгоритма. Показано, что элементы данных групп могут быть представлены в виде битовых строк, а их умножение осуществляется на основе полиномов Жегалкина. Во втором разделе представлен псевдокод алгоритма, на основе которого вычисляются полиномы Жегалкина. На первом этапе алгоритма вычисляется pc-представление группы, на основе которого получают полиномы Холла. На заключительном этапе полиномы Холла преобразуются в полиномы Жегалкина. В третьем разделе продемонстрирован пример получения полиномов Жегалкина для двупорожденой группы периода 4. В заключении рассматриваются перспективы применения алгоритма на реальных вычислительных устройствах. Отмечается, что предложенное представление элементов группы в форме битовых векторов позволяет применять их даже на самых примитивных микроконтроллерах.