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.

Advisor - Qing Nie

We present a proof of a theorem of Gitik and Shelah that places limits on the structure of quotient algebras by sigma-additive ideals. We will start by showing connections between Cohen forcing and Baire category on the reals. Then by using generic ultrapowers, we will prove that no sigma-additive ideal yields an atomless algebra with a countable dense subset. We will discuss connections with Ulam's measure problem: How many measures does it take to measure all sets of reals?