そういえば思い出しました。

> FFTでのかけ算、Montogomery Reductionでのmodulo計算などなど、
> 整数計算の高速化アルゴリズムなどが一つにまとまったライブラリが欲しい

[ruby-talk:77470]
http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/77470

によれば、LibTomMath というプロジェクトがあるんだとか。
  http://math.libtomcrypt.org/
必要なものは LibTomMath に含まれていそうです。

これの ruby ラッパを Feldt さんは公開しているのかしらん。