3243 Clever Y
概要
x^y == k (mod Z)
となるyを求める.
解法
素因数分解と同じで離散対数問題を解くのは大変なんだけど,Hashtableを使うとO(√Z)で計算できるというのを初めて知った.
Baby-step Giant-stepアルゴリズムと言うらしい.
http://en.wikipedia.org/wiki/Baby-step_giant-step
数論ってすごいなあー
x^y == k (mod Z)
となるyを求める.
素因数分解と同じで離散対数問題を解くのは大変なんだけど,Hashtableを使うとO(√Z)で計算できるというのを初めて知った.
Baby-step Giant-stepアルゴリズムと言うらしい.
http://en.wikipedia.org/wiki/Baby-step_giant-step
数論ってすごいなあー