Cryptology ePrint Archive: Report 2012/470

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

Sorin Iftene

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).

Category / Keywords: implementation

Date: received 15 Aug 2012, last revised 13 Sep 2012

Contact author: siftene at info uaic ro

Available formats: PDF | BibTeX Citation

Note: D. J. Bernstein has pointed us the fact that replacing the exponention $ \alpha^{\frac{p-1}{2}}$ with the evaluation of the Legendre-Jacobi symbol has been already presented by Cohen in [10].

Version: 20120913:075746 (All versions of this report)

Discussion forum: Show discussion | Start new discussion