FFT & Field Extension | Lesson 3

This lecture dives into the mechanics of finite field extensions and the highly efficient Fast Fourier Transform (FFT) algorithm. From the foundational concepts of polynomials over fields to practical algorithms used to dramatically speed up cryptographic operations: 

As an exercise, you can:

1. Review the "meta trick" of field extensions. Take the real numbers and the polynomial x2+1 (which has no real roots). Manually trace how defining a new element x where x2=−1 maps perfectly to the imaginary number i, creating the complex plane.

2. Try splitting a simple polynomial of degree 3 (e.g., f(x)=3x3+2x2+x+5) into its even and odd coordinate vectors, exactly as the FFT "divide" step requires.