
To this day, no method of finding a generator of
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
. — Keith Conrad
An th root of unity in a finite field
is an element
satisfying
, where
is an integer. If
is the smallest positive integer with this property,
is called a primitive
th root of unity. If
is a primitive
th root of unity, then all elements in the set
are also roots of unity. Actually, the set
form a cyclic group of order
under multiplication, with generator
.
Problem: Suppose you are given a finite field of degree
, and you are promised that there indeed exists a primitive
th root of unity
for
prime. Find
, 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.
Continue reading “Finding a Primitive p-th Root of Unity in a Finite Field, with C++ Code”