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

Полный текст

Введение

Проектирование сети многопроцессорной вычислительной системы (МВС) или дата-центра представляет собой важную проблему, в рамках которой осуществляется поиск моделей графов, обладающих привлекательными топологическими свойствами и позволяющих применять эффективные алгоритмы маршрутизации. Указанными свойствами, в частности такими, как высокая симметрия, иерархическая структура, рекурсивная конструкция, высокая связность и отказоустойчивость, обладают графы Кэли [1]. Например, такие базовые топологии сети, как «кольцо», «гиперкуб» и «тор», являются графами Кэли.

Определение графа Кэли подразумевает, что вершины графа являются элементами некоторой алгебраической группы. Выбор группы и ее порождающих элементов позволяет получить граф [2], отвечающий необходимым требованиям по диаметру, степени вершин, количеству узлов и т. д. Решению данной задачи посвящено большое количество научных статей и монографий, среди которых выделим работы [3–15].

Как было сказано, одной из широко применяемых топологий МВС является k-мерный гиперкуб. Данный граф задается k-порожденной бернсайдовой группой периода 2. Данная группа имеет простую структуру и равна прямому произведению k экземпляров циклической группы порядка 2. Обобщением гиперкуба является n-мерный тор, который порождается прямым произведением n экземпляров циклических подгрупп, порядки которых могут не совпадать. В статьях [16–19] изучаются графы Кэли бернсайдовых групп периода 3, 4, 5 и 7.

Для исследования графов Кэли, порожденных группами бòльших периодов, в первую очередь необходимо разработать быстрые алгоритмы умножения элементов в данных группах. Такие алгоритмы помогают осуществлять эффективную маршрутизацию на соответствующих графах Кэли.

Цель настоящей работы – создать алгоритм быстрого умножения элементов в конечных 2-группах, т. е. в группах периода 2ⁿ. 

В первом разделе статьи дано теоретическое обоснование алгоритма быстрого умноженияв конечных 2-группах. Показано, что элементы данных групп могут быть представлены в виде битовых строк, а их умножение осуществляется на основе полиномов Жегалкина.

Во втором разделе представлен псевдокод алгоритма, на основе которого вычисляются полиномы Жегалкина.

В третьем разделе продемонстрирован пример получения полиномов Жегалкина для двупорожденой группы периода 4.

В заключении рассматриваются перспективы применения алгоритма на реальных вычислительных устройствах.

1. Доказательство основного результата

Теорема. Пусть G – произвольная конечная группа 2-группа, порядок которой равен .Тогда будут верны следующие утверждения:

1. $\forall x\in G\Rightarrow x=\left(x_1\mathrm{,...,}{x}_n\right)\in {\mathbb{Z}}_2^n.$
2. $\forall x,y,z\in G:x\cdot y=z\Rightarrow z_i=f_i(x,y)\in {\mathbb{Z}}_2$, где $f_i(x,y)$ – некоторые полиномы Жегалкина.

Доказательство. Любая конечная 2-группа G имеет pc-представление (power commutator presentation [3; 4]):

$G=\{a_1,\dots ,a_n\mid a_i^2=v_{ii}\mathrm{,1}\le i\le n,[a_k,a_j]=v_{jk}\mathrm{,1}\le j<k\le n\},$

где слово $v_{jk}$ при $1\le j\le k\le n$ выражается через $a_{k+1},\dots ,a_n$ следующим образом:

$v_{jk}=a_{k+1}^{x_{k+1}}\dots a_n^{x_n},x_i\in {\mathbb{Z}}_2.$

В этом случае

$\forall x\in G\Rightarrow x=a_1^{x_1}\dots a_n^{x_n},x_i\in {\mathbb{Z}}_2.$

Каждый элемент группы x единственным образом задается через степени $x_1,\dots ,x_n$, поэтому мы можем записывать элементы группы следующим образом:

$\forall x\in G\Rightarrow x=\left(x_1\mathrm{,...,}{x}_n\right)\in {\mathbb{Z}}_2^n.$

Таким образом, мы можем естественным образом представлять элементы группы в виде булевых (битовых) векторов размерности n.

Пусть $x=\left(x_1\mathrm{,...,}{x}_n\right)$ и $y=\left(y_1\mathrm{,...,}{y}_n\right)$ – два произвольных элемента группы $G$, рассмотрим их произведение $x\cdot y=z=\left(z_1\mathrm{,...,}{z}_n\right)$.

Вычисление степеней  традиционно осуществляется на основе собирательного процесса Холла [3; 4]. Однако существует более эффективный способ умножения элементов, основанный на полиномах Холла [20]. В этом случае

$z_i=x_i+y_i+p_i(x_1,\dots ,x_{i-1},y_1,\dots ,y_{i-1}),x_i,y_i,z_i\in {\mathbb{Z}}_2.$

Заметим, что операции умножения и сложения в поле ${\mathbb{Z}}_2$ тождественны булевым операциям «и», а также исключающему «или» соответственно. Произведя указанную замену операцийв полиномах Холла, мы получим полиномы Жегалкина [21]. Таким образом,

$\forall x,y,z\in G:x\cdot y=z\Rightarrow z_i=f_i(x,y)\in {\mathbb{Z}}_2$,

где $f_i(x,y)$ – некоторые полиномы Жегалкина. 

2. Алгоритм вычисления полиномов Жегалкина

В данном разделе рассмотрен алгоритм вычисления полиномов Жегалкина для конечной 2-группы G. Алгоритму на входе известны такие параметры группы, как число порождающих элементов, порядок G и её период. Также в качестве входного аргумента может фигурировать ступень нильпотентности группы.

Ниже приведен псевдокод алгоритма. 

Вход: G – конечная группа 2-группа G

Выход: полиномы Жегалкина для группы G

1. $pc=\mathrm{pq}\left(G\right)$ – вычисляем pc-представление группы при помощи p-quotient алгоритма [3, 4]. Заметим, что данный алгоритм уже реализован в таких системах компьютерной алгебры, как GAP и Magma.
2. $H=\mathrm{Hall}\left(pc\right)$ – на основе pc-представления вычисляем полиномы Холла при помощи алгоритма из [22].
3. $F=\mathrm{Zhegalkin}\left(H\right)$ – получаем полиномы Жегалкина из полиномов Холла путем замены операции умножения и сложения в поле ${\mathbb{Z}}_2$ тождественными булевыми операциям «и», а также исключающему «или» соответственно.

3. Пример

В качестве примера рассмотрим максимальную двупорожденную конечную группу $G=⟨a_1,a_2⟩$ периода $2^2=4$,  которую обычно обозначают $B\left(\mathrm{2,4}\right)$ или $B_2\left(4\right)$. Порядок данной группы равен $2^{12}$, и для каждого элемента из G существует уникальное pc-представление вида $a_1^{x_1}\dots a_{12}^{x_{12}}$,  где $x_i\in {\mathbb{Z}}_2$, $i=\mathrm{1,2,}\dots \mathrm{,12}$.  Здесь $a_1$ и $a_2$ – порождающие элементы $G$, $a_3\dots ,a_{12}$ вычисляются рекурсивно через $a_1$ и $a_2$.

Получим в системе компьютерной алгебры GAP pc-представление данной группы.

Для краткости тривиальные коммутаторные соотношения не приводятся (например, такое, как $[a_4,a_1]=1$ и др.).

$a_1^2=a_4, a_2^2=a_5, a_3^2=a_8{a}_9{a}_{10}{a}_{11}{a}_{12}, a_4^2=1, a_5^2=1, a_6^2=a_{11}, a_7^2=a_{11}{a}_{12}, a_i^2=1 (8\le i\le 12)$,

$[a_3,a_1]=a_6, [a_3,a_2]=a_7, [a_4,a_2]=a_6{a}_8{a}_9{a}_{10}{a}_{12}, [a_4,a_3]=a_8{a}_{11}, [a_5,a_1]=a_7{a}_8{a}_9{a}_{10},$

$[a_5,a_3]=a_{10}{a}_{11}{a}_{12}, [a_5,a_4]=a_9{a}_{11}, [a_6,a_1]=a_8, [a_6,a_2]=a_9, [a_6,a_3]=a_{11}, [a_6,a_4]=a_{11}$,

$[a_6,a_5]=a_{11}, [a_7,a_1]=a_9{a}_{12}, [a_7,a_2]=a_{10}, [a_7,a_3]=a_{11}{a}_{12}, [a_7,a_4]=a_{11}{a}_{12}, [a_7,a_5]=a_{11}{a}_{12},$

$[a_8,a_1]=a_{11}, [a_8,a_2]=a_{12}, [a_9,a_1]=a_{11}{a}_{12}, [a_9,a_2]=a_{11}, [a_{10},a_1]=a_{12}, [a_{10},a_2]=a_{11}{a}_{12}.$

Вычислим полиномы Холла группы G для порождающих элементов $a_1$ и $a_2$ на основе алгоритма из [22]: 

1) $a_1\cdot a_1^{y_1}\dots a_{12}^{y_{12}}=a_1^{z_1}\dots a_{12}^{z_{12}}$, где

$z_1=y_1+\mathrm{1,}$

$z_2=y_2,$

$z_3=y_3,$

$z_4=y_1+y_4,$

$z_5=y_5,$

$z_6=y_6+y_1{y}_2,$

$z_7=y_7,$

$z_8=y_8+y_1{y}_2+y_1{y}_3,$

$z_9=y_9+y_1{y}_2,$

$z_{10}=y_{10}+y_1{y}_2,$

$z_{11}=y_{11}+y_1{y}_3+y_1{y}_2{y}_3+y_1{y}_2{y}_4+y_1{y}_2{y}_5+y_1{y}_2{y}_6,$

$z_{12}=y_{12}+y_1{y}_2;$

2) $a_2\cdot a_1^{y_1}\dots a_{12}^{y_{12}}=a_1^{z_1}\dots a_{12}^{z_{12}}$, где

$z_1=y_1,$

$z_2=y_2+\mathrm{1,}$

$z_3=y_1+y_3,$

$z_4=y_4,$

$z_5=y_2+y_5,$

$z_6=y_6,$

$z_7=y_7+y_1{y}_2,$

$z_8=y_8+y_1{y}_3,$

$z_9=y_9+y_1{y}_3+y_2{y}_4,$

$z_{10}=y_{10}+y_1{y}_2+y_1{y}_3+y_2{y}_3,$

$z_{11}=y_{11}+y_1{y}_2+y_1{y}_3+y_2{y}_3+y_2{y}_4+y_1{y}_2{y}_3+y_1{y}_2{y}_4+y_1{y}_2{y}_5+y_1{y}_2{y}_7,$

$z_{12}=y_{12}+y_1{y}_2+y_1{y}_3+y_2{y}_3+y_1{y}_2{y}_3+y_1{y}_2{y}_4+y_1{y}_2{y}_5+y_1{y}_2{y}_7.$

Заменим операции умножения и сложения булевым операциями «и», а также исключающему «или» соответственно. В результате получим полиномы Жегалкина. 

Каждый элемент группы представляет собой битовую строку $(z_1,z_2,\dots ,z_{12})$.  Таким образом, для кодирования одного элемента в $B\left(\mathrm{2,4}\right)$ потребуется 12 бит. В общем случае, если порядок группы равен $2^n$, то для хранения одного элемента потребуется n бит.

Заключение

В заключение скажем, что в задачах, требующих вычисления большого количества произведений элементов группы, описанный в работе метод позволит кардинально уменьшить время работы компьютерных программ. Например, одной из таких проблем является задача поиска кратчайших маршрутов на графах Кэли, которые часто применяются при проектировании топологий для сетей межпроцессорного соединения в суперкомпьютерах, а также дата-центрах.

Кроме того, следует отметить, что предложенное представление элементов группы в форме битовых векторов позволяет применять их даже на самых примитивных микроконтроллерах. 

Об авторах

Александр Алексеевич Кузнецов

Сибирский государственный университет науки и технологий имени академика М. Ф. Решетнева

Автор, ответственный за переписку.
Email: alex_kuznetsov80@mail.ru

доктор физико-математических наук, профессор, директор НОЦ «Институт космических исследований и высоких технологий»

Россия, 660037, г. Красноярск, просп. им. газ. «Красноярский Рабочий», 31

Александра Сергеевна Кузнецова

Сибирский государственный университет науки и технологий имени академика М. Ф. Решетнева

Email: alexakuznetsova85@gmail.com

кандидат физико-математических наук, доцент кафедры прикладной математики

Россия, 660037, г. Красноярск, просп. им. газ. «Красноярский Рабочий», 31

Владимир Владимирович Кишкан

Сибирский государственный университет науки и технологий имени академика М. Ф. Решетнева

Email: kishkan@mail.ru

кандидат физико-математических наук, доцент кафедры информатики и вычислительной техники

Россия, 660037, г. Красноярск, просп. им. газ. «Красноярский Рабочий», 31

Список литературы

Дополнительные файлы