I found there that a polynomial in $F[x]$ with $|F| =q $ with degree $n$ will have its roots in $K$ of order $q^n$
Here, I found that either all the roots are primitive or none of them are.
I am looking for a way to build efficiently a polynomial $P_n$ of degree $n$ which roots are of multiplicative order $p^n -1$ in $K$.
If such algorithm exists, is there a way to find among all possible $P_n$, the one(s) with the smallest hamming weight ? (fewest non-zero coefficients)
Any help is welcome