冪剰余実装中

単にメモリ割り当てを減らしただけでは鍵対生成に対して実用的なパフォーマンスが得られないことが分かったので(2048bitで5秒からかかる)、どこが遅いかを調査した。結果、素数テストを行っている手続きで使用されている冪剰余の計算が遅いことが判明。x^e mod mを計算する際のx, e, m全ての数が2048bitあった際に20秒かかるという脅威の遅さだった。(3GHz Core i7)

Javaは2048bitの鍵対生成でも同マシンで1秒以下の時間で作ってくる。篩とかあるけど、何より素数チェック、その中で使われている冪剰余が高速なのだと仮定して実装をチェック。素数チェックはTwitterでも呟いたけど、Miller Rabinテストが1024bitを超えると試行回数が2回で、その代わりメルセンヌ数のチェックが入っていた。冪剰余についてはColin PlumbのBignumライブラリを元にした高速な実装になっている。

現状Sagittariusでは冪剰余を求める際に単純なバイナリ法を使っている。普通に

(mod (expt x e) m)

とするよりは遥かに高速なのだが、数値がBignumになってくると計算の度にメモリ割り当てが入りあまり嬉しくない。(eは1bitずつ右シフトされるので、2048bitあると、32bit環境では単純計算で2000回以上の割り当てがexponent部分だけで発生する)。
上記の実装(とりあえずはJavaの)ではメモリ割り当てがかなり削られている。正確には数えていないが、最大でも20回行かない程度に抑えられそうである。

ならばやらないわけには行くまいと、とりあえずJavaから実装を移植したら嵌った。

問題になったのはJavaのBigIntegerは内部で持っているintの配列のオーダーがSagittariusとは逆順になっているのだ。理由は知らないんだけど、きっとその方が効率がいい場面が多いのだろう。もしくはPrimitiveな配列でさえサイズを取ることができるからなのかもしれない。なので、単純にJavaから実装を持ってくるのは失敗に終わった。

恐らく中で何をやっているのか理解してやれば逆順に対応するのも難しくはないのだろうが、高速なモントゴメリ法の実装自体に興味があるわけではないので、可能な限りその労力は避けたい(ものぐさ)。ということでオリジナルの実装を当たってみることにした。←いまここ