2012 Reports : Cryptology ePrint Archive Forum

Discussion forum for Cryptology ePrint Archive reports posted in 2012. Please put the report number in the subject.

2012/470 primitive roots: well known, standard

Posted by: **djb** (IP Logged)

Date: 01 September 2012 21:25

Henri Cohen, "A course in computational algebraic number theory", first edition, 1993, Algorithm 1.4.4, checks whether an integer modulo p is a primitive root by checking exponents (p-1)/p_1, (p-1)/p_2, ...; here p_1, p_2, ... are the distinct prime divisors of p-1.

The comments after the algorithm describe various speedups, including the following: "The test for p_i=2 can be replaced by the more efficient check that the Legendre symbol ... is equal to -1 (see Algorithm 1.4.10 below)."

eprint 2012/470 proposes "an improvement of the classic randomized algorithm for generating primitive roots modulo a prime, by replacing an exponentiation with the evaluation of the Legendre-Jacobi symbol, which is much faster." This is exactly the same speedup.

---D. J. Bernstein

Research Professor, Computer Science, University of Illinois at Chicago

The comments after the algorithm describe various speedups, including the following: "The test for p_i=2 can be replaced by the more efficient check that the Legendre symbol ... is equal to -1 (see Algorithm 1.4.10 below)."

eprint 2012/470 proposes "an improvement of the classic randomized algorithm for generating primitive roots modulo a prime, by replacing an exponentiation with the evaluation of the Legendre-Jacobi symbol, which is much faster." This is exactly the same speedup.

---D. J. Bernstein

Research Professor, Computer Science, University of Illinois at Chicago

Please log in for posting a message. Only registered users may post in this forum.