Is 6 a generator of this Group?

Question

I've had the opportunity to learn about the mathematics behind Diffie-Hellman key exchanges, prime numbers, generators of groups, and all that good stuff. I wish I understood it, it's discomforting writing code you don't fundamentally understand.

As I take baby steps, I'm using small values for $N$ (the prime number). The largest prime that can fit in 8-bits is 251. Now, I need to find a generator for this group (which I believe is notated as $Z^*_{251}$).

It's my understanding that a generator $g$ should be a value such that $g^a \mod N = A$ can generate an $A$ in $[1,250]$ (250 is $N-1$). Using a brute-force approach I selected as a candidate, $g=2$, and found quickly that I could not generate $[1,250]$. $g=3$ was also invalid.

Using this brute force I found that the following are generators for $Z^*_{251}$: $[6, 11, 14, 18, 19, 24, 26, 29, 30, 33, 34, 37, 42, 43, 44, 46, 53, 54, 55, 56, 57, 59, 61, 62, 70, 71, 72, 76, 77, 78, 82, 87, 90, 95, 96, 97, 98, 99, 104, 107, 109, 111, 116, 120, 127, 129, 130, 132, 133, 134, 136, 137, 139, 141, 143, 145, 146, 148, 150, 158, 159, 162, 163, 165, 166, 167, 168, 170, 172, 176, 177, 178, 183, 184, 185, 186, 191, 193, 199, 202, 203, 206, 210, 212, 213, 215, 216, 220, 223, 224, 228, 229, 230, 234, 236, 238, 239, 242, 244, 248]$.

My question is straightforward: do I understand the definition of $Z^*_N$ and what are valid generators of said group? Are there more efficient algorithms for calculating the set of generators?

For reference: the code (written in Python).

N=251
generators=[]

for g in range(1,250):
    group = []
    for i in range(1,N):
        A = pow(g, i, N)
        group.append(A)

    for i in range(1,N):
        is_a_g = True
        if i not in group:
            is_a_g = False
            break

    if is_a_g:
        generators.append(g)

print generators

Answer 1

Once you have a generator $g$ of a cyclic group $G$ of order $n$, all the other generators are given by $g^a$ where $\gcd(a,n)=1$. So you pick a random element, test it: $$\forall p|n,\qquad g^{n/p}\neq e,$$ and as soon as you find a generator, you find them all.

Since the order of $(\mathbb{Z}/251\mathbb{Z})^*$ is $250=2\cdot 5^3$, any element $a\in (\mathbb{Z}/251\mathbb{Z})^*$ such that: $$a^{125}\not\equiv 1\pmod{251},\qquad a^{50}\not\equiv 1\pmod{251}$$ is a generator. In order to find $a^{125}$ and $a^{50}$, just compute $a^5$ and $a^{25}$ before, then compute a fifth power and a square.

Answer 2

Yes, there are better approaches.

A better approach is to verify that $g^{n-1} \equiv 1 \mod n$ (which is always true) and $g^{\frac{n-1}{d}} \not \equiv 1 \mod n$ for the factors $d$ of $n-1$. This can be optimized a little bit. See this answer by André Nicolas for a bit more there.

Once you've found one, you can get all the others "for free." In general, we know the order of powers of a number. If $g$ is of order $o$, meaning that $g^o \equiv 1 \pmod n$ and $o$ is the smallest such integer, then the order of $g^k$ is $k/\gcd(o,k)$. So the other generators are obtained from integers $k$ that are relatively prime to $o$.

This is also why there are exactly $\varphi(n-1)$ generators of $(\mathbb{Z}/n\mathbb{Z})^\times$ (if there are any).

Answer 3

If $GF(p^n)$ is the Galois field with $p^n$ elements ($p$ prime), there is no known algorithm that allows for the finding of a generator. Take $n=1$ and you'll discover that, in particular, it is not known how to discover a generator for $GF(p)= \mathbb{Z}_p$. When $N$ is composite, it is easy to understand that the situation is even more difficult (there is a supplementary integer factorization to be done, another hard problem so far). I do not have any bibliography at hand, but by using Wikipedia and Google as a starting point you will be able to find your way if you really need more information.

(In particular, this is why in elliptic curve cryptography curves are also given together with a generator.)