galois-fft-0.1.0: FFTs over finite fields

Safe HaskellNone



Discrete Fourier transforms for polynomial interpolation



type CoeffVec f = [f] Source #

Polynomial represented as a coefficient vector, little-endian

dftNaive Source #


:: Num f 
=> f

principal 2^k-th root of unity

-> CoeffVec f

polynomial coefficients, length should be 2^k for some k

-> DFT f 

Naive discrete Fourier transformation performed by evaluating the polynomial at the appropriate roots of unity.

fft Source #


:: GaloisField k 
=> (Int -> k)

function that gives for input n the principal (2^n)-th root of unity

-> CoeffVec k

length should be n

-> DFT k 

Fast Fourier transformation.

fftMult :: GaloisField k => (Int -> k) -> CoeffVec k -> CoeffVec k -> CoeffVec k Source #

Multiply polynomials using FFT

fftTargetPoly :: GaloisField k => (Int -> k) -> Int -> VPoly k Source #

interpolate :: GaloisField k => (Int -> k) -> [k] -> VPoly k Source #

Create a polynomial that goes through the given values.

inverseDft :: GaloisField k => (Int -> k) -> DFT k -> CoeffVec k Source #

Inverse discrete Fourier transformation, uses FFT.