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)
|
|