10/9 PKU

2417 Discrete Logging

離散対数問題。整数B,N,P(Pは素数)が与えられたとき、B^L mod P = Nなる最小の整数Lを求めよ。

Pが2^31ぐらいあるので普通にやるとTLEするが、だいたいO(√P log P)ぐらいで計算できる方法がある。
P < xy なる整数x,yをとる。x+yができるだけ小さいのが望ましい。列1ではB^0, B^1, B^2, …, B^(x-1)を計算する。列2ではB^0, B^x, B^(2x), …, B^( (y-1)x )を計算する。どんなkに対しても、B^kはこの2つの列の適当な2つを選んで、その積を求めれば求まる。両方計算しておいて、片方の列のすべての要素に対してもう一つの列にぴったり合う(積がNになる)ものがあるかを確かめればよい。もう一つの列をソートしておくと、この操作はO(log(列の大きさ))でできる。列の大きさ(=x, y)はO(√P)にできるので、計算量はO(√P log P)ぐらいである。