zinc_uair/ideal/
rotation.rs

1use crate::{
2    ideal::{Ideal, IdealCheck, IdealCheckError},
3    ideal_collector::IdealOrZero,
4};
5use crypto_primitives::{FromWithConfig, PrimeField, Semiring};
6use num_traits::{Euclid, Zero};
7use zinc_poly::{EvaluatablePolynomial, univariate::dynamic::over_field::DynamicPolynomialF};
8use zinc_utils::from_ref::FromRef;
9
10/// An ideal of `R[X]` generated by `X^W - generating_root`.
11///
12/// - `W = 1`: the ideal `(X - a)`, checked via point evaluation at `a`.
13/// - `W > 1`: the ideal `(X^W - a)`, checked via polynomial reduction modulo
14///   `X^W - a`.
15///
16/// The compile-time `W` parameter allows the membership check to
17/// specialize: `W = 1` avoids allocating a remainder buffer and uses
18/// Horner evaluation, while `W > 1` uses a chunk-based reduction.
19#[derive(Clone, Copy, Debug)]
20pub struct RotationIdeal<R: Semiring, const W: usize> {
21    generating_root: R,
22}
23
24impl<R: Semiring, const W: usize> RotationIdeal<R, W> {
25    /// Creates a new ideal of `R[X]` generated by `X^W - generating_root`.
26    pub fn new(generating_root: R) -> Self {
27        const { assert!(W >= 1, "Rotation ideal degree W must be at least 1") };
28        Self { generating_root }
29    }
30}
31
32impl<R: Semiring, const W: usize> FromRef<RotationIdeal<R, W>> for RotationIdeal<R, W> {
33    #[inline(always)]
34    fn from_ref(ideal: &RotationIdeal<R, W>) -> Self {
35        ideal.clone()
36    }
37}
38
39impl<R: Semiring, const W: usize> Ideal for RotationIdeal<R, W> {}
40
41impl<F: PrimeField, const W: usize> RotationIdeal<F, W> {
42    pub fn from_with_cfg<R>(ideal_over_ring: &RotationIdeal<R, W>, field_cfg: &F::Config) -> Self
43    where
44        R: Semiring,
45        F: for<'a> FromWithConfig<&'a R>,
46    {
47        Self {
48            generating_root: F::from_with_cfg(&ideal_over_ring.generating_root, field_cfg),
49        }
50    }
51}
52
53impl<F: PrimeField, const W: usize> IdealCheck<DynamicPolynomialF<F>>
54    for IdealOrZero<RotationIdeal<F, W>>
55{
56    fn contains(&self, value: &DynamicPolynomialF<F>) -> Result<bool, IdealCheckError> {
57        if value.is_zero() {
58            return Ok(true);
59        }
60
61        match self {
62            IdealOrZero::NonZero(RotationIdeal { generating_root }) => {
63                if !value.coeffs.is_empty() {
64                    // We could technically do the conversion here, but this is not expected
65                    // to happen and likely signifies a bug.
66                    let coeffs_modulus = value.coeffs[0].modulus();
67                    if coeffs_modulus != generating_root.modulus() {
68                        return Err(IdealCheckError(format!(
69                            "Coefficient modulus {:?} doesn not match generating root modulus {:?}",
70                            coeffs_modulus,
71                            generating_root.modulus()
72                        )));
73                    }
74                }
75
76                if W == 1 {
77                    Ok(F::is_zero(
78                        &value
79                            .evaluate_at_point(generating_root)
80                            .expect("arithmetic overflow"),
81                    ))
82                } else {
83                    Ok(remainder_is_zero::<F, W>(&value.coeffs, generating_root))
84                }
85            }
86            IdealOrZero::Zero => Ok(value.is_zero()),
87        }
88    }
89}
90
91/// Checks whether the polynomial with the given `coeffs` lies in the ideal
92/// `(X^W - a)`, i.e., whether `p(X) mod (X^W - a) == 0`.
93///
94/// Groups coefficients into chunks of `W` and folds from highest to lowest
95/// using `rem = a * rem + chunk`, which is the Horner scheme applied to the
96/// "base-`X^W`" representation of `p(X)`.
97#[allow(clippy::arithmetic_side_effects)] // Was hand-checked to be correct.
98fn remainder_is_zero<F: PrimeField, const W: usize>(coeffs: &[F], a: &F) -> bool {
99    debug_assert!(W > 0, "Was pre-checked so this cannot fail");
100
101    if coeffs.is_empty() {
102        return true;
103    }
104
105    let cfg = coeffs[0].cfg();
106    let zero = F::zero_with_cfg(cfg);
107    let mut rem: [F; W] = std::array::from_fn(|_| zero.clone());
108
109    let n = coeffs.len();
110    let (num_full_chunks, partial_len) = n.div_rem_euclid(&W);
111
112    if partial_len > 0 {
113        let start = num_full_chunks * W;
114        for (j, coeff) in coeffs[start..].iter().enumerate().take(partial_len) {
115            rem[j] = coeff.clone();
116        }
117    }
118
119    for chunk_idx in (0..num_full_chunks).rev() {
120        let start = chunk_idx * W;
121        for j in 0..W {
122            rem[j] *= a;
123            rem[j] += &coeffs[start + j];
124        }
125    }
126
127    rem.iter().all(F::is_zero)
128}
129
130#[cfg(test)]
131mod tests {
132    use super::*;
133    use crypto_bigint::{U128, const_monty_params};
134    use crypto_primitives::crypto_bigint_const_monty::ConstMontyField;
135    use num_traits::{ConstZero, Euclid};
136
137    const_monty_params!(Params, U128, "00000000b933426489189cb5b47d567f");
138    type F = ConstMontyField<Params, { U128::LIMBS }>;
139
140    fn poly(coeffs: &[i32]) -> DynamicPolynomialF<F> {
141        DynamicPolynomialF::new(coeffs.iter().map(|&c| c.into()).collect::<Vec<_>>())
142    }
143
144    #[test]
145    fn w1_ideal_contains_member() {
146        // (X - 2): polynomial X - 2 should be in ideal (X-2) since eval at 2 is 0.
147        let ideal = IdealOrZero::NonZero(RotationIdeal::<F, 1>::new(F::from(2)));
148        let p = poly(&[-2, 1]); // X - 2
149        assert!(ideal.contains(&p).unwrap());
150    }
151
152    #[test]
153    fn w1_ideal_rejects_nonmember() {
154        let ideal = IdealOrZero::NonZero(RotationIdeal::<F, 1>::new(F::from(2)));
155        let p = poly(&[1, 1]); // X + 1, eval at 2 = 3 ≠ 0
156        assert!(!ideal.contains(&p).unwrap());
157    }
158
159    #[test]
160    fn w2_ideal_contains_generator() {
161        // (X^2 - 1): the polynomial X^2 - 1 should be in this ideal.
162        let ideal = IdealOrZero::NonZero(RotationIdeal::<F, 2>::new(F::from(1)));
163        let p = poly(&[-1, 0, 1]); // X^2 - 1
164        assert!(ideal.contains(&p).unwrap());
165    }
166
167    #[test]
168    fn w2_ideal_contains_multiple_of_generator() {
169        // (X^2 - 1): X * (X^2 - 1) = X^3 - X should be in the ideal.
170        let ideal = IdealOrZero::NonZero(RotationIdeal::<F, 2>::new(F::from(1)));
171        let p = poly(&[0, -1, 0, 1]); // X^3 - X
172        assert!(ideal.contains(&p).unwrap());
173    }
174
175    #[test]
176    fn w2_ideal_rejects_nonmember() {
177        let ideal = IdealOrZero::NonZero(RotationIdeal::<F, 2>::new(F::from(1)));
178        let p = poly(&[1, 1]); // X + 1
179        assert!(!ideal.contains(&p).unwrap());
180    }
181
182    #[test]
183    fn w3_ideal_contains_member() {
184        // (X^3 - 2): the polynomial X^3 - 2 should be in the ideal.
185        let ideal = IdealOrZero::NonZero(RotationIdeal::<F, 3>::new(F::from(2)));
186        let p = poly(&[-2, 0, 0, 1]); // X^3 - 2
187        assert!(ideal.contains(&p).unwrap());
188    }
189
190    #[test]
191    fn w3_ideal_rejects_nonmember() {
192        let ideal = IdealOrZero::NonZero(RotationIdeal::<F, 3>::new(F::from(2)));
193        let p = poly(&[1, 0, 0, 1]); // X^3 + 1 (not in (X^3 - 2))
194        assert!(!ideal.contains(&p).unwrap());
195    }
196
197    #[test]
198    fn zero_polynomial_always_in_ideal() {
199        let ideal = IdealOrZero::NonZero(RotationIdeal::<F, 4>::new(F::from(5)));
200        assert!(ideal.contains(&DynamicPolynomialF::<F>::ZERO).unwrap());
201    }
202
203    #[test]
204    fn zero_ideal_only_contains_zero() {
205        let zero_ideal = IdealOrZero::<RotationIdeal<F, 2>>::zero();
206        assert!(zero_ideal.contains(&DynamicPolynomialF::<F>::ZERO).unwrap());
207        assert!(!zero_ideal.contains(&poly(&[1])).unwrap());
208    }
209
210    #[test]
211    fn w2_reduction_cross_check_with_div_rem() {
212        // Verify our specialized reduction matches generic Euclidean division.
213        let ideal = IdealOrZero::NonZero(RotationIdeal::<F, 2>::new(F::from(3)));
214        let divisor = poly(&[-3, 0, 1]); // X^2 - 3
215
216        for p in [
217            poly(&[1, 2, 3, 4, 5]),
218            poly(&[0, 0, 0, 0, 6]),
219            poly(&[-3, 0, 1]),        // X^2 - 3 itself
220            poly(&[0, -3, 0, 1]),     // X * (X^2 - 3)
221            poly(&[-9, 0, 6, 0, -1]), // -(X^2 - 3)^2 + some remainder
222        ] {
223            let (_, rem) = p.div_rem_euclid(&divisor);
224            let mut rem_trimmed = rem;
225            rem_trimmed.trim();
226            let is_member_by_divrem = rem_trimmed.is_zero();
227            assert_eq!(
228                ideal.contains(&p).unwrap(),
229                is_member_by_divrem,
230                "Mismatch for polynomial: {p}"
231            );
232        }
233    }
234}
zinc_uair/ideal/rotation.rs

zinc_uair/ideal/
rotation.rs
