zinc_poly/univariate/
dynamic.rs

1use crypto_primitives::{
2    FieldConfig, ProjectElementWithConfig, RingConfig, SemiringConfig, SetConfig, boolean::Boolean,
3};
4use derive_more::From;
5use itertools::Itertools;
6use std::fmt::Display;
7use zinc_transcript::traits::{ConstTranscribable, GenTranscribable, Transcribable};
8use zinc_utils::{add, mul, projectable_to_field::ProjectableToField, rem};
9
10use crate::{
11    EvaluationError,
12    univariate::{binary::BinaryPoly, dense::DensePolynomial},
13};
14
15#[allow(clippy::arithmetic_side_effects)]
16fn new_coeffs_trimmed<R: Clone>(coeffs: &[R], is_zero: impl Fn(&R) -> bool) -> Vec<R> {
17    if let Some((non_zero, _)) = coeffs.iter().rev().find_position(|&coeff| !is_zero(coeff)) {
18        let deg_plus_one = coeffs.len() - non_zero;
19
20        coeffs.iter().take(deg_plus_one).cloned().collect()
21    } else {
22        Vec::new()
23    }
24}
25
26#[allow(clippy::arithmetic_side_effects)]
27fn degree<R>(coeffs: &[R], is_zero: impl Fn(&R) -> bool) -> Option<usize> {
28    coeffs
29        .iter()
30        .rev()
31        .find_position(|coeff| !is_zero(coeff))
32        .map(|(non_zero, _)| coeffs.len() - non_zero - 1)
33}
34
35#[allow(clippy::arithmetic_side_effects)]
36fn trim<R>(coeffs: &mut Vec<R>, is_zero: impl Fn(&R) -> bool) {
37    coeffs.truncate(degree(coeffs, is_zero).map_or(0, |degree| degree + 1))
38}
39
40fn is_zero<R>(coeffs: &[R], is_zero: impl Fn(&R) -> bool) -> bool {
41    coeffs.iter().all(is_zero)
42}
43
44/// Polynomials of dynamic degree over an arbitrary semiring (fixed like
45/// `Int`, or dynamic like a random finite field). To be used in UAIR and
46/// PIOP where ZIP+ degree bound is not observed anymore.
47///
48/// This is a dumb data holder: all operations are performed via
49/// [`DynamicPolynomialConfig`], obtainable from the coefficient config with
50/// [`HasDynamicPolynomialConfig::dyn_poly_cfg`].
51///
52/// Note that operations involving dynamic polynomials
53/// do not trim leading zeros meaning
54/// one can end up with unequal objects of the type
55/// `DynamicPolynomial<E>` that represent equal polynomials,
56/// therefore [`DynamicPolynomialConfig::trim`] has to be called before
57/// checking equality.
58#[derive(Debug, Clone, From, Hash, PartialEq, Eq)]
59pub struct DynamicPolynomial<E> {
60    pub coeffs: Vec<E>,
61}
62
63impl<E> DynamicPolynomial<E> {
64    pub const ZERO: Self = Self { coeffs: Vec::new() };
65
66    /// Maps every field element through `f`, preserving structure — used to
67    /// lift elements into wire integers and to project wire integers back
68    /// into elements at the (de)serialization boundary.
69    pub fn try_map<T, Er>(
70        &self,
71        f: impl FnMut(&E) -> Result<T, Er> + Copy,
72    ) -> Result<DynamicPolynomial<T>, Er> {
73        Ok(DynamicPolynomial {
74            coeffs: self.coeffs.iter().map(f).try_collect()?,
75        })
76    }
77
78    /// Create a new polynomial with the given coefficients.
79    #[inline(always)]
80    pub fn new(coeffs: impl AsRef<[E]>) -> Self
81    where
82        E: Clone,
83    {
84        Self {
85            coeffs: Vec::from(coeffs.as_ref()),
86        }
87    }
88}
89
90impl<E> Default for DynamicPolynomial<E> {
91    fn default() -> Self {
92        Self::ZERO
93    }
94}
95
96impl<E> FromIterator<E> for DynamicPolynomial<E> {
97    #[inline(always)]
98    fn from_iter<T: IntoIterator<Item = E>>(iter: T) -> Self {
99        Self {
100            coeffs: iter.into_iter().collect(),
101        }
102    }
103}
104
105impl<E: Display> Display for DynamicPolynomial<E> {
106    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
107        write!(f, "[")?;
108        let mut first = true;
109
110        for coeff in self.coeffs.iter() {
111            if first {
112                first = false;
113            } else {
114                write!(f, ", ")?;
115            }
116            write!(f, "{}", coeff)?;
117        }
118
119        write!(f, "]")
120    }
121}
122
123impl<E, const DEGREE_PLUS_ONE: usize> From<DensePolynomial<E, DEGREE_PLUS_ONE>>
124    for DynamicPolynomial<E>
125{
126    fn from(dense_poly: DensePolynomial<E, DEGREE_PLUS_ONE>) -> Self {
127        Self {
128            coeffs: Vec::from(dense_poly.coeffs),
129        }
130    }
131}
132
133impl<const DEGREE_PLUS_ONE: usize> From<BinaryPoly<DEGREE_PLUS_ONE>>
134    for DynamicPolynomial<Boolean>
135{
136    fn from(binary_poly: BinaryPoly<DEGREE_PLUS_ONE>) -> Self {
137        Self::from(DensePolynomial::from(binary_poly))
138    }
139}
140
141/// Configuration of the polynomial semiring $S[X]$ over the (semi)ring
142/// configured by `S`, with [`DynamicPolynomial`] as its element.
143///
144/// Implements exactly the layer its coefficients provide: [`SemiringConfig`]
145/// over a semiring, additionally [`RingConfig`] over a ring. The polynomial
146/// ring is never a field, hence no [`FieldConfig`].
147///
148/// Checked operations delegate to the coefficient config's checked
149/// operations, so overflow behavior follows the coefficients (e.g. `Int`
150/// coefficients can overflow, field coefficients cannot).
151#[derive(Debug, Clone, Copy, PartialEq, Eq)]
152pub struct DynamicPolynomialConfig<'a, S: SemiringConfig> {
153    pub cfg: &'a S,
154}
155
156/// Extension trait providing [`DynamicPolynomialConfig`] from a coefficient
157/// config, so that the same config can be used to perform operations on
158/// dynamic polynomials: `cfg.poly_cfg().mul(&p, &q)`.
159pub trait HasDynamicPolynomialConfig: SemiringConfig + Sized {
160    #[inline(always)]
161    fn dyn_poly_cfg(&self) -> DynamicPolynomialConfig<'_, Self> {
162        DynamicPolynomialConfig { cfg: self }
163    }
164}
165
166impl<S: SemiringConfig> HasDynamicPolynomialConfig for S {}
167
168impl<'a, S: SemiringConfig> SetConfig for DynamicPolynomialConfig<'a, S> {
169    type Element = DynamicPolynomial<S::Element>;
170}
171
172impl<'a, S: SemiringConfig> SemiringConfig for DynamicPolynomialConfig<'a, S> {
173    fn is_zero(&self, value: &Self::Element) -> bool {
174        is_zero(&value.coeffs, |e| self.cfg.is_zero(e))
175    }
176
177    fn zero(&self) -> Self::Element {
178        DynamicPolynomial::ZERO
179    }
180
181    fn one(&self) -> Self::Element {
182        DynamicPolynomial {
183            coeffs: vec![self.cfg.one()],
184        }
185    }
186
187    fn add(&self, x: &Self::Element, y: &Self::Element) -> Self::Element {
188        let mut res = x.clone();
189        self.add_assign(&mut res, y);
190        res
191    }
192
193    fn sub(&self, x: &Self::Element, y: &Self::Element) -> Self::Element {
194        let mut res = x.clone();
195        self.sub_assign(&mut res, y);
196        res
197    }
198
199    fn mul(&self, x: &Self::Element, y: &Self::Element) -> Self::Element {
200        if self.is_zero(x) || self.is_zero(y) {
201            return self.zero();
202        }
203        let mut coeffs =
204            vec![self.cfg.zero(); add!(x.coeffs.len(), y.coeffs.len()).saturating_sub(1)];
205        for (i, a) in x.coeffs.iter().enumerate() {
206            for (j, b) in y.coeffs.iter().enumerate() {
207                let prod = self.cfg.mul(a, b);
208                self.cfg.add_assign(&mut coeffs[add!(i, j)], &prod);
209            }
210        }
211        DynamicPolynomial { coeffs }
212    }
213
214    fn pow_u32(&self, x: &Self::Element, y: u32) -> Self::Element {
215        let mut res = self.one();
216        for _ in 0..y {
217            res = self.mul(&res, x);
218        }
219        res
220    }
221
222    fn checked_add(&self, x: &Self::Element, y: &Self::Element) -> Option<Self::Element> {
223        let mut res = x.clone();
224        if res.coeffs.len() < y.coeffs.len() {
225            res.coeffs.resize(y.coeffs.len(), self.cfg.zero());
226        }
227        for (xc, yc) in res.coeffs.iter_mut().zip(&y.coeffs) {
228            *xc = self.cfg.checked_add(xc, yc)?;
229        }
230        Some(res)
231    }
232
233    fn checked_sub(&self, x: &Self::Element, y: &Self::Element) -> Option<Self::Element> {
234        let mut res = x.clone();
235        if res.coeffs.len() < y.coeffs.len() {
236            res.coeffs.resize(y.coeffs.len(), self.cfg.zero());
237        }
238        for (xc, yc) in res.coeffs.iter_mut().zip(&y.coeffs) {
239            *xc = self.cfg.checked_sub(xc, yc)?;
240        }
241        Some(res)
242    }
243
244    fn checked_mul(&self, x: &Self::Element, y: &Self::Element) -> Option<Self::Element> {
245        if self.is_zero(x) || self.is_zero(y) {
246            return Some(self.zero());
247        }
248        let mut coeffs =
249            vec![self.cfg.zero(); add!(x.coeffs.len(), y.coeffs.len()).saturating_sub(1)];
250        for (i, a) in x.coeffs.iter().enumerate() {
251            for (j, b) in y.coeffs.iter().enumerate() {
252                let prod = self.cfg.checked_mul(a, b)?;
253                let idx = add!(i, j);
254                coeffs[idx] = self.cfg.checked_add(&coeffs[idx], &prod)?;
255            }
256        }
257        Some(DynamicPolynomial { coeffs })
258    }
259
260    fn checked_pow_u32(&self, x: &Self::Element, y: u32) -> Option<Self::Element> {
261        let mut res = self.one();
262        for _ in 0..y {
263            res = self.checked_mul(&res, x)?;
264        }
265        Some(res)
266    }
267
268    fn add_assign(&self, x: &mut Self::Element, y: &Self::Element) {
269        if x.coeffs.len() < y.coeffs.len() {
270            x.coeffs.resize(y.coeffs.len(), self.cfg.zero());
271        }
272        for (xc, yc) in x.coeffs.iter_mut().zip(&y.coeffs) {
273            self.cfg.add_assign(xc, yc);
274        }
275    }
276
277    fn sub_assign(&self, x: &mut Self::Element, y: &Self::Element) {
278        if x.coeffs.len() < y.coeffs.len() {
279            x.coeffs.resize(y.coeffs.len(), self.cfg.zero());
280        }
281        for (xc, yc) in x.coeffs.iter_mut().zip(&y.coeffs) {
282            self.cfg.sub_assign(xc, yc);
283        }
284    }
285}
286
287impl<'a, S: RingConfig> RingConfig for DynamicPolynomialConfig<'a, S> {
288    fn neg(&self, x: &Self::Element) -> Self::Element {
289        DynamicPolynomial {
290            coeffs: x.coeffs.iter().map(|c| self.cfg.neg(c)).collect(),
291        }
292    }
293
294    fn checked_neg(&self, x: &Self::Element) -> Option<Self::Element> {
295        Some(DynamicPolynomial {
296            coeffs: x
297                .coeffs
298                .iter()
299                .map(|c| self.cfg.checked_neg(c))
300                .collect::<Option<Vec<_>>>()?,
301        })
302    }
303}
304
305impl<'a, S: SemiringConfig> DynamicPolynomialConfig<'a, S> {
306    /// Create a new polynomial with the given coefficients, trimming the
307    /// leading zeros.
308    #[inline(always)]
309    pub fn new_trimmed(&self, coeffs: impl AsRef<[S::Element]>) -> DynamicPolynomial<S::Element> {
310        DynamicPolynomial {
311            coeffs: new_coeffs_trimmed(coeffs.as_ref(), |e| self.cfg.is_zero(e)),
312        }
313    }
314
315    #[inline(always)]
316    pub fn degree(&self, poly: &DynamicPolynomial<S::Element>) -> Option<usize> {
317        degree(&poly.coeffs, |e| self.cfg.is_zero(e))
318    }
319
320    #[inline(always)]
321    pub fn trim(&self, poly: &mut DynamicPolynomial<S::Element>) {
322        trim(&mut poly.coeffs, |e| self.cfg.is_zero(e));
323    }
324
325    /// Evaluate the polynomial at the given point using Horner's method.
326    pub fn evaluate_at_point(
327        &self,
328        poly: &DynamicPolynomial<S::Element>,
329        point: &S::Element,
330    ) -> Result<S::Element, EvaluationError> {
331        let mut result = poly.coeffs.last().cloned().unwrap_or(self.cfg.zero());
332
333        for coeff in poly.coeffs.iter().rev().skip(1) {
334            self.cfg.mul_assign(&mut result, point);
335            self.cfg.add_assign(&mut result, coeff);
336        }
337
338        Ok(result)
339    }
340
341    /// Evaluate the polynomial at the given point using Horner's method,
342    /// with overflow-checked coefficient operations.
343    pub fn checked_evaluate_at_point(
344        &self,
345        poly: &DynamicPolynomial<S::Element>,
346        point: &S::Element,
347    ) -> Result<S::Element, EvaluationError> {
348        let mut result = poly.coeffs.last().cloned().unwrap_or(self.cfg.zero());
349
350        for coeff in poly.coeffs.iter().rev().skip(1) {
351            let term = self
352                .cfg
353                .checked_mul(&result, point)
354                .ok_or(EvaluationError::Overflow)?;
355            result = self
356                .cfg
357                .checked_add(&term, coeff)
358                .ok_or(EvaluationError::Overflow)?;
359        }
360
361        Ok(result)
362    }
363
364    /// Right-rotate the coefficient vector by `c` positions within width `D`.
365    ///
366    /// The output coefficient at position `i` is the input coefficient at
367    /// `(i + c) mod D`. Missing coefficients are padded with zero before the
368    /// rotation.
369    pub fn rotate_right<const D: usize>(
370        &self,
371        poly: &DynamicPolynomial<S::Element>,
372        c: usize,
373    ) -> DynamicPolynomial<S::Element> {
374        assert!(
375            c > 0 && c < D,
376            "rotate_right count {c} out of range (must satisfy 0 < c < {D})",
377        );
378        assert!(
379            poly.coeffs.len() <= D,
380            "rotate_right coefficient length {} exceeds width {D}",
381            poly.coeffs.len(),
382        );
383
384        let mut coeffs = poly.coeffs.clone();
385        coeffs.resize(D, self.cfg.zero());
386        DynamicPolynomial {
387            coeffs: (0..D)
388                .map(|i| coeffs[rem!(add!(i, c), D)].clone())
389                .collect(),
390        }
391    }
392
393    /// Right-shift the coefficient vector by `c` positions within width `D`.
394    ///
395    /// The output coefficient at position `i` is the input coefficient at
396    /// `i + c`, or zero when that index is outside width `D`. Missing
397    /// coefficients are padded with zero before the shift.
398    pub fn shr<const D: usize>(
399        &self,
400        poly: &DynamicPolynomial<S::Element>,
401        c: usize,
402    ) -> DynamicPolynomial<S::Element> {
403        assert!(
404            c > 0 && c < D,
405            "shr count {c} out of range (must satisfy 0 < c < {D})",
406        );
407        assert!(
408            poly.coeffs.len() <= D,
409            "shr coefficient length {} exceeds width {D}",
410            poly.coeffs.len(),
411        );
412
413        let zero = self.cfg.zero();
414        let mut coeffs = poly.coeffs.clone();
415        coeffs.resize(D, zero.clone());
416        DynamicPolynomial {
417            coeffs: (0..D)
418                .map(|i| {
419                    let j = add!(i, c);
420                    if j < D {
421                        coeffs[j].clone()
422                    } else {
423                        zero.clone()
424                    }
425                })
426                .collect(),
427        }
428    }
429}
430
431/// Projection by evaluation: a dynamic polynomial over projectable
432/// coefficients maps to the field element obtained by projecting the
433/// coefficients and evaluating at the sampled point.
434impl<E, C> ProjectableToField<C> for DynamicPolynomial<E>
435where
436    C: FieldConfig + ProjectElementWithConfig<E> + Clone + Send + Sync + 'static,
437{
438    fn prepare_projection(cfg: &C, sampled_value: &C::Element) -> impl Fn(&Self) -> C::Element {
439        let cfg = cfg.clone();
440        let sampled_value = sampled_value.clone();
441
442        move |poly: &Self| {
443            // Horner's method, projecting coefficients on the fly.
444            let mut result = cfg.zero();
445            for coeff in poly.coeffs.iter().rev() {
446                cfg.mul_assign(&mut result, &sampled_value);
447                let projected = cfg.project(coeff);
448                cfg.add_assign(&mut result, &projected);
449            }
450            result
451        }
452    }
453}
454
455/// Unfortunately, we cannot implement of `GenTranscribable` for
456/// `Vec<DynamicPolynomial<E>>` since they both are foreign types, so we define
457/// this wrapper as a workaround.
458///
459/// Polynomials are transcribed as raw elements without any field metadata:
460/// the field config is bound into the transcript separately, when the field
461/// is sampled. Polynomials are written untrimmed (trimming requires a config),
462/// so writers should trim beforehand if proof size matters.
463#[derive(Debug, Default, Clone, From, Hash, PartialEq, Eq)]
464#[repr(transparent)]
465pub struct DynamicPolyVec<E>(pub Vec<DynamicPolynomial<E>>);
466
467impl<E> DynamicPolyVec<E> {
468    pub fn reinterpret(value: &Vec<DynamicPolynomial<E>>) -> &Self {
469        // Safety: `DynamicPolyVec<E>` is a transparent wrapper, so the memory
470        // layout is the same.
471        unsafe { &*(value as *const Vec<DynamicPolynomial<E>> as *const Self) }
472    }
473}
474
475impl<E> GenTranscribable for DynamicPolyVec<E>
476where
477    E: ConstTranscribable,
478{
479    fn read_transcription_bytes_exact(mut bytes: &[u8]) -> Self {
480        let mut result = Vec::new();
481        while !bytes.is_empty() {
482            let (len, rest) = u32::read_transcription_bytes_subset(bytes);
483            let len = usize::try_from(len).expect("polynomial length must fit into usize");
484            bytes = rest;
485            let end = mul!(len, E::NUM_BYTES);
486            let coeffs: Vec<E> = Vec::read_transcription_bytes_exact(&bytes[..end]);
487            result.push(DynamicPolynomial { coeffs });
488            bytes = &bytes[end..];
489        }
490        result.into()
491    }
492
493    fn write_transcription_bytes_exact(&self, mut buf: &mut [u8]) {
494        for poly in self.0.iter() {
495            let len = u32::try_from(poly.coeffs.len()).expect("poly length must fit into u32");
496            len.write_transcription_bytes_exact(&mut buf[0..u32::NUM_BYTES]);
497            buf = &mut buf[u32::NUM_BYTES..];
498
499            let end = mul!(poly.coeffs.len(), E::NUM_BYTES);
500            poly.coeffs.write_transcription_bytes_exact(&mut buf[..end]);
501            buf = &mut buf[end..];
502        }
503        assert!(buf.is_empty(), "Entire buffer should be used");
504    }
505}
506
507impl<E> Transcribable for DynamicPolyVec<E>
508where
509    E: ConstTranscribable,
510{
511    fn get_num_bytes(&self) -> usize {
512        self.0
513            .iter()
514            .map(|poly| add!(u32::NUM_BYTES, mul!(poly.coeffs.len(), E::NUM_BYTES)))
515            .sum()
516    }
517}
518
519#[cfg(test)]
520#[allow(
521    clippy::arithmetic_side_effects,
522    clippy::clone_on_copy,
523    clippy::redundant_clone
524)]
525mod field_tests {
526    use crypto_primitives::{
527        BaseFieldConfig, ProjectElementWithConfig,
528        crypto_bigint_monty::{MontyField, MontyFieldElement},
529        crypto_bigint_uint::Uint,
530    };
531
532    use super::*;
533
534    const LIMBS: usize = 4;
535    type F = MontyField<LIMBS>;
536    type P = DynamicPolynomial<MontyFieldElement<LIMBS>>;
537
538    fn field_config() -> F {
539        let modulus =
540            Uint::from_be_hex("0000000000000000000000000000000000860995AE68FC80E1B1BD1E39D54B33");
541        F::new(&modulus).expect("modulus should be a valid odd prime")
542    }
543
544    fn f(v: i64) -> MontyFieldElement<LIMBS> {
545        field_config().project(&v)
546    }
547
548    fn p(coeffs: impl IntoIterator<Item = i64>) -> P {
549        coeffs.into_iter().map(f).collect()
550    }
551
552    #[test]
553    fn new_trimmed_creates_correctly() {
554        let field_cfg = field_config();
555        let cfg = field_cfg.dyn_poly_cfg();
556        assert_eq!(cfg.new_trimmed(p([1, 2, 3, 0, 0]).coeffs), p([1, 2, 3]));
557    }
558
559    #[test]
560    fn add_zero() {
561        let field_cfg = field_config();
562        let cfg = field_cfg.dyn_poly_cfg();
563
564        assert_eq!(cfg.add(&P::ZERO, &P::ZERO), P::ZERO);
565
566        let x = p([2, 0, 2, 0, 0]);
567        assert_eq!(cfg.add(&x, &P::ZERO), x);
568        assert_eq!(cfg.add(&P::ZERO, &x), x);
569
570        let mut y = x.clone();
571        cfg.add_assign(&mut y, &P::ZERO);
572        assert_eq!(y, x);
573    }
574
575    #[test]
576    fn addition_is_correct() {
577        let field_cfg = field_config();
578        let cfg = field_cfg.dyn_poly_cfg();
579        let (x, y) = (p([2, 0, 2, 0, 0]), p([1, 2, 3]));
580
581        let res = p([3, 2, 5, 0, 0]);
582
583        assert_eq!(cfg.add(&x, &y), res);
584        assert_eq!(cfg.add(&y, &x), res);
585        assert_eq!(cfg.checked_add(&x, &y), Some(res.clone()));
586
587        let mut z = x.clone();
588        cfg.add_assign(&mut z, &y);
589        assert_eq!(z, res);
590    }
591
592    #[test]
593    fn subtraction_is_correct() {
594        let field_cfg = field_config();
595        let cfg = field_cfg.dyn_poly_cfg();
596        let (x, y) = (p([2, 0, 2, 0, 0]), p([1, 2, 3]));
597
598        let res = p([1, -2, -1, 0, 0]);
599
600        assert_eq!(cfg.sub(&x, &y), res);
601        assert_eq!(cfg.checked_sub(&x, &y), Some(res.clone()));
602
603        let mut z = x.clone();
604        cfg.sub_assign(&mut z, &y);
605        assert_eq!(z, res);
606
607        // Subtraction with the result longer than the lhs
608        assert_eq!(
609            cfg.sub(&p([1, 2, 3]), &p([2, 0, 2, -1, 0])),
610            p([-1, 2, 1, 1, 0])
611        );
612    }
613
614    #[test]
615    fn multiplication_is_correct() {
616        let field_cfg = field_config();
617        let cfg = field_cfg.dyn_poly_cfg();
618        let (x, y) = (p([2, 0, 2]), p([1, 2, 3]));
619
620        let res = p([2, 4, 8, 4, 6]);
621
622        assert_eq!(cfg.mul(&x, &y), res);
623        assert_eq!(cfg.mul(&y, &x), res);
624        assert_eq!(cfg.checked_mul(&x, &y), Some(res));
625
626        assert_eq!(cfg.mul(&x, &cfg.zero()), cfg.zero());
627        assert_eq!(cfg.mul(&cfg.zero(), &x), cfg.zero());
628    }
629
630    #[test]
631    fn test_trim() {
632        let field_cfg = field_config();
633        let cfg = field_cfg.dyn_poly_cfg();
634
635        let mut x = p([0, 0, 0, 0, 0]);
636        cfg.trim(&mut x);
637        assert_eq!(x, P::ZERO);
638
639        let mut x = p([2, 3, 0, 0, 0]);
640        cfg.trim(&mut x);
641        assert_eq!(x, p([2, 3]));
642    }
643
644    #[test]
645    fn evaluate_zero_poly() {
646        let field_cfg = field_config();
647        let cfg = field_cfg.dyn_poly_cfg();
648        assert_eq!(cfg.evaluate_at_point(&P::ZERO, &f(1)), Ok(f(0)))
649    }
650
651    #[test]
652    fn evaluation_is_correct() {
653        let field_cfg = field_config();
654        let cfg = field_cfg.dyn_poly_cfg();
655        // 1 + 2x + 3x² at x = 2 → 1 + 4 + 12 = 17
656        assert_eq!(cfg.evaluate_at_point(&p([1, 2, 3]), &f(2)), Ok(f(17)));
657    }
658
659    #[test]
660    fn projection_evaluates_at_sampled_point() {
661        use crypto_primitives::crypto_bigint_int::Int;
662        type IntPoly = DynamicPolynomial<Int<4>>;
663
664        let field_cfg = field_config();
665        let sampled = f(2);
666        let project = IntPoly::prepare_projection(&field_cfg, &sampled);
667        // 1 + 2x + 3x² at x = 2 → 17
668        let poly: IntPoly = [1i8, 2, 3].map(Int::from_i8).into_iter().collect();
669        assert_eq!(project(&poly), f(17));
670        assert_eq!(project(&IntPoly::ZERO), f(0));
671    }
672
673    #[test]
674    fn rotate_right_pads_and_permutes_coefficients() {
675        let field_cfg = field_config();
676        let cfg = field_cfg.dyn_poly_cfg();
677        assert_eq!(cfg.rotate_right::<5>(&p([1, 2, 3]), 2), p([3, 0, 0, 1, 2]));
678    }
679
680    #[test]
681    fn shr_pads_and_drops_coefficients() {
682        let field_cfg = field_config();
683        let cfg = field_cfg.dyn_poly_cfg();
684        assert_eq!(cfg.shr::<5>(&p([1, 2, 3]), 2), p([3, 0, 0, 0, 0]));
685    }
686
687    #[test]
688    #[should_panic(expected = "rotate_right count 0 out of range")]
689    fn rotate_right_panics_on_zero() {
690        let field_cfg = field_config();
691        let _ = field_cfg.dyn_poly_cfg().rotate_right::<5>(&p([1]), 0);
692    }
693
694    #[test]
695    #[should_panic(expected = "shr count 5 out of range")]
696    fn shr_panics_on_full_width() {
697        let field_cfg = field_config();
698        let _ = field_cfg.dyn_poly_cfg().shr::<5>(&p([1]), 5);
699    }
700}
701
702#[cfg(test)]
703#[allow(clippy::clone_on_copy, clippy::redundant_clone)]
704mod semiring_tests {
705    use crypto_primitives::{FixedConfig, crypto_bigint_int::Int};
706    use num_traits::ConstZero;
707
708    use super::*;
709
710    type R = Int<4>;
711    type P = DynamicPolynomial<R>;
712    type FC = FixedConfig<R>;
713
714    fn p(coeffs: impl IntoIterator<Item = i8>) -> P {
715        coeffs.into_iter().map(Int::from_i8).collect()
716    }
717
718    fn get_2_test_polynomials() -> (P, P) {
719        (p([2, 0, 2, 0, 0]), p([1, 2, 3]))
720    }
721
722    #[test]
723    fn new_trimmed_creates_correctly() {
724        let int_cfg = FC::default();
725        let cfg = int_cfg.dyn_poly_cfg();
726        assert_eq!(cfg.new_trimmed(p([1, 2, 3, 0, 0]).coeffs), p([1, 2, 3]));
727    }
728
729    #[test]
730    fn add_zero() {
731        let int_cfg = FC::default();
732        let cfg = int_cfg.dyn_poly_cfg();
733
734        assert_eq!(cfg.add(&P::ZERO, &P::ZERO), P::ZERO);
735
736        let x = p([2, 0, 2, 0, 0]);
737        assert_eq!(cfg.add(&x, &P::ZERO), x);
738        assert_eq!(cfg.add(&P::ZERO, &x), x);
739
740        let mut y = x.clone();
741        cfg.add_assign(&mut y, &P::ZERO);
742        assert_eq!(y, x);
743    }
744
745    #[test]
746    fn addition_is_correct() {
747        let int_cfg = FC::default();
748        let cfg = int_cfg.dyn_poly_cfg();
749        let (x, y) = get_2_test_polynomials();
750
751        let res = p([3, 2, 5, 0, 0]);
752
753        assert_eq!(cfg.add(&x, &y), res);
754        assert_eq!(cfg.add(&y, &x), res);
755        assert_eq!(cfg.checked_add(&x, &y), Some(res.clone()));
756        assert_eq!(cfg.checked_add(&y, &x), Some(res.clone()));
757
758        let mut z = x.clone();
759        cfg.add_assign(&mut z, &y);
760        assert_eq!(z, res);
761
762        let mut z = y.clone();
763        cfg.add_assign(&mut z, &x);
764        assert_eq!(z, res);
765    }
766
767    #[test]
768    fn subtraction_is_correct() {
769        let int_cfg = FC::default();
770        let cfg = int_cfg.dyn_poly_cfg();
771        let (x, y) = get_2_test_polynomials();
772
773        let res = p([1, -2, -1, 0, 0]);
774
775        assert_eq!(cfg.sub(&x, &y), res);
776        assert_eq!(cfg.checked_sub(&x, &y), Some(res.clone()));
777
778        let mut z = x.clone();
779        cfg.sub_assign(&mut z, &y);
780        assert_eq!(z, res);
781
782        // Subtraction with the result longer than the lhs
783        assert_eq!(
784            cfg.sub(&p([1, 2, 3]), &p([2, 0, 2, -1, 0])),
785            p([-1, 2, 1, 1, 0])
786        );
787    }
788
789    #[test]
790    fn mul_zero() {
791        let int_cfg = FC::default();
792        let cfg = int_cfg.dyn_poly_cfg();
793
794        assert_eq!(cfg.mul(&P::ZERO, &P::ZERO), P::ZERO);
795
796        let x = p([2, 0, 2, 0, 0]);
797        assert_eq!(cfg.mul(&x, &P::ZERO), P::ZERO);
798        assert_eq!(cfg.mul(&P::ZERO, &x), P::ZERO);
799        assert_eq!(cfg.checked_mul(&x, &P::ZERO), Some(P::ZERO));
800    }
801
802    #[test]
803    fn multiplication_is_correct() {
804        let int_cfg = FC::default();
805        let cfg = int_cfg.dyn_poly_cfg();
806        let (x, y) = get_2_test_polynomials();
807
808        // Untrimmed operands: result carries the trailing zeros.
809        let res = p([2, 4, 8, 4, 6, 0, 0]);
810
811        assert_eq!(cfg.mul(&x, &y), res);
812        assert_eq!(cfg.mul(&y, &x), res);
813        assert_eq!(cfg.checked_mul(&x, &y), Some(res.clone()));
814        assert_eq!(cfg.checked_mul(&y, &x), Some(res));
815    }
816
817    #[test]
818    fn negation_is_correct() {
819        let int_cfg = FC::default();
820        let cfg = int_cfg.dyn_poly_cfg();
821        let x = p([1, -2, 3]);
822
823        assert_eq!(cfg.neg(&x), p([-1, 2, -3]));
824        assert_eq!(cfg.checked_neg(&x), Some(p([-1, 2, -3])));
825    }
826
827    #[test]
828    fn checked_ops_detect_coefficient_overflow() {
829        let int_cfg = FC::default();
830        let cfg = int_cfg.dyn_poly_cfg();
831
832        let max = P::new([Int::MAX]);
833        let one = cfg.one();
834
835        assert_eq!(cfg.checked_add(&max, &one), None);
836        assert_eq!(cfg.checked_mul(&max, &p([2])), None);
837
838        let min = P::new([Int::MIN]);
839        assert_eq!(cfg.checked_sub(&min, &one), None);
840        assert_eq!(cfg.checked_neg(&min), None);
841    }
842
843    #[test]
844    fn checked_evaluation_detects_overflow() {
845        let int_cfg = FC::default();
846        let cfg = int_cfg.dyn_poly_cfg();
847
848        // 1 + 2x + 3x² at x = 2 → 17
849        assert_eq!(
850            cfg.checked_evaluate_at_point(&p([1, 2, 3]), &Int::from_i8(2)),
851            Ok(Int::from_i8(17))
852        );
853        assert_eq!(
854            cfg.checked_evaluate_at_point(&P::new([Int::ZERO, Int::MAX]), &Int::from_i8(2)),
855            Err(EvaluationError::Overflow)
856        );
857    }
858
859    #[test]
860    fn test_trim() {
861        let int_cfg = FC::default();
862        let cfg = int_cfg.dyn_poly_cfg();
863
864        let mut x = p([0, 0, 0, 0, 0]);
865        cfg.trim(&mut x);
866        assert_eq!(x, P::ZERO);
867
868        let mut x = p([2, 3, 0, 0, 0]);
869        cfg.trim(&mut x);
870        assert_eq!(x, p([2, 3]));
871    }
872}
zinc_poly/univariate/dynamic.rs

zinc_poly/univariate/
dynamic.rs
