In cryptography, the follow sentence appears very common： “Let G be cyclic group of Prime order q and with a generator g.” This is the first step in many encryption/signature scheme such as ElGamal encryption.
But how is this accomplished exactly? It turns out that this problem is not that trivial. Some research finds the following commonly used method.

Zp*={1,2,…,p-1} is known to be a cyclic group of order p-1 if p is a prime number. When p=2q+1 where q is also a prime number, p is said to be a safe prime number. q is very interesting here because p-1=2q means that any subgroup of Zp* can only have order 2 or order q.. Moreover, they are all cyclic groups. Let’s call the subgroup of order q Gq. This is the group we are interested in (cyclic group of prime order q).

Now we need to find one of its generator. If we find an element of order q in Zp*, is it a generator of Gq? The answer is yes. For any element, the order of the element can only be 2,q or p-1. If an element g is of order q, it follows from definition of cyclic group that Gq=. Actually, any element other than the identity in Gq is a generator.

Now we have sketched the outline of an algorithm to generate a cyclic group Gq of prime order q with generator g.

1. Generate random prime q until p=2q+1 is also a prime.
2. Randomly generate an integer 2<=g<=p-1.
3. If g^2 = 1 mod p, goto 2
4. If g^q != 1 mod p, goto 2.
5. Output p,q,g.

I implemented this algorithm in Golang, you can easily port the code into other programming language if you are interested.

package main
import (
    "crypto/rand"
    "math/big"
)

func gen(n int) (*big.Int, *big.Int, *big.Int) {
    for {
        q, err := rand.Prime(rand.Reader, n - 1)
        if err != nil {
            panic(err.Error())
        }
        n := new(big.Int).Mul(q, big.NewInt(2))
        p := new(big.Int).Add(n, big.NewInt(1))
        // p = 2q + 1, order(p)=n=2q
        if p.ProbablyPrime(40) {
            for {
                a, err := rand.Int(rand.Reader, p)
                if err != nil {
                    panic(err.Error())
                }                                                                         
                if b := new(big.Int).Exp(a, big.NewInt(2), p); b.Cmp(big.NewInt(1)) == 0 {
                    continue
                }
                if b := new(big.Int).Exp(a, q, p); b.Cmp(big.NewInt(1)) == 0 {
                    return p, q, a
                }
            }
        }
    }
    return nil, nil, nil
}
func main() {
    p, q, g := gen(1024)
    fmt.Println(p)
    fmt.Println(q)
    fmt.Println(g)
}

Running the above code can generate p,q,g of 1024 bits. Note that if there is not enough randomness on your computer, the above code can take a long time (10 minutes or longer). One way to increase randomness on a linux computer is to use the keyboard, mouse and send/receive network packages.