discrete_log_core

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

template <class X, class S, class Op, class Act, class Key>
std::int64_t discrete_log_core(X x, S s, const S &t, const X &id, Op op, Act act, Key to_key, std::int64_t lb, std::int64_t ub);

概要

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

作用素 x（演算 op で合成、単位元 id）を状態に作用 act させ、 $x^n$ を s に作用させた結果が t と一致する最小の n を $[lb, ub)$ から返す。 群とは限らず逆元を仮定しないため、giant-step での一致は候補にすぎず、 区間を線形走査して実際の解を確認する。線形走査が 2 回空振りしたら解なしと判定する。 to_key は到達しうる状態上で単射（衝突しない完全キー）であることを呼び出し側が保証する。

戻り値

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

計算量

• $N = ub - lb$ として期待 $O(\sqrt N)$

備考

• $N = ub - lb$、ブロック幅 $\sqrt N$ で baby-step・giant-step を回すため全体 $O(\sqrt N)$。 作用 act は $O(\sqrt N)$ 回（baby-step $\sqrt N$ + giant-step $\sqrt N$ + 線形走査は高々 2 ブロックで $2\sqrt N$）、合成 op は二分累乗の $O(\log N)$ 回。

関連項目

• discrete_log_acted — モノイド作用に関する離散対数問題
• discrete_log_monoid — モノイド M における離散対数 $a^n = b$