冪剰余。x^y mod zみたいなやつ。python風に書くと(x**y)%z。 暗号とかで使うのだけれど、暗号で使うような場合は桁数がやばいので、お察しの通り絶望的に演算が遅い。

と、思ったら。 流石python、組み込み関数に冪剰余計算してくれる奴がありました。

>>> pow(123, 456, 789)
699

速い。結構速い。

ちなみに

>>> pow(3, 3)
27

みたいな感じで普通の冪乗にも使えます。

参考: 2. 組み込み関数 - Python 2.7ja1 documentation