3 ms·
> In other words: in finite fields there's no restriction on the evaluation points What about prime-power order? Does it also hold?
by ithinkso 3y ago
> In other words: in finite fields there's no restriction on the evaluation points
What about prime-power order? Does it also hold?
- meindnoch 3y agoI 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?