# primitive roots using libgmp

**Niels Möller
**
nisse@lysator.liu.se

*18 Dec 2002 10:40:22 +0100*

Haig Didizian <haig@didizian.com> 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
follows:
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
mod p.
Ok, this is not the complete truth, do be strict, the condition is
something like
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.
/Niels