primitive_root

関数 · 素因数分解

std::uint64_t primitive_root(std::uint64_t p);

概要

原始根

パラメータ

戻り値

p の最小の原始根

計算量

• $p-1$ の素因数分解は期待 $O(p^{1/4}\log p)$、各候補の検査は $O(\omega(p-1)\log p)$

関連項目

• factorize — 素因数分解
• number_of_divisors — 素因数列 v から元の整数の正の約数個数を返す