Squaring the Generator

Introduction

A finite field $F_q$ (a field with $q$ elements) and its nonzero elements $F^*_q$ form a cyclic multiplicative group. Within this group, a generator is an element that can generate all the nonzero elements through successive powers.

In Fast Fourier Transform (FFT) over finite fields, polynomial multiplication, working with the points of this cyclic group is crucial. By squaring the generator $g$, we can transform the group structure to effectively “halve” the domain or focus on subsets(n-th roots of unity) of points, providing computational advantages.

Squaring the Generator in Groups of Power of two Order

Example 1

Consider $F_{7} = \{0, 1, 2, 3, 4, 5, 6\}$. The multiplicative group $F^*_{7}$ has $q-1=7 - 1= 6$ elements (excluding $0$), and it is cyclic, meaning has a generator $\omega$.

Step 0 (The generator($\omega$) of $F^*_{7}$)

We are proving that $F^*_{7} = \langle 3 \rangle$:

\[\begin{aligned} &3^0 = \boxed{1},\\ &3^1 = \boxed{3},\\ &3^2 \equiv \boxed{2},\\ &3^3 \equiv 2 * 3 \equiv \boxed{6},\\ &3^4 \equiv 6 * 3\equiv \boxed{4},\\ &3^5 \equiv 4 * 3 \equiv \boxed{5},\\ &3^6 \equiv 5 * 3 \equiv \boxed{1}, \end{aligned}\]

How about $3^{7}$?

\[ 3^{7} = 3^{6} * 3 \equiv 1 * 3 = 3\\\]

You can see for all $k \ge 7$, the element $3^k$ is equal to one of the $3^0, 3^1, 3^2, \dots, 3^{6}$.

Then $\langle 3 \rangle = \{1, 2, \dots, 6\} = F^*_{7}$.

The below Python code uses the galois library to identify primitive elements (generators) in $F_7$.

import galois
 
GF = galois.GF(7)
 
primitive_elements = GF.primitive_elements
print("Primitive elements:", primitive_elements)
# Primitive elements: [3 5]
 
# Alternatively, find a single primitive element
# suitable when there are a lot of primitive elements
primitive_element = GF.primitive_element
print("A primitive element:", primitive_element)
# A primitive element: 3

Step 1

As you can see in above examples $\omega = 3$.

\[H_{6} = \{3^0=1,3^1, 3^2,\dots, 3^{5}\}\]

Explicitly,

\[H_{6} =\{1 , 3, 2, 6, 4, 5\}\space(\text{all 6 elements})\]

$H_{6}$ is $6$-th roots of unity and $\omega =3$ is primitive $6$-th root of unity.

Step 2

When we square the generator $\omega = 3$, the new generator becomes $\omega^2 = 3^2 = 9 \equiv 2$. Now, $2$ is new generator

\[\text{Powers of $2$} = \{2^0=1,2^1, 2^2,\dots\}\]

Note that for all $k \ge 3$, the element $2^k$ is equal to one of the $2^0, 2^1, 2^2$. Explicitly,

\[H_{3} =\{1 , 2, 4\}\space(\text{all 3 elements})\]

$H_{3}$ is $3$-th roots of unity and $2$ is primitive $3$-th root of unity. You can see by squaring the generator $\omega$ the domain halved.

At this point, continued squaring doesn’t produce anything new, and ultimately, the subgroup collapses to $\{1\}$

Remark

For the purpose of multiplying polynomials with coefficients in $F_q$ and use in FFT, we are interested in integers $n$ of form $n = 2^k$.

The multiplicative group $F^*_q$ is a finite cyclic group of size $q-1$, So there exist $g$ such that $g$ is generates $F^*_q$.

Suppose $n$ divides $q-1$, then we have a primitive $n$-th root of unity like $\omega = g^{\frac{q-1}{n}}$ such that the subgroup of size $n$ is exactly $n$-th roots of unity $H_n$ which generated by $\omega$

\[H_n = \{1, \omega^1, \omega^2, \dots, \omega^{n-1}\}\]

The subgroup generated by $\omega^2$ will have half of the order of $H_n$. This is because the squaring operation effectively skips every other element in the cycle generated by $\omega$.

\[H_{\frac{n}{2}}= \{(\omega^2)^0, (\omega^2)^1, (\omega^2)^2, \dots, (\omega^2)^{\frac{n}{2}-1}\} = \{1, \omega^2, \omega^4, \dots, \omega^{n-2}\}\]

Repeat Until $n=1$. Continue halving the subgroup size by squaring the generator, halving $n$, and recalculating the roots of unity.

Example 2

Consider $F_{17} = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16\}$. The multiplicative group $F^*_{17}$ has $q-1=17-1= 16$ elements (excluding $0$), and it is cyclic, meaning has a generator $\omega$.

Step 1

A valid primitive $16$-th root of unity is $\omega = 3$, because $3^{16} = 1$ and no lower power of $3$ gives $1$.

\[H_{16} = \{3^0=1,3^1, 3^2,\dots, 3^{15}\}\]

Explicitly,

\[H_{16} =\{1 , 3, 9, 10, 13, 5, 15, 11, 16, 14, 8, 7, 4, 12, 2, 6\}\space(\text{all 16 elements})\]

$H_{16}$ is $16$-th roots of unity and $\omega =3$ is primitive $16$-th root of unity.

Step 2

When squaring the $\omega = 3$ the $8$-th roots of unity will generate which is a subgroup of order 8.

When we square the generator $\omega = 3$, the new generator becomes $\omega^2 = 3^2 = 9$.

\[H_{8} = \{9^0, 9^1, 9^2, 9^3, 9^4, 9^5, 9^6, 9^7\}\]

Explicitly, the subgroup generated by $9$ is:

\[H_{8} = \{1, 9, 13, 15, 16, 8, 4, 2\}\]

This group is $8$-th roots of unity and the element $9$ is primitive $8$-th root of unity.

Step 3

Squaring new generator (primitive $8$-th root of unity) which is $9$, we have $9^2 = 81 \equiv 13$ is primitive 4-th root of unity and the powers of $13$ generates the subgroup of 4-th roots of unity:

\[H_{4} = \{13^0, 13^1, 13^2, 13^3\}\]

Explicitly, the subgroup generated by $13$ is:

\[H_{4} = \{1, 13, 16, 4\}\]

Step 4

Squaring new generator (primitive 4-th root of unity) which is $13$, we have $13^2 \equiv 16$ is primitive $2$-th root of unity and the powers of $16$ generates the subgroup of $2$-th roots of unity:

\[H_{2} = \{16^0, 16^1\}\]

Explicitly, the subgroup generated by $16$ is:

\[H_{2} = \{1, 16\}\]

Note: In $F_{17}$ the element $16 \equiv -1$.

# Define the prime and its generator
p = 17  # Prime field: F_p
g = 3   # Generator of the multiplicative group F_p*
 
# Function to compute all n-th roots of unity in F_p
def compute_roots_of_unity(p, g, n):
    roots = [(g**k) % p for k in range(n)]  # Calculate powers of g modulo p
    return roots
 
# Function to perform halving steps
def halving_steps(p, g, n):
    current_roots = compute_roots_of_unity(p, g, n)  # Full group (n roots)
    print(f"n={n} roots of unity: {current_roots}")
    
    step = 1
    while n > 1:
        g = (g**2) % p   # Square the generator
        n = n // 2       # Halve the subgroup size
        current_roots = compute_roots_of_unity(p, g, n)
        print(f"Step {step}: n={n} roots of unity: {current_roots}")
        step += 1
 
# Prime Field F_17: Roots of Unity example
n = 16  # Choose a power of 2
halving_steps(p, g, n)

// Outputs
step 1: n=16 roots of unity: [1 , 3, 9, 10, 13, 5, 15, 11, 16, 14, 8, 7, 4, 12, 2, 6]
step 2: n=8 roots of unity: [1, 9, 13, 15, 16, 8, 12, 6]
Step 3: n=4 roots of unity: [1, 13, 16, 12]
Step 4: n=2 roots of unity: [1, 16]

Summary

Field $F_q$ and generator of $F^*_q$:

The multiplicative group of nonzero elements, $F^*_q$, is cyclic and can be generated by a primitive element (generator) $\omega$.

Squaring the Generator:

Squaring $\omega$ (i.e., $\omega^2$) yields a new generator, which skips every alternate element in the group.

This halves the group size, reducing the domain of 𝑛 -th roots of unity.

Iterative Halving:

Repeatedly squaring the generator continues halving the group size, eventually collapsing it to $\{1\}$.

Practical applications include evaluating polynomials over finite fields by successively reducing the computational workload.

roots-of-unity-v1 polynomial-representations-v1

Squaring the Generator

Introduction