Pebble Coding

ソフトウェアエンジニアによるIT関連技術や数学の備忘録

secp256k1における逆数計算

secp256k1における逆数つまり1/aの計算方法を解説します。
素数qに対して、 {a}^{q-2}が1/aとなります。
なぜなら {a}^{q-2} {a} = {a}^{q-1} = 1 \mod q
最後の等号は、フェルマーの小定理を使っています。

やることは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

でやったのと同じ手法で、計算すればよいだけです。

プライバシーポリシー

お問い合わせ

スポンサーリンク