primitive roots using libgmp

[Niels Möller]

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