If we're trying to find an element modulo $n$ that has multiplicative order at least $\sqrt{n}$, how quickly can we do this? We don't know if $n$ is prime or composite, only that $n$ definitely has a value with multiplicative order at least $\sqrt{n}$.
I'm interested in both randomized and non-randomized, deterministic algorithms. I'd like to know the asymptotic bounds for the running time.