FLINT3.7.0-dev
/

n_mod_barrett, n_mod_barrett_lazy

Synopsis#include <flint/ulong_extras.h>
ulong n_mod_barrett(ulong x, ulong n, ulong npre)source
ulong n_mod_barrett_lazy(ulong x, ulong n, ulong npre)source

Returns x \bmod n using Barrett reduction [Bar1987]. The lazy version returns a residue in [0, 2n) instead of [0, n). No restrictions on x. Both support n = 1 if npre is set to UWORD_MAX.

References#

  • [Bar1987] P. Barrett, "Implementing the Rivest Shamir and Adleman public key encryption algorithm on a standard digital signal processor", Advances in Cryptology – CRYPTO '86, LNCS 263 (1987), 311–323
Cite this page

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