barrett

クラス · internal/internal_math.hpp

struct barrett;

概要

Fast modular multiplication by barrett reduction Reference: https://en.wikipedia.org/wiki/Barrett_reduction NOTE: reconsider after Ice Lake NOTE: 法は 32bit (unsigned int) 前提。64bit 法には montgomery を使う

関連項目

• montgomery — Montgomery modular multiplication
• is_SPRP64 — given $2 \le n, a < 2^{64}$, $a$ prime, check whether $n$ is $a$-SPRP without 2,3,5,13,19,73,193,407521,299210837
• primitive_root_constexpr — Compile time primitive root