Ruby

[Ruby] (巨大な整数でも) 冪剰余を求める


概要

冪剰余 とは冪乗の剰余のことです。

例えば $ 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} $ が巨大な整数となってしまうため計算できません :sob:

こんなときでもあら不思議、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

求めることができるのだ :tada:

なお Integer#pow で第 2 引数を与えることで冪剰余が計算できるようになったのは Ruby 2.5.0 からでした。


参考