Fact 1: 
Let p = 2*q+1 be a safe prime, where q is a prime number. 
An integer g is a generator for (Z/pZ)* iff g != 1 (mod  p), 
g^2 != 1 (mod p) and g^q != 1 (mod p).

Fact 2:
If g is a generator for (Z/pZ)*, then so is g^k whenever
GCD(k,p-1) = 1.

Corollary:
For a safe prime p = 2*q+1, there are q-1 generators for (Z/pZ)*.

Corollary:
There is an efficient probabilistic algorithm for finding generators
for (Z/pZ)*, where p is a safe prime.

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Example:
ElGamal with p = 23 (safe prime) = 2*11+1

Note 2 and 3 are not generators for (Z/23Z)* but 5 is, since
5 != 1, 5^2 != 1 and 5^11 != 1.

Bob's public keys are p=23, g=5, and B
and his secret key is A so that B = g^A (mod p).

Say A = 3 and B = 10

Suppose Alice wants to send a message m=2.
She selects a random exponent k (mod p-1), say k = 7,
and computes
 (1) cipher = m * B^k (mod p) = 2 * 10^7 (mod 23) = 5. The full-mask used is f = B^k = 10^7 = 14 (mod p).
 (2) half-mask h = g^k (mod p) = 5^7 (mod 23) = 17

Her message to Bob is (half-mask, cipher) = (17, 5).

Bob retrieves Alice's plaintext message m by computing:

  m = cipher * [(half-mask)^B]^{-1} = 5 * (17^3)^{-1} = 5 * 14^{-1}

To compute 14^{-1} (mod 23), we use the trusted Aryabhata table:
--------------------------------------------------------------
  p	f	Q	R	X1	Y1	X2	Y2
--------------------------------------------------------------
  23	14	1	9	1	0	0	1
  14	9	1	5	0	1	1	-1
  9	5	1	4	1	-1	-1	2
  5	4	1	1	-1	2	2	-3
  4	1	4	0	2	-3	-3	5
--------------------------------------------------------------
check: 1 = 23*(-3) + 14*5

Therefore, 14^{-1} (mod 23) = 5.

So, Alice's message is

  m = 5 * 5 (mod 23) = 2