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

Sorin Iftene

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

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

Metadata

Available format(s): PDF
Publication info: Published elsewhere. Unknown where it was published
Keywords: implementation
Contact author(s): siftene @ info uaic ro
History: 2012-09-13: revised; 2012-08-18: received; See all versions
Short URL: https://ia.cr/2012/470
License: CC BY

BibTeX

@misc{cryptoeprint:2012/470,
      author = {Sorin Iftene},
      title = {Some Connections Between Primitive Roots and Quadratic Non-Residues Modulo a Prime},
      howpublished = {Cryptology {ePrint} Archive, Paper 2012/470},
      year = {2012},
      url = {https://eprint.iacr.org/2012/470}
}