Implement G(X), K(X) optimized computation following Claim 4.5

[arnaucube]

Implement the more efficient (than the current one) computation of $G(X), K(X)$ described in the Claim 4.5 from ProtoGalaxy (https://eprint.iacr.org/2023/1106).

[winderica]

Closing this issue since the optimization was already implemented in dev when I was adapting ProtoGalaxy to our new FS trait design.

Note that while the paper said it's possible to do only (d - 1)k + 1 evaluations, I was a bit lazy when implementing this and instead computed dk + 1 evaluations, which was good enough to me :D

sonobe/wip/fs/src/protogalaxy/mod.rs

Lines 332 to 383 in 6f0dc78

	// Optimized G(X) computation as described in Claim 4.5 of the paper.
	let s_evals = (0..r1cs.n_variables())
	.map(|i| {
	lagrange_bases
	.iter()
	.zip(&zs)
	.map(|(l, z)| l * z[i])
	.fold(DensePolynomial::zero(), |acc, x| acc + x)
	.evaluate_over_domain(G)
	.evals
	})
	.collect::<Vec<_>>();
	let mut invs = G
	.elements()
	.map(|e| e - VC::Scalar::one())
	.collect::<Vec<_>>();
	batch_inversion(&mut invs);
	// Compute evaluations of G(X) - F(alpha)*L_0(X)
	let beta_star_pows = Pow::powers_from_repeated_squares(&betas_star);
	let g_evals = G
	.elements()
	.zip(invs)
	.enumerate()
	.map(|(k, (e, inv))| {
	if k.is_multiple_of(H.size()) {
	return Ok(VC::Scalar::zero());
	}
	let z = AssignmentsOwned::from((
	s_evals[0][k],
	(1..1 + r1cs.n_public_inputs())
	.map(|i| s_evals[i][k])
	.collect(),
	(1 + r1cs.n_public_inputs()..r1cs.n_variables())
	.map(|i| s_evals[i][k])
	.collect(),
	));
	let v = r1cs.eval_assignments(z)?;
	// L_0(e) = (e^H.size() - 1) / (e - 1) / H.size()
	let l_0_eval = H.evaluate_vanishing_polynomial(e) * inv * H.size_inv();
	Ok(v.into_iter().scalar_rlc(&beta_star_pows) - f_alpha * l_0_eval)
	})
	.collect::<Result<Vec<_>, Error>>()?;
	// Interpolate G(X) - F(alpha)*L_0(X)
	let g_poly = Evaluations::from_vec_and_domain(g_evals, G).interpolate();
	// Compute K(X) = (G(X) - F(alpha)*L_0(X)) / Z(X)
	let (mut k_poly, r) = g_poly.divide_by_vanishing_poly(H);
	if !r.is_zero() {
	return Err(Error::IndivisibleByVanishingPoly);
	}