Rot256 : Cryptography & Other Random Bits.

# 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.

SageMath code (click to expand)
  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