Module convolution 

Contains convolution::ConvolutionAlgorithm, an abstraction for algorithms for computing convolutions, together with various implementations.

Modules

fft

Contains an implementation of computing convolutions using complex floating-point FFTs.

generic_testsgeneric_tests

karatsuba

Contains an optimized implementation of Karatsuba’s for computing convolutions

ntt

Contains an implementation of computing convolutions using NTTs, i.e. FFTs over a finite field that has suitable roots of unity.

rns

Contains an implementation of computing convolutions by considering them modulo various primes that are either smaller or allow for suitable roots of unity.

Structs

KaratsubaAlgorithm

Implementation of convolutions that uses Karatsuba’s algorithm with a threshold defined by KaratsubaHint.

Constants

STANDARD_CONVOLUTION

Good default algorithm for computing convolutions, using Karatsuba’s algorithm with a threshold defined by KaratsubaHint.

Traits

ConvolutionAlgorithm

Trait for objects that can compute a convolution over some ring.

KaratsubaHintunstable-enable

Trait to allow rings to customize the parameters with which KaratsubaAlgorithm will compute convolutions over the ring.