昨日の続き. mpn_sec_invertに勝ちたい. 02.04.2020 - ぺんぎんさんのおうち
\(p\)は全ビットが1なので, \(p-2\)を2進数で書くと\(p-2 = (111...01)_{2}\)
下位2ビット以外はすべてビットが立っているのでsliding window methodで上手いことやれそう.
本来のアルゴリズムと違って場合分けを考えなくてよい（すべてのビットが立っている）ので, w-sizeを\(k\)とすると\(x^{2^{k}-1}\)だけを事前計算で準備しておけばよい.
事前計算とループ内で発生するmulMod, sqrModの回数をなるべく小さくできるような\(k\)を選ぶ.
\(t := 519 \, mod \, k \), \(r\)の初期値を\(x^{2^{t}-1}\)としておけば\(k\)は519を割り切る必要はない. うまいこと調整する.
\(t < k\) なので \(x^{2^{k}-1}\)を計算する途中で\(x^{2^{t}-1}\)が出てくる.
sliding window methodを適用するとこんな感じ
input: x
output: x^{-1} mod p
b <- x^{2^{k}-1}
r <- x^{2^{t}-1}
for _ in range((519-t)/k):
r <- r^{2^{k}}
r <- r*b
r <- r^{4}
r <- r*x // 下位2ビット
return r
w-size 5ビットでそこそこの差をつけて勝利. メルセンヌ素数2^{521}-1の逆元計算の速度比較 · GitHub
だと思っていたら, mpn_sec_invertの引数nbcntをドキュメント推奨値にしていた（もっと小さい値でよい）のでフェアじゃなかった. 521*2に設定してやり直したら数usecの差で勝っていたのでまあよい.
6bitsにしてもあまり変わらない. 確認してないけど7bitsは無理そう.
