Restore divide_by_vanishing_poly_on_coset_in_place

[swasilyev]

arkworks-rs/groth16#40 (comment)

What do you think?

[Pratyush]

because the vanishing polynomial is sparse, standard schoolbook division is actually efficient enough. This is implemented as https://docs.rs/ark-poly/0.4.0-alpha.3/ark_poly/polynomial/univariate/struct.DensePolynomial.html#method.divide_by_vanishing_poly

I suspect that this will be more efficient than dividing in the evaluation domain over the coset, no?

[achimcc]

But the evaluation domain consists of roots of unity and because of this the vanishing polynomial is constant on the coset domain and we therefore have to evaluate it in only one point like it is done here: https://github.com/achimcc/groth16/blob/master/src/r1cs_to_qap.rs#L201
That should be way more efficient than a general polynomial division?

[Pratyush]

Since the vanishing polynomial consists of only two terms, general polynomial division is equally efficient.

[swasilyev]

My point probably was that you don't always have the polynomial in the monomial form. I wanted to present Groth16 as an example but then realized that the division can be avoided altogether by normalizing the crs, see arkworks-rs/groth16#41

Still, current implementation of Groth16 does the coset division : https://github.com/arkworks-rs/groth16/blob/9bac46fb3b1fbc0d2c88c6bc59b0ba798216bf6f/src/r1cs_to_qap.rs#L201-L208