Circulant matrices over $\mathbb{F}_2$ and their use for the construction of efficient linear transformations with high branch numbers

Linear transformations over $\mathbb{F}_2$ with high branch number are studied. New class of transformations is proposed — transformations, corresponding to the multiplication in the ring $\mathbb{F}_2[x]/f(x)$. An important subclass of this class is studied in detail — transformations defined by circulant matrices over $\mathbb{F}_2$. It is shown that for the software implementation of this class of transformations it is sufficient to use two instructions from the (extended) set of processor instructions and store only one row of the matrix. It is proposed to decompose any matrix over $\mathbb{F}_2$ into the sum of products of diagonal matrices and matrices corresponding to the multiplication in the ring $\mathbb{F}_2[x]/f(x)$. The number of summands is estimated in the case of known $f(x)$, the efficiency of the software implementation is justified. In the case of unknown $f(x)$ some probabilistic relations between matrix rows are derived. For any circulant matrix over $\mathbb{F}_{2^{s}}$ and $f(x) = x^{n}+1$ the number of summands does not exceed $s$ in the general case and does not exceed $k$ in the case when each element of the matrix has only $k$ nonzero low-order digits. AES and Whirlpool matrices have been decomposed using this method into two and four summands.