Choosing an optimal generator for an irreducible polynomial over a binary field? I am reading the Certicom tutorial “An Example of an Elliptic Curve Group over F2m ” and I have following questions: 


How do they assume that generator $g = (0010)$ is correct for this polynomial?
How can/should one choose an optimal generator from a group of generators for a specific field?
What you need is a primitive polynomial of degree $m$ (for using with $\operatorname{GF}(2^m)$). 

This is an irreducible polynomial whose roots have maximal multiplicative order $2^m-1.$ 

There are tables of these, at least one is guaranteed to exist for each degree. Alternatively they can be found by randomised methods. Use a polynomial factorisation algorithm to get an irreducible of degree $m$, say $f(X)$  and then check that $$X^i \bmod f(X)\neq 1$$ for any proper divisors $i,~1&lt;i&lt;2^m-1$, of $2^m-1.$

If you know one such polynomial with a root $X$ then its roots are $X,X^2,\ldots , X^{2^{m-1}}$ each with multiplicity 1. By trying $X^u$ with $\gcd(u, 2^m-1)=1$ you may find a lower weight polynomial to enable efficient implementation, just write the new polynomial as 
$$
f_u(z)=(Z-X^u)(Z-X^{2u})(Z-X^{2^{m-1}u})
$$
and simplify over $\operatorname{GF}(2).$

Edit: Error in last equation corrected.