2012 Reports :  Cryptology ePrint Archive Forum
Discussion forum for Cryptology ePrint Archive reports posted in 2012. Please put the report number in the subject. 
Goto Thread: PreviousNext
Goto: Forum ListMessage ListNew TopicSearchLog In
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

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