An algorithm for fast multiplication of elements in 2-groups based on the Zhegalkin polynomials

Full Text

Introduction

Designing a network of a multiprocessor computing system (MCS) or a data center is an important problem in which graph models are searched for that have attractive topological properties and allow the use of effective routing algorithms. Cayley graphs possess these properties, in particular such as high symmetry, hierarchical structure, recursive construction, high connectivity and fault tolerance [1]. For example, such basic network topologies as "ring", "hypercube" and "torus" are Cayley graphs.

The definition of a Cayley graph implies that the vertices of the graph are elements of some algebraic group. The choice of the group and its generating elements allows us to obtain a graph [2] that meets the necessary requirements in diameter, degree of vertices, number of nodes, etc. A large number of scientific articles and monographs have been devoted to solving this problem, among which we highlight the works [3–15].

As it was said, one of the widely used MCS topologies is the k-dimensional hypercube. This graph is given by the k-generated Burnside group of exponent 2. This group has a simple structure and is equal to the direct product of k instances of a cyclic 2-group. A generalization of the hypercube is an n-dimensional torus, which is generated by the direct multiplication of n instances of cyclic subgroups whose orders may not coincide. In articles [16–19], Cayley graphs of Burnside groups of exponents 3, 4, 5 and 7 are studied.

To study Cayley graphs generated by groups of higher exponents, first of all, it is necessary to develop fast algorithms for multiplying elements in these groups. Such algorithms help to implement efficient routing on the corresponding Cayley graphs.

The purpose of this work is to create an algorithm for fast multiplication of elements in finite 2-groups, i.e. in groups of exponent ²ⁿ. 

The first section of the article provides a theoretical justification for the algorithm of fast multiplication in finite 2-groups. It is shown that the elements of these groups can be represented as bit strings, and their multiplication is carried out on the basis of Zhegalkin polynomials.

The second section presents the pseudocode of the algorithm on the basis of which the Zhegalkin polynomials are calculated.

In the third section, an example of obtaining Zhegalkin polynomials for a two-generated group of exponent 4 is demonstrated.

In conclusion, the prospects of using the algorithm on real computing devices are considered.

1. Proof of the main result

The theorem. Let G be an arbitrary finite group 2-a group whose order is equal to .Then the following statements will be true:

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)$, where are some Zhegalkin polynomials.

Proof. Any finite 2-group G has a pc-presentation (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\},$

where the word $v_{jk}$ при $1\le j\le k\le n$ expressed in terms of as $a_{k+1},\dots ,a_n$ follows:

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

In this case

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

Each element of the group x is uniquely defined in terms of degrees $x_1,\dots ,x_n$, so we can write the elements of the group as follows:

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

Thus, we can naturally represent the elements of the group in the form of Boolean (bit) vectors of dimension n.

Let $x=\left(x_1\mathrm{,...,}{x}_n\right)$ and $y=\left(y_1\mathrm{,...,}{y}_n\right)$ – be two arbitrary elements of the group $G$, consider their multiplication $x\cdot y=z=\left(z_1\mathrm{,...,}{z}_n\right)$.

The calculation of degrees is traditionally carried out on the basis of the collective Hall process [3; 4]. However, there is a more efficient way to multiply elements based on Hall polynomials [20].In this case

$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.$

Note that the multiplication and addition operations in the field are ${\mathbb{Z}}_2$ identical to the Boolean operations "and", as well as the exclusive "or", respectively. By performing the specified substitution of operations in Hall polynomials, we obtain Zhegalkin polynomials [21]. Thus,

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

where $f_i(x,y)$ are some Zhegalkin polynomials.

2. Algorithm for calculating Zhegalkin polynomials

In this section, we consider an algorithm for calculating Zhegalkin polynomials for a finite 2-group G. The input algorithm knows such parameters of the group as the number of generating elements, the order of G and its exponent. Also, the nilpotence level of the group may appear as an input data.

The pseudocode of the algorithm is shown below. 

Input: G – finite group 2-group G

Output: Zhegalkin polynomials for group G

1. $pc=\mathrm{pq}\left(G\right)$ – we calculate the pc-presentation of the group using the p-quotient algorithm [3, 4]. Note that this algorithm has already been implemented in computer algebra systems such as GAP and Magma.
2. $H=\mathrm{Hall}\left(pc\right)$ – based on the pc-presentation, we calculate the Hall polynomials using the algorithm from [22].
3. $F=\mathrm{Zhegalkin}\left(H\right)$ – we obtain Zhegalkin polynomials from Hall polynomials by replacing the multiplication and summing operations in the field with ${\mathbb{Z}}_2$ 
4. identical Boolean operations "and", as well as the exclusive "or", respectively.

3. An example

As an example, consider the maximum two - generated finite $G=⟨a_1,a_2⟩$ period group $2^2=4$,  which is usually denoted by $B\left(\mathrm{2,4}\right)$ or $B_2\left(4\right)$. The order of this group is equal $2^{12}$, and for each element of G there is a unique pc-presentation of the form $a_1^{x_1}\dots a_{12}^{x_{12}}$,  where $x_i\in {\mathbb{Z}}_2$, $i=\mathrm{1,2,}\dots \mathrm{,12}$.  Here $a_1$ and $a_2$  are the generating elements $G$, $a_3\dots ,a_{12}$ calculated recursively through $a_1$ and $a_2$.

We obtain a GAP pc-presentation of this group in the computer algebra system.

For brevity, trivial commutator relations are not given (for example, such as $[a_4,a_1]=1$ etc.).

$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}.$

Calculate the Hall polynomials of group G for generating elements $a_1$ and $a_2$ based on the algorithm from [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}}$, where

$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.$

Replace the multiplication and summing operations with the Boolean operations "and", as well as the exclusive "or", respectively. As a result, we obtain the Zhegalkin polynomials.  

Each element of the group is a bit string $(z_1,z_2,\dots ,z_{12})$.  Thus, it will $B\left(\mathrm{2,4}\right)$ take 12 bits to encode one element in. In general, if the order of the group is equal  $2^n$, then it will take n bits to store one element.

Conclusion

In conclusion, we say that in tasks requiring the calculation of a large number of multiplications of group elements, the method described in this paper will dramatically reduce the running time of computer programs. For example, one of these problems is the task of finding the shortest routes on Cayley graphs, which are often used in the design of topologies for interprocessor connection networks in supercomputers, as well as data centers.

In addition, it should be noted that the proposed presentation of the group elements in the form of bit vectors allows them to be used even on the most primitive microcontrollers. 

About the authors

Alexander A. Kuznetsov

Reshetnev Siberian State University of Science and Technology

Author for correspondence.
Email: alex_kuznetsov80@mail.ru

Dr.  Sc., Professor, Head of Institute of Space Research and High Technologies

Russian Federation, 31, Krasnoyarskii Rabochii prospekt, Krasnoyarsk, 660037

Alexandra S. Kuznetsova

Reshetnev Siberian State University of Science and Technology

Email: alexakuznetsova85@gmail.com

Cand. Sc., Associate Professor of the Department of Applied Mathematics

Russian Federation, 31, Krasnoyarskii Rabochii prospekt, Krasnoyarsk, 660037

Vladimir V. Kishkan

Reshetnev Siberian State University of Science and Technology

Email: kishkan@mail.ru

Cand. Sc., Associate Professor of the Department of Informatics and Computer Science

Russian Federation, 31, Krasnoyarskii Rabochii prospekt, Krasnoyarsk, 660037

References

Supplementary files