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 zeroknowledge proof systems (not just those mentioned in the Introduction), it will also give us some crucial intuition about what is happening in DEEPFRI 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)

