Lagrange Basis & Fast Fourier Transform

We start by getting a grasp of how the FFT can be used to quickly compute a change of basis change for the elements of \( \mathbb{F}_p[X] \). Besides being an essential tool in improving the performance of many zero-knowledge proof systems (not just those mentioned in the Introduction), it will also give us some crucial intuition about what is happening in DEEP-FRI over prime fields.

But of course we need a finite field with a subgroup of \( 2^k \)-th roots of unity. Since the multiplicative group of a finite field is always cyclic this simply means that \( 2^k \ | \ p - 1 \). Finding such a field can be done using rejection sampling.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

def find_group(k, cp = 1):
    # find field with 2^k order multiplicative sub-group
    e = 2^k
    N = 0
    while 1:
        p = e * N * cp + 1
        if is_pseudoprime(p):
            break
        N += 1

    F = GF(p)

    # recover 2^k roots of unity sub-group
    g = F.multiplicative_generator()
    c = g.multiplicative_order() / e
    w = g^c

    return F, w