7
$\begingroup$

Let $V$ be a vector space of dimension $n$ over the field $F=\mathrm{GF}(2)$. We identify $V$ with the set of columns of length $n$ over $F$. Let $G = \mathrm{AGL}(V)$ be a group of affine permutations of $V$. That is for every $g\in G$ there exists a square invertible binary matrix $M$ and vector $b$ such that for every $v \in V$ we have $$ g(v) = Mv + b $$

It is not hard to find a cycle type of a given permutation $g\in G$. But I don't know how to find all possible cycle types of permutations from $G$

My question. Are there any theoretical results, which provide information about all possible cycle types of affine permutations? Or, maybe there are some efficient algorithms for finding all such cycle types?

This question has a natural cryptographic nature. If we have a permutation $\pi$ of $V$ and $\pi$ is conjugated with one from $G$, then $\pi$ is a vulnerable permutation (S-box). So, if we can answer the question above, we can separate good and bad cryptographic permutations in this sense.

$\endgroup$
  • $\begingroup$ Do you mean $\pi$ is a conjugate of a permutation from $V$? $\endgroup$ – kodlu Feb 24 at 20:15
  • $\begingroup$ I mean that $\pi$ is conjugate of some affine permutation of V $\endgroup$ – Mikhail Goltvanitsa Feb 24 at 21:04
4
$\begingroup$

Are there any theoretical results, which provide information about all possible cycle types of affine permutations?

Yes: basic linear algebra.

There is no reason to restrict to a field on 2 elements, so let me assume that $K$ is an arbitrary finite field $K$.

(a) First, assume that $b=0$, i.e. let's understand cycle decomposition of linear automorphisms $M$. The automorphism $M$ makes $V=K^n$ a $K[t]$-module.

(a1) First suppose that $K^n$ is a cyclic $K[t]/P(t)$-module, for some irreducible monic polynomial $P$ (that is, $K^n$ is irreducible under $M$, whose minimal polynomial is $P$).

Given $v\in K^n\smallsetminus\{0\}$, we have $M^dv=v$ if and only if $(M^d-1)v=0$, if and only if $M^d=1$. Hence, let $d_1$ be the minimal $d\ge 1$ such that $P(t)$ divides $t^d-1$ (which is computable): then the cycle decomposition of $M$ is one 1-cycle (the fixed point 0) and the remainder consists of $d_1$-cycles (hence there are $(|K|^n-1)/d_1$ such cycles).

(a2) the next case is when $K^n$ is a cyclic $K[t]/P(t)^m$-module, for some irreducible monic polynomial $P$ and $m\ge 1$. So in $K^n$, the invariant subspaces form a chain of subspaces $V_i=\mathrm{Ker}(P(M)^i)$, with $0=V_0\subsetneq V_1\subsetneq\dots\subsetneq V_m=K^n$, and $\dim_K(V_i)=i\deg(P)$ for $i\le m$. Let $d_i$ be the minimal $d\ge 1$ such that $P(t)^i$ divides $t^d-1$. If I'm correct, the cycle decomposition of $M$ in $V_i\smallsetminus V_{i-1}$ consists only of $d_i$-cycles. Note $V_i\smallsetminus V_{i-1}$ has cardinal $|K|^{i\deg(P)}-$|K|^{(i-1)\deg(P)}$.

(a3) The general (linear) case: by the structure of modules over PIDs (known as cyclic decomposition in the context of linear algebra), one can write $K^n=\bigoplus_{j=1}^\ell W_j$. For each cycle $C_j$ in $W_j$ for each $j$, one gets an $M$-invariant subset $\prod_j C_j$, which is made up of cycles of length $\mathrm{lcm}_j(|C_j|)$. All this is computable.

(b) Finally, we have to pass to the affine case, but this is not so complicated. Indeed first write $K^n=W\oplus W'$, and write accordingly $M=M_1\oplus N$, where $W$ is the characteristic subspace of $M$ with respect to the eigenvalue 1. Since $N-1$ is invertible, by a conjugation one can suppose that $b\in W$. This yields a product decomposition of the map $v\mapsto Mv+b$, so arguing as in (a3) allows to reduces to the case of $v\mapsto Nv$ which was covered in (a3), and to the case of $v\mapsto M_1v+b$.

In other words, we reduce to understand the case when $M-1$ is nilpotent and $v\mapsto Mv+b$ has no fixed point (since otherwise we reduce to the linear case). Also, a decomposition into a product allows to reduce to the case when $M$ is cyclic, so that $M$ makes $K^n$ a free $K[t]/(t-1)^n$-module of rank 1. Also, a conjugation by a translation allows to change $b$ by adding any element of $\mathrm{Im}(M-1)$, and also conjugation by a homothety allows to renormalize $b$.

Hence, we can suppose that $M$ is a Jordan matrix: $$M=\begin{pmatrix}1 & 1 & 0 & \dots& 0\\ 0 & \ddots & \ddots & \ddots &\vdots\\ \vdots &\ddots & \ddots &\ddots & 0\\ \vdots & & \ddots & 1 & 1\\ 0 & \dots & & 0 & 1\end{pmatrix},\quad b=\begin{pmatrix} 0\\ \vdots \\ \\ 0 \\ 1\end{pmatrix}.$$

We have $g^m(v)=M^mv+(M^{m-1}+\dots+M+1)b$, so $g^mv=v$ writes as $(M^m-1)v+(M^{m-1}+\dots+M+1)b=0$, which can be rewritten as $(M^{m-1}+\dots+M+1)((M-1)v+b)=0$.

Solving this is a computation which should be doable; I'll do later: note that since $(M-1)v+b\neq 0$, for this to vanish, $M^{m-1}+\dots+M+1$ has to be non-invertible, which holds iff it the characteristic $p$ of $K$ divides $m$.


Edit: actually if $M^{m-1}+\dots+M+1$ is nonzero, one easily checks that $(M^{m-1}+\dots+M+1)((M-1)v+b)\neq 0$. Hence the question is simply, for which minimal $m_0=m\ge 1$ is $M^{m-1}+\dots+M+1$ equal to 0, for $M$ this special matrix above. This question depends on $n$ (size of the matrix) and on the ground characteristic. Let's already retain anyway that for such a case, all cycles have the same length.

Now let's focus on characteristic 2 since this is the OP's question; write $m_0=m_0(n)$.

We have $m_0(0)=1$, $m_0(1)=2$, $m_0(2)=m_0(3)=4$, and $m_0(i)=8$ for $i=4,5,6,7$. It seems that $m_0(i)$ is the smallest power of 2 that is $>i$, which I haven't checked although I guess it's a simple verification on binomials.

$\endgroup$
  • $\begingroup$ thank you for your answer. Can you explain, please, what $N$ stand for in item (b)? $\endgroup$ – Mikhail Goltvanitsa Apr 2 at 13:16
  • $\begingroup$ N is the restriction of $M$ to $W'$. $\endgroup$ – YCor Apr 2 at 13:26
  • $\begingroup$ Why from $K^n = W \oplus W'$ we obtain $M = M_1 \oplus N$? I don't understand why $W'$ is invariant subspace. $\endgroup$ – Mikhail Goltvanitsa Apr 2 at 16:28
  • $\begingroup$ For every monic irreducible polynomial $P\in K[t]$, the characteristic subspace $W_P=\mathrm{Ker}(P(M)^n)$ is $M$-invariant. By definition, $W=W_t$ and $W'=\bigoplus_{P\neq t}W_P$ is $M$-invariant. Equivalently, if $\chi(t)$ is the characteristic polynomial of $M$, write $\chi(t)=t^kQ(t)$ with $Q(0)\neq 0$. Then $W'=\mathrm{Ker}(Q(M))$ is $M$-invariant. $\endgroup$ – YCor Apr 2 at 17:09
  • $\begingroup$ Oo, I thought, that you mean the set of all eigenvectors of eigenvalue 1. $\endgroup$ – Mikhail Goltvanitsa Apr 2 at 17:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.