Re:An Interactive Introduction to Fourier Transforms
by meindnoch on Thursday May 18, 2023 @05:22PM
(#35994221)
I meant GF(q) to be the general finite field, i.e. GF(p^m) for prime p, and n >= 1
The multiplicative group of a finite field is always cyclic of order one less than the order of the field.
What's more interesting to ask is what happens when you're working over GF(q) and want to do evaluate polynomials of length N, if N does not divide q-1? You see, the Fourier transform needs a primitive Nth root of unity to work, but in GF(q) there's no Nth root of unity if N doesn't divide q-1.
Maybe if we extend the polynomial with zero coefficients we can upgrade our Fourier transform from length N < q-1 to length q-1? It sounds workable. But is there a similar trick for Lagrange interpolation?
The multiplicative group of a finite field is always cyclic of order one less than the order of the field.
What's more interesting to ask is what happens when you're working over GF(q) and want to do evaluate polynomials of length N, if N does not divide q-1? You see, the Fourier transform needs a primitive Nth root of unity to work, but in GF(q) there's no Nth root of unity if N doesn't divide q-1.
Maybe if we extend the polynomial with zero coefficients we can upgrade our Fourier transform from length N < q-1 to length q-1? It sounds workable. But is there a similar trick for Lagrange interpolation?