Date Added: Sep 2012
Generating primitive roots modulo a prime is a fundamental problem in number theory, with major applications in cryptography. Diffie-Hellman key establishment scheme, ElGamal public-key cryptosystem, Schnorr identification scheme and Digital Signature Scheme are only a few examples which rely on generating primitive roots or elements of a certain order. Finding quadratic non-residues modulo a prime is another interesting problem in number theory. Tonelli-Shanks algorithm and Cippola-Lehmer algorithm for computing square roots modulo a prime and Goldwasser-Micali probabilistic encryption scheme are the most important applications that rely on generating quadratic non-residues. In this paper, the authors present some interesting connections between primitive roots and quadratic non-residues modulo a prime. Using these correlations, they propose some polynomial deterministic algorithms for generating primitive roots for primes with special forms.