# Finding Roots Of Unity
*Thanks [Matan](https://sites.google.com/view/matanprasmashomepage/publications) for teaching the topic!*
Roots of unity are the elements in a [field](https://en.wikipedia.org/wiki/Field_(mathematics)) that satisfy the equation
$$
x^n = 1
$$
In cryptography, you might come across having to use the [Discrete Fourier Transform](https://en.wikipedia.org/wiki/Discrete_Fourier_transform) (DFT) to optimize polynomial multiplications or [dealing with commitment schemes](https://hackmd.io/@brech1/fk). Roots of unity are a key structure for the DFT, in this post I'll review the steps to find a [generator](https://crypto.stanford.edu/pbc/notes/numbertheory/gen.html) for a group of $n$-th [roots of unity](https://crypto.stanford.edu/pbc/notes/numbertheory/rootsunity.html).
## Prime Field
A prime field is a [finite field](https://en.wikipedia.org/wiki/Finite_field) with a prime number of elements. It is usually denoted by $\mathbb{F}_p$ where $p$ is prime.
In prime fields, every nonzero element has a multiplicative inverse, and there are no zero divisors. This guarantees that the [multiplicative group](https://en.wikipedia.org/wiki/Multiplicative_group) $\mathbb{F}_p^*$ is cyclic (has a generator).
The [cyclic](https://crypto.stanford.edu/pbc/notes/numbertheory/cyclic.html) nature of $\mathbb{F}_p^*$ means that any [subgroup](https://math.libretexts.org/Bookshelves/Abstract_and_Geometric_Algebra/First-Semester_Abstract_Algebra%3A_A_Structural_Approach_(Sklar)/04%3A_Subgroups/4.01%3A_Introduction_to_Subgroups), such as the group of $n$-th roots of unity, is also cyclic.
## Roots Of Unity
An element $\omega$ of a field is an $n$-th root of unity if
$$
\omega^n = 1
$$
For example, in the complex numbers the $n$-th roots of unity are given by
$$
\omega_k = e^{\frac{2\pi i k}{n}} \quad \text{for } k = 0, 1, 2, \dots, n-1
$$
## Lagrange's Theorem
[Lagrange's Theorem](https://en.wikipedia.org/wiki/Lagrange%27s_theorem_(group_theory)) states that for any finite group $G$ and subgroup $H$, the order (number of elements) of $H$ divides the order of $G$:
$$
|H| \mid |G|
$$
When applied to the multiplicative group of a finite field, such as $\mathbb{F}_{p}^*$, we know that this group is cyclic and has order $p$. Therefore, any subgroup of $\mathbb{F}_{p}^*$ must have an order that divides $p$.
## Extending The Field
Now, let's assume we need $n$ roots of unity for our operation. We have to work with a finite field with a sufficiently large multiplicative group ($>n$).
To get a larger field, we consider an [extension field](https://mathworld.wolfram.com/ExtensionField.html), typically denoted by $\mathbb{F}_{p^N}$. This notation indicates that each element of $\mathbb{F}_{p^N}$ can be uniquely written as a linear combination of $N$ basis elements. Since there are $p$ choices for each coefficient, the total number of elements in $\mathbb{F}_{p^N}$ is $p^N$.
Since the multiplicative group excludes the zero element, the group $\mathbb{F}_{p^N}^*$ is of order
$$
p^N - 1
$$
By Lagrange, we can define our condition as:
$$
n \mid (p^N - 1)
$$
To find the minimal extension degree we can perform this check for every element:
```python
def minimal_extension_degree(p, n):
N = 1
while (p**N - 1) % n != 0:
N += 1
return N
```
## Finding $w$
Now that we have extended our field, we can find a generator for the subgroup of $n$-th roots of unity.
To verify whether a candidate element $g$ is a generator, we must check that raising it to the power $\frac{n}{p}$ does not yield the [identity element](https://en.wikipedia.org/wiki/Identity_element). So:
$$
g^{n/p} \neq 1
$$
If any of these powers equals $1$, the element's order is a proper divisor of $n$, and it cannot be a generator. The naive implementation looks like this:
```python
def is_generator(g, group_order):
# Factor the group order
for p, e in factor(group_order):
if g^(group_order // p) == 1:
return False
return True
```
Sage, however, provides a more efficient method for this, which you can view [here](https://github.com/sagemath/sage/blob/develop/src/sage/rings/finite_rings/finite_field_base.pyx#L830).
Since the multiplicative group $\mathbb{F}_{p^N}^*$ is cyclic, every element can be written as a power of a generator $g$. We want to find a primitive $n$-th root of unity $\omega$ that satisfies
$$
\omega^n = 1
$$
Assume that $\omega$ can be written as a power of $g$:
$$
w = g^k
$$
Then we have
$$
w^n = (g^k)^n = g^{kn}
$$
Because $g$ is a generator of $\mathbb{F}_{p^N}^*$ we know that
$$
g^{|F^*|} = g^{p^N - 1} = 1.
$$
In a cyclic group, the equation $g^m = 1$ holds if and only if $|F^*|$ divides $m$. Therefore, for
$$
g^{kn} = 1,
$$
it is necessary and sufficient that $|F^*|$ divides $kn$.
To ensure that $\omega$ is a primitive \(n\)-th root of unity, we choose the smallest $k$ such that this condition is met. The minimal choice is
$$
k = \frac{|F^*|}{n} = \frac{p^N - 1}{n}
$$
Resulting in
$$
\omega = g^{\frac{p^N - 1}{n}}
$$
Once we have our primitive $n$-th root of unity $\omega$, we can generate the complete set of $n$-th roots of unity by taking its successive powers:
$$
\mu_n = \{ \omega^0, \omega^1, \omega^2, \dots, \omega^{n-1} \}
$$
## Mersenne Prime
*Not related to the main topic, but I'll use this in the implementation example.*
A Mersenne number is a number of the form
$$
M_n = 2^n - 1
$$
When a Mersenne number is prime, it is called a Mersenne prime.
> 💡 The present [largest known prime](https://www.mersenne.org/primes/?press=M136279841) is a Mersenne prime.
An interesting one for us is $M_{31}$
$$
M_{31} = 2^{31} - 1
$$
Since $M_{31}$ is a 32-bit prime, every element in the field $\mathbb{F}_{M_{31}}$ can be stored in a single computer word. This leads to very efficient arithmetic operations.
## Full steps
Below are the steps to find the generator for:
- $n = 8$
- $p = M_{31}$
```sage
# Declare n and p
n = 8
p = 2**31 - 1
# Get N (degree of field extension)
N = minimal_extension_degree(p, n)
# Define the Prime Field of order p^N
F = FiniteField(p**N)
# Get the generator of F_p* with Sage's method
gen_mul_subg = F.multiplicative_generator()
# Get roots of unity generator
w = gen_mul_subg ** ((F.cardinality() - 1) // n)
```
After computing this we get:
- $\omega$ = `1816824951*z2 + 1438809788`
- $\mu_n$ = {`1`, `1816824951*z2 + 1438809788`, `209180821*z2 + 2126293891`, ` 1816824951*z2 + 1438744252`, `2147483646`,`330658696*z2 + 708673859`, `1938302826*z2 + 21189756`, `330658696*z2 + 708739395`}
We can verify the obtained roots:
```sage
roots = [w**k for k in range(n)]
for k, r in enumerate(roots):
if r**n != F(1):
print("Verification Failed for root", k)
break
else:
print("All roots verified")
```
## References
- [Circle STARKs: notes from a seminar in Stateless Consensus EF (2024)](https://sites.google.com/view/matanprasmashomepage/publications)
- [Roots of Unity](https://crypto.stanford.edu/pbc/notes/numbertheory/rootsunity.html)
- [Plonky3](https://github.com/Plonky3/Plonky3/blob/main/mersenne-31/src/mersenne_31.rs)
- [Why I’m Excited By Circle Stark And Stwo](https://starkware.co/integrity-matters-blog/why-im-excited-by-circle-stark-and-stwo/)
- [Sage](https://www.sagemath.org/)
Sign in with Wallet
Connect another wallet