Efficient algorithms for Primitive roots where time-complexity is $\leq O(\sqrt{n})$ I have an algorithm for primitive roots for input number $n$ that I believe is $O(n)$ currently. I also have separate algorithms for $\varphi(n)$ and $factorise(n)$ which I believe are both $O(\sqrt{n})$ whose results are used in my primitive root algorithm.
The primitive root alg is based on this Wikipedia entry:

First, compute $\varphi(n)$. Then determine different prime factors of $\varphi(n)$, say $p_1, \cdots, p_k$. 
  Now, for every element m of $\mathbb{Z}_n^*$, compute $$m^{\varphi(n)/p_i}\pmod{n}$$ for $i=1, \cdots,k$, using a fast algorithm for modular exponentiation such as exponentiation by squaring. 
A number $m$ for which these $k$ results are all different from $1$ is a primitive root.

Question:
I'm looking for examples of efficient algorithms for Primitive roots where time-complexity is $\leq O(\sqrt{n})$.
I have found lots of examples of algorithms that find primitive roots online, however they do not have the time-complexity noted.
 A: Be careful about what 'n' means in your analysis.  Typically in this use it should represent the size of the input, hence this is subexponential since we have to factor.
See Finding a primitive root of a prime number for a nice answer about the process of finding a primitive root.
See Efficient polynomial time algorithms computing industrial-strength primitive roots for a paper on a polynomial time method for probabilistic primitive roots.
Add: See Finding Primitive Roots Pseudo-Deterministically for another discussion.  This shows complexities based on factoring (both deterministic and using best known factoring methods).  It also points out an answer to the questions below about how far we have to look to find a primitive root: assuming the GRH, $O(\log^6 p)$, which is polynomial in the size of $p$, so the factoring time dominate.
For this purpose, finding phi consists of finding a power which is quite fast.  Then factoring it which is the majority of the time spent.  The unknown is searching for the first root (which requires one or more modular exponentiations each), and I'm not immediately seeing a hard bound on the number we will have to search.  In my experience the factoring dominates the time.
There are some ways to skip some values in practice, but they don't impact the asymptotic number.
Assuming one searches in order, we can look at how the sequence http://oeis.org/A046145 grows.  It looks like we find one under $\log^2(n)$ but that's just a few billion examples, and even if that's right we need more analysis to turn that into a proper term.
