# Finding a Primitive p-th Root of Unity in a Finite Field, with C++ Code

To this day, no method of finding a generator of $Z_p^*$ is known to be more efficient than essentially trying 2, then 3, and so on. Who cares? Well, the difficulty of breaking a certain public key cryptosystem (due to El Gamal) depends on the difficulty of working with generators of $Z_p^*$.Keith Conrad

An $n$th root of unity in a finite field $F$ is an element $r \in F$ satisfying $r^n=1$, where $n$ is an integer. If $n$ is the smallest positive integer with this property, $r$ is called a primitive $n$th root of unity. If $r$ is a primitive $n$th root of unity, then all elements in the set $\mu_n = \{1, r, r^2, \cdots, r^{n-1}\}$ are also roots of unity. Actually, the set $\mu_n$ form a cyclic group of order $n$ under multiplication, with generator $r$.

Problem: Suppose you are given a finite field $F=GF(2^d)$ of degree $d$, and you are promised that there indeed exists a primitive $p$th root of unity $r\in F$ for $p$ prime. Find $r$, and in particular, produce a C++code that finds it.

In what follows, we talk about how to find such a root and provide my C++ code; the code uses the awesome NTL library.

# Const-Pointer and Pointer-to-Const in C / C++

You must have known it already, but I can’t stop myself from showing off the interplay of const with pointers in C/C++.

Here goes the code. It’s simple.


void main() {

int arr[]={1,2,3,4}; // data

const int *p1 = &arr[0]; // non-const ptr to const data
int const *p2 = &arr[0]; // non-const ptr to const data
int* const p3 = &arr[0]; // const ptr to non-const data
const int* const p4 = &arr[0]; // const ptr to const data

p1++; // ok
p1[0]++; // compile error: modifying const data

p2++; // ok
p2[0]++; // compile error: modifying const data

p3++; // compile error: modifying const ptr
p3[0]++; // ok

p4++; // compile error: modifying const ptr
p4[0]++; // compile error: modifying const data

}