is_SPRP64

関数 · internal/internal_math.hpp

constexpr bool is_SPRP64(const montgomery &m, std::uint64_t a);

概要

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

関連項目

• 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
• primitive_root_constexpr — Compile time primitive root