[Back] In ElGamal we select a generator value (G):
Picking G value in ElGamal
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?