# Roots of unity & FFTs

### Notation

Say we have a finite field $\mathbb{F}$ of order $p$.
We write $p-1 = 2^k * t$ for some $t$ and $k$
* $\mathbb{F}$ has **two** subgroups of order $2^k$ and $t$

Denote a generator $\alpha$ of the $n = 2^k$ order subgroup $\mathbb{G}$:
* $|\mathbb{G}| = n$ (number of points in the subgroup)
* $\mathbb{G} = \{1,\alpha,\alpha^2,\dots, \alpha^{n-1}\}$

### Roots of unity

A nth-root of unity is a number $x$ such that $x^n \equiv 1 (\textrm{mod } p)$
In this case, regardless of the which element $a$ of $G$ you take, you always get $a^n \equiv 1$ because $a = \alpha^{i}$ so $a^n = (\alpha^{n})^i = (1)^i = 1$ since $ord(\alpha) = n$ so by definition $\alpha^n = 1$ (from Little Fermat Theorem).

### Primitive Roots of unity

$\omega$ is a nth primitive root of unity when $\omega$ is
* a nth-root of unity
* $w^i \not\equiv 1$ for all $j >0$ and $j|n$ and $j \neq n$

It is called primitive because $\{w^i\}$ with $i>0$ generates the set of all nth-roots of unity.

#### Properties

The following two properties are useful when computing with the polynomials during the arithmetization:

* **Negation**: $\omega^{n/2 + i} = -\omega^i$
* **Halving**: $(\omega^{n/2 + i})^2 = (\omega^i)^2$
* This means that squaring all roots of unity: $(\omega^i)^2$ only gives back _half_ of these roots.
* $(\omega^3)^2 = (\omega^{n/2 + 3})^3$ - both elements are equal
* This "half" is actually the set of $n/2$-roots of unity since each of the $n/2$ roots of unity can be expressed as $w^i$ for $i:0 \rightarrow n/2$, so we have the following relationship:

$$
(w^i)^{n/2} = w^{in/2} = (w^n)^{i/2} = 1
$$
Therefore, each such $w^i$ element is a $n/2$ root of unity.

### Example in $\mathbb{F_7}$

**3rd-roots of unity**: `[print(f"{i} -> {i**3 % 7}") for i in range(0,7)]`
0 -> 0^3 = 0
1 -> 1^3 = 1 --> **YES**
2 -> 2^3 = 1 --> **YES**
3 -> 3^3 = 6
4 -> 4^3 = 1 --> **YES**
5 -> 5^3 = 6
6 -> 6^3 = 6

The set $\{1,2,4\}$ is the set of all 3rd roots of unity.
**Primitive 3rd-roots of unity**:
We try to find if 2 is a 3rd primitive roots of unity, i.e. for all $i | n$, we compute $2^{(n/i)}$ and look if result is $\neq 1$.
* 2^(3/1) = 2 -> 1 is a primitive root of unity but it doesn't "count" really
* 2^(3/2) -> 2 doesn't divide 3

We stop here since we only do the$2^{(n/i)}$ operations where $i$ is a _divisor_ of 3.

### Code example

Code to find all roots of unity and primitive roots of unity

#!/usr/bin/python

def is_roots_of_unity(q,n,a):
    return a**n % q == 1
    
def is_primitive(q,n,a):
    if not is_roots_of_unity(q,n,a):
        return False
    for i in range(1,n): # only start from 1 since i > 0
        if i % n != 0:
            continue # i must be a divisor of n
        wi = a**(n/i) % n 
        print(f"{i}: {a}^{n/i} mod {q} = {wi}")
        if wi == 1: # primitive must be different than 1 at all times
            return False
    return True

field = 7
roots = 3
for a in range(1,7):
    print(f"is {a} a primitive {roots}-roots of unity {is_primitive(field,roots,a)}")

Example output:

is 1 a primitive 3-roots of unity True
is 2 a primitive 3-roots of unity True
is 3 a primitive 3-roots of unity False
is 4 a primitive 3-roots of unity True
is 5 a primitive 3-roots of unity False
is 6 a primitive 3-roots of unity False

## FFT

To multiply two polynomials $A(x)$ $B(x)$ together, we can either:
* multiply using **the coefficients** which takes $O(n^2)$
* multiply using the **evaluations points** which takes $O(n)$, **much better**

To use the second method the overall strategy is:
1. Convert the polynomials to evaluation points
+ $A = \{(x_1,A(x_1)),\dots,(x_n,A(x_n))\}$
+ $B = \{(x_1,B(x_1)),\dots,(x_n,B(x_n))\}$
2. Multiply the points together
+ $C = \{(x_1,A(x_,1)*B(x_1)),\dots,(x_n,A(x_n)*B(x_n))\}$
3. Revert back to the coefficients forms
+ $C = c_0 + c_1 * x + \dots + c_{n-1} * x^{n-1}$

FFTs enables us to do the first step in $O(nlog(n))$ instead of $O(n^2)$

### 1. Divide and conquer

Let's express $A$ into a sum of even and odds powers polynomials:
* $A(x) = A_1(x) + x * A_2(x)$
* ex: $1 + 3x + 8x^2 + 2x^3 = (1 + 8x^2) + x*(3 + 2x^2)$
* **Equivalent form** $A(x) = A_e(x^2) + x * A_o(x^2)$

### 2. Using roots of unity

As the evaluation points, we will be using the roots of unity! So each input is a power of the primitive root of unity $w$:
$$
A(w^i) = A_e((w^i)^2) + w^i*A_o((w^i)^2)
$$
We want to evaluate $A$ on all $n$th roots of unity which is a set of size $n$. By using the **negation rule** of the primitive root of unity, we can express the "upper" half of the powers ($w^i$ for $i:n/2 \rightarrow n$) as a combination of the evaluation of the "lower" part of the set. For $i: 0 \rightarrow n/2$, we have:
$$
A(w^{i+n/2}) = A_e((-w^{i+n/2})^2) + w^{i+n/2}*A_o(-(w^{i+n/2})^2)=\\
A_e((w^i)^2) - w^i*A_o((w^i)^2)
$$

In short, by evaluating half of the points, we can compute the evaluation of the second half!. Here it suffices to compute $A_e((w^i)^2)$ and $A_o((w^i)^2)$. **We went from 1 polynomial evaluation of degree to 2 polynomial evaluation of degree n/2.**

### 3. Recurse

We went from evaluating $n$ points to evaluating $n/2$ points. The idea here is to recurse. Using the same logic, we need a way to evaluate the $n/2$ roots of unity $w^i$ in terms of the $n/4$ roots of unity. Well, it turns out that squaring the first $n/2$ $n$-roots of unity gives us the $n/2$ roots of unity !
That means we can now recurse using the $n/2$ roots of unity:

TO DO LEFT