冪剰余

まだ実装中なんだけど、必要な部分は出来て動いたのでちょっとベンチマークを取ってみた。

(import (rnrs) (crypto) (math) (time))
(time (generate-key-pair RSA :size 1024 :prng (pseudo-random RC4)))

自宅のX60で2048bitの鍵を作るのは自殺行為なので1024bitで。っで、以下が結果。

$ sash test.scm

;;  (generate-key-pair RSA :size 1024 :prng (pseudo-random RC4))
;;  4.265625 real    4.188000 user    0.078000 sys

$ ./build/sash.exe -Llib -Lsitelib -Lext/crypto test.scm

;;  (generate-key-pair RSA :size 1024 :prng (pseudo-random RC4))
;;  0.953125 real    0.890000 user    0.046000 sys

下が開発版。4倍程度高速になっているのが分かる。これくらい高速なら実用に耐えるだろうか？まだJavaと比較すると2倍から3倍遅いが・・・(比較する対象が間違っているのかもしれないと思い始めてもいる。)

Javaの実装に習って、Miller Rabinテストの試行回数を1024bit以上の時は2回にしてメルセンヌ数をチェックする処理を試したんだけど、結果が返ってこなかった。多分ヤコビシンボルを探すのが遅いのだろう。さすがにそこまでC側で実装するべきか悩むところだ。(Lucus Lehmer法自体がBignumを直接操作しないと遅いのかもしれない。まぁ、後の課題にする。)

mod-exptの動作としては、まだ対称の数(x ^ e mod mのx)が偶数の場合の処理が未テストかつ多分動きがおかしいはず。テストを書きつつ動作を検証していかないと。