位数を求める
$ \bmod pにおいて、与えられた整数$ aに対して$ a^k \equiv 1 \pmod pとなる最小の正整数$ kを求めたい。
$ p-1を素因数分解する方法（前計算$ O(\sqrt p)、クエリ$ O(\log p)）
前計算: $ p-1を素因数分解し、素因数を求める。
1. $ k \leftarrow p - 1とする。
2. 各素因数$ qについて、$ q | kであり、$ a^{k/q}\equiv 1 \pmod pである間、$ k \leftarrow k / qとする。（条件が満たされている間繰り返す。）
また、$ p-1自体は大きいが、小さい素因数しか含まない場合は離散対数問題としてPohlig-Hellman法を使って解くこともできる。
$ p-1の最大の素因数を$ qとしたとき、計算量は$ \max\{O(q), O(\log^3 p)\}となる。
参考