離散対数問題:Baby-step giant-stepのアルゴリズム
はじめに
離散対数問題についての問題がAtCoder Beginner Contestで出題され、色々と調べてみたので、その内容をメモします。
離散対数問題
を満たす最小の整数kを求める問題です。
これを求めるアルゴリズムにBaby-step giant-stepがあります。
Baby-step Giant-stepのアルゴリズム
まず、アルゴリズム概要を記載します。
とする。
kはmで割った商iと余りjによって、と表すことができる。
なので、全探索するととなる。
ここで、
を変形して、
とすると、左辺はiに依存せず一定となる。
そのため、予めをハッシュマップ等に記録しておくことで、各iについてで該当のjがあるか判定できるようになり、全体としてで探索できる。
考え方としては、m個の要素を含むm個の区画に分割し、区画内にYが存在するかを調べるというものです。
何個目の区画にあるか順番に調べていく部分がGiant-step、区画内で何番目にあるかを調べるのがBaby-stepに該当すると考えられます。
適用条件
Baby-step giant-stepでは、逆元が必要です。
逆元が存在するための条件は、XとMが互いに素であることです。
互いに素でない場合どうするかですが、下記サイトにその考え方がありました。
https://divinejk.hatenablog.com/entry/2021/02/07/133155
テールとサイクルに分けて、サイクルをBaby-step giant-stepで探索すれば良いとのことでした。
アルゴリズムとは直接関係ないですが、上記サイトによれば、サイクルのサイズはオイラーのトーシェント関数の約数になるということでした。
これは、ARCのこの問題の解説の証明になっています。
実装
ABCで提出したコード(正の整数バージョン):■
Library Checker(非負整数バージョン):■
改変したBaby-step giant-stepを使用したABCのコード:■ Twitterで言及されていた別解です。
その他参考サイト
Baby-step Giant-stepアルゴリズムを解釈する
Baby-step giant-step - Wikipedia