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.

Let be the multiplicative group of the finite field . Let is the order of . For a th root of to exist, must divide . Why? Because by Lagrange’s theorem, the order of a subgroup, here the group of the th roots of unity under multiplication, must divide the order of the group, which is .

So, how does one find ? The short answer is, via a generator of in three steps: (1) Randomly pick an element . (2) check that for all prime factors of . (3) The element will be a th root of unity in .

**About the code**

The following C++ code is written using Victor Shoup’s super awesome library NTL. The code is part of another project I am working on: I need to compute the rank of submatrices of a Vandermonde matrix generated by a th root of unity in the finite field , given divides . The field is represented as the set of polynomials of degree strictly less than over , which is isomorphic to the quotient ring where is an irreducible polynomial of degree exactly . Since is irreducible over , this ring is indeed a field.

The following code implicitly uses namespace NTL. The type NTL::Vec has been typedef’d to Vector.

**Part 1: Finding a generator of a cyclic group **

The multiplicative group of a finite field is cyclic. (Why?) Moreover, it is a direct product of many cyclic subgroups.

There is no algebraic method to directly pinpoint a generator of a multiplicative group. The number of generators of equals the number of integers in that are coprime to . This quantity is , where is Euler’s totient function defined as and . It is known that the ratio is at least . (Source?) Hence a random element has a decent probability of being a generator.

Now, given an element , how do we test whether a given element generates the entire multiplicative group and not any subgroup? For to be a generator of , we need . Obviously, we need to check that . Second, we need to check that for all positive integers between and , that . However, there is a better of

However, there is a better way of checking this provided we are also given the list of prime factors of . If generates a subgroup of , then would be a proper divisor of since by Lagrange’s theorem, the order of a subgroup divides the order of the group. Since we have already seen $latx g^p=1$, we can be sure that for all other prime factors of . We don’t need to test all divisors of ; checking that for all primes dividing suffices since they cover the candidate divisors.

The following code uses the function factorInt() to extract unique prime factors of ; this function is discussed later on.

GF2X findGenerator() { GF2X gen; ZZ otherFactor(groupOrder / params.p); factors.kill(); factorInt(factors, otherFactor); unique<zz>(factors); factors.append(ZZ(params.p)); bool genGood = false; while (not genGood) { // try a random element as a generator gen = GF2X::zero(); while (IsZero(gen)) random(gen, params.degree); // gen != zero genGood = true; // temporarily for (auto factor : factors) { ZZ orderOverFactor(groupOrder / factor); if (unity == PowerMod(gen, orderOverFactor, modpoly)) { genGood = false; break; } } } // gen^factor != unity for all factors, including p return gen; }

**Part 2: Finding a primitive root of unity**

Next, let us find a primitive th root of unity using the generator . If we set and where is a generator of , then . Note that must be a positive integer since divides . It follows that is a th root of unity in the finite field . Moreover, since is prime, the cyclic group has no non-trivial subgroups, meaning there cannot be any integer such that . Hence is a primitive th root of unity.

(To do: how would one proceed if was not a prime and we insisted on a *primitive* root instead of any root?)

// Set the unity and the monomial X element SetCoeff(unity, 0, 1); SetCoeff(X, 1, 1); // Multiplicative group order ZZ one(1L); groupOrder = LeftShift(one, params.degree) - 1; // unknown degree, got to build irred and the modulus BuildIrred(irred, params.degree); build(modpoly, irred); GF2E::init(irred); // p must divide the (multiplicative) group order if (groupOrder == (ZZ) params.p) { // prime order gen = rootP = X; factors.kill(); factors.append((ZZ) params.p); } else { gen = findGenerator(); // gen is a generator // compute r=gen^(ord/p) so that r^p = gen^ord = 1 // since gen is a generator, gen^x = 1 for no x < ord rootP = PowerMod(gen, groupOrder / params.p, modpoly); }

**Part 3: Finding the unique prime factors of any integer**

The above code uses a factorization function to factorize . Since we don’t need the exponents of individual primes for our application, only a list of unique factors suffices. Here is a code which implements Pollard’s rho algorithm, combined with Miller’s probabilistic primality test. It’s not supersonic, but good enough.

Given an integer , the algorithm basically finds one (possibly composite) factor and then proceeds recursively. First, it checks if is even (or a power of 2), in which case a factor. (We could have done this for first few primes, but I didn’t.)

Next, the obvious: it (probabilistically) checks whether is a prime, and if so, it gives up. The checking is performed using the celebrated Miller-Rabin probabilistic primality test. (Digression: I had a chanced to attend a lecture/conference from Gary Miller; he is awesome.)

Next, we randomly seed Pollard’s rho algorithm and find a factor. If it fails, we retry several times. If it still fails, we think that is probably prime. I tried 10 times, but you could do as many times as you please. The function is used to imitate a pseudo-random sequence.

Once Pollard’s rho algorithm finds a factor of , the next is obvious: we remove all powers of from . Then we recurse on and .

void factorInt(Vec<ZZ>& factors, ZZ n) { if (n <= 1) return; ZZ x, y, gcd, seed; ZZ numTrials(10L); ZZ trial(0L); ZZ q; //long n2 = conv<long>(n); do { // even if (not IsOdd(n)) { factors.append(ZZ(2)); while (n > 2 && divide(q, n, 2)) n = q; // power of two if (n <= 2) return; } if (ProbPrime(n)) break; // n is not a prime RandomBnd(seed, numTrials); x = y = seed + 2; gcd = ZZ(1L); //n2 = conv<long>(n); while (gcd == 1) { g(x, x, n); g(y, y, n); g(y, y, n); gcd = GCD( abs(x-y), n); } long gcd2 = conv<long>(gcd); if (gcd == n) { trial++; continue; // retry } else { // remove all powers of gcd from n while (divide(q, n, gcd)) n = q; //long n2 = conv<long>(n); // subsequent factors Vec<ZZ> childFactors; if (n > 1) factorInt(childFactors, n); if (gcd > 1) factorInt(childFactors, gcd); factors.append(childFactors); // done return; } } while (n > 1 && trial < numTrials ); // probably prime factors.append(n); return; }

**A brief remark on Pollard’s rho algorithm.** *(Please let me know if I have a gap in my argument.)* Imagine the group as a cycle of size . Then, the function samples a (sub)cycle of this big cycle where divides . If we are unlucky, the sampled cycle is the original one. Otherwise, the sampled cycle is pretty small (of size ). This means the set , corresponding to the seed , the element being the identity element with order . Hence it is a subgroup of $Z/nZ$. By Lagrange’s theorem, must divide $n=ord(Z/nZ)$.

Note that Pollard’s rho algorithm actually detects two elements which are congruent modulo . Then the difference must be a multiple of . The algorithm outputs , which is strictly less than if indeed .

As mentioned in the Wikipedia article linked above, this algorithm can be improved by replacing multiple GCD computations with a single computation (in batch, you could say).

**Bonus material: Unique elements from an NTL vector**

Finally, the following code keeps only the unique elements in an NTL vector. I used a brute force time loop. Ideally, one should use a better search method (possibly via a binary search tree or a hash table.) However, GCC was complaining when I wanted to use a hashmap with NTL::ZZ keys/values, so I gave up for the sake of some development-time.

template <typename T> void unique(Vec<T> & src) { std::vector<T> arr; toStdVector<T>(arr, src); src.kill(); while (arr.size() != 0) { T elem = arr[0]; src.append(elem); auto it = arr.begin(); while (it != arr.end()) { if (*it == elem) it = arr.erase(it); else it++; } } // // // typedef std::unordered_map<T, T> Map; // Map ht; // for (T& item : src) { // if (ht.find(item) == ht.end()) // ht[item] = item; // } // src.kill(); // for (auto pos = ht.begin(); pos != ht.end(); pos++) { // src.append(pos->first); // } }

I’d be glad to hear what you think. How would *you* have done it?