またmpn_sec_invertの話. いい感じの\(k, t\)を選ぶと速くできるが, （おそらく）最適なものが出た.
メルセンヌ素数2^{521}-1の逆元計算の速度比較 · GitHub
事前計算とループ内の計算のコストは, 事前計算で\(x^{2^{k}-1}\)を準備するので \((-1+k)M + (-1+k)S \) とループ内で\(519S + \frac{519-t}{k}M\) .
事前計算は工夫すればもう少し計算が減るけど一旦この式で算出してみる.
2乗は乗算より若干速いので重みとして0.8をかけてあげることにすると\(k=17, 18\)あたりで最小になる.
\(k=5\)あたりからコストがあまり変化しなくなるのと, 1回のmulModはけっこう速いので回数が減っても速くなったことに気付けない可能性がある.
ほんとうに若干の変化. もっと速くしたいならmulMod, sqrModの改善を頑張るしかない. mul, sqrはmpn_を使っているのでmodの改善になるかな.
