Answering #2 from list of questions here:

An ONB of Type I exists a given field $GF(2^{m})$ if:

• $m+1$ is a prime
• 2 is a primitive in $GF(m+1)$

A Type II optimal normal basis exists in $GF(2^{m})$ if:

• $2m+1$ is prime
• either 2 is a primitive in $GF(2m+1)$ or $2m+1\equiv 3 \left (mod\; 4 \right )$ and 2 generates the quadratic residues in $GF(2m+1)$

Interesting notes:

An ONB exists in $GF(2^{m})$ for 23% of all possible values of $m$

said this paper. Hmmm, that’s something.