FLINT3.7.0-dev
/

fft_small_ifft_tr_nmod, fft_small_fft_tr

Synopsis#include <flint/fft_small.h>
void fft_small_ifft_tr_nmod(fft_small_op_t X, const ulong * a, ulong an, nmod_t mod, const fft_small_plan_t P)source
void fft_small_fft_tr(fft_small_op_t X, ulong itrunc, const fft_small_plan_t P)source

The transposes of fft_small_ifft and fft_small_fft_nmod, for transposed products. fft_small_ifft_tr_nmod converts (a, a_n), read as zero-padded to P->ztrunc coefficients (so a_n \le P->ztrunc), and applies the transposed inverse transform; X is then in the primal domain. fft_small_fft_tr applies the transposed forward transform with truncation itrunc \le P->ztrunc in place to an operand in the product domain, whose first itrunc slots can then be exported.

For a plan of the window [0, z_n) of a convolution of length a_n + z_n - 1, with B the transform of (a, a_n) made by fft_small_fft_nmod, the calls

fft_small_ifft_tr_nmod(X, v, vn, mod, P); fft_small_op_mul(X, X, B, P); fft_small_fft_tr(X, ztrunc, P); fft_small_export_nmod_range(z, X, 0, zn, mod, P);

compute the transposed product of _nmod_poly_mul_tr_mpn_ctx, where ztrunc is the truncation for z_n (_fft_small_op_trunc). The normalisation is applied by the pointwise product, as for ordinary products. The primes are processed in parallel as in fft_small_fft_nmod and fft_small_ifft. See Transposed products.

Guides#

Cite this page

The FLINT team, “fft_small_ifft_tr_nmod, fft_small_fft_tr (fft_small.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/fft_small/fft_small_ifft_tr_nmod.html (generated 2026-10-20).