FPGA

今日も有限体計算の話が聞けて幸せだった。
自分の計算ではKaratsuba法を適応させることで
標数2のm次拡大体の4次拡大、s^2=s+1、t^2＝t+s、
1、s、t、st基底では通常16回の掛け算が必要になるものが
10回まで減らせる換算だけど、
すごくトリッキーな方法で9回まで減らせた。
加算に関しても同じ項を代入して使うことで20回に減らせた。
これは2次拡大を二回無理やり使う方法と同じ回数になることがわかったが、
そっちの方は複雑なのでこれを実装した。
まぁ時間にして1.8秒かかっていたものが自分の実装で1.4秒まで減らせて
加法、乗法ともに減らしたこちらの方法では1.3秒まで落とせた。
EtaPairingに関して言うと、Pairingの内部で4次拡大体の乗算を使わないので
最終べきに関してのみの高速化になり0.8秒くらいになった。
うん。これで残りは2のm次拡大体の高速化のみとなったが、
もはやBigIntegerを脱するしかないのか…