## Constructing Higher Order Elements in Finite Fields

Speaker:
Qi Cheng
Institution:
University of Oklahoma
Time:
Wed, 03/21/2012 - 10:00am - 11:00am
Host:
Daqing Wan
Location:
440R

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.