secp256k1における逆数つまり1/aの計算方法を解説します。
法素数qに対して、が1/aとなります。
なぜなら
最後の等号は、フェルマーの小定理を使っています。
やることはaをq-2回ベキ乗することです。
pythonでq-2を2進表現してみましょう。
>>> q = 2 ** 256 - 2 ** 32 - 2 ** 9 - 2** 8 - 2 ** 7 - 2 ** 6 - 2 ** 4 -1 115792089237316195423570985008687907853269984665640564039457584007908834671663 >>> print(q-2) 115792089237316195423570985008687907853269984665640564039457584007908834671661 >>> print(format(q-2, 'b')) 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111011111111111111111111110000101101
1が223個,1が22個,1が1個,1が2個,最後に1が2個という5つの1の連続領域に分かれています。 あとは、
secp256k1における平方剰余計算 - Pebble Coding
でやったのと同じ手法で、計算すればよいだけです。
