さて、ここからが本題です。 $X^{K}\equiv Y\bmod M$ で、 $X$ と $M$ が互いに素とは限らない一般の場合の離散対数問題を解きます。

実験

$A$ から $AX\bmod M$ の向きに辺を結んでできた有向グラフを考えます。鳩の巣原理より、どのような $X$ についても、少なくとも $M$ 乗するとより小さい指数乗の値に戻ることがわかるので、いつかは同じ頂点に戻ってきます。この巡回する部分を「サイクル」と呼ぶことにします。また、サイクルに含まれない部分を「テール」と呼ぶことにします。いくつかの $M$ について、 $X^{k}$ がどのようになるか見てみたいと思います。

mod 10

$M$ の素因数分解	$\varphi(M)$	$\varphi(M)$ の約数
$2\times 5$	$4$	$\{1, 2, 4\}$

$X$	サイクルの長さ	テールの長さ
0	1	1
1	1	0
2	4	1
3	4	0
4	2	1
5	1	1
6	1	1
7	4	0
8	4	1
9	2	0

f:id:DivineJK:20210204135707p:plain — mod 10でのふるまい

mod 8

$M$ の素因数分解	$\varphi(M)$	$\varphi(M)$ の約数
$2^{3}$	$4$	$\{1, 2, 4\}$

$X$	サイクルの長さ	テールの長さ
0	1	1
1	1	0
2	1	3
3	2	0
4	1	2
5	2	0
6	1	3
7	2	0

f:id:DivineJK:20210204141617p:plain — mod 8でのふるまい

mod 30

$M$ の素因数分解	$\varphi(M)$	$\varphi(M)$ の約数
$2\times 3\times 5$	$8$	$\{1, 2, 4, 8\}$

$X$	サイクルの長さ	テールの長さ
0	1	1
1	1	0
2	4	1
3	4	1
4	2	1
5	2	1
6	1	1
7	4	0
8	4	1
9	2	0
10	1	1
11	2	0
12	4	1
13	4	0
14	2	1
15	1	1
16	1	1
17	4	0
18	4	1
19	2	0
20	1	1
21	1	1
22	4	1
23	4	0
24	2	1
25	1	1
26	2	1
27	4	1
28	4	1
29	2	0

f:id:DivineJK:20210204142358p:plain — mod 30でのふるまい

mod 12

$M$ の素因数分解	$\varphi(M)$	$\varphi(M)$ の約数
$2^{2}\times 3$	$4$	$\{1, 2, 4\}$

$X$	サイクルの長さ	テールの長さ
0	1	1
1	1	0
2	2	2
3	2	1
4	1	1
5	2	0
6	1	2
7	2	0
8	1	1
9	1	1
10	1	2
11	2	0

f:id:DivineJK:20210205180500p:plain — mod 12でのふるまい

予想

以上の結果から、いくつかの予想ができます。

$X$ の素因数分解が $X = p _ 1^{e _ 1}\times p _ 2^{e _ 2}\times\cdots\times p _ m^{e _ m}$ であったとする。すべての $i(1\le i \le m)$ について、 $X^{k}$ の素因数分解における $p _ i$ の指数が $M$ のそれ以上であれば、 $X^{k} \bmod M$ はサイクルに含まれる。そうでなければ、テールに含まれる。
サイクルの長さは $\varphi(M)$ の約数である。
サイクルに含まれる数と $M$ との最大公約数は全て等しい。

証明

前提

$\mathrm{gcd}(A, B) = \mathrm{gcd}(A\%B, B)$
$\mathrm{gcd}(A, B) = 1 \Rightarrow \varphi(AB) = \varphi(A)\varphi(B)$

1. と2. の証明

$X$ を素因数分解して現れる全ての素数について、 $M$ に含まれるものをすべて掛け合わせたものを $P$ とし、 $M' = M / P$ とします。累乗の計算によって素数の種類数は変化しないので、 $P$ と $M'$ は $X$ の何乗かに依存しません。

予想1. での仮定から、 $X^{k}\equiv 0 \bmod P$ です。よって、任意の非負整数 $l$ に対して $X^{k+l}\equiv X^{k} \equiv 0 \bmod P$ です。

また、 $M'$ の定義より、 $X$ と $M'$ は互いに素です。よって、フェルマーの小定理から $X^{\varphi(M')}\equiv 1\bmod M'$ が成り立ちます。両辺に $X^{k}$ を掛け合わせて、 $X^{k+\varphi(M')}\equiv X^{k}\bmod M'$ を得ます。

以上より、中国剰余定理を用いることで $X^{k+\varphi(M')}\equiv X^{k}\bmod M$ であることが示されました。さらに、予想2. のより強い主張として、「サイクルの長さは $\varphi(M')$ の約数である。」が得られました。

また、ある $i(1\le i \le m)$ について、 $X^{k}$ の素因数分解における $p _ i$ の指数が $M$ のそれ未満であるときを考えてみます。このとき、 $X^{k}$ は $P$ で割り切れないためサイクル内のどの要素とも一致しません。よって、サイクルには含まれません。そして、 $X$ を掛けていくことで一度サイクルに入ってしまうとそれ以降はサイクルから抜けることはありません。よってこのとき、 $X^{k}$ はテールに含まれます。

3. の証明

先程の証明の $M', P$ を引き継ぎます。サイクルに含まれる任意の要素 $A$ について、 $A\equiv 0 \bmod P$ であり、 $A$ と $M'$ は互いに素です。よって、 $\mathrm{gcd}(A, M) = P$ です。

実装への考察

テールの部分を別に調べて、そこで解が見つかれば終了、そうでなければサイクルをBSGSの要領で調べれば良さそうです。その際、BSGSで見つかった解にはテールの長さを足す必要があります。

テールの長さ

$X$ の素因数分解を $X = p _ 1^{e _ 1}\times p _ 2^{e _ 2}\times\cdots\times p _ m^{e _ m}$ とします。また、 $P = p _ 1^{f _ 1}\times p _ 2^{f _ 2}\times\cdots\times p _ m^{f _ m}$ とします。予想1. の帰結より、 $X^{k}$ がサイクルに含まれる条件は、全ての $i(1\le i \le m)$ が存在して $ke _ i \ge f _ i$ となることです。よって、テールの長さは $\min _ {1\le i\le m}(\lceil f _ i / e _ i\rceil)$ になります。

サイクルの性質

サイクルの長さを $C$ とします。サイクルの中の任意の数 $A$ について、 $AX^{C}\equiv A\bmod M$ です。よって、このサイクルの単位元「のようなもの」は $X^{C}$ です。「のようなもの」という表現は、 $X^{C}$ がこのサイクルの中に含まれていないことがあるためです（例： $\bmod 40, X = 14$ のとき、 $C=2, X^{C}=36$ となりますが、これはサイクルに含まれません）。しかし、 $X$ をかけていくといつかはサイクルの中に入ることと、 $X^{tC}$ もまた $AX^{tC}\equiv A\bmod M$ を満たすので、サイクルの中から単位元を見つけることができます。実装上はどちらでも問題ないです。 $X^{C}$ の方が計算量は少ないですが、サイクルの中の要素で演算を閉じさせたいという場合はそのような要素を探すこともできます。

そして、「 $X$ を掛ける」という操作の逆演算、つまり、サイクルの進む向きとは逆に進む操作を考えることができます。これが $X'$ を掛けることによって実現するとしましょう。言い換えると、サイクル内の任意の数 $A$ について $AXX'\equiv A\bmod M$ が成り立ちます。先程の単位元「のようなもの」を考えたときの式から推察できることとして、たとえば $XX'\equiv X^{C}\bmod M$ 、すなわち $X'\equiv X^{C-1}$ とするといつでもこの等式が成り立ちます。この $X'$ を逆元「のようなもの」と呼び、 $X^{-1}$ と表記します。

別の方法でこの $X^{-1}$ を求める方法があります。単位元「のようなもの」を $e$ とします。満たすべき等式は $XX'\equiv e\bmod M$ です。ところで、競技プログラミングでおなじみのmod逆元というものがありますが、大きく2通りの求め方がありました。ひとつはフェルマーの小定理を使って求めるもの、もうひとつは拡張ユークリッドの互除法を使って求めるもの、です。 $X^{C-1}$ で求めた方法はフェルマーの小定理的です。実は、拡張ユークリッドの互除法によって $X^{-1}$ を求めることができます。

等式 $ax \equiv b\bmod m$ を満たす整数 $x$ が存在する条件として、 $b\% \mathrm{gcd}(a, m) = 0$ です。今回の場合、 $e\% \mathrm{gcd}(X, M) = 0$ です。予想1. の証明で出てきた $P$ を用いると、 $\mathrm{gcd}(e, m)$ は $P$ または $X^{C}$ に等しく、どちらも $\mathrm{gcd}(X, M)$ で割り切れます。よって、 $X^{-1}$ の存在が保証されたと同時に、拡張ユークリッドの互除法で $X^{-1}$ を求めることができることがわかりました。

実装

実装方針

以上のことをまとめると、実装方針は次のようになります。

入力: $M, X, Y$ : 整数 $(M\ge 1, 0\le X, Y\lt M)$

出力: $X^{K}\equiv Y\bmod M$ を満たす最小の非負整数 $K$ （存在しなければ $-1$ ）

$X = 0$ のとき、別で処理する。
$X$ を素因数分解する。 $X = p _ 1^{e _ 1}\times p _ 2^{e _ 2}\times\cdots\times p _ m^{e _ m}$ とする。
全ての $1\le i\le m$ について、 $M$ が $p _ i$ で最大 $f _ i$ 回割り切れるとして、 $ke _ i \le f _ i$ となる最小の $k$ を求める。この $k$ がテールの長さで、 $tail$ とおく。
$0\le i \lt tail$ について、 $X^{i}\equiv Y\bmod M$ となる $i$ があれば、 $i$ を返して終了。
$bas = X^{tail}$ とする。もし $Y$ が $\mathrm{gcd}(bas, M)$ で割り切れなければ、 $-1$ を返して終了。
サイクルの長さが $\varphi(M)$ の約数であることから、 $bas \times X^{C}\equiv bas\bmod M$ である最小の約数 $C$ をさがす。この $C$ がサイクルの長さである。
以下、サイクル内の要素でBSGS。