ruby - ruby で電源を入れて改造する効率的な方法

Question

次のような 3 つの値の累乗と mod の値を知る必要があります。

print 1_299_709 ** 1_300_751 % 104_729

ルビーの宝石やルビーを使用してこれを計算するより高速な方法はありましたか?

Answer 1

これは剰余累乗と呼ばれ、暗号化で頻繁に使用されます。剰余累乗アルゴリズムを作成するのはかなり簡単です。デモンストレーションは、上記のウィキペディアの記事にあります。

標準ライブラリ openssl を使用して、目標を達成できます。

require 'openssl'
1_299_709.to_bn.mod_exp(1_300_751, 104_729) # => 90827