Store Unrandomized Polynomials

[aszepieniec]

Here is a potential space and speed improvement: do not store the randomized trace polynomials but store the unrandomized trace polynomials instead.

For starters, this gives faster interpolation. The domain size is half.

To randomize the polynomial in monomial-coefficient form, select a vector of k uniformly random field elements, and add this vector to the vector of coefficients in slices [0:k] and [N:N+k]. This corresponds to adding a multiple of $X^N+1$ where the cofactor consists of k uniformly random coefficients. By construction, this term disappears on the trace domain (whose length is N.)

The next step is to not even bother storing the k randomizer coefficients for every column -- instead, derive them pseudorandomly from a random seed and the column index. You only need the full polynomial when low-degree extending; afterwards the k randomizer coefficients can be thrown away again to save space.