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&lt;BigInteger&gt; 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&lt;BigInteger&gt; zGenerator(BigInteger i, boolean safePrime, int count)
{
    Set&lt;BigInteger&gt; numbers = new TreeSet&lt;BigInteger&gt;();

    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) &gt; 0)
                numbers.add(num);
            else
                numbers.add(num.negate().mod(i));
            num = num.add(BigInteger.ONE);
        }while((--count &gt; 0) &amp;&amp; (num.compareTo(i) &lt; 0));
    }

    return (new ArrayList&lt;BigInteger&gt;(numbers));
}


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

I even tried using $g^q=p-1 \bmod p$
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.