Struct FFTree

pub struct FFTree<F: Field> {

    pub f: BinaryTree<F>,
    pub recombine_matrices: BinaryTree<Mat2x2<F>>,
    pub decompose_matrices: BinaryTree<Mat2x2<F>>,
    pub rational_maps: Vec<RationalMap<F>>,
    pub subtree: Option<Box<Self>>,
    pub xnn_s: Vec<F>,
    pub xnn_s_inv: Vec<F>,
    pub z0_s1: Vec<F>,
    pub z1_s0: Vec<F>,
    pub z0_inv_s1: Vec<F>,
    pub z1_inv_s0: Vec<F>,
    pub z0z0_rem_xnn_s: Vec<F>,
    pub z1z1_rem_xnn_s: Vec<F>,
}

Fields

f: BinaryTree<F>

recombine_matrices: BinaryTree<Mat2x2<F>>

decompose_matrices: BinaryTree<Mat2x2<F>>

rational_maps: Vec<RationalMap<F>>

subtree: Option<Box<Self>>

xnn_s: Vec<F>

xnn_s_inv: Vec<F>

z0_s1: Vec<F>

z1_s0: Vec<F>

z0_inv_s1: Vec<F>

z1_inv_s0: Vec<F>

z0z0_rem_xnn_s: Vec<F>

z1z1_rem_xnn_s: Vec<F>

Implementations

impl<F: Field> FFTree<F>

pub fn new(leaves: Vec<F>, rational_maps: Vec<RationalMap<F>>) -> Self

pub fn extend(&self, evals: &[F], moiety: Moiety) -> Vec<F>

Extends evals on the chosen moiety

pub fn mextend(&self, evals: &[F], moiety: Moiety) -> Vec<F>

Extends special monic polynomials

pub fn enter(&self, coeffs: &[F]) -> Vec<F>

Converts from coefficient to evaluation representation of a polynomial

pub fn degree(&self, evals: &[F]) -> usize

Evaluates the degree of an evaluation table in O(n log n)

pub fn exit_impl(&self, evals: &[F]) -> Vec<F>

pub fn exit(&self, evals: &[F]) -> Vec<F>

Converts from evaluation to coefficient representation of a polynomial

pub fn redc_z0(&self, evals: &[F], a: &[F]) -> Vec<F>

Computes <P(X)*Z_0(x)^(-1) mod a ≀ S> Z_0 is the vanishing polynomial of S_0 a must be a polynomial of max degree n/2 having no zeroes in S_0

pub fn redc_z1(&self, evals: &[F], a: &[F]) -> Vec<F>

Computes <P(X)*Z_1(x)^(-1) mod A ≀ S> Z_1 is the vanishing polynomial of S_1 A must be a polynomial of max degree n/2 having no zeroes in S_1

pub fn modular_reduce(&self, evals: &[F], a: &[F], c: &[F]) -> Vec<F>

Computes MOD algorithm a must be a polynomial of max degree n/2 having no zeroes in S_0 c must be the evaluation table <Z_0^2 mod a ≀ S>

pub fn vanish(&self, vanish_domain: &[F]) -> Vec<F>

Returns an evaluation of the vanishing polynomial Z(x) = ∏ (x - a_i) Runtime O(n log^2 n). vanishi_domain = [a_0, a_1, ..., a_(n - 1)] Section 7.1 https://arxiv.org/pdf/2107.08473.pdf

pub fn subtree_with_size(&self, n: usize) -> &Self

Returns a FFTree with n leaves

Trait Implementations

impl<F: Field> CanonicalDeserialize for FFTree<F>

fn deserialize_with_mode<R: Read>( reader: R, compress: Compress, validate: Validate, ) -> Result<Self, SerializationError>

The general deserialize method that takes in customization flags.

fn deserialize_compressed<R>(reader: R) -> Result<Self, SerializationError>

where R: Read,

fn deserialize_compressed_unchecked<R>( reader: R, ) -> Result<Self, SerializationError>

where R: Read,

fn deserialize_uncompressed<R>(reader: R) -> Result<Self, SerializationError>

where R: Read,

fn deserialize_uncompressed_unchecked<R>( reader: R, ) -> Result<Self, SerializationError>

where R: Read,

impl<F: Field> CanonicalSerialize for FFTree<F>

fn serialize_with_mode<W: Write>( &self, writer: W, compress: Compress, ) -> Result<(), SerializationError>

The general serialize method that takes in customization flags.

fn serialized_size(&self, compress: Compress) -> usize

fn serialize_compressed<W>(&self, writer: W) -> Result<(), SerializationError>

where W: Write,

fn compressed_size(&self) -> usize

fn serialize_uncompressed<W>(&self, writer: W) -> Result<(), SerializationError>

where W: Write,

fn uncompressed_size(&self) -> usize

impl<F: Clone + Field> Clone for FFTree<F>

fn clone(&self) -> FFTree<F>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<F: Debug + Field> Debug for FFTree<F>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<F: Field> Valid for FFTree<F>

fn check(&self) -> Result<(), SerializationError>

fn batch_check<'a>( batch: impl Iterator<Item = &'a Self> + Send, ) -> Result<(), SerializationError>

where Self: 'a,