zinc_poly/univariate/dynamic/
over_field.rs

1use crypto_primitives::{PrimeField, Semiring};
2use derive_more::From;
3use num_traits::{CheckedAdd, CheckedMul, CheckedNeg, CheckedSub, ConstZero, Euclid, Zero};
4use std::{
5    fmt::Display,
6    ops::{Add, AddAssign, Div, Mul, MulAssign, Neg, Rem, Sub, SubAssign},
7};
8use zinc_transcript::traits::{ConstTranscribable, GenTranscribable, Transcribable};
9use zinc_utils::{
10    UNCHECKED, add,
11    inner_product::{InnerProduct, InnerProductError},
12    mul,
13};
14
15use crate::{
16    EvaluatablePolynomial, EvaluationError, Polynomial,
17    univariate::{dense::DensePolynomial, dynamic},
18};
19
20/// Polynomials of dynamic degree. The implementation
21/// is tailored to work with random finite fields.
22/// To be used in UAIR and PIOP where ZIP+ degree bound
23/// is not observed anymore.
24///
25/// Note that operations involving dynamic polynomials
26/// do not trim leading zeros meaning
27/// one can end up with unequal objects of the type
28/// `DynamicPoly<F>` that represent equal polynomials,
29/// therefore `trim` has to be called before checking
30/// equality.
31#[derive(Debug, Clone, From, Hash, PartialEq, Eq)]
32pub struct DynamicPolynomialF<F: PrimeField> {
33    pub coeffs: Vec<F>,
34}
35
36impl<F: PrimeField> DynamicPolynomialF<F> {
37    /// Create a new polynomial with the given coefficients.
38    #[inline(always)]
39    pub fn new_trimmed(coeffs: impl AsRef<[F]>) -> Self {
40        Self {
41            coeffs: dynamic::new_coeffs_trimmed(coeffs.as_ref(), F::is_zero),
42        }
43    }
44
45    #[inline(always)]
46    pub fn new(coeffs: impl AsRef<[F]>) -> Self {
47        Self {
48            coeffs: Vec::from(coeffs.as_ref()),
49        }
50    }
51
52    #[inline(always)]
53    pub fn degree(&self) -> Option<usize> {
54        dynamic::degree(&self.coeffs, F::is_zero)
55    }
56
57    #[inline(always)]
58    pub fn trim(&mut self) {
59        dynamic::trim(&mut self.coeffs, F::is_zero);
60    }
61
62    pub fn constant_poly(a: F) -> Self {
63        if F::is_zero(&a) {
64            Self::default()
65        } else {
66            DynamicPolynomialF { coeffs: vec![a] }
67        }
68    }
69}
70
71/// Inner product for dynamic polynomials over a prime field.
72pub struct DynamicPolyFInnerProduct;
73
74impl<F: PrimeField> InnerProduct<[F], F, F> for DynamicPolyFInnerProduct {
75    #[allow(clippy::arithmetic_side_effects)]
76    fn inner_product<const CHECK: bool>(
77        lhs: &[F],
78        rhs: &[F],
79        zero: F,
80    ) -> Result<F, InnerProductError> {
81        Ok(lhs
82            .iter()
83            .zip(rhs)
84            .fold(zero, |acc, (coeff, power)| acc + coeff.clone() * power))
85    }
86}
87
88impl<F: PrimeField> Display for DynamicPolynomialF<F> {
89    #[inline(always)]
90    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
91        dynamic::display(&self.coeffs, f)
92    }
93}
94
95impl<F: PrimeField> Default for DynamicPolynomialF<F> {
96    fn default() -> Self {
97        Self {
98            coeffs: Default::default(),
99        }
100    }
101}
102
103impl<F: PrimeField> Zero for DynamicPolynomialF<F> {
104    #[inline(always)]
105    fn zero() -> Self {
106        Default::default()
107    }
108
109    #[inline(always)]
110    fn is_zero(&self) -> bool {
111        dynamic::is_zero(&self.coeffs, F::is_zero)
112    }
113}
114
115impl<F: PrimeField> ConstZero for DynamicPolynomialF<F> {
116    const ZERO: Self = Self { coeffs: Vec::new() };
117}
118
119impl<F: PrimeField> Neg for DynamicPolynomialF<F> {
120    type Output = Self;
121
122    #[inline(always)]
123    fn neg(self) -> Self::Output {
124        Self {
125            coeffs: dynamic::neg(self.coeffs),
126        }
127    }
128}
129
130impl<F: PrimeField> Add for DynamicPolynomialF<F> {
131    type Output = Self;
132
133    fn add(self, rhs: Self) -> Self::Output {
134        self.add(&rhs)
135    }
136}
137
138impl<F: PrimeField> Add<&Self> for DynamicPolynomialF<F> {
139    type Output = Self;
140
141    #[inline(always)]
142    fn add(mut self, rhs: &Self) -> Self::Output {
143        self.add_assign(rhs);
144
145        self
146    }
147}
148
149impl<F: PrimeField> Sub for DynamicPolynomialF<F> {
150    type Output = Self;
151
152    fn sub(self, rhs: Self) -> Self::Output {
153        self.sub(&rhs)
154    }
155}
156
157impl<F: PrimeField> Sub<&Self> for DynamicPolynomialF<F> {
158    type Output = Self;
159
160    fn sub(mut self, rhs: &Self) -> Self::Output {
161        self.sub_assign(rhs);
162
163        self
164    }
165}
166
167impl<F: PrimeField> Mul for DynamicPolynomialF<F> {
168    type Output = Self;
169
170    #[allow(clippy::arithmetic_side_effects)]
171    fn mul(self, rhs: Self) -> Self::Output {
172        &self * &rhs
173    }
174}
175
176impl<F: PrimeField> Mul<&Self> for DynamicPolynomialF<F> {
177    type Output = Self;
178
179    #[allow(clippy::arithmetic_side_effects)]
180    fn mul(self, rhs: &Self) -> Self::Output {
181        &self * rhs
182    }
183}
184
185impl<'a, F: PrimeField> Mul<&'a DynamicPolynomialF<F>> for &'a DynamicPolynomialF<F> {
186    type Output = DynamicPolynomialF<F>;
187
188    #[allow(clippy::arithmetic_side_effects)]
189    fn mul(self, rhs: Self) -> Self::Output {
190        Self::Output {
191            coeffs: dynamic::mul::<_, UNCHECKED>(&self.coeffs, &rhs.coeffs, F::is_zero)
192                .expect("overflow in a field will not happen"),
193        }
194    }
195}
196
197impl<F: PrimeField> CheckedAdd for DynamicPolynomialF<F> {
198    #[allow(clippy::arithmetic_side_effects)] // We are in a field.
199    fn checked_add(&self, rhs: &Self) -> Option<Self> {
200        Some(self.clone() + rhs)
201    }
202}
203
204impl<F: PrimeField> CheckedSub for DynamicPolynomialF<F> {
205    #[allow(clippy::arithmetic_side_effects)] // We are in a field.
206    fn checked_sub(&self, rhs: &Self) -> Option<Self> {
207        Some(self.clone() - rhs)
208    }
209}
210
211impl<F: PrimeField> CheckedMul for DynamicPolynomialF<F> {
212    #[allow(clippy::arithmetic_side_effects)] // We are in a field.
213    fn checked_mul(&self, rhs: &Self) -> Option<Self> {
214        Some(self * rhs)
215    }
216}
217
218impl<F: PrimeField> CheckedNeg for DynamicPolynomialF<F> {
219    fn checked_neg(&self) -> Option<Self> {
220        // We are in a field.
221        Some(self.clone().neg())
222    }
223}
224
225impl<F: PrimeField> AddAssign for DynamicPolynomialF<F> {
226    fn add_assign(&mut self, rhs: Self) {
227        self.add_assign(&rhs);
228    }
229}
230
231impl<F: PrimeField> AddAssign<&Self> for DynamicPolynomialF<F> {
232    #[allow(clippy::arithmetic_side_effects)] // by definition
233    fn add_assign(&mut self, rhs: &Self) {
234        dynamic::add_assign(&mut self.coeffs, &rhs.coeffs, |elem| {
235            F::zero_with_cfg(elem.cfg())
236        });
237    }
238}
239
240impl<F: PrimeField> SubAssign for DynamicPolynomialF<F> {
241    #[allow(clippy::arithmetic_side_effects)] // by definition
242    fn sub_assign(&mut self, rhs: Self) {
243        self.sub_assign(&rhs);
244    }
245}
246
247impl<F: PrimeField> SubAssign<&Self> for DynamicPolynomialF<F> {
248    #[allow(clippy::arithmetic_side_effects)] // by definition
249    fn sub_assign(&mut self, rhs: &Self) {
250        dynamic::sub_assign(&mut self.coeffs, &rhs.coeffs, |elem| {
251            F::zero_with_cfg(elem.cfg())
252        });
253    }
254}
255
256impl<F: PrimeField> MulAssign for DynamicPolynomialF<F> {
257    #[allow(clippy::arithmetic_side_effects)] // by definition
258    fn mul_assign(&mut self, rhs: Self) {
259        let res = rhs * &*self;
260
261        *self = res
262    }
263}
264
265impl<F: PrimeField> MulAssign<&Self> for DynamicPolynomialF<F> {
266    #[allow(clippy::arithmetic_side_effects)] // by definition
267    fn mul_assign(&mut self, rhs: &Self) {
268        let res = &*self * rhs;
269
270        *self = res;
271    }
272}
273
274impl<F: PrimeField> Semiring for DynamicPolynomialF<F> {}
275
276impl<F: PrimeField> Div for DynamicPolynomialF<F> {
277    type Output = Self;
278
279    fn div(self, rhs: Self) -> Self::Output {
280        self.div_rem_euclid(&rhs).0
281    }
282}
283
284impl<F: PrimeField> Rem for DynamicPolynomialF<F> {
285    type Output = Self;
286
287    fn rem(self, rhs: Self) -> Self::Output {
288        self.div_rem_euclid(&rhs).1
289    }
290}
291
292impl<F: PrimeField> Euclid for DynamicPolynomialF<F> {
293    fn div_euclid(&self, v: &Self) -> Self {
294        self.div_rem_euclid(v).0
295    }
296
297    fn rem_euclid(&self, v: &Self) -> Self {
298        self.div_rem_euclid(v).1
299    }
300
301    #[allow(clippy::arithmetic_side_effects)]
302    fn div_rem_euclid(&self, divisor: &Self) -> (Self, Self) {
303        let zero_poly = DynamicPolynomialF::zero();
304
305        let divisor_deg = divisor.degree().expect("division by zero polynomial");
306
307        let Some(dividend_deg) = self.degree() else {
308            return (zero_poly.clone(), zero_poly);
309        };
310
311        let cfg = self.coeffs[0].cfg();
312        let zero = F::zero_with_cfg(cfg);
313
314        if dividend_deg < divisor_deg {
315            return (zero_poly.clone(), self.clone());
316        }
317
318        // Copy dividend as working remainder
319        let mut remainder = self.coeffs.clone();
320        let quotient_len = dividend_deg - divisor_deg + 1;
321        let mut quotient = vec![zero.clone(); quotient_len];
322
323        let divisor_lead_inv = F::one_with_cfg(cfg) / divisor.coeffs[divisor_deg].clone();
324
325        for i in (0..quotient_len).rev() {
326            let rem_idx = i + divisor_deg;
327            if remainder[rem_idx] == zero {
328                continue;
329            }
330
331            // Compute quotient coefficient
332            let coeff = remainder[rem_idx].clone() * &divisor_lead_inv;
333
334            // Subtract coeff * x^i * divisor from remainder (skip leading term)
335            for j in 0..divisor_deg {
336                remainder[i + j] -= coeff.clone() * &divisor.coeffs[j];
337            }
338            // Leading coefficient is guaranteed to be zero
339            remainder[rem_idx] = zero.clone();
340
341            quotient[i] = coeff;
342        }
343
344        (
345            DynamicPolynomialF { coeffs: quotient },
346            DynamicPolynomialF { coeffs: remainder },
347        )
348    }
349}
350
351impl<F: PrimeField, const DEGFEE_PLUS_ONE: usize> From<DensePolynomial<F, DEGFEE_PLUS_ONE>>
352    for DynamicPolynomialF<F>
353{
354    fn from(dense_poly: DensePolynomial<F, DEGFEE_PLUS_ONE>) -> Self {
355        Self {
356            coeffs: Vec::from(dense_poly.coeffs),
357        }
358    }
359}
360
361impl<F: PrimeField> Polynomial<F> for DynamicPolynomialF<F> {
362    const DEGREE_BOUND: usize = usize::MAX;
363}
364
365impl<F: PrimeField> EvaluatablePolynomial<F, F> for DynamicPolynomialF<F> {
366    type EvaluationPoint = F;
367
368    fn evaluate_at_point(&self, point: &F) -> Result<F, EvaluationError> {
369        // Horner's method.
370        let mut result = self
371            .coeffs
372            .last()
373            .cloned()
374            .unwrap_or(F::zero_with_cfg(point.cfg()));
375
376        for coeff in self.coeffs.iter().rev().skip(1) {
377            result *= point;
378            result += coeff;
379        }
380
381        Ok(result)
382    }
383}
384
385impl<F: PrimeField> FromIterator<F> for DynamicPolynomialF<F> {
386    #[inline(always)]
387    fn from_iter<T: IntoIterator<Item = F>>(iter: T) -> Self {
388        Self {
389            coeffs: iter.into_iter().collect(),
390        }
391    }
392}
393
394/// Unfortunately, we cannot implement of `GenTranscribable` for
395/// `Vec<DynamicPolynomialF<F>>` since they both are foreign types, so we define
396/// this wrapper as a workaround.
397#[derive(Debug, Default, Clone, From, Hash, PartialEq, Eq)]
398#[repr(transparent)]
399pub struct DynamicPolyVecF<F: PrimeField>(pub Vec<DynamicPolynomialF<F>>);
400
401impl<F: PrimeField> DynamicPolyVecF<F> {
402    pub fn reinterpret(value: &Vec<DynamicPolynomialF<F>>) -> &Self {
403        // Safety: `DynamicPolyVecF<F>` is a transparent wrapper, so the memory layout
404        // is the same.
405        unsafe { &*(value as *const Vec<DynamicPolynomialF<F>> as *const Self) }
406    }
407}
408
409impl<F> GenTranscribable for DynamicPolyVecF<F>
410where
411    F: PrimeField,
412    F::Inner: ConstTranscribable,
413    F::Modulus: ConstTranscribable,
414{
415    fn read_transcription_bytes_exact(bytes: &[u8]) -> Self {
416        if bytes.is_empty() {
417            return vec![].into();
418        }
419
420        let modulus_present = match bytes[0] {
421            0 => false,
422            1 => true,
423            v => panic!("Invalid modulus presence flag: expected 0 or 1, got {v}"),
424        };
425        let mut bytes = &bytes[1..];
426        let cfg_option = if modulus_present {
427            let mod_size = F::Modulus::NUM_BYTES;
428            let cfg = zinc_transcript::read_field_cfg::<F>(&bytes[0..mod_size]);
429            bytes = &bytes[mod_size..];
430            Some(cfg)
431        } else {
432            None
433        };
434        let mut result = Vec::new();
435        while !bytes.is_empty() {
436            let (len, rest) = u32::read_transcription_bytes_subset(bytes);
437            let len = usize::try_from(len).expect("polynomial length must fit into usize");
438            bytes = rest;
439            let end = mul!(len, F::Inner::NUM_BYTES);
440            let coeffs = if let Some(ref cfg) = cfg_option {
441                zinc_transcript::read_field_vec_with_cfg(&bytes[..end], cfg)
442            } else {
443                assert_eq!(len, 0, "modulus must be present when poly is non-empty");
444                Vec::new()
445            };
446            result.push(DynamicPolynomialF { coeffs });
447            bytes = &bytes[end..];
448        }
449        assert!(bytes.is_empty(), "All bytes should be consumed");
450        result.into()
451    }
452
453    fn write_transcription_bytes_exact(&self, mut buf: &mut [u8]) {
454        if self.0.is_empty() {
455            return;
456        }
457        if let Some(element) = self.0.iter().find_map(|poly| poly.coeffs.first()) {
458            buf[0] = 1; // Indicate that modulus is present
459            buf = zinc_transcript::append_field_cfg::<F>(&mut buf[1..], &element.modulus());
460        } else {
461            buf[0] = 0;
462            buf = &mut buf[1..];
463        }
464        for poly in self.0.iter() {
465            // This allows writing untrimmed polynomials without overhead
466            let len = poly.degree().map(|d| add!(d, 1)).unwrap_or(0);
467            buf = {
468                let len = u32::try_from(len).expect("polynomial length must fit into u32");
469                len.write_transcription_bytes_exact(&mut buf[0..u32::NUM_BYTES]);
470                &mut buf[u32::NUM_BYTES..]
471            };
472            buf = zinc_transcript::append_field_vec_inner(buf, &poly.coeffs[0..len]);
473        }
474        assert!(buf.is_empty(), "Entire buffer should be used");
475    }
476}
477
478impl<F> Transcribable for DynamicPolyVecF<F>
479where
480    F: PrimeField,
481    F::Inner: ConstTranscribable,
482    F::Modulus: ConstTranscribable,
483{
484    fn get_num_bytes(&self) -> usize {
485        if self.0.is_empty() {
486            return 0;
487        }
488        // 1 byte for the modulus presence flag
489        let has_modulus = self.0.iter().any(|p| !p.coeffs.is_empty());
490        let modulus_bytes = if has_modulus {
491            F::Modulus::NUM_BYTES
492        } else {
493            0
494        };
495        let poly_bytes: usize = self
496            .0
497            .iter()
498            .map(|poly| {
499                let len = poly.degree().map(|d| add!(d, 1)).unwrap_or(0);
500                add!(u32::NUM_BYTES, mul!(len, F::Inner::NUM_BYTES))
501            })
502            .sum();
503        add!(add!(1, modulus_bytes), poly_bytes)
504    }
505}
506
507#[cfg(test)]
508#[allow(clippy::arithmetic_side_effects)]
509mod tests {
510    use crypto_bigint::{Odd, modular::MontyParams};
511    use crypto_primitives::{FromWithConfig, crypto_bigint_monty::F256};
512    use proptest::prelude::*;
513    use rand::Rng;
514
515    use super::*;
516
517    const LIMBS: usize = 4;
518    type F = F256;
519
520    fn test_config() -> MontyParams<LIMBS> {
521        let modulus = crypto_bigint::Uint::<LIMBS>::from_be_hex(
522            "0000000000000000000000000000000000860995AE68FC80E1B1BD1E39D54B33",
523        );
524        let modulus = Odd::new(modulus).expect("modulus should be odd");
525        MontyParams::new(modulus)
526    }
527
528    #[test]
529    fn new_creates_correctly() {
530        let field_cfg = test_config();
531        assert_eq!(
532            DynamicPolynomialF::new_trimmed([
533                F::from_with_cfg(1i32, &field_cfg),
534                F::from_with_cfg(2i32, &field_cfg),
535                F::from_with_cfg(3i32, &field_cfg),
536                F::zero_with_cfg(&field_cfg),
537                F::zero_with_cfg(&field_cfg),
538            ]),
539            DynamicPolynomialF {
540                coeffs: vec![
541                    F::from_with_cfg(1i32, &field_cfg),
542                    F::from_with_cfg(2i32, &field_cfg),
543                    F::from_with_cfg(3i32, &field_cfg),
544                ]
545            }
546        );
547    }
548
549    fn get_2_test_polynomial() -> (DynamicPolynomialF<F>, DynamicPolynomialF<F>) {
550        let field_cfg = test_config();
551
552        let x = DynamicPolynomialF::new(vec![
553            F::from_with_cfg(2i32, &field_cfg),
554            F::zero_with_cfg(&field_cfg),
555            F::from_with_cfg(2i32, &field_cfg),
556            F::zero_with_cfg(&field_cfg),
557            F::zero_with_cfg(&field_cfg),
558        ]);
559
560        let y = DynamicPolynomialF::new(vec![
561            F::from_with_cfg(1i32, &field_cfg),
562            F::from_with_cfg(2i32, &field_cfg),
563            F::from_with_cfg(3i32, &field_cfg),
564        ]);
565
566        (x, y)
567    }
568
569    #[test]
570    fn add_zero() {
571        let field_cfg = test_config();
572
573        assert_eq!(
574            DynamicPolynomialF::<F>::ZERO + DynamicPolynomialF::ZERO,
575            DynamicPolynomialF::ZERO
576        );
577
578        let x = DynamicPolynomialF::new(vec![
579            F::from_with_cfg(2i32, &field_cfg),
580            F::zero_with_cfg(&field_cfg),
581            F::from_with_cfg(2i32, &field_cfg),
582            F::zero_with_cfg(&field_cfg),
583            F::zero_with_cfg(&field_cfg),
584        ]);
585
586        assert_eq!(x.clone() + &DynamicPolynomialF::ZERO, x);
587        assert_eq!(DynamicPolynomialF::ZERO + x.clone(), x);
588        assert_eq!(DynamicPolynomialF::ZERO + &x, x);
589
590        let mut y = x.clone();
591
592        y += DynamicPolynomialF::ZERO;
593
594        assert_eq!(y, x);
595
596        y += &DynamicPolynomialF::ZERO;
597
598        assert_eq!(y, x);
599    }
600
601    #[test]
602    fn addition_is_correct() {
603        let (x, y) = get_2_test_polynomial();
604
605        let field_cfg = test_config();
606
607        let res = DynamicPolynomialF::new(vec![
608            F::from_with_cfg(3i32, &field_cfg),
609            F::from_with_cfg(2i32, &field_cfg),
610            F::from_with_cfg(5i32, &field_cfg),
611            F::zero_with_cfg(&field_cfg),
612            F::zero_with_cfg(&field_cfg),
613        ]);
614
615        assert_eq!(x.clone() + &y, res);
616        assert_eq!(y.clone() + &x, res);
617        assert_eq!(x.clone() + y.clone(), res);
618        assert_eq!(x.checked_add(&y), Some(res.clone()));
619
620        let mut z = x.clone();
621        z += y.clone();
622        assert_eq!(z, res);
623
624        let mut z = x.clone();
625        z += &y;
626        assert_eq!(z, res);
627
628        let mut z = y.clone();
629        z += x.clone();
630        assert_eq!(z, res);
631
632        let mut z = y.clone();
633        z += &x;
634        assert_eq!(z, res);
635    }
636
637    #[test]
638    fn subtraction_is_correct() {
639        let (x, y) = get_2_test_polynomial();
640
641        let field_cfg = test_config();
642
643        let res = DynamicPolynomialF::new(vec![
644            F::from_with_cfg(1i32, &field_cfg),
645            F::from_with_cfg(-2i32, &field_cfg),
646            F::from_with_cfg(-1i32, &field_cfg),
647            F::zero_with_cfg(&field_cfg),
648            F::zero_with_cfg(&field_cfg),
649        ]);
650
651        assert_eq!(x.clone() - &y, res);
652        assert_eq!(x.clone() - y.clone(), res);
653        assert_eq!(x.checked_sub(&y), Some(res.clone()));
654
655        let mut z = x.clone();
656        z -= y.clone();
657        assert_eq!(z, res);
658
659        let mut z = x.clone();
660        z -= &y;
661        assert_eq!(z, res);
662
663        let x = y;
664        let y = DynamicPolynomialF::new(vec![
665            F::from_with_cfg(2i32, &field_cfg),
666            F::from_with_cfg(0i32, &field_cfg),
667            F::from_with_cfg(2i32, &field_cfg),
668            F::from_with_cfg(-1i32, &field_cfg),
669            F::zero_with_cfg(&field_cfg),
670        ]);
671
672        let res = DynamicPolynomialF::new(vec![
673            F::from_with_cfg(-1i32, &field_cfg),
674            F::from_with_cfg(2i32, &field_cfg),
675            F::from_with_cfg(1i32, &field_cfg),
676            F::from_with_cfg(1i32, &field_cfg),
677            F::zero_with_cfg(&field_cfg),
678        ]);
679
680        assert_eq!(x.clone() - &y, res);
681        assert_eq!(x.clone() - y.clone(), res);
682        assert_eq!(x.checked_sub(&y), Some(res.clone()));
683
684        let mut z = x.clone();
685        z -= y.clone();
686        assert_eq!(z, res);
687
688        let mut z = x.clone();
689        z -= &y;
690        assert_eq!(z, res);
691    }
692
693    #[test]
694    fn mul_zero() {
695        assert_eq!(
696            DynamicPolynomialF::<F>::ZERO * DynamicPolynomialF::ZERO,
697            DynamicPolynomialF::ZERO
698        );
699
700        let field_cfg = test_config();
701
702        let x = DynamicPolynomialF::new(vec![
703            F::from_with_cfg(2i32, &field_cfg),
704            F::zero_with_cfg(&field_cfg),
705            F::from_with_cfg(2i32, &field_cfg),
706            F::zero_with_cfg(&field_cfg),
707            F::zero_with_cfg(&field_cfg),
708        ]);
709
710        assert_eq!(
711            x.clone() * &DynamicPolynomialF::ZERO,
712            DynamicPolynomialF::ZERO
713        );
714        assert_eq!(
715            DynamicPolynomialF::ZERO * x.clone(),
716            DynamicPolynomialF::ZERO
717        );
718        assert_eq!(DynamicPolynomialF::ZERO * &x, DynamicPolynomialF::ZERO);
719
720        let mut y = x.clone();
721
722        y *= DynamicPolynomialF::ZERO;
723
724        assert_eq!(y, DynamicPolynomialF::ZERO);
725
726        y *= &DynamicPolynomialF::ZERO;
727
728        assert_eq!(y, DynamicPolynomialF::ZERO);
729    }
730
731    #[test]
732    fn multiplication_is_correct() {
733        let (x, y) = get_2_test_polynomial();
734
735        let field_cfg = test_config();
736
737        let res = DynamicPolynomialF::new(vec![
738            F::from_with_cfg(2i32, &field_cfg),
739            F::from_with_cfg(4i32, &field_cfg),
740            F::from_with_cfg(8i32, &field_cfg),
741            F::from_with_cfg(4i32, &field_cfg),
742            F::from_with_cfg(6i32, &field_cfg),
743            F::zero_with_cfg(&field_cfg),
744            F::zero_with_cfg(&field_cfg),
745        ]);
746
747        assert_eq!(x.clone() * y.clone(), res);
748        assert_eq!(x.clone() * &y, res);
749        assert_eq!(&x * &y, res);
750        assert_eq!(y.clone() * x.clone(), res);
751        assert_eq!(y.clone() * &x, res);
752        assert_eq!(&y * &x, res);
753        assert_eq!(x.checked_mul(&y), Some(res.clone()));
754        assert_eq!(y.checked_mul(&x), Some(res.clone()));
755
756        let mut z = x.clone();
757        z *= y.clone();
758        assert_eq!(z, res);
759
760        let mut z = x.clone();
761        z *= &y;
762        assert_eq!(z, res);
763
764        let mut z = y.clone();
765        z *= x.clone();
766        assert_eq!(z, res);
767
768        let mut z = y.clone();
769        z *= &x;
770        assert_eq!(z, res);
771    }
772
773    #[test]
774    fn test_trim() {
775        let field_cfg = test_config();
776
777        let mut x = DynamicPolynomialF::new([
778            F::zero_with_cfg(&field_cfg),
779            F::zero_with_cfg(&field_cfg),
780            F::zero_with_cfg(&field_cfg),
781            F::zero_with_cfg(&field_cfg),
782            F::zero_with_cfg(&field_cfg),
783        ]);
784        x.trim();
785        assert_eq!(x, DynamicPolynomialF::ZERO);
786
787        let mut x = DynamicPolynomialF::new([
788            F::from_with_cfg(2i32, &field_cfg),
789            F::from_with_cfg(3i32, &field_cfg),
790            F::zero_with_cfg(&field_cfg),
791            F::zero_with_cfg(&field_cfg),
792            F::zero_with_cfg(&field_cfg),
793        ]);
794        x.trim();
795        assert_eq!(
796            x,
797            DynamicPolynomialF::new([
798                F::from_with_cfg(2i32, &field_cfg),
799                F::from_with_cfg(3i32, &field_cfg),
800            ])
801        );
802    }
803
804    #[test]
805    fn evaluate_zero_poly() {
806        assert_eq!(
807            DynamicPolynomialF::<F>::ZERO.evaluate_at_point(&F::one_with_cfg(&test_config())),
808            Ok(F::zero_with_cfg(&test_config()))
809        )
810    }
811
812    fn f(v: u64) -> F {
813        F::from_with_cfg(v, &test_config())
814    }
815
816    #[test]
817    #[should_panic(expected = "division by zero polynomial")]
818    fn test_div_rem_zero_divisor() {
819        let dividend = DynamicPolynomialF {
820            coeffs: vec![f(1), f(1)],
821        };
822        let divisor = DynamicPolynomialF {
823            coeffs: vec![f(0), f(0)],
824        };
825
826        let _ = dividend.div_rem_euclid(&divisor);
827    }
828
829    #[test]
830    fn test_div_euclid_and_rem_euclid() {
831        let dividend = DynamicPolynomialF {
832            coeffs: vec![f(1), f(2), f(1)],
833        };
834        let divisor = DynamicPolynomialF {
835            coeffs: vec![f(1), f(1)],
836        };
837
838        let (q, r) = dividend.div_rem_euclid(&divisor);
839        let q2 = dividend.div_euclid(&divisor);
840        let r2 = dividend.rem_euclid(&divisor);
841
842        assert_eq!(q, q2);
843        assert_eq!(r, r2);
844    }
845
846    fn any_f() -> impl Strategy<Value = F> {
847        let cfg = test_config();
848        any::<u64>().prop_map(move |v| F::from_with_cfg(v, &cfg))
849    }
850
851    fn any_poly(max_degree: usize) -> impl Strategy<Value = DynamicPolynomialF<F>> {
852        let cfg = test_config();
853        (0usize..=max_degree).prop_flat_map(move |degree| {
854            let cfg = cfg;
855            prop::collection::vec(any_f(), degree + 1).prop_map(move |mut coeffs| {
856                let mut rng = rand::rngs::ThreadRng::default();
857                let zero = F::from_with_cfg(0, &cfg);
858                while coeffs[degree] == zero {
859                    let val: u64 = rng.random();
860                    coeffs[degree] = F::from_with_cfg(val, &cfg);
861                }
862                DynamicPolynomialF { coeffs }
863            })
864        })
865    }
866
867    fn sparse_poly(max_degree: usize) -> impl Strategy<Value = DynamicPolynomialF<F>> {
868        let cfg = test_config();
869        (1usize..=max_degree).prop_flat_map(move |degree| {
870            let cfg = cfg;
871            let num_nonzero = std::cmp::min(3, degree);
872            (
873                prop::collection::vec(0usize..degree, num_nonzero),
874                prop::collection::vec(any_f(), num_nonzero + 1),
875            )
876                .prop_map(move |(positions, values)| {
877                    let mut rng = rand::rngs::ThreadRng::default();
878                    let zero = F::from_with_cfg(0, &cfg);
879                    let mut coeffs = vec![zero.clone(); degree + 1];
880                    positions
881                        .iter()
882                        .zip(values.iter())
883                        .for_each(|(p, v)| coeffs[*p] = v.clone());
884                    coeffs[degree] = values.last().unwrap().clone();
885                    while coeffs[degree] == zero {
886                        let val: u64 = rng.random();
887                        coeffs[degree] = F::from_with_cfg(val, &cfg);
888                    }
889                    DynamicPolynomialF { coeffs }
890                })
891        })
892    }
893
894    fn small_coeff_poly(max_degree: usize) -> impl Strategy<Value = DynamicPolynomialF<F>> {
895        let cfg = test_config();
896        (0usize..=max_degree).prop_flat_map(move |degree| {
897            let cfg = cfg;
898            prop::collection::vec(0u64..=2, degree + 1).prop_map(move |raw| {
899                let mut rng = rand::rngs::ThreadRng::default();
900                let zero = F::from_with_cfg(0, &cfg);
901                let mut coeffs: Vec<F> = raw.iter().map(|&v| F::from_with_cfg(v, &cfg)).collect();
902                while coeffs[degree] == zero {
903                    let val: u64 = rng.random::<u64>() % 2 + 1;
904                    coeffs[degree] = F::from_with_cfg(val, &cfg);
905                }
906                DynamicPolynomialF { coeffs }
907            })
908        })
909    }
910
911    fn any_poly_varied(max_degree: usize) -> impl Strategy<Value = DynamicPolynomialF<F>> {
912        prop_oneof![
913            2 => any_poly(max_degree),
914            1 => sparse_poly(max_degree),
915            1 => small_coeff_poly(max_degree),
916        ]
917    }
918
919    proptest! {
920        #![proptest_config(ProptestConfig::with_cases(500))]
921
922        #[test]
923        fn prop_div_rem_random(
924            dividend in any_poly_varied(50),
925            divisor in any_poly_varied(50)
926        ) {
927            let (quotient, remainder) = dividend.div_rem_euclid(&divisor);
928
929            let product = &quotient * &divisor;
930            let reconstructed = product + &remainder;
931
932            let mut dividend_trimmed = dividend.clone();
933            let mut reconstructed_trimmed = reconstructed;
934            dividend_trimmed.trim();
935            reconstructed_trimmed.trim();
936
937            prop_assert_eq!(dividend_trimmed, reconstructed_trimmed);
938        }
939
940        #[test]
941        fn prop_div_rem_exact_division(
942            q in any_poly_varied(25),
943            d in any_poly_varied(25)
944        ) {
945            let dividend = &q * &d;
946            let (quotient, remainder) = dividend.div_rem_euclid(&d);
947
948            let mut remainder_trimmed = remainder;
949            let mut quotient_trimmed = quotient;
950            remainder_trimmed.trim();
951            quotient_trimmed.trim();
952
953            let mut q_trimmed = q.clone();
954            q_trimmed.trim();
955
956            prop_assert_eq!(remainder_trimmed, DynamicPolynomialF::ZERO);
957            prop_assert_eq!(quotient_trimmed, q_trimmed);
958        }
959    }
960}
zinc_poly/univariate/dynamic/over_field.rs

zinc_poly/univariate/dynamic/
over_field.rs
