2
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ Please note that this question has multiple answers, one of which is accepted. Neither of these answers contain any code. Clearly, this question is not about the code, it is about finding a curve with a prime order. Just keep this in mind when voting to keep open or close. $\endgroup$
    – Maarten Bodewes
    Sep 3, 2019 at 0:20

3 Answers 3

10
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ Thanks for this. It helped me greatly. As a followup; is there a quick way to find a large group's order without computing all of its elements and then counting them? $\endgroup$ Feb 2, 2015 at 12:09
  • $\begingroup$ @MortenSalte: as long as we're talking about a subgroup of $Z_p^*$, any subgroup's order will be a (not necessarily proper) divisor of $p-1$. So, if you know the factorization of $p-1$, you can just check either $g^q \equiv 1$ for various factors $q$ of $p-1$. $\endgroup$
    – poncho
    Feb 2, 2015 at 13:56
  • $\begingroup$ Why is the probability $1/q$? $\endgroup$
    – qweruiop
    Aug 1, 2018 at 23:55
  • $\begingroup$ @qweruiop: because there are $(p-1)/q$ elements with $h^{(p-1)/q} = 1$ (because the size of that group is $(p-1)/q$), out of a total of $p-1$ total elements. Hence, the probability that, if you pick an element randomly, you'll pick one of those elements is $\frac{ (p-1)/q}{p-1} = 1/q$ $\endgroup$
    – poncho
    Aug 2, 2018 at 12:16
  • $\begingroup$ Another way to derive the probability $1/q$: We first need to count elements with an order $d$ such that $d \mid (p−1)/q$. According to the Primitive Root Thm, that is $\Sigma_{d \mid (p−1)/q} \phi(d)$, which equals $(p-1)/q$. Thus the probability of choosing one of such elements is $1/q$. $\endgroup$
    – qweruiop
    Aug 2, 2018 at 19:11
1
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ Nit: there's only one element with order 2 ($p-1$ aka $-1$). The element 1 has order 1. $\endgroup$
    – poncho
    Jan 8, 2021 at 18:43
0
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.