1//! This module implements useful functions for the permutation check protocol.
 2
 3use crate::poly_iop::errors::PolyIOPErrors;
 4use arithmetic::identity_permutation_mles;
 5use ark_ff::PrimeField;
 6use ark_poly::DenseMultilinearExtension;
 7use ark_std::{end_timer, start_timer};
 8use std::sync::Arc;
 9
10/// Returns the evaluations of two list of MLEs:
11/// - numerators = (a1, ..., ak)
12/// - denominators = (b1, ..., bk)
13///
14///  where
15///  - beta and gamma are challenges
16///  - (f1, ..., fk), (g1, ..., gk),
17///  - (s_id1, ..., s_idk), (perm1, ..., permk) are mle-s
18///
19/// - ai(x) is the MLE for `fi(x) + \beta s_id_i(x) + \gamma`
20/// - bi(x) is the MLE for `gi(x) + \beta perm_i(x) + \gamma`
21///
22/// The caller is responsible for sanity-check
23#[allow(clippy::type_complexity)]
24pub(super) fn computer_nums_and_denoms<F: PrimeField>(
25    beta: &F,
26    gamma: &F,
27    fxs: &[Arc<DenseMultilinearExtension<F>>],
28    gxs: &[Arc<DenseMultilinearExtension<F>>],
29    perms: &[Arc<DenseMultilinearExtension<F>>],
30) -> Result<
31    (
32        Vec<Arc<DenseMultilinearExtension<F>>>,
33        Vec<Arc<DenseMultilinearExtension<F>>>,
34    ),
35    PolyIOPErrors,
36> {
37    let start = start_timer!(|| "compute numerators and denominators");
38
39    let num_vars = fxs[0].num_vars;
40    let mut numerators = vec![];
41    let mut denominators = vec![];
42    let s_ids = identity_permutation_mles::<F>(num_vars, fxs.len());
43    for l in 0..fxs.len() {
44        let mut numerator_evals = vec![];
45        let mut denominator_evals = vec![];
46
47        for (&f_ev, (&g_ev, (&s_id_ev, &perm_ev))) in fxs[l]
48            .iter()
49            .zip(gxs[l].iter().zip(s_ids[l].iter().zip(perms[l].iter())))
50        {
51            let numerator = f_ev + *beta * s_id_ev + gamma;
52            let denominator = g_ev + *beta * perm_ev + gamma;
53
54            numerator_evals.push(numerator);
55            denominator_evals.push(denominator);
56        }
57        numerators.push(Arc::new(DenseMultilinearExtension::from_evaluations_vec(
58            num_vars,
59            numerator_evals,
60        )));
61        denominators.push(Arc::new(DenseMultilinearExtension::from_evaluations_vec(
62            num_vars,
63            denominator_evals,
64        )));
65    }
66
67    end_timer!(start);
68    Ok((numerators, denominators))
69}