[Back] In ElGamal we select a generator value (G):

## Picking G value in ElGamal |

## Outline

At the core of discrete logarithms we have:

Y = G^x mod p

where p is a prime number and G is a generator, with x being a random number. What we want is the each value of x that we choose should give us a unique value of Y (obviously between 0 and p-1), so:

3^1 mod 5 gives 3, while 3^2 mod 5 gives 4, and so on.

So how do we select of the G value in ElGamal (and in Diffie-Hellman (D-H), of course), and here was my explanation:

But, in order to demonstrate the principle, I have done this is a long-handed way, so how do I find out all the possible values of G for a given prime number (p)? Well here's a nice simple method in Python that I created to test up to p):

import sys import random p=11 for x in range (1,p): rand = x exp=1 next = rand % p while (next <> 1 ): next = (next*rand) % p exp = exp+1 if (exp==p-1): print rand

So what are the G values for p=11? Well I get:

2, 6, 7 and 8

which tallies with my spreadsheet calculation (notice that 3, 4, 5 and 9 repeat, and cannot be used as generators) [here]

So, can you determine the generators for 17?