primitive roots using libgmp
18 Dec 2002 10:40:22 +0100
Haig Didizian <firstname.lastname@example.org> writes:
> Anyway, is there a nice way to:
> a) check to see if an integer is a primitive root of large number
> b) implement it easily using libgmp?
You should really check Handbook of Applied Cryptography and/or
Cohen's Computational Algebraic Number Theory. They should explain
this. However, if I remember correctly, the simplest test is as
Let p be an odd prime. Pick a random a. Compute b = a^( (p-1)/2) mod
p. If b != 1, then a (often) generates the entire multiplicative group
Ok, this is not the complete truth, do be strict, the condition is
a generates the entire multiplicative group mod p if and only if
a^d != 1 for each d that is a non-trivial divisor of p-1, or
a^d != 1 for each d of the form (p-1)/q, with q a prime divisor of p-1.
To understand the reasoning behind this, you need to know that the
order of any element must divide p-1.
So it simplifies the test if you know that (p-1)/2 is prime, because
then you only need to check for d = 2 (always satisfied for a smaller
than sqrt(p)) and d = (p-1)/2.
Anyway, for diffie-hellman, what matters is not that you choose an a
that generates the *entire* multiplicative group modulo p. It's good
enough if it generates a large subgroup.