Every finite field has many multiplicative generators. However,
finding one in polynomial time is an important open problem .
In fact, even finding elements of high order has not been solved
satisfactorily. In this paper, we present an algorithm that for any
positive integer $c$ and prime power $q$, finding an element of
order $\exp(\Omega(\sqrt{q^c}) ) $ in the finite field $\F_{q^{(q^c-1)/(q-1)}}$
in deterministic time $(q^c)^{O(1)}$. We also show that there are
$\exp(\Omega(\sqrt{q^c}) ) $ many weak keys for the discrete logarithm problems
in those fields with respect to certain bases.