discrete_log_acted

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

template <class M, class U, class Key>
requires acts_on<M, U>
std::int64_t discrete_log_acted(const typename M::value_type &x, U s, U t, Key to_key, std::int64_t lb, std::int64_t ub);

概要

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

作用素モノイド M（合成 op・単位元 id・作用 f）の元 x について、 $x^n$ を状態 s に作用させた結果が t となる最小の n を $[lb, ub)$ から返す。 逆元を仮定しないモノイド作用で動く（標準的な離散対数・関数反復の合成などを含む）。

テンプレートパラメータ

戻り値

最小の n。存在しなければ -1。

計算量

• $N = ub - lb$ として $O(\sqrt N)$。内訳はモノイド作用 f が $O(\sqrt N)$ 回、 モノイド合成 op が $O(\log N)$ 回、キー関数 to_key が $O(\sqrt N)$ 回（ハッシュ集合操作込み）。

関連項目

• discrete_log_core — モノイド作用に関する離散対数問題の本体（Baby-step Giant-step）
• discrete_log_monoid — モノイド M における離散対数 $a^n = b$