snarkify / sirius

A Plonkish folding framework for Incrementally Verifiable Computation (IVC).
MIT License
106 stars 15 forks source link

feat(poly): impl fft/ifft methods #258

Closed cyphersnake closed 1 month ago

cyphersnake commented 1 month ago

The fft (Fast Fourier Transform) and ifft (Inverse Fast Fourier Transform) are algorithms used to compute the discrete Fourier transform (DFT) and its inverse efficiently

Also within this task we have to realize finding a cyclic group of a certain size

// axiom halo2_proofs:src/poly/domain.rs
pub struct EvaluationDomain<F: Field> {
      n: u64, //n =2^k
      k: u32, 
      omega: F,  // fft {w,w^2,w^4,...,1}
      omega_inv: F, // ifft  {w',w'^2,w'^4,...,1}
      ifft_divisor: F,

      // not sure
      t_evaluations: Vec<F>,
      // Recursive stuff
      // not sure
      fft_data: HashMap<usize, FFTData<F>>,
  }

Implement or import fft/ifft methods which will be used later

cyphersnake commented 1 month ago

https://github.com/snarkify/halo2-axiom/blob/73c81e2f0332a3d79475dc861138e96cc91400b5/halo2_proofs/src/poly/domain.rs#L783-L820