Some Connections Between Primitive Roots and Quadratic Non-Residues Modulo a Prime.

Abstract—In this paper we present some interesting connections between primitive roots and quadratic non-residues modulo a prime. Using these correlations, we propose some polynomial deterministic algorithms for generating primitive roots for primes with special forms (for example, for safe primes). Index Terms—primitive roots, Legendre-Jacobi symbol, quadratic non-residues, square roots. I.