Henri Cohen, "A course in computational algebraic number theory", first edition, 1993, Algorithm 1.4.4, checks whether an integer modulo p is a primitive root by checking exponents (p-1)/p_1, (p-1)/p_2, ...; here p_1, p_2, ... are the distinct prime divisors of p-1.

The comments after the algorithm describe various speedups, including the following: "The test for p_i=2 can be replaced by the more efficient check that the Legendre symbol ... is equal to -1 (see Algorithm 1.4.10 below)."

eprint 2012/470 proposes "an improvement of the classic randomized algorithm for generating primitive roots modulo a prime, by replacing an exponentiation with the evaluation of the Legendre-Jacobi symbol, which is much faster." This is exactly the same speedup.

---D. J. Bernstein
Research Professor, Computer Science, University of Illinois at Chicago