fft_small_mulmod_satisfies_bounds
Synopsis
#include <flint/fft_small.h>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-10-20).
@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-10-20}
}