geam1113’s diary

主にAtcoderのコンテストの備忘録を書きます。AtCoder緑と水色を行ったり来たりしています。

離散対数問題:Baby-step giant-stepのアルゴリズム

はじめに

離散対数問題についての問題がAtCoder Beginner Contestで出題され、色々と調べてみたので、その内容をメモします。

 

離散対数問題

X^k \equiv Y\ mod\ Mを満たす最小の整数kを求める問題です。

これを求めるアルゴリズムにBaby-step giant-stepがあります。

 

Baby-step Giant-stepのアルゴリズム

まず、アルゴリズム概要を記載します。

 

m=\lceil \sqrt{M} \rceil とする。

kはmで割った商iと余りjによって、k=im+jと表すことができる。

0 \leq i \lt m,\ 0\leq j \lt mなので、全探索するとO(m^2)となる。

ここで、

a^{im+j} \equiv Y\ mod \ M

を変形して、

a^{j} \equiv Y(X^{-m})^{i}\ mod \ M

とすると、左辺はiに依存せず一定となる。

そのため、予めa^0,a^1,...,a^{m-1}をハッシュマップ等に記録しておくことで、各iについてO(1)で該当のjがあるか判定できるようになり、全体としてO(m)で探索できる。

 

考え方としては、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

離散対数問題 | libalgo