ABC335G - Discrete Logarithm Problems のメモ

# フェルマーの小定理

$p$ が素数で、$a$ が $p$ の倍数でない自然数のとき
```math
a^{p-1} \equiv 1 \pmod p
```
が成り立ちます。
$a$ が $p$ の倍数のときは、 $a^m \equiv 0 \pmod p  (mは任意の自然数)$ です。

# 位数
```math
a^{k} \equiv 1 \pmod p
```
が成り立つ最小の自然数 $k$ は $\mod p$ における $a$ の位数と呼ばれます。

$p-1$ を 位数 $k$ で割ったときの商を $q$, 余りを$ r ( 0 \leqq r < k) $ とすると、
```math
a^{p-1} = a^{qk+r}=(a^k)^q \cdot a^r \equiv 1^q \cdot a^r\equiv a^r\pmod p \\

```
より $a^{p-1} \equiv a^r \equiv 1 \pmod p$ となりますが、$r$ は位数$k$ より小さいので、位数の定義から$r$ が自然数 ($0<r<k$) であれば $a^r \not\equiv 1 \pmod p$ であり式を満たしません。そのため$r=0$ 、つまり$p-1$は$k$で割り切れる、逆に言うと、$k$ は$p-1$の約数でなければなりません。

ここで、$a$ の位数が$k$ のとき、$(a^{s})^k \equiv (a^k)^s \equiv 1^s \equiv 1 \pmod p (sは自然数)$ であるため、$a^1, a^2, \cdots , a^{k-1} \pmod p$ (これらは互いに相異なる) の位数は $k$ か $k$ の約数です。

# 位数の求め方
$p-1$ を素因数分解したら $p-1= p_1^{e_1} \cdot p_2^{e_2} \cdots p_n^{e_n}　(p_i は素数、e_i > 0)$ になるとします。$a$の位数$k$は$p-1$の約数だから $k= p_1^{k_1} \cdot p_2^{k_2} \cdots p_n^{k_n}　(0\le k_i \le e_i)$ の形で表せます。
$p-1=M$とおきます。まず$a^M\equiv 1 \pmod p$ は成立します。
ここで、$M/p_1,　M/p_1^2,　M/p_1^3 ,\cdots  $ について $a^{M/p_1^i}\equiv 1 \pmod p$ が成り立つか計算して確かめます。成り立たなくなるのは、$p_1$の指数が$k_1$より小さくなる場合です。
$a^{M/p_1^i}\equiv 1 \pmod p$ まで成り立ち、$a^{M/p_1^{i+1}}\not\equiv 1 \pmod p$ で成り立たなくなる場合、$k_1=e_1-i$ と指数が確定します。
これを $p_2, \cdots,p_n$ に繰り返せば 位数$k$が確定します。

# 具体例
$p=13$ で調べてみます。以下$\mod 13$ を省略します。

![108.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/547341/5f939a07-114b-9a93-6d01-24dc531025ce.jpeg)

$p-1=12=2^2\cdot 3$ と素因数分解できます。
$a^{12/2} =a^6\equiv 1$ となるのは$a=1,3,4,9,10,12$ の6つです。
残りの $a=2,5,6,7,8,11$ の位数は $2^2 \cdot 3^k$ の形になります。
$a^{12/4} = a^3 \equiv 1$となるのは $a=1,3,9$ です。そのため
$a=4,10,12$ は$2^1\cdot 3^k$, 
$a=1,3,9$ は $2^0 \cdot 3^k$ の形にないります。
続いて、$a^{12/3} =a^4\equiv 1$ となるのは$a=1,5,8,12$ の4つです。
$a=2,3,4,6,7,9,10,11$ は$3^k = 3^1$
$a=1,5,8,12$ は$3^k = 3^0$ となります。
以上から、1～12の位数はそれぞれ $1,12,3,6,4,12,12,4,3,6,12,2$ と決まります。

もう少し見てみると、$a^2$ の行に出てくる値 $1,4,9,3,12,10$ の位数は $\frac{12}{2}=6$ の約数になっていて、 
$a^3$ の行に出てくる値 $1,8,12,5$ の位数は $\frac{12}{3}=4$ の約数になっていて、
$a^4$ の行に出てくる値 $1,3,9$ の位数は $\frac{12}{4}=3$ の約数になっていて、
$a^6$ の行に出てくる値 $1,12$ の位数は $\frac{12}{6}=2$ の約数になっています。

$a^2$ の行に出てくる値 $1,4,9,3,12,10$ は、位数が6 の4,10 の列を縦方向に見たときにあらわれる値です。
$a^3$ の行に出てくる値 $1,8,12,5$ は、位数が4の5,8 の列を縦方向に見たときにあらわれる値です。
$a^4$ の行に出てくる値 $1,3,9$ は、位数が3の3,9 の列を縦方向に見たときにあらわれる値です。
$a^6$ の行に出てくる値 $1,12$ は、位数が2の12 の列を縦方向に見たときにあらわれる値です。

# 問題にもどって
$A_i^k\equiv A_j \pmod P$  となる $k$ が存在するかが問題となります。
$A_i \equiv 0 \pmod P$ の場合 $A_j \equiv 0 \pmod P$ であれば存在し、$A_j \not\equiv 0 \pmod P$ であれば存在しません。(問題の制約条件から$A_i \equiv 0 \pmod P$ は除外されているので、このケースは考えなくてよいです)

$A_i$ の位数が $P-1$の場合、$A_i^1, A_i^2, \cdots , A_i^{P-1} \pmod P$ に 1から$P-1$ までが1回ずつあらわれるため $A_j \not\equiv 0 \pmod P$ であれば条件を満たす $k$ が存在します。

$A_i$ の位数$k_i$ が $P-1$　より小さい場合、$A_i^1, A_i^2, \cdots , A_i^{P-1} \pmod P$ には$k_i$ 種類の値しか登場しません。$A_j$ がこの中に含まれるのであれば条件を満たす$k$が存在し、含まれない場合は存在しません。

$A_j$ が $A_i^1, A_i^2, \cdots , A_i^{P-1} \pmod P$ に含まれるための必要十分条件は、$A_j$ の位数$k_j$ が$k_i$ の約数であることです。

$P=13$の例でみたように、$A_i$ の位数が$k_i$ の約数である値は、$a^{\frac{P-1}{k_i}}$ の行に登場し、約数でない値はその行にありません。$a^{\frac{P-1}{k_i}}$ の行に登場する値のみが$A_i^1, A_i^2, \cdots , A_i^{P-1} \pmod P$ にあらわれます。

したがって、$A_j$の位数$k_j$ が $A_i$ の位数$k_i$ を割り切る場合にのみ
$A_i^k\equiv A_j \pmod P$  となる $k$ が存在することになります。