# fft_small.h – FFT modulo word-size primes

This module currently requires building FLINT with support for AVX2 or NEON instructions.

## Integer multiplication

type mpn_ctx_struct
type mpn_ctx_t

  Context object for multiplications allowing non-FFT moduli. The structure contains FFT context objects for multiple FFT primes (currently 8) together with tables for Chinese remaindering.

void mpn_ctx_init(mpn_ctx_t R, ulong p)

  Initialize multiplication context object with initial prime `p`.

void mpn_ctx_clear(mpn_ctx_t R)

  Free memory allocated by the context object.

mpn_ctx_struct *get_default_mpn_ctx(void)

  Return a pointer to a cached thread-local context object used by default for multiplications. Calling `flint_cleanup()` or `flint_cleanup_master()` frees the cache.

void mpn_ctx_mpn_mul(mpn_ctx_t R, ulong *r1, const ulong *i1, ulong n1, const ulong *i2, ulong n2)
void mpn_mul_default_mpn_ctx(nn_ptr r1, nn_srcptr i1, slong n1, nn_srcptr i2, slong n2)

  Writes to `r1` the product of the integers `(i1, n1)` and `(i2, n2)`. Assumes that \(n_1 \ge n_2 \ge 1\), respectively using a given context object `R` or the default thread-local object.

## Polynomial arithmetic

void _nmod_poly_mul_mid_mpn_ctx(ulong *z, ulong zl, ulong zh, const ulong *a, ulong an, const ulong *b, ulong bn, nmod_t mod, mpn_ctx_t R)
void _nmod_poly_mul_mid_default_mpn_ctx(nn_ptr res, slong zl, slong zh, nn_srcptr a, slong an, nn_srcptr b, slong bn, nmod_t mod)

  Writes to `z` the middle product containing coefficients in the range \([zl, zh)\) of the product of the polynomials `(a, an)` and `(b, bn)`, respectively using a given context object `R` or the default thread-local object. Assumes that \(an \ge bn \ge 1\).

int _fmpz_poly_mul_mid_mpn_ctx(fmpz *z, ulong zl, ulong zh, const fmpz *a, ulong an, const fmpz *b, ulong bn, mpn_ctx_t R)
int _fmpz_poly_mul_mid_default_mpn_ctx(fmpz *z, ulong zl, ulong zh, const fmpz *a, ulong an, const fmpz *b, ulong bn)

  Like the `nmod` functions. Performs the multiplication and returns 1 if there are sufficiently many primes `R` to compute the result; otherwise returns 0 without touching the output.

void _nmod_poly_divrem_mpn_ctx(ulong *q, ulong *r, const ulong *a, ulong an, const ulong *b, ulong bn, nmod_t mod, mpn_ctx_t R)

  Polynomial division with remainder.

## Preconditioned polynomial arithmetic

type mul_precomp_struct

void _mul_precomp_init(mul_precomp_struct *M, const ulong *b, ulong bn, ulong btrunc, ulong depth, nmod_t mod, mpn_ctx_t R)
void _mul_precomp_clear(mul_precomp_struct *M)

  Represents `(b, bn)` in transformed form for preconditioned multiplication.

int _nmod_poly_mul_mid_precomp(ulong *z, ulong zl, ulong zh, const ulong *a, ulong an, mul_precomp_struct *M, nmod_t mod, mpn_ctx_t R)

  Polynomial multiplication given a precomputed transform `M`. Returns 1 if successful, 0 if the precomputed transform is too short.

type nmod_poly_divrem_precomp_struct

void _nmod_poly_divrem_precomp_init(nmod_poly_divrem_precomp_struct *M, const ulong *b, ulong bn, ulong Bn, nmod_t mod, mpn_ctx_t R)
void _nmod_poly_divrem_precomp_clear(nmod_poly_divrem_precomp_struct *M)

  Represents `(b, bn)` and its inverse in transformed form for preconditioned multiplication.

int _nmod_poly_divrem_precomp(ulong *q, ulong *r, const ulong *a, ulong an, nmod_poly_divrem_precomp_struct *M, nmod_t mod, mpn_ctx_t R)

  Polynomial multiplication given a precomputed transform `M`. Returns 1 if successful, 0 if the precomputed transform is too short.