`fft_small_mulmod_satisfies_bounds`

Synopsis#include <flint/fft_small.h>

int fft_small_mulmod_satisfies_bounds(ulong n)source

Returns whether the floating-point modular multiplication modulo $n$ maps products in $(-2n^2, 2n^2)$ into $(-n, n)$ and products in $(-4n^2, 4n^2)$ into $(-3n/2, 3n/2)$ , by a bound that uses the actual error of the double $1/n$ . Every prime below $2^{49}$ passes, and about one 50-bit prime in 900 fails.

AlgorithmModular arithmetic in floating pointExact arithmetic modulo

n < 2^{50}

on integers stored in doubles, using a precomputed

1/n

and a fused multiply-add to split the product, as in FLINT's small-prime FFT.

Cite this page

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

@misc{flint-doc-fft-small-fft-small-mulmod-satisfies-bounds,
  author       = {{The FLINT team}},
  title        = {{fft\_small\_mulmod\_satisfies\_bounds (fft\_small.h)}},
  howpublished = {FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev},
  year         = {2026},
  url          = {https://flintlib.org/doc/fft_small/fft_small_mulmod_satisfies_bounds.html},
  note         = {Generated 2026-11-02}
}

Edit this page · PDF version · Built with fdoc from 0a4634bf95