# Z*p Generator (Cyclic Group) in java

I am trying to implement ElGamal in java without using the in-built libraries. The problem occurs when I am trying to find the generators of the number(in this case 11). Everything works perfectly except that it is returns 10 as a valid generator of 11(which it is not, right?)

public void generateKey()
{
SecureRandom r = new SecureRandom();
BigInteger i ;
//i = new BigInteger(2048, certainty, r);
i = new BigInteger("11");
ArrayList<BigInteger> numbers = new ArrayList();
boolean safePrime = isSafePrime(i);

numbers = zGenerator(i, safePrime, 10);

System.out.println(numbers);
}

public boolean isSafePrime(BigInteger i)
{
return i.subtract(BigInteger.ONE).divide(new BigInteger("2")).isProbablePrime(90);
}

public ArrayList<BigInteger> zGenerator(BigInteger i, boolean safePrime, int count)
{
Set<BigInteger> numbers = new TreeSet<BigInteger>();

if(safePrime)
{
BigInteger num = new BigInteger("2");
BigInteger exp = i.subtract(BigInteger.ONE).divide(new BigInteger("2"));
do
{
if(num.modPow(exp, i).compareTo(BigInteger.ONE) > 0)
else
}while((--count > 0) && (num.compareTo(i) < 0));
}

return (new ArrayList<BigInteger>(numbers));
}


Output: [2, 6, 7, 8, 10]

I even tried using $g^q=p-1 \bmod p$

-
Write down the criteria defining a valid generator; then the method you use to find them; hopefully that will help. – fgrieu Jan 28 '14 at 6:36

Well, if $g$ is a generator of $\bmod\ p$ for prime $p$; that is, if all values in the range $[1, p-1]$ are possible values for $g^i \bmod p$, then we have $g^a \neq 1 \bmod p$ for any $a = (p-1)/r$ where $r$ is a prime factor of $p-1$.

You select $p$ to be a "safe prime", that is $p-1 = 2 \times q$ where $q$ is also a prime. This implies that, in this case, there are only two values of $a$ that are of interest:

• $a = q$ (with $r = 2$), this implies the condition that $g^q \ne 1 \bmod p$

• $a = 2$ (with $r = q$), this implies the condition that $g^2 \ne 1 \bmod p$

Both conditions must be true, however your code tests only the first condition; it doesn't test the second. Now, it turns out that the only possible values of $g$ that do not meet this second condition is $g=1$ (which doesn't pass the first either), and $g=p-1$, or in your case, $g=10$.

Because you're not testing this second condition, you're seeing $g=10$ as looking like a generator when it is not.

Now, $p-1$ is the only value which is excluded by this second condition, in practice it's probably easy just to test values in the range $[2, p-2]$, and not bother explicitly testing this second condition.

-