Finite Fields

Finite Fields

A finite field (or Galois field) $\text{GF}(q)$ has exactly $q$ elements, where $q$ must be a prime power: $q = p^k$.

$\text{GF}(p)$ — Prime Fields

When $k = 1$, $\text{GF}(p) = \mathbb{Z}_p$. These are the simplest finite fields.

Multiplicative Group Structure

The nonzero elements of $\text{GF}(p)$ form a cyclic group under multiplication. A primitive root (generator of this group) $g$ satisfies:

$\{g^1, g^2, \ldots, g^{p-1}\} = \{1, 2, \ldots, p-1\}$

Finding Primitive Roots

An element $g$ is a primitive root mod $p$ if and only if $g^{(p-1)/q} \not\equiv 1 \pmod{p}$ for every prime factor $q$ of $p - 1$.

Discrete Logarithm

Given a primitive root $g$, the discrete logarithm $\log_g(a)$ is the unique $k$ such that $g^k \equiv a \pmod{p}$.

def discrete_log(g, a, p):
    power = 1
    for k in range(p - 1):
        if power == a:
            return k
        power = (power * g) % p
    return -1

The difficulty of computing discrete logarithms in large fields is the basis of many cryptographic systems.

Your Task

Implement is_primitive_root(g, p), find_primitive_roots(p) returning all sorted primitive roots, and discrete_log(g, a, p).