概要
冪剰余 とは冪乗の剰余のことです。
例えば $ 4^{13} \bmod 497 $ を Ruby で計算すると
4 ** 13 % 497
# => 445
となります。
では $ 4^{1234567890} \bmod 497 $ は？
4 ** 1_234_567_890
# warning: in a**b, b may be too big
# => Infinity
4 ** 1_234_567_890 % 497
# warning: in a**b, b may be too big
# => NaN
$ 4^{1234567890} $ が巨大な整数となってしまうため計算できません 
こんなときでもあら不思議、Integer#pow を使うと……
4.pow(1_234_567_890)
# warning: in a**b, b may be too big
# => Infinity
4.pow(1_234_567_890, 497)
# => 190
求めることができるのだ 
なお Integer#pow で第 2 引数を与えることで冪剰余が計算できるようになったのは Ruby 2.5.0 からでした。
参考
-
Python の組み込み関数 pow()
- Python の pow() が巨大な数でも冪剰余を計算できたので Ruby ではどう実現できるかを調べた。