モンゴメリ・リダクションの実装。たいへんやらかしました。
いや、実装は正しいんですよ。問題は無駄な処理。
明日公開の話で終了、コードコミットは今日で終わり、の予定だったんだけども、これはちょっと許容できないな、と言うわけでゴリッと対処しました。
仕方がないので最終話にちょっと手を入れ最適化の話を追加。最終話のコードコミットはないはずだったんだけどなあ。
とはいえこのモンゴメリ・リダクションの最適化で中国剰余定理のありなしで3倍違うようになりました。理論値に近づいてホッとしています。
余談ですが一番効いたのがミラー・ラビンテスト。通常の実装とモンゴメリ・リダクション適用とでおおよそ10倍速だったのが最適化後は70倍速になりました。
モンゴメリ・リダクションの最適化だけでそこからさらに7倍……。
いや、モンゴメリ・リダクション適用で10倍速くなったんでいやっふーしたのが間違いだったんです。でも脳汁出ちゃうよね。10倍ですよ10倍。
今回の追加で追い脳汁出ましたけど、最初から出せよって話です。
さらに公開鍵計算においてもモンゴメリ・リダクション最適化前後で3倍違いました。
ホントやらかしですわね……orz