Function winter_math::fft::infer_degree

pub fn infer_degree<B, E>(evaluations: &[E], domain_offset: B) -> usize
where
    B: StarkField,
    E: FieldElement<BaseField = B>,

Returns the degree of a polynomial implied by the provided evaluations.

The polynomial is assumed to be evaluated over a multiplicative subgroup of length equal to the length of evaluations in the field defined by B type parameter and shifted by the domain_offset.

The shifted domain is defined as the original domain with every element multiplied by the domain_offset.

The degree is determined by first interpolating the polynomial into a coefficient form using FFT-based polynomial interpolation, and then finding the first non-zero coefficient.

Panics

Panics if

• Length of evaluations is not a power of two.
• Field specified by B does not contain a multiplicative subgroup of size domain_size.
• domain_offset is ZERO.

Examples

let offset = BaseElement::GENERATOR;
// p(x) = x^2 + 1
let p = [
    BaseElement::new(1),
    BaseElement::ZERO,
    BaseElement::new(1),
    BaseElement::ZERO,
];

let g = BaseElement::get_root_of_unity(p.len().ilog2());
let domain = get_power_series(g, p.len());
let shifted_domain = domain.iter().map(|&x| x * offset).collect::<Vec<_>>();
let evaluations = polynom::eval_many(&p, &shifted_domain);

assert_eq!(2, infer_degree(&evaluations, offset));