Lagrange basis optimization to Aurora's Lincheck

[ValarDragon]

In Aurora, part of the verifier work is evaluating p_alpha^(1) at the query point. Due to the current choice of p_alpha^(1), (which is evaluations of powers of alpha), the verifier has to do an IFFT to get p_alpha^(1) as a polynomial, and then do a linear time evaluation procedure. Alternatively it can do lagrange interpolation to evaluate this at the point. Both of these procedures are pretty slow though.

Within succinct Aurora, part of how Succinct lincheck achieves succinctness is by having the verifier sample the random polynomial from the lagrange basis. This is because this random polynomial can be efficiently sampled and evaluated in polylog operations. We should integrate this into Aurora for p_alpha^(1), to save the verifier O(H) operations per query for interpolating p_alpha^(1).

** OUTDATED Benchmarks, may or may not still hold:
This is currently implemented on the branch lagrange_basis_aurora_speedup, and it achieves a 20% verifier time speedup in the multiplicative case, and a 30% verifier time speedup in the additive case, and noticeable improvement in the prover time. The verifier should speedup even more after we add a method to check if subsets are equal.

However this is only implemented in the case where |constraint domain| >= |variable domain|. When |variable domain| > |constraint domain|, we must have p_alpha^(1) evaluate to 0 for x \in (variable domain / constraint domain) . I believe that the degrees work out correctly if we instead set p_alpha^(1) to be this lagrange sampled polynomial multiplied by Z_{variable domain} * Z_{constraint domain}^{-1}. We should add this extra computation in the case where |constraint domain| >= |variable domain|.

We also need to add some documentation around this, as its not specified in the Aurora paper.