Function winter_math::polynom::syn_div_roots_in_place

pub fn syn_div_roots_in_place<E>(p: &mut [E], roots: &[E])
where
    E: FieldElement,

Divides a polynomial by a polynomial given its roots and saves the result into the original polynomial.

Specifically, divides polynomial p by polynomial \prod_{i = 1}^m (x - x_i) using synthetic division method and saves the result into p. If the polynomials don’t divide evenly, the remainder is ignored. Polynomial p is expected to be in the coefficient form, and the result will be in coefficient form as well.

This function is significantly faster than the generic polynom::div() function, using the coefficients of the divisor.

Panics

Panics if:

• roots.len() is zero;
• p.len() is smaller than or equal to roots.len().

Examples

// p(x) = x^3 - 7 * x + 6
let mut p = [
    BaseElement::new(6),
    -BaseElement::new(7),
    BaseElement::new(0),
    BaseElement::new(1),
];

// divide by (x - 1) * (x - 2)
let zeros = vec![BaseElement::new(1), BaseElement::new(2)];
syn_div_roots_in_place(&mut p, &zeros);

// expected result = x + 3
let expected = [
    BaseElement::new(3),
    BaseElement::new(1),
    BaseElement::ZERO,
    BaseElement::ZERO,
];

assert_eq!(expected, p);