montgomery

クラス · internal/internal_math.hpp

struct montgomery;

概要

Montgomery modular multiplication

関連項目

• 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 を使う
• 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

参照

• https://rsk0315.hatenablog.com/entry/2022/11/27/060616