Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants
We present two new data structures for computing values of an n-variate polynomial P of degree at most d over a finite field of q elements. Assuming that d divides q- 1 , our first data structure relies on (d+ 1) n + 2 tabulated values of P to produce the value of P at any of the qn points using O(nqd2) arithmetic operations in the finite field. Assuming that s divides d and d / s divides q- 1 , o