zinc_uair/ideal/
rotation.rs

1use crate::{
2    ideal::{Ideal, IdealCheck, IdealCheckError},
3    ideal_collector::IdealOrZero,
4};
5use crypto_primitives::{FieldConfig, ProjectElementWithConfig, SemiringConfig, SetElement};
6use num_traits::Euclid;
7use std::fmt::{Display, Formatter};
8use zinc_poly::univariate::dynamic::{DynamicPolynomial, DynamicPolynomialConfig};
9use zinc_utils::from_ref::FromRef;
10
11/// An ideal of `R[X]` generated by `X^W - generating_root`.
12///
13/// - `W = 1`: the ideal `(X - a)`, checked via point evaluation at `a`.
14/// - `W > 1`: the ideal `(X^W - a)`, checked via polynomial reduction modulo
15///   `X^W - a`.
16///
17/// The compile-time `W` parameter allows the membership check to
18/// specialize: `W = 1` avoids allocating a remainder buffer and uses
19/// Horner evaluation, while `W > 1` uses a chunk-based reduction.
20#[derive(Clone, Copy, Debug)]
21pub struct RotationIdeal<E: SetElement, const W: usize> {
22    generating_root: E,
23}
24
25impl<E: SetElement, const W: usize> RotationIdeal<E, W> {
26    /// Creates a new ideal of `R[X]` generated by `X^W - generating_root`.
27    pub fn new(generating_root: E) -> Self {
28        const { assert!(W >= 1, "Rotation ideal degree W must be at least 1") };
29        Self { generating_root }
30    }
31}
32
33impl<E: SetElement, const W: usize> FromRef<RotationIdeal<E, W>> for RotationIdeal<E, W> {
34    #[inline(always)]
35    fn from_ref(ideal: &RotationIdeal<E, W>) -> Self {
36        ideal.clone()
37    }
38}
39
40impl<E: SetElement, const W: usize> Ideal for RotationIdeal<E, W> {}
41
42impl<E: SetElement, const W: usize> Display for RotationIdeal<E, W> {
43    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
44        write!(f, "RotationIdeal<{:?}, {W}>", self.generating_root)
45    }
46}
47
48impl<E: SetElement, const W: usize> RotationIdeal<E, W> {
49    /// Project a rotation ideal over the ring `R` into the field configured
50    /// by `field_cfg`, by projecting the generating root.
51    pub fn project<C, R>(field_cfg: &C, ideal_over_ring: &RotationIdeal<R, W>) -> Self
52    where
53        C: FieldConfig + ProjectElementWithConfig<R> + SemiringConfig<Element = E>,
54        R: SetElement,
55    {
56        Self {
57            generating_root: field_cfg.project(&ideal_over_ring.generating_root),
58        }
59    }
60}
61
62impl<'a, C: FieldConfig, const W: usize> IdealCheck<DynamicPolynomialConfig<'a, C>>
63    for IdealOrZero<RotationIdeal<C::Element, W>>
64{
65    fn contains(
66        &self,
67        cfg: &DynamicPolynomialConfig<'a, C>,
68        value: &DynamicPolynomial<C::Element>,
69    ) -> Result<bool, IdealCheckError> {
70        if cfg.is_zero(value) {
71            return Ok(true);
72        }
73
74        match self {
75            IdealOrZero::NonZero(RotationIdeal { generating_root }) => {
76                // Elements no longer carry a field config, so a modulus
77                // mismatch between coefficients and the generating root is
78                // not observable here: `cfg` is the single source of truth
79                // for the field both live in.
80                if W == 1 {
81                    Ok(cfg.cfg.is_zero(
82                        &cfg.evaluate_at_point(value, generating_root)
83                            .expect("evaluation of a non-empty polynomial cannot fail"),
84                    ))
85                } else {
86                    Ok(remainder_is_zero::<C, W>(
87                        cfg.cfg,
88                        &value.coeffs,
89                        generating_root,
90                    ))
91                }
92            }
93            IdealOrZero::Zero => Ok(cfg.is_zero(value)),
94        }
95    }
96}
97
98/// Checks whether the polynomial with the given `coeffs` lies in the ideal
99/// `(X^W - a)`, i.e., whether `p(X) mod (X^W - a) == 0`.
100///
101/// Groups coefficients into chunks of `W` and folds from highest to lowest
102/// using `rem = a * rem + chunk`, which is the Horner scheme applied to the
103/// "base-`X^W`" representation of `p(X)`.
104#[allow(clippy::arithmetic_side_effects)] // Was hand-checked to be correct.
105fn remainder_is_zero<C: SemiringConfig, const W: usize>(
106    cfg: &C,
107    coeffs: &[C::Element],
108    a: &C::Element,
109) -> bool {
110    debug_assert!(W > 0, "Was pre-checked so this cannot fail");
111
112    if coeffs.is_empty() {
113        return true;
114    }
115
116    let mut rem: [C::Element; W] = std::array::from_fn(|_| cfg.zero());
117
118    let n = coeffs.len();
119    let (num_full_chunks, partial_len) = n.div_rem_euclid(&W);
120
121    if partial_len > 0 {
122        let start = num_full_chunks * W;
123        for (j, coeff) in coeffs[start..].iter().enumerate().take(partial_len) {
124            rem[j] = coeff.clone();
125        }
126    }
127
128    for chunk_idx in (0..num_full_chunks).rev() {
129        let start = chunk_idx * W;
130        for j in 0..W {
131            cfg.mul_assign(&mut rem[j], a);
132            cfg.add_assign(&mut rem[j], &coeffs[start + j]);
133        }
134    }
135
136    rem.iter().all(|r| cfg.is_zero(r))
137}
138
139#[cfg(test)]
140mod tests {
141    use super::*;
142    use crypto_bigint::{U128, const_monty_params};
143    use crypto_primitives::{FixedConfig, crypto_bigint_const_monty::ConstMontyField};
144    use zinc_poly::univariate::dynamic::HasDynamicPolynomialConfig;
145
146    const_monty_params!(Params, U128, "00000000b933426489189cb5b47d567f");
147    type F = ConstMontyField<Params, { U128::LIMBS }>;
148    type Cfg = FixedConfig<F>;
149
150    fn poly(coeffs: &[i32]) -> DynamicPolynomial<F> {
151        DynamicPolynomial::new(coeffs.iter().map(|&c| c.into()).collect::<Vec<_>>())
152    }
153
154    #[test]
155    fn w1_ideal_contains_member() {
156        // (X - 2): polynomial X - 2 should be in ideal (X-2) since eval at 2 is 0.
157        let field_cfg = Cfg::default();
158        let ideal = IdealOrZero::NonZero(RotationIdeal::<F, 1>::new(F::from(2)));
159        let p = poly(&[-2, 1]); // X - 2
160        assert!(ideal.contains(&field_cfg.dyn_poly_cfg(), &p).unwrap());
161    }
162
163    #[test]
164    fn w1_ideal_rejects_nonmember() {
165        let field_cfg = Cfg::default();
166        let ideal = IdealOrZero::NonZero(RotationIdeal::<F, 1>::new(F::from(2)));
167        let p = poly(&[1, 1]); // X + 1, eval at 2 = 3 ≠ 0
168        assert!(!ideal.contains(&field_cfg.dyn_poly_cfg(), &p).unwrap());
169    }
170
171    #[test]
172    fn w2_ideal_contains_generator() {
173        // (X^2 - 1): the polynomial X^2 - 1 should be in this ideal.
174        let field_cfg = Cfg::default();
175        let ideal = IdealOrZero::NonZero(RotationIdeal::<F, 2>::new(F::from(1)));
176        let p = poly(&[-1, 0, 1]); // X^2 - 1
177        assert!(ideal.contains(&field_cfg.dyn_poly_cfg(), &p).unwrap());
178    }
179
180    #[test]
181    fn w2_ideal_contains_multiple_of_generator() {
182        // (X^2 - 1): X * (X^2 - 1) = X^3 - X should be in the ideal.
183        let field_cfg = Cfg::default();
184        let ideal = IdealOrZero::NonZero(RotationIdeal::<F, 2>::new(F::from(1)));
185        let p = poly(&[0, -1, 0, 1]); // X^3 - X
186        assert!(ideal.contains(&field_cfg.dyn_poly_cfg(), &p).unwrap());
187    }
188
189    #[test]
190    fn w2_ideal_rejects_nonmember() {
191        let field_cfg = Cfg::default();
192        let ideal = IdealOrZero::NonZero(RotationIdeal::<F, 2>::new(F::from(1)));
193        let p = poly(&[1, 1]); // X + 1
194        assert!(!ideal.contains(&field_cfg.dyn_poly_cfg(), &p).unwrap());
195    }
196
197    #[test]
198    fn w3_ideal_contains_member() {
199        // (X^3 - 2): the polynomial X^3 - 2 should be in the ideal.
200        let field_cfg = Cfg::default();
201        let ideal = IdealOrZero::NonZero(RotationIdeal::<F, 3>::new(F::from(2)));
202        let p = poly(&[-2, 0, 0, 1]); // X^3 - 2
203        assert!(ideal.contains(&field_cfg.dyn_poly_cfg(), &p).unwrap());
204    }
205
206    #[test]
207    fn w3_ideal_rejects_nonmember() {
208        let field_cfg = Cfg::default();
209        let ideal = IdealOrZero::NonZero(RotationIdeal::<F, 3>::new(F::from(2)));
210        let p = poly(&[1, 0, 0, 1]); // X^3 + 1 (not in (X^3 - 2))
211        assert!(!ideal.contains(&field_cfg.dyn_poly_cfg(), &p).unwrap());
212    }
213
214    #[test]
215    fn zero_polynomial_always_in_ideal() {
216        let field_cfg = Cfg::default();
217        let ideal = IdealOrZero::NonZero(RotationIdeal::<F, 4>::new(F::from(5)));
218        assert!(
219            ideal
220                .contains(&field_cfg.dyn_poly_cfg(), &DynamicPolynomial::<F>::ZERO)
221                .unwrap()
222        );
223    }
224
225    #[test]
226    fn zero_ideal_only_contains_zero() {
227        let field_cfg = Cfg::default();
228        let zero_ideal = IdealOrZero::<RotationIdeal<F, 2>>::zero();
229        assert!(
230            zero_ideal
231                .contains(&field_cfg.dyn_poly_cfg(), &DynamicPolynomial::<F>::ZERO)
232                .unwrap()
233        );
234        assert!(
235            !zero_ideal
236                .contains(&field_cfg.dyn_poly_cfg(), &poly(&[1]))
237                .unwrap()
238        );
239    }
240
241    #[test]
242    fn w2_reduction_cross_check_with_naive_substitution() {
243        // Verify our specialized chunked-Horner reduction against an
244        // independent naive algorithm: substitute $X^2 \to a$ one degree at
245        // a time, folding the leading coefficient down until the degree
246        // drops below 2.
247        let field_cfg = Cfg::default();
248        let cfg = field_cfg.dyn_poly_cfg();
249        let a = F::from(3);
250        let ideal = IdealOrZero::NonZero(RotationIdeal::<F, 2>::new(a));
251
252        let is_member_naive = |p: &DynamicPolynomial<F>| {
253            let mut coeffs = p.coeffs.clone();
254            while coeffs.len() > 2 {
255                let top = coeffs.pop().expect("len > 2");
256                let idx = coeffs.len() - 2;
257                let folded = field_cfg.mul(&top, &a);
258                field_cfg.add_assign(&mut coeffs[idx], &folded);
259            }
260            coeffs.iter().all(|c| field_cfg.is_zero(c))
261        };
262
263        for p in [
264            poly(&[1, 2, 3, 4, 5]),
265            poly(&[0, 0, 0, 0, 6]),
266            poly(&[-3, 0, 1]),        // X^2 - 3 itself
267            poly(&[0, -3, 0, 1]),     // X * (X^2 - 3)
268            poly(&[-9, 0, 6, 0, -1]), // -(X^2 - 3)^2
269            poly(&[-8, 0, 6, 0, -1]), // -(X^2 - 3)^2 + 1
270        ] {
271            assert_eq!(
272                ideal.contains(&cfg, &p).unwrap(),
273                is_member_naive(&p),
274                "Mismatch for polynomial: {p}"
275            );
276        }
277    }
278}
zinc_uair/ideal/rotation.rs

zinc_uair/ideal/
rotation.rs
