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},
note = {\url{https://eprint.iacr.org/2012/470}},
url = {https://eprint.iacr.org/2012/470}
}
