International Association
for Cryptologic Research

In this paper we present some interesting connections between primitive roots and quadratic non-residues modulo a prime. Using these correlations, we improve the existing randomized algorithm for generating primitive roots and we propose a polynomial deterministic algorithm for generating primitive roots for primes

with special forms (for example, for safe primes). The key point of our improvement is the fact that the evaluation of Legendre-Jacobi symbol is much faster than an exponentiation.