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. 



Cycle types of permutations from affine group

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


