discrete_log_monoid

関数 · モノイド作用に関する離散対数問題

template <class M, class Key>
requires monoid<M>
std::int64_t discrete_log_monoid(typename M::value_type a, typename M::value_type b, Key to_key, std::int64_t lb, std::int64_t ub);

概要

モノイド M における離散対数 $a^n = b$

作用を左からの合成 op とみなした特殊形。群の log_a b を含む。

テンプレートパラメータ

戻り値

最小の n（$[lb, ub)$）。存在しなければ -1。

計算量

• $N = ub - lb$ として $O(\sqrt N)$（合成 op を $O(\sqrt N)$ 回・二分累乗で $O(\log N)$ 回）。

関連項目

• discrete_log_core — モノイド作用に関する離散対数問題の本体（Baby-step Giant-step）
• discrete_log_acted — モノイド作用に関する離散対数問題