I've asked some other questions before about Rijndael's S-boxes, and step by step I'm coming to an understanding; but those steps often guide me to new questions.
I did some lines of code to understand how these S-boxes work implementing $S(z) = f(g(z))$ where $g(z)$ is the transformation by multiplicative inverse in a polynomial field and $f(z)$ the affine mapping understanding a word as element in a polynomial ring following the expression.
\begin{equation} \begin{aligned} b(z) &= \mu(z) \cdot a(z) + \nu(z) \\ &= (z^4+z^3+z^2+z+1) \cdot a(z) + (z^6+z^5+z+1) \;\bmod{(z^8+1)} \end{aligned} \end{equation}
In the "AES proposal"(version 2 from 1999), section 7.2 explains that $\mu(z)$ was chosen from the set of co-primes with $z^8+1$ as the one with the simplest description. But what can be understood as "simple description"? The condition to select $\nu(z)$ looks to be much clear (no fixed points, neither opposite fixed points, isn't it?).
If I did it well, there are 129 co-prime polynomials to select 1 (and its inverse) and I cannot see what makes this special. $\mu(z)$ has 5 ones and its inverse $\mu^{-1} (z)$ has 3, and there are other pair candidates with a relation 3-3 or 5-5 of 1s. Another description of simplicity perhaps was palindromic representation, but it's neither the case. They are not the shortest or longest ones to highlight them over the others. What makes them special to be chosen?
Ps: In the mentioned "AES proposal" the $\mu(z)$ and $\nu(z)$ are not the ones above, neither are the ones shown in section 3.4.1 from "The Design of Rijndael" but with the 2 shown here I've reproduced the official S-boxes and the tables of the section C of the mention book. Would I be wrong?
Update 20150320 based on the comments received:
Based on the definition of the "simplicity" criteria to select $\mu(z)$, it cannot be evaluated what makes $z^4+z^3+z^2+z+1$ special. The only known requirement of this polynomial is that it must have a multiplicative inverse in the ring defined by $z^8+1$: there are 129 elements invertible.
The other parameter $\nu(z)$ has an evaluable criteria to do a selecting: it must not produce any fixed point, neither opposite fixed point. Checked this, the number of polynomial pairs that satisfies that in the ring are 21717. A big number. In a shorter view like fixing $\mu(z)$, the number of possible $\nu(z)$ that satisfies the seconds criteria are 223.
Even Rijndael usually is implemented storing the S-Boxes, the calculation times looks not very relevant, but perhaps they are, aren't it?
In those boxplots are represented average calculation for each of the candidate pairs. On the left using doing the modular product and on the right using the MDS matrix suggested in the Rijndael's documents.
Apart from the think that the matrix method is not better in general, the times for the official pair are represented by coloured dots. There are very many better candidates.
I did a seconds figure as a branch that assumes that the official $\mu(z)$ has something special I cannot see.
Here that data set are the 223 different $\nu(z)$ having $\mu(z)=z^4+z^3+z^2+z+1$. Again be careful with the scales on the y axis.
The calculation time for the official pairs have been also draw as coloured points. And here the official $\nu(z)$ doesn't show any timing property.
The code of this test is in a Rijndael project in github. From a command line it can be repeated by call $ python Polynomials.py --test-ring=8 and the basic things make with R are in a Polynomials subdirectory.
