有效的方式来功率和红宝石

Question

我需要知道的权力和3个值的MOD值MOD，比如：

print 1_299_709 ** 1_300_751 % 104_729 

是没有任何红宝石宝石或计算该使用Ruby更快的方法？

Answer 1

这叫做modular exponentiation，在密码学中被大量使用。它很容易编写一个模幂算法，演示在上面列出的维基百科文章中。

您可以使用标准库的OpenSSL来实现自己的目标：

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