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.