Generation of a cyclic group of prime order

Question

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<BigInteger> getElements() {
        // This method is horribly ineffective for large groups and should not be used

        ArrayList<BigInteger> elements = new ArrayList<BigInteger>();

        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.

Answer 1

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.

Answer 2

The simplest case for you is to consider prime number p of the form $p=2.p_1+1$. Where p1 is also prime. The structure of the multiplicative group of $\mathbb{Z}_n = \{1,2, ... ,p-1 \}$ splits into 3 subgroups of order 2, $p_1$, p-1. Only quadratic non residue residue have maximal order. elements of order 2 are 1 and p-1. The quadratic residue are those having prime order equal to $p_1$. Use Legendre symbol for testing Quadratic residusie.

Answer 3

Here's a cyclic group of any order $q \ge 1$:

• Identity: $0$.
• Generator: $1$.
• Group operation: $a \cdot b$ is (a + b) % q.