lambdaworks_math/polynomial/
mod.rs

1use super::field::element::FieldElement;
2use crate::field::traits::{IsField, IsPrimeField, IsSubFieldOf};
3use alloc::string::{String, ToString};
4use alloc::{borrow::ToOwned, format, vec, vec::Vec};
5use core::{fmt::Display, ops, slice};
6pub mod dense_multilinear_poly;
7mod error;
8pub mod sparse_multilinear_poly;
9
10/// Represents the polynomial c_0 + c_1 * X + c_2 * X^2 + ... + c_n * X^n
11/// as a vector of coefficients `[c_0, c_1, ... , c_n]`
12#[derive(Debug, Clone, PartialEq, Eq)]
13pub struct Polynomial<FE> {
14    pub coefficients: Vec<FE>,
15}
16
17impl<F: IsField> Polynomial<FieldElement<F>> {
18    /// Creates a new polynomial with the given coefficients
19    pub fn new(coefficients: &[FieldElement<F>]) -> Self {
20        // Removes trailing zero coefficients at the end
21        let mut unpadded_coefficients = coefficients
22            .iter()
23            .rev()
24            .skip_while(|x| **x == FieldElement::zero())
25            .cloned()
26            .collect::<Vec<FieldElement<F>>>();
27        unpadded_coefficients.reverse();
28        Polynomial {
29            coefficients: unpadded_coefficients,
30        }
31    }
32
33    /// Creates a new monomial term coefficient*x^degree
34    pub fn new_monomial(coefficient: FieldElement<F>, degree: usize) -> Self {
35        let mut coefficients = vec![FieldElement::zero(); degree];
36        coefficients.push(coefficient);
37        Self::new(&coefficients)
38    }
39
40    /// Creates the null polynomial
41    pub fn zero() -> Self {
42        Self::new(&[])
43    }
44
45    /// Returns a polynomial that interpolates the points with x coordinates and y coordinates given by
46    /// `xs` and `ys`.
47    /// `xs` and `ys` must be the same length, and `xs` values should be unique. If not, panics.
48    /// In short, it finds P(x) such that P(xs[i]) = ys[i]
49    pub fn interpolate(
50        xs: &[FieldElement<F>],
51        ys: &[FieldElement<F>],
52    ) -> Result<Self, InterpolateError> {
53        // TODO: try to use the type system to avoid this assert
54        if xs.len() != ys.len() {
55            return Err(InterpolateError::UnequalLengths(xs.len(), ys.len()));
56        }
57        if xs.is_empty() {
58            return Ok(Polynomial::new(&[]));
59        }
60
61        let mut denominators = Vec::with_capacity(xs.len() * (xs.len() - 1) / 2);
62        let mut indexes = Vec::with_capacity(xs.len());
63
64        let mut idx = 0;
65
66        for (i, xi) in xs.iter().enumerate().skip(1) {
67            indexes.push(idx);
68            for xj in xs.iter().take(i) {
69                if xi == xj {
70                    return Err(InterpolateError::NonUniqueXs);
71                }
72                denominators.push(xi - xj);
73                idx += 1;
74            }
75        }
76
77        FieldElement::inplace_batch_inverse(&mut denominators).unwrap();
78
79        let mut result = Polynomial::zero();
80
81        for (i, y) in ys.iter().enumerate() {
82            let mut y_term = Polynomial::new(slice::from_ref(y));
83            for (j, x) in xs.iter().enumerate() {
84                if i == j {
85                    continue;
86                }
87                let denominator = if i > j {
88                    denominators[indexes[i - 1] + j].clone()
89                } else {
90                    -&denominators[indexes[j - 1] + i]
91                };
92                let denominator_poly = Polynomial::new(&[denominator]);
93                let numerator = Polynomial::new(&[-x, FieldElement::one()]);
94                y_term = y_term.mul_with_ref(&(numerator * denominator_poly));
95            }
96            result = result + y_term;
97        }
98        Ok(result)
99    }
100
101    /// Evaluates a polynomial P(t) at a point x, using Horner's algorithm
102    /// Returns y = P(x)
103    pub fn evaluate<E>(&self, x: &FieldElement<E>) -> FieldElement<E>
104    where
105        E: IsField,
106        F: IsSubFieldOf<E>,
107    {
108        self.coefficients
109            .iter()
110            .rev()
111            .fold(FieldElement::zero(), |acc, coeff| {
112                coeff + acc * x.to_owned()
113            })
114    }
115
116    /// Evaluates a polynomial P(t) at a slice of points x
117    /// Returns a vector y such that y[i] = P(input[i])
118    pub fn evaluate_slice(&self, input: &[FieldElement<F>]) -> Vec<FieldElement<F>> {
119        input.iter().map(|x| self.evaluate(x)).collect()
120    }
121
122    /// Returns the degree of a polynomial, which corresponds to the highest power of x^d
123    /// with non-zero coefficient
124    pub fn degree(&self) -> usize {
125        if self.coefficients.is_empty() {
126            0
127        } else {
128            self.coefficients.len() - 1
129        }
130    }
131
132    /// Returns the coefficient accompanying x^degree
133    pub fn leading_coefficient(&self) -> FieldElement<F> {
134        if let Some(coefficient) = self.coefficients.last() {
135            coefficient.clone()
136        } else {
137            FieldElement::zero()
138        }
139    }
140
141    /// Returns coefficients of the polynomial as an array
142    /// \[c_0, c_1, c_2, ..., c_n\]
143    /// that represents the polynomial
144    /// c_0 + c_1 * X + c_2 * X^2 + ... + c_n * X^n
145    pub fn coefficients(&self) -> &[FieldElement<F>] {
146        &self.coefficients
147    }
148
149    /// Returns the length of the vector of coefficients
150    pub fn coeff_len(&self) -> usize {
151        self.coefficients().len()
152    }
153
154    /// Returns the derivative of the polynomial with respect to x.
155    pub fn differentiate(&self) -> Self {
156        let degree = self.degree();
157        if degree == 0 {
158            return Polynomial::zero();
159        }
160        let mut derivative = Vec::with_capacity(degree);
161        for (i, coeff) in self.coefficients().iter().enumerate().skip(1) {
162            derivative.push(FieldElement::<F>::from(i as u64) * coeff);
163        }
164        Polynomial::new(&derivative)
165    }
166
167    /// Computes quotient with `x - b` in place.
168    pub fn ruffini_division_inplace(&mut self, b: &FieldElement<F>) {
169        let mut c = FieldElement::zero();
170        for coeff in self.coefficients.iter_mut().rev() {
171            *coeff = &*coeff + b * &c;
172            core::mem::swap(coeff, &mut c);
173        }
174        self.coefficients.pop();
175    }
176
177    /// Computes the quotient of the division of P(x) with x - b using Ruffini's rule
178    pub fn ruffini_division<L>(&self, b: &FieldElement<L>) -> Polynomial<FieldElement<L>>
179    where
180        L: IsField,
181        F: IsSubFieldOf<L>,
182    {
183        if let Some(c) = self.coefficients.last() {
184            let mut c = c.clone().to_extension();
185            let mut coefficients = Vec::with_capacity(self.degree());
186            for coeff in self.coefficients.iter().rev().skip(1) {
187                coefficients.push(c.clone());
188                c = coeff + c * b;
189            }
190            coefficients = coefficients.into_iter().rev().collect();
191            Polynomial::new(&coefficients)
192        } else {
193            Polynomial::zero()
194        }
195    }
196
197    /// Computes quotient and remainder of polynomial division.
198    ///
199    /// Output: (quotient, remainder)
200    pub fn long_division_with_remainder(self, dividend: &Self) -> (Self, Self) {
201        if dividend.degree() > self.degree() {
202            (Polynomial::zero(), self)
203        } else {
204            let mut n = self;
205            let mut q: Vec<FieldElement<F>> = vec![FieldElement::zero(); n.degree() + 1];
206            let denominator = dividend.leading_coefficient().inv().unwrap();
207            while n != Polynomial::zero() && n.degree() >= dividend.degree() {
208                let new_coefficient = n.leading_coefficient() * &denominator;
209                q[n.degree() - dividend.degree()] = new_coefficient.clone();
210                let d = dividend.mul_with_ref(&Polynomial::new_monomial(
211                    new_coefficient,
212                    n.degree() - dividend.degree(),
213                ));
214                n = n - d;
215            }
216            (Polynomial::new(&q), n)
217        }
218    }
219
220    /// Extended Euclidean Algorithm for polynomials.
221    ///
222    /// This method computes the extended greatest common divisor (GCD) of two polynomials `self` and `y`.
223    /// It returns a tuple of three elements: `(a, b, g)` such that `a * self + b * y = g`, where `g` is the
224    /// greatest common divisor of `self` and `y`.
225    pub fn xgcd(&self, y: &Self) -> (Self, Self, Self) {
226        let one = Polynomial::new(&[FieldElement::one()]);
227        let zero = Polynomial::zero();
228        let (mut old_r, mut r) = (self.clone(), y.clone());
229        let (mut old_s, mut s) = (one.clone(), zero.clone());
230        let (mut old_t, mut t) = (zero.clone(), one.clone());
231
232        while r != Polynomial::zero() {
233            let quotient = old_r.clone().div_with_ref(&r);
234            old_r = old_r - &quotient * &r;
235            core::mem::swap(&mut old_r, &mut r);
236            old_s = old_s - &quotient * &s;
237            core::mem::swap(&mut old_s, &mut s);
238            old_t = old_t - &quotient * &t;
239            core::mem::swap(&mut old_t, &mut t);
240        }
241
242        let lcinv = old_r.leading_coefficient().inv().unwrap();
243        (
244            old_s.scale_coeffs(&lcinv),
245            old_t.scale_coeffs(&lcinv),
246            old_r.scale_coeffs(&lcinv),
247        )
248    }
249
250    pub fn div_with_ref(self, dividend: &Self) -> Self {
251        let (quotient, _remainder) = self.long_division_with_remainder(dividend);
252        quotient
253    }
254
255    pub fn mul_with_ref(&self, factor: &Self) -> Self {
256        let degree = self.degree() + factor.degree();
257        let mut coefficients = vec![FieldElement::zero(); degree + 1];
258
259        if self.coefficients.is_empty() || factor.coefficients.is_empty() {
260            Polynomial::new(&[FieldElement::zero()])
261        } else {
262            for i in 0..=factor.degree() {
263                if factor.coefficients[i] != FieldElement::zero() {
264                    for j in 0..=self.degree() {
265                        if self.coefficients[j] != FieldElement::zero() {
266                            coefficients[i + j] += &factor.coefficients[i] * &self.coefficients[j];
267                        }
268                    }
269                }
270            }
271            Polynomial::new(&coefficients)
272        }
273    }
274
275    /// Scales the coefficients of a polynomial P by a factor
276    /// Returns P(factor * x)
277    pub fn scale<S: IsSubFieldOf<F>>(&self, factor: &FieldElement<S>) -> Self {
278        let scaled_coefficients = self
279            .coefficients
280            .iter()
281            .zip(core::iter::successors(Some(FieldElement::one()), |x| {
282                Some(x * factor)
283            }))
284            .map(|(coeff, power)| power * coeff)
285            .collect();
286        Self {
287            coefficients: scaled_coefficients,
288        }
289    }
290
291    /// Multiplies all coefficients by a factor
292    pub fn scale_coeffs(&self, factor: &FieldElement<F>) -> Self {
293        let scaled_coefficients = self
294            .coefficients
295            .iter()
296            .map(|coeff| factor * coeff)
297            .collect();
298        Self {
299            coefficients: scaled_coefficients,
300        }
301    }
302
303    /// Returns a vector of polynomials [p₀, p₁, ..., p_{d-1}], where d is `number_of_parts`, such that `self` equals
304    /// p₀(Xᵈ) + Xp₁(Xᵈ) + ... + X^(d-1)p_{d-1}(Xᵈ).
305    ///
306    /// Example: if d = 2 and `self` is 3 X^3 + X^2 + 2X + 1, then `poly.break_in_parts(2)`
307    /// returns a vector with two polynomials `(p₀, p₁)`, where p₀ = X + 1 and p₁ = 3X + 2.
308    pub fn break_in_parts(&self, number_of_parts: usize) -> Vec<Self> {
309        let coef = self.coefficients();
310        let mut parts: Vec<Self> = Vec::with_capacity(number_of_parts);
311        for i in 0..number_of_parts {
312            let coeffs: Vec<_> = coef
313                .iter()
314                .skip(i)
315                .step_by(number_of_parts)
316                .cloned()
317                .collect();
318            parts.push(Polynomial::new(&coeffs));
319        }
320        parts
321    }
322
323    /// Embeds the coefficients of a polynomial into an extension field
324    /// For example, given a polynomial with coefficients in F_p, returns the same
325    /// polynomial with its coefficients as elements in F_{p^2}
326    pub fn to_extension<L: IsField>(self) -> Polynomial<FieldElement<L>>
327    where
328        F: IsSubFieldOf<L>,
329    {
330        Polynomial {
331            coefficients: self
332                .coefficients
333                .into_iter()
334                .map(|x| x.to_extension::<L>())
335                .collect(),
336        }
337    }
338
339    pub fn truncate(&self, k: usize) -> Self {
340        if k == 0 {
341            Self::zero()
342        } else {
343            Self::new(&self.coefficients[0..k.min(self.coefficients.len())])
344        }
345    }
346    pub fn reverse(&self, d: usize) -> Self {
347        let mut coeffs = self.coefficients.clone();
348        coeffs.resize(d + 1, FieldElement::zero());
349        coeffs.reverse();
350        Self::new(&coeffs)
351    }
352}
353
354impl<F: IsPrimeField> Polynomial<FieldElement<F>> {
355    // Print the polynomial as a string ready to be used in SageMath, or just for pretty printing.
356    pub fn print_as_sage_poly(&self, var_name: Option<char>) -> String {
357        let var_name = var_name.unwrap_or('x');
358        if self.coefficients.is_empty()
359            || self.coefficients.len() == 1 && self.coefficients[0] == FieldElement::zero()
360        {
361            return String::new();
362        }
363
364        let mut string = String::new();
365        let zero = FieldElement::<F>::zero();
366
367        for (i, coeff) in self.coefficients.iter().rev().enumerate() {
368            if *coeff == zero {
369                continue;
370            }
371
372            let coeff_str = coeff.representative().to_string();
373
374            if i == self.coefficients.len() - 1 {
375                string.push_str(&coeff_str);
376            } else if i == self.coefficients.len() - 2 {
377                string.push_str(&format!("{coeff_str}*{var_name} + "));
378            } else {
379                string.push_str(&format!(
380                    "{}*{}^{} + ",
381                    coeff_str,
382                    var_name,
383                    self.coefficients.len() - 1 - i
384                ));
385            }
386        }
387
388        string
389    }
390}
391
392/// Pads a polynomial with zeros until the desired length
393/// This function can be useful when evaluating polynomials with the FFT
394pub fn pad_with_zero_coefficients_to_length<F: IsField>(
395    pa: &mut Polynomial<FieldElement<F>>,
396    n: usize,
397) {
398    pa.coefficients.resize(n, FieldElement::zero());
399}
400
401/// Pads polynomial representations with minimum number of zeros to match lengths.
402pub fn pad_with_zero_coefficients<L: IsField, F: IsSubFieldOf<L>>(
403    pa: &Polynomial<FieldElement<F>>,
404    pb: &Polynomial<FieldElement<L>>,
405) -> (Polynomial<FieldElement<F>>, Polynomial<FieldElement<L>>) {
406    let mut pa = pa.clone();
407    let mut pb = pb.clone();
408
409    if pa.coefficients.len() > pb.coefficients.len() {
410        pad_with_zero_coefficients_to_length(&mut pb, pa.coefficients.len());
411    } else {
412        pad_with_zero_coefficients_to_length(&mut pa, pb.coefficients.len());
413    }
414    (pa, pb)
415}
416
417/// Computes the composition of polynomials P1(t) and P2(t), that is P1(P2(t))
418/// It uses interpolation to determine the evaluation at points x_i and evaluates
419/// P1(P2(x[i])). The interpolation theorem ensures that we can reconstruct the polynomial
420/// uniquely by interpolation over a suitable number of points
421/// This is an inefficient version, for something more efficient, use FFT for evaluation,
422/// provided the field satisfies the necessary traits
423pub fn compose<F>(
424    poly_1: &Polynomial<FieldElement<F>>,
425    poly_2: &Polynomial<FieldElement<F>>,
426) -> Polynomial<FieldElement<F>>
427where
428    F: IsField,
429{
430    let max_degree: u64 = (poly_1.degree() * poly_2.degree()) as u64;
431
432    let mut interpolation_points = vec![];
433    for i in 0_u64..max_degree + 1 {
434        interpolation_points.push(FieldElement::<F>::from(i));
435    }
436
437    let values: Vec<_> = interpolation_points
438        .iter()
439        .map(|value| {
440            let intermediate_value = poly_2.evaluate(value);
441            poly_1.evaluate(&intermediate_value)
442        })
443        .collect();
444
445    Polynomial::interpolate(interpolation_points.as_slice(), values.as_slice())
446        .expect("xs and ys have equal length and xs are unique")
447}
448
449// impl Add
450impl<F, L> ops::Add<&Polynomial<FieldElement<L>>> for &Polynomial<FieldElement<F>>
451where
452    L: IsField,
453    F: IsSubFieldOf<L>,
454{
455    type Output = Polynomial<FieldElement<L>>;
456
457    fn add(self, a_polynomial: &Polynomial<FieldElement<L>>) -> Self::Output {
458        let (pa, pb) = pad_with_zero_coefficients(self, a_polynomial);
459        let iter_coeff_pa = pa.coefficients.iter();
460        let iter_coeff_pb = pb.coefficients.iter();
461        let new_coefficients = iter_coeff_pa.zip(iter_coeff_pb).map(|(x, y)| x + y);
462        let new_coefficients_vec = new_coefficients.collect::<Vec<FieldElement<L>>>();
463        Polynomial::new(&new_coefficients_vec)
464    }
465}
466
467impl<F, L> ops::Add<Polynomial<FieldElement<L>>> for Polynomial<FieldElement<F>>
468where
469    L: IsField,
470    F: IsSubFieldOf<L>,
471{
472    type Output = Polynomial<FieldElement<L>>;
473
474    fn add(self, a_polynomial: Polynomial<FieldElement<L>>) -> Polynomial<FieldElement<L>> {
475        &self + &a_polynomial
476    }
477}
478
479impl<F, L> ops::Add<&Polynomial<FieldElement<L>>> for Polynomial<FieldElement<F>>
480where
481    L: IsField,
482    F: IsSubFieldOf<L>,
483{
484    type Output = Polynomial<FieldElement<L>>;
485
486    fn add(self, a_polynomial: &Polynomial<FieldElement<L>>) -> Polynomial<FieldElement<L>> {
487        &self + a_polynomial
488    }
489}
490
491impl<F, L> ops::Add<Polynomial<FieldElement<L>>> for &Polynomial<FieldElement<F>>
492where
493    L: IsField,
494    F: IsSubFieldOf<L>,
495{
496    type Output = Polynomial<FieldElement<L>>;
497
498    fn add(self, a_polynomial: Polynomial<FieldElement<L>>) -> Polynomial<FieldElement<L>> {
499        self + &a_polynomial
500    }
501}
502
503// impl neg, that is, additive inverse for polynomials P(t) + Q(t) = 0
504impl<F: IsField> ops::Neg for &Polynomial<FieldElement<F>> {
505    type Output = Polynomial<FieldElement<F>>;
506
507    fn neg(self) -> Polynomial<FieldElement<F>> {
508        let neg = self
509            .coefficients
510            .iter()
511            .map(|x| -x)
512            .collect::<Vec<FieldElement<F>>>();
513        Polynomial::new(&neg)
514    }
515}
516
517impl<F: IsField> ops::Neg for Polynomial<FieldElement<F>> {
518    type Output = Polynomial<FieldElement<F>>;
519
520    fn neg(self) -> Polynomial<FieldElement<F>> {
521        -&self
522    }
523}
524
525// impl Sub
526impl<F, L> ops::Sub<&Polynomial<FieldElement<L>>> for &Polynomial<FieldElement<F>>
527where
528    L: IsField,
529    F: IsSubFieldOf<L>,
530{
531    type Output = Polynomial<FieldElement<L>>;
532
533    fn sub(self, substrahend: &Polynomial<FieldElement<L>>) -> Polynomial<FieldElement<L>> {
534        self + (-substrahend)
535    }
536}
537
538impl<F, L> ops::Sub<Polynomial<FieldElement<L>>> for Polynomial<FieldElement<F>>
539where
540    L: IsField,
541    F: IsSubFieldOf<L>,
542{
543    type Output = Polynomial<FieldElement<L>>;
544
545    fn sub(self, substrahend: Polynomial<FieldElement<L>>) -> Polynomial<FieldElement<L>> {
546        &self - &substrahend
547    }
548}
549
550impl<F, L> ops::Sub<&Polynomial<FieldElement<L>>> for Polynomial<FieldElement<F>>
551where
552    L: IsField,
553    F: IsSubFieldOf<L>,
554{
555    type Output = Polynomial<FieldElement<L>>;
556
557    fn sub(self, substrahend: &Polynomial<FieldElement<L>>) -> Polynomial<FieldElement<L>> {
558        &self - substrahend
559    }
560}
561
562impl<F, L> ops::Sub<Polynomial<FieldElement<L>>> for &Polynomial<FieldElement<F>>
563where
564    L: IsField,
565    F: IsSubFieldOf<L>,
566{
567    type Output = Polynomial<FieldElement<L>>;
568
569    fn sub(self, substrahend: Polynomial<FieldElement<L>>) -> Polynomial<FieldElement<L>> {
570        self - &substrahend
571    }
572}
573
574impl<F> ops::Div<Polynomial<FieldElement<F>>> for Polynomial<FieldElement<F>>
575where
576    F: IsField,
577{
578    type Output = Polynomial<FieldElement<F>>;
579
580    fn div(self, dividend: Polynomial<FieldElement<F>>) -> Polynomial<FieldElement<F>> {
581        self.div_with_ref(&dividend)
582    }
583}
584
585impl<F: IsField> ops::Mul<&Polynomial<FieldElement<F>>> for &Polynomial<FieldElement<F>> {
586    type Output = Polynomial<FieldElement<F>>;
587    fn mul(self, factor: &Polynomial<FieldElement<F>>) -> Polynomial<FieldElement<F>> {
588        self.mul_with_ref(factor)
589    }
590}
591
592impl<F: IsField> ops::Mul<Polynomial<FieldElement<F>>> for Polynomial<FieldElement<F>> {
593    type Output = Polynomial<FieldElement<F>>;
594    fn mul(self, factor: Polynomial<FieldElement<F>>) -> Polynomial<FieldElement<F>> {
595        &self * &factor
596    }
597}
598
599impl<F: IsField> ops::Mul<Polynomial<FieldElement<F>>> for &Polynomial<FieldElement<F>> {
600    type Output = Polynomial<FieldElement<F>>;
601    fn mul(self, factor: Polynomial<FieldElement<F>>) -> Polynomial<FieldElement<F>> {
602        self * &factor
603    }
604}
605
606impl<F: IsField> ops::Mul<&Polynomial<FieldElement<F>>> for Polynomial<FieldElement<F>> {
607    type Output = Polynomial<FieldElement<F>>;
608    fn mul(self, factor: &Polynomial<FieldElement<F>>) -> Polynomial<FieldElement<F>> {
609        &self * factor
610    }
611}
612
613/* Operations between Polynomials and field elements */
614/* Multiplication field element at left */
615impl<F, L> ops::Mul<FieldElement<F>> for Polynomial<FieldElement<L>>
616where
617    L: IsField,
618    F: IsSubFieldOf<L>,
619{
620    type Output = Polynomial<FieldElement<L>>;
621
622    fn mul(self, multiplicand: FieldElement<F>) -> Polynomial<FieldElement<L>> {
623        let new_coefficients = self
624            .coefficients
625            .iter()
626            .map(|value| &multiplicand * value)
627            .collect();
628        Polynomial {
629            coefficients: new_coefficients,
630        }
631    }
632}
633
634impl<F, L> ops::Mul<&FieldElement<F>> for &Polynomial<FieldElement<L>>
635where
636    L: IsField,
637    F: IsSubFieldOf<L>,
638{
639    type Output = Polynomial<FieldElement<L>>;
640
641    fn mul(self, multiplicand: &FieldElement<F>) -> Polynomial<FieldElement<L>> {
642        self.clone() * multiplicand.clone()
643    }
644}
645
646impl<F, L> ops::Mul<FieldElement<F>> for &Polynomial<FieldElement<L>>
647where
648    L: IsField,
649    F: IsSubFieldOf<L>,
650{
651    type Output = Polynomial<FieldElement<L>>;
652
653    fn mul(self, multiplicand: FieldElement<F>) -> Polynomial<FieldElement<L>> {
654        self * &multiplicand
655    }
656}
657
658impl<F, L> ops::Mul<&FieldElement<F>> for Polynomial<FieldElement<L>>
659where
660    L: IsField,
661    F: IsSubFieldOf<L>,
662{
663    type Output = Polynomial<FieldElement<L>>;
664
665    fn mul(self, multiplicand: &FieldElement<F>) -> Polynomial<FieldElement<L>> {
666        &self * multiplicand
667    }
668}
669
670/* Multiplication field element at right */
671impl<F, L> ops::Mul<&Polynomial<FieldElement<L>>> for &FieldElement<F>
672where
673    L: IsField,
674    F: IsSubFieldOf<L>,
675{
676    type Output = Polynomial<FieldElement<L>>;
677
678    fn mul(self, multiplicand: &Polynomial<FieldElement<L>>) -> Polynomial<FieldElement<L>> {
679        multiplicand * self
680    }
681}
682
683impl<F, L> ops::Mul<Polynomial<FieldElement<L>>> for &FieldElement<F>
684where
685    L: IsField,
686    F: IsSubFieldOf<L>,
687{
688    type Output = Polynomial<FieldElement<L>>;
689
690    fn mul(self, multiplicand: Polynomial<FieldElement<L>>) -> Polynomial<FieldElement<L>> {
691        &multiplicand * self
692    }
693}
694
695impl<F, L> ops::Mul<&Polynomial<FieldElement<L>>> for FieldElement<F>
696where
697    L: IsField,
698    F: IsSubFieldOf<L>,
699{
700    type Output = Polynomial<FieldElement<L>>;
701
702    fn mul(self, multiplicand: &Polynomial<FieldElement<L>>) -> Polynomial<FieldElement<L>> {
703        multiplicand * self
704    }
705}
706
707impl<F, L> ops::Mul<Polynomial<FieldElement<L>>> for FieldElement<F>
708where
709    L: IsField,
710    F: IsSubFieldOf<L>,
711{
712    type Output = Polynomial<FieldElement<L>>;
713
714    fn mul(self, multiplicand: Polynomial<FieldElement<L>>) -> Polynomial<FieldElement<L>> {
715        &multiplicand * &self
716    }
717}
718
719/* Addition field element at left */
720impl<F, L> ops::Add<&FieldElement<F>> for &Polynomial<FieldElement<L>>
721where
722    L: IsField,
723    F: IsSubFieldOf<L>,
724{
725    type Output = Polynomial<FieldElement<L>>;
726
727    fn add(self, other: &FieldElement<F>) -> Polynomial<FieldElement<L>> {
728        Polynomial::new_monomial(other.clone(), 0) + self
729    }
730}
731
732impl<F, L> ops::Add<FieldElement<F>> for Polynomial<FieldElement<L>>
733where
734    L: IsField,
735    F: IsSubFieldOf<L>,
736{
737    type Output = Polynomial<FieldElement<L>>;
738
739    fn add(self, other: FieldElement<F>) -> Polynomial<FieldElement<L>> {
740        &self + &other
741    }
742}
743
744impl<F, L> ops::Add<FieldElement<F>> for &Polynomial<FieldElement<L>>
745where
746    L: IsField,
747    F: IsSubFieldOf<L>,
748{
749    type Output = Polynomial<FieldElement<L>>;
750
751    fn add(self, other: FieldElement<F>) -> Polynomial<FieldElement<L>> {
752        self + &other
753    }
754}
755
756impl<F, L> ops::Add<&FieldElement<F>> for Polynomial<FieldElement<L>>
757where
758    L: IsField,
759    F: IsSubFieldOf<L>,
760{
761    type Output = Polynomial<FieldElement<L>>;
762
763    fn add(self, other: &FieldElement<F>) -> Polynomial<FieldElement<L>> {
764        &self + other
765    }
766}
767
768/* Addition field element at right */
769impl<F, L> ops::Add<&Polynomial<FieldElement<L>>> for &FieldElement<F>
770where
771    L: IsField,
772    F: IsSubFieldOf<L>,
773{
774    type Output = Polynomial<FieldElement<L>>;
775
776    fn add(self, other: &Polynomial<FieldElement<L>>) -> Polynomial<FieldElement<L>> {
777        Polynomial::new_monomial(self.clone(), 0) + other
778    }
779}
780
781impl<F, L> ops::Add<Polynomial<FieldElement<L>>> for FieldElement<F>
782where
783    L: IsField,
784    F: IsSubFieldOf<L>,
785{
786    type Output = Polynomial<FieldElement<L>>;
787
788    fn add(self, other: Polynomial<FieldElement<L>>) -> Polynomial<FieldElement<L>> {
789        &self + &other
790    }
791}
792
793impl<F, L> ops::Add<Polynomial<FieldElement<L>>> for &FieldElement<F>
794where
795    L: IsField,
796    F: IsSubFieldOf<L>,
797{
798    type Output = Polynomial<FieldElement<L>>;
799
800    fn add(self, other: Polynomial<FieldElement<L>>) -> Polynomial<FieldElement<L>> {
801        self + &other
802    }
803}
804
805impl<F, L> ops::Add<&Polynomial<FieldElement<L>>> for FieldElement<F>
806where
807    L: IsField,
808    F: IsSubFieldOf<L>,
809{
810    type Output = Polynomial<FieldElement<L>>;
811
812    fn add(self, other: &Polynomial<FieldElement<L>>) -> Polynomial<FieldElement<L>> {
813        &self + other
814    }
815}
816
817/* Substraction field element at left */
818impl<F, L> ops::Sub<&FieldElement<F>> for &Polynomial<FieldElement<L>>
819where
820    L: IsField,
821    F: IsSubFieldOf<L>,
822{
823    type Output = Polynomial<FieldElement<L>>;
824
825    fn sub(self, other: &FieldElement<F>) -> Polynomial<FieldElement<L>> {
826        -Polynomial::new_monomial(other.clone(), 0) + self
827    }
828}
829
830impl<F, L> ops::Sub<FieldElement<F>> for Polynomial<FieldElement<L>>
831where
832    L: IsField,
833    F: IsSubFieldOf<L>,
834{
835    type Output = Polynomial<FieldElement<L>>;
836
837    fn sub(self, other: FieldElement<F>) -> Polynomial<FieldElement<L>> {
838        &self - &other
839    }
840}
841
842impl<F, L> ops::Sub<FieldElement<F>> for &Polynomial<FieldElement<L>>
843where
844    L: IsField,
845    F: IsSubFieldOf<L>,
846{
847    type Output = Polynomial<FieldElement<L>>;
848
849    fn sub(self, other: FieldElement<F>) -> Polynomial<FieldElement<L>> {
850        self - &other
851    }
852}
853
854impl<F, L> ops::Sub<&FieldElement<F>> for Polynomial<FieldElement<L>>
855where
856    L: IsField,
857    F: IsSubFieldOf<L>,
858{
859    type Output = Polynomial<FieldElement<L>>;
860
861    fn sub(self, other: &FieldElement<F>) -> Polynomial<FieldElement<L>> {
862        &self - other
863    }
864}
865
866/* Substraction field element at right */
867impl<F, L> ops::Sub<&Polynomial<FieldElement<L>>> for &FieldElement<F>
868where
869    L: IsField,
870    F: IsSubFieldOf<L>,
871{
872    type Output = Polynomial<FieldElement<L>>;
873
874    fn sub(self, other: &Polynomial<FieldElement<L>>) -> Polynomial<FieldElement<L>> {
875        Polynomial::new_monomial(self.clone(), 0) - other
876    }
877}
878
879impl<F, L> ops::Sub<Polynomial<FieldElement<L>>> for FieldElement<F>
880where
881    L: IsField,
882    F: IsSubFieldOf<L>,
883{
884    type Output = Polynomial<FieldElement<L>>;
885
886    fn sub(self, other: Polynomial<FieldElement<L>>) -> Polynomial<FieldElement<L>> {
887        &self - &other
888    }
889}
890
891impl<F, L> ops::Sub<Polynomial<FieldElement<L>>> for &FieldElement<F>
892where
893    L: IsField,
894    F: IsSubFieldOf<L>,
895{
896    type Output = Polynomial<FieldElement<L>>;
897
898    fn sub(self, other: Polynomial<FieldElement<L>>) -> Polynomial<FieldElement<L>> {
899        self - &other
900    }
901}
902
903impl<F, L> ops::Sub<&Polynomial<FieldElement<L>>> for FieldElement<F>
904where
905    L: IsField,
906    F: IsSubFieldOf<L>,
907{
908    type Output = Polynomial<FieldElement<L>>;
909
910    fn sub(self, other: &Polynomial<FieldElement<L>>) -> Polynomial<FieldElement<L>> {
911        &self - other
912    }
913}
914
915#[derive(Debug)]
916pub enum InterpolateError {
917    UnequalLengths(usize, usize),
918    NonUniqueXs,
919}
920
921impl Display for InterpolateError {
922    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
923        match self {
924            InterpolateError::UnequalLengths(x, y) => {
925                write!(f, "xs and ys must be the same length. Got: {x} != {y}")
926            }
927            InterpolateError::NonUniqueXs => write!(f, "xs values should be unique."),
928        }
929    }
930}
931
932#[cfg(feature = "std")]
933impl std::error::Error for InterpolateError {}
934
935#[cfg(test)]
936mod tests {
937    use crate::field::fields::u64_prime_field::U64PrimeField;
938
939    // Some of these tests work when the finite field has order greater than 2.
940    use super::*;
941    const ORDER: u64 = 23;
942    type F = U64PrimeField<ORDER>;
943    type FE = FieldElement<F>;
944
945    fn polynomial_a() -> Polynomial<FE> {
946        Polynomial::new(&[FE::new(1), FE::new(2), FE::new(3)])
947    }
948
949    fn polynomial_minus_a() -> Polynomial<FE> {
950        Polynomial::new(&[FE::new(ORDER - 1), FE::new(ORDER - 2), FE::new(ORDER - 3)])
951    }
952
953    fn polynomial_b() -> Polynomial<FE> {
954        Polynomial::new(&[FE::new(3), FE::new(4), FE::new(5)])
955    }
956
957    fn polynomial_a_plus_b() -> Polynomial<FE> {
958        Polynomial::new(&[FE::new(4), FE::new(6), FE::new(8)])
959    }
960
961    fn polynomial_b_minus_a() -> Polynomial<FE> {
962        Polynomial::new(&[FE::new(2), FE::new(2), FE::new(2)])
963    }
964
965    #[test]
966    fn adding_a_and_b_equals_a_plus_b() {
967        assert_eq!(polynomial_a() + polynomial_b(), polynomial_a_plus_b());
968    }
969
970    #[test]
971    fn adding_a_and_a_plus_b_does_not_equal_b() {
972        assert_ne!(polynomial_a() + polynomial_a_plus_b(), polynomial_b());
973    }
974
975    #[test]
976    fn add_5_to_0_is_5() {
977        let p1 = Polynomial::new(&[FE::new(5)]);
978        let p2 = Polynomial::new(&[FE::new(0)]);
979        assert_eq!(p1 + p2, Polynomial::new(&[FE::new(5)]));
980    }
981
982    #[test]
983    fn add_0_to_5_is_5() {
984        let p1 = Polynomial::new(&[FE::new(5)]);
985        let p2 = Polynomial::new(&[FE::new(0)]);
986        assert_eq!(p2 + p1, Polynomial::new(&[FE::new(5)]));
987    }
988
989    #[test]
990    fn negating_0_returns_0() {
991        let p1 = Polynomial::new(&[FE::new(0)]);
992        assert_eq!(-p1, Polynomial::new(&[FE::new(0)]));
993    }
994
995    #[test]
996    fn negating_a_is_equal_to_minus_a() {
997        assert_eq!(-polynomial_a(), polynomial_minus_a());
998    }
999
1000    #[test]
1001    fn negating_a_is_not_equal_to_a() {
1002        assert_ne!(-polynomial_a(), polynomial_a());
1003    }
1004
1005    #[test]
1006    fn substracting_5_5_gives_0() {
1007        let p1 = Polynomial::new(&[FE::new(5)]);
1008        let p2 = Polynomial::new(&[FE::new(5)]);
1009        let p3 = Polynomial::new(&[FE::new(0)]);
1010        assert_eq!(p1 - p2, p3);
1011    }
1012
1013    #[test]
1014    fn substracting_b_and_a_equals_b_minus_a() {
1015        assert_eq!(polynomial_b() - polynomial_a(), polynomial_b_minus_a());
1016    }
1017
1018    #[test]
1019    fn constructor_removes_zeros_at_the_end_of_polynomial() {
1020        let p1 = Polynomial::new(&[FE::new(3), FE::new(4), FE::new(0)]);
1021        assert_eq!(p1.coefficients, &[FE::new(3), FE::new(4)]);
1022    }
1023
1024    #[test]
1025    fn pad_with_zero_coefficients_returns_polynomials_with_zeros_until_matching_size() {
1026        let p1 = Polynomial::new(&[FE::new(3), FE::new(4)]);
1027        let p2 = Polynomial::new(&[FE::new(3)]);
1028
1029        assert_eq!(p2.coefficients, &[FE::new(3)]);
1030        let (pp1, pp2) = pad_with_zero_coefficients(&p1, &p2);
1031        assert_eq!(pp1, p1);
1032        assert_eq!(pp2.coefficients, &[FE::new(3), FE::new(0)]);
1033    }
1034
1035    #[test]
1036    fn multiply_5_and_0_is_0() {
1037        let p1 = Polynomial::new(&[FE::new(5)]);
1038        let p2 = Polynomial::new(&[FE::new(0)]);
1039        assert_eq!(p1 * p2, Polynomial::new(&[FE::new(0)]));
1040    }
1041
1042    #[test]
1043    fn multiply_0_and_x_is_0() {
1044        let p1 = Polynomial::new(&[FE::new(0)]);
1045        let p2 = Polynomial::new(&[FE::new(0), FE::new(1)]);
1046        assert_eq!(p1 * p2, Polynomial::new(&[FE::new(0)]));
1047    }
1048
1049    #[test]
1050    fn multiply_2_by_3_is_6() {
1051        let p1 = Polynomial::new(&[FE::new(2)]);
1052        let p2 = Polynomial::new(&[FE::new(3)]);
1053        assert_eq!(p1 * p2, Polynomial::new(&[FE::new(6)]));
1054    }
1055
1056    #[test]
1057    fn multiply_2xx_3x_3_times_x_4() {
1058        let p1 = Polynomial::new(&[FE::new(3), FE::new(3), FE::new(2)]);
1059        let p2 = Polynomial::new(&[FE::new(4), FE::new(1)]);
1060        assert_eq!(
1061            p1 * p2,
1062            Polynomial::new(&[FE::new(12), FE::new(15), FE::new(11), FE::new(2)])
1063        );
1064    }
1065
1066    #[test]
1067    fn multiply_x_4_times_2xx_3x_3() {
1068        let p1 = Polynomial::new(&[FE::new(3), FE::new(3), FE::new(2)]);
1069        let p2 = Polynomial::new(&[FE::new(4), FE::new(1)]);
1070        assert_eq!(
1071            p2 * p1,
1072            Polynomial::new(&[FE::new(12), FE::new(15), FE::new(11), FE::new(2)])
1073        );
1074    }
1075
1076    #[test]
1077    fn division_works() {
1078        let p1 = Polynomial::new(&[FE::new(1), FE::new(3)]);
1079        let p2 = Polynomial::new(&[FE::new(1), FE::new(3)]);
1080        let p3 = p1.mul_with_ref(&p2);
1081        assert_eq!(p3 / p2, p1);
1082    }
1083
1084    #[test]
1085    fn division_by_zero_degree_polynomial_works() {
1086        let four = FE::new(4);
1087        let two = FE::new(2);
1088        let p1 = Polynomial::new(&[four, four]);
1089        let p2 = Polynomial::new(&[two]);
1090        assert_eq!(Polynomial::new(&[two, two]), p1 / p2);
1091    }
1092
1093    #[test]
1094    fn evaluate_constant_polynomial_returns_constant() {
1095        let three = FE::new(3);
1096        let p = Polynomial::new(&[three]);
1097        assert_eq!(p.evaluate(&FE::new(10)), three);
1098    }
1099
1100    #[test]
1101    fn evaluate_slice() {
1102        let three = FE::new(3);
1103        let p = Polynomial::new(&[three]);
1104        let ret = p.evaluate_slice(&[FE::new(10), FE::new(15)]);
1105        assert_eq!(ret, [three, three]);
1106    }
1107
1108    #[test]
1109    fn create_degree_0_new_monomial() {
1110        assert_eq!(
1111            Polynomial::new_monomial(FE::new(3), 0),
1112            Polynomial::new(&[FE::new(3)])
1113        );
1114    }
1115
1116    #[test]
1117    fn zero_poly_evals_0_in_3() {
1118        assert_eq!(
1119            Polynomial::new_monomial(FE::new(0), 0).evaluate(&FE::new(3)),
1120            FE::new(0)
1121        );
1122    }
1123
1124    #[test]
1125    fn evaluate_degree_1_new_monomial() {
1126        let two = FE::new(2);
1127        let four = FE::new(4);
1128        let p = Polynomial::new_monomial(two, 1);
1129        assert_eq!(p.evaluate(&two), four);
1130    }
1131
1132    #[test]
1133    fn evaluate_degree_2_monomyal() {
1134        let two = FE::new(2);
1135        let eight = FE::new(8);
1136        let p = Polynomial::new_monomial(two, 2);
1137        assert_eq!(p.evaluate(&two), eight);
1138    }
1139
1140    #[test]
1141    fn evaluate_3_term_polynomial() {
1142        let p = Polynomial::new(&[FE::new(3), -FE::new(2), FE::new(4)]);
1143        assert_eq!(p.evaluate(&FE::new(2)), FE::new(15));
1144    }
1145
1146    #[test]
1147    fn simple_interpolating_polynomial_by_hand_works() {
1148        let denominator = Polynomial::new(&[FE::new(1) * (FE::new(2) - FE::new(4)).inv().unwrap()]);
1149        let numerator = Polynomial::new(&[-FE::new(4), FE::new(1)]);
1150        let interpolating = numerator * denominator;
1151        assert_eq!(
1152            (FE::new(2) - FE::new(4)) * (FE::new(1) * (FE::new(2) - FE::new(4)).inv().unwrap()),
1153            FE::new(1)
1154        );
1155        assert_eq!(interpolating.evaluate(&FE::new(2)), FE::new(1));
1156        assert_eq!(interpolating.evaluate(&FE::new(4)), FE::new(0));
1157    }
1158
1159    #[test]
1160    fn interpolate_x_2_y_3() {
1161        let p = Polynomial::interpolate(&[FE::new(2)], &[FE::new(3)]).unwrap();
1162        assert_eq!(FE::new(3), p.evaluate(&FE::new(2)));
1163    }
1164
1165    #[test]
1166    fn interpolate_x_0_2_y_3_4() {
1167        let p =
1168            Polynomial::interpolate(&[FE::new(0), FE::new(2)], &[FE::new(3), FE::new(4)]).unwrap();
1169        assert_eq!(FE::new(3), p.evaluate(&FE::new(0)));
1170        assert_eq!(FE::new(4), p.evaluate(&FE::new(2)));
1171    }
1172
1173    #[test]
1174    fn interpolate_x_2_5_7_y_10_19_43() {
1175        let p = Polynomial::interpolate(
1176            &[FE::new(2), FE::new(5), FE::new(7)],
1177            &[FE::new(10), FE::new(19), FE::new(43)],
1178        )
1179        .unwrap();
1180
1181        assert_eq!(FE::new(10), p.evaluate(&FE::new(2)));
1182        assert_eq!(FE::new(19), p.evaluate(&FE::new(5)));
1183        assert_eq!(FE::new(43), p.evaluate(&FE::new(7)));
1184    }
1185
1186    #[test]
1187    fn interpolate_x_0_0_y_1_1() {
1188        let p =
1189            Polynomial::interpolate(&[FE::new(0), FE::new(1)], &[FE::new(0), FE::new(1)]).unwrap();
1190
1191        assert_eq!(FE::new(0), p.evaluate(&FE::new(0)));
1192        assert_eq!(FE::new(1), p.evaluate(&FE::new(1)));
1193    }
1194
1195    #[test]
1196    fn interpolate_x_0_y_0() {
1197        let p = Polynomial::interpolate(&[FE::new(0)], &[FE::new(0)]).unwrap();
1198        assert_eq!(FE::new(0), p.evaluate(&FE::new(0)));
1199    }
1200
1201    #[test]
1202    fn composition_works() {
1203        let p = Polynomial::new(&[FE::new(0), FE::new(2)]);
1204        let q = Polynomial::new(&[FE::new(0), FE::new(0), FE::new(1)]);
1205        assert_eq!(
1206            compose(&p, &q),
1207            Polynomial::new(&[FE::new(0), FE::new(0), FE::new(2)])
1208        );
1209    }
1210
1211    #[test]
1212    fn break_in_parts() {
1213        // p = 3 X^3 + X^2 + 2X + 1
1214        let p = Polynomial::new(&[FE::new(1), FE::new(2), FE::new(1), FE::new(3)]);
1215        let p0_expected = Polynomial::new(&[FE::new(1), FE::new(1)]);
1216        let p1_expected = Polynomial::new(&[FE::new(2), FE::new(3)]);
1217        let parts = p.break_in_parts(2);
1218        assert_eq!(parts.len(), 2);
1219        let p0 = &parts[0];
1220        let p1 = &parts[1];
1221        assert_eq!(p0, &p0_expected);
1222        assert_eq!(p1, &p1_expected);
1223    }
1224
1225    use proptest::prelude::*;
1226    proptest! {
1227        #[test]
1228        fn ruffini_inplace_equals_division(p in any::<Vec<u64>>(), b in any::<u64>()) {
1229            let p: Vec<_> = p.into_iter().map(FE::from).collect();
1230            let mut p = Polynomial::new(&p);
1231            let b = FE::from(b);
1232
1233            let p_ref = p.clone();
1234            let m = Polynomial::new_monomial(FE::one(), 1) - b;
1235
1236            p.ruffini_division_inplace(&b);
1237            prop_assert_eq!(p, p_ref / m);
1238        }
1239    }
1240
1241    proptest! {
1242        #[test]
1243        fn ruffini_inplace_equals_ruffini(p in any::<Vec<u64>>(), b in any::<u64>()) {
1244            let p: Vec<_> = p.into_iter().map(FE::from).collect();
1245            let mut p = Polynomial::new(&p);
1246            let b = FE::from(b);
1247            let q = p.ruffini_division(&b);
1248            p.ruffini_division_inplace(&b);
1249            prop_assert_eq!(q, p);
1250        }
1251    }
1252    #[test]
1253    fn test_xgcd() {
1254        // Case 1: Simple polynomials
1255        let p1 = Polynomial::new(&[FE::new(1), FE::new(0), FE::new(1)]); // x^2 + 1
1256        let p2 = Polynomial::new(&[FE::new(1), FE::new(1)]); // x + 1
1257        let (a, b, g) = p1.xgcd(&p2);
1258        // Check that a * p1 + b * p2 = g
1259        let lhs = a.mul_with_ref(&p1) + b.mul_with_ref(&p2);
1260        assert_eq!(a, Polynomial::new(&[FE::new(12)]));
1261        assert_eq!(b, Polynomial::new(&[FE::new(12), FE::new(11)]));
1262        assert_eq!(lhs, g);
1263        assert_eq!(g, Polynomial::new(&[FE::new(1)]));
1264
1265        // x^2-1 :
1266        let p3 = Polynomial::new(&[FE::new(ORDER - 1), FE::new(0), FE::new(1)]);
1267        // x^3-x = x(x^2-1)
1268        let p4 = Polynomial::new(&[FE::new(0), FE::new(ORDER - 1), FE::new(0), FE::new(1)]);
1269        let (a, b, g) = p3.xgcd(&p4);
1270
1271        let lhs = a.mul_with_ref(&p3) + b.mul_with_ref(&p4);
1272        assert_eq!(a, Polynomial::new(&[FE::new(1)]));
1273        assert_eq!(b, Polynomial::zero());
1274        assert_eq!(lhs, g);
1275        assert_eq!(g, p3);
1276    }
1277
1278    #[test]
1279    fn test_differentiate() {
1280        // 3x^2 + 2x + 42
1281        let px = Polynomial::new(&[FE::new(42), FE::new(2), FE::new(3)]);
1282        // 6x + 2
1283        let dpdx = px.differentiate();
1284        assert_eq!(dpdx, Polynomial::new(&[FE::new(2), FE::new(6)]));
1285
1286        // 128
1287        let px = Polynomial::new(&[FE::new(128)]);
1288        // 0
1289        let dpdx = px.differentiate();
1290        assert_eq!(dpdx, Polynomial::new(&[FE::new(0)]));
1291    }
1292
1293    #[test]
1294    fn test_reverse() {
1295        let p = Polynomial::new(&[FE::new(3), FE::new(2), FE::new(1)]);
1296        assert_eq!(
1297            p.reverse(3),
1298            Polynomial::new(&[FE::new(0), FE::new(1), FE::new(2), FE::new(3)])
1299        );
1300    }
1301
1302    #[test]
1303    fn test_truncate() {
1304        let p = Polynomial::new(&[FE::new(3), FE::new(2), FE::new(1)]);
1305        assert_eq!(p.truncate(2), Polynomial::new(&[FE::new(3), FE::new(2)]));
1306    }
1307
1308    #[test]
1309    fn test_print_as_sage_poly() {
1310        let p = Polynomial::new(&[FE::new(1), FE::new(2), FE::new(3)]);
1311        assert_eq!(p.print_as_sage_poly(None), "3*x^2 + 2*x + 1");
1312    }
1313}
lambdaworks_math/polynomial/mod.rs

lambdaworks_math/polynomial/
mod.rs
