[Crypto] What does a linear function with huge order mean?

TL;DR Skip to the bottom for update.

As is well known, the mapping $$L:\{0,1\}^n\rightarrow \{0,1\}^n,$$ of a primitive LFSR on $n$ bits has a single very long cycle of length $2^n-1,$ and a cycle of length $1$ (which maps zero to zero).

As a permutation, this mapping has huge order, i.e., the for almost all the state space the smallest $k,$ such that the $k-$fold composition of $L$ gives the identity map is $k=2^{n}-1:$ $$L^{k}(\cdot)=L(L(\cdots(L(\cdot)))).$$

A randomly chosen permutation on $\{0,1\}^n$ has at least one fixed point with probability $(1-e^{-1})$, and considered as a state mapping, it has a lot of short cycles.

The expected number of fixed points of a random permutation is actually 1, but that is not so relevant, the relevance is the relatively large number of small cycles.

In fact the fraction of permutations with no cycles of length $k$ or less is $e^{-H_k}$ where $H_k=1+2+\cdots+k$ is the Harmonic number. You can use the approximation $H_k \approx\ln k$ to obtain some rough estimates.

Also see this answer on mathoverflow for some details. This is not desirable here and the permutation must be carefully chosen.

Edit: For more concrete results see the paper by Odlyzko-Flajolet here where for example, it is proved that the expected "rho length" i.e., initial segment followed by a closed cycle from a random starting point in the state space is $O(\sqrt{N}),$ for a permutation on $N$ points (Theorem 7).

Now compare with the $O(N)$ cycle length in the primitive LFSR example with $N=2^n.$