Generation of a cyclic group of prime order I am trying to implement a cyclic group generator in Java, but I am running into some issues. In many cryptosystems, the following phrase is expressed during the key generation stage.


  Let G be cyclic group of prime order q and with a generator g


I have done some research on this and have been able to implement a cyclic group generator with a modulus p and a generator g. However, I am currently stuck on how to make sure that the generated group's order is a prime q.

This is what I have:

public class CyclicGroup {
    private static final int EQUAL = 0;
    private static final BigInteger TWO = new BigInteger("2");

    private BigInteger p, g;

    public CyclicGroup(int bitLength) {
        init(bitLength);
    }

    private void init(int bitLength) {
        BigInteger q = BigInteger.ZERO;

        while (true) {
            q = CryptoUtil.getPrime(bitLength);
            p = (q.multiply(TWO)).add(BigInteger.ONE); // p = 2q+1

            if (!p.isProbablePrime(40)) {
                continue;
            }

            while (true) {
                g = CryptoUtil.rand(TWO, p.subtract(BigInteger.ONE));

                BigInteger exp = (p.subtract(BigInteger.ONE)).divide(q);

                if (g.modPow(exp, p).compareTo(BigInteger.ONE) != EQUAL) {
                    break;
                }
            }

            break;
        }
    }

    public BigInteger getRandomElement() {      
        return g.modPow(CryptoUtil.rand(BigInteger.ONE, p), p);
    }

    public ArrayList&lt;BigInteger&gt; getElements() {
        // This method is horribly ineffective for large groups and should not be used

        ArrayList&lt;BigInteger&gt; elements = new ArrayList&lt;BigInteger&gt;();

        BigInteger index = BigInteger.ONE;
        BigInteger element = BigInteger.ZERO;

        while (element.compareTo(BigInteger.ONE) != EQUAL) {
            element = g.modPow(index, p);
            elements.add(element);

            index = index.add(BigInteger.ONE); // index++
        }

        return elements;
    }

    public BigInteger getModulus() {
        return p;
    }

    public BigInteger getGenerator() {
        return g;
    }
}


The above class generates a cyclic group with modulus p and a generator g. The following code will produce the subsequent sample output. Note that the tiny bitlength of 4 is to avoid huge numbers in the sample output.

public class App {
    public static void main(String[] args) throws IOException {
        CyclicGroup cg = new CyclicGroup(4);

        System.out.println("Modulus (p): " + cg.getModulus());
        System.out.println("Generator (g): " + cg.getGenerator());
        System.out.println(cg.getElements());
        System.out.println("Random element in group: " + cg.getRandomElement());
    }
}



  Modulus (p): 23
  
  Generator (g): 9
  
  [9, 12, 16, 6, 8, 3, 4, 13, 2, 18, 1]
  
  Random element in group: 9


To sum up, how can I make sure that the generated cyclic group's order is prime? In the above sample output I got lucky that its order is 11. It would also be nice to be able to make the determination without computing all the group's elements and then to count them.

I appriciate any help you are able to give me on this. For your information, my background in group theory is limited at best. Thanks in advance.
One way to do this, if you're working with a multiplicative group $Z^*_p$, is to pick a prime $p$ so that $p-1$ has a large prime factor $q$; once you have this, then to generate a generator of order $q$, you pick a random value $h$, compute $g = h^{(p-1)/q}$, and if that is not 1, then $g$ is a generator of your group.

Obvious questions:


How do you find a large prime factor $q$, given that $p-1$ is hard to factor?  Well, you pick the prime factor $q$ first, and you look for a prime $p$ in the form $kq+1$.
How likely is it that $h^{(p-1)/q} \ne 1$?  Well, if $h$ is selected randomly from the range $[1, p-1]$, that will be one with probability $1/q$, and so you'll almost always get a usable $g$ with just one random $h$.


Another way to do this is pick a prime $p$ with $q = (p-1)/2$ also prime and $p \equiv 7 \pmod{8}$.  In this case, $g=2$ is guaranteed to be a generator of order $q$.  This is a bit more work, however you can use the primes $p$ from this RFC; all those primes have these properties.