Pebble Coding

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

secp256k1における体演算の最適化

secp256k1の体演算の最適化手法として、x,yが法素数q未満であることと256bit値の範囲内であることを用いて、
256bitサイズの値を9個の26bit値と1つの22bitの値(9*26+22=256bit)に分割する手法があります。
素数q=0x FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F

q未満の値のマスク値をビット表現すると、上位から
1111_1111_1111_1111_1111_1111_1111_1111 = 0x FFFFFFFF
1111_1111_1111_1111_1111_1111_1111_1111 = 0x FFFFFFFF
1111_1111_1111_1111_1111_1111_1111_1111 = 0x FFFFFFFF
1111_1111_1111_1111_1111_1111_1111_1111 = 0x FFFFFFFF
1111_1111_1111_1111_1111_1111_1111_1111 = 0x FFFFFFFF
1111_1111_1111_1111_1111_1111_1111_1111 = 0x FFFFFFFF
1111_1111_1111_1111_1111_1111_1111_1110 = 0x FFFFFFFE
1111_1111_1111_1111_1111_1100_0010_1111 = 0x FFFFFC2F
となり下位から26bitずつにわけ10個目を22ビットとします。
11_1111_1111_1111_1111_1111 = 0x 3FFFFF
11_1111_1111_1111_1111_1111_1111 = 0x 3FFFFFF
11_1111_1111_1111_1111_1111_1111 = 0x 3FFFFFF
11_1111_1111_1111_1111_1111_1111 = 0x 3FFFFFF
11_1111_1111_1111_1111_1111_1111 = 0x 3FFFFFF
11_1111_1111_1111_1111_1111_1111 = 0x 3FFFFFF
11_1111_1111_1111_1111_1111_1111 = 0x 3FFFFFF
11_1111_1111_1111_1111_1111_1111 = 0x 3FFFFFF
11_1111_1111_1111_1111_1011_1111 = 0x 3FFFFBF
11_1111_1111_1111_1100_0010_1111 = 0x 3FFFC2F

26ビットの値は変数としてuint32_tを使い、32ビットの値の範囲内の演算であれば、そのまま計算できます。
元は法素数倍してもmod qの世界では同一値ですから、10個の要素に同時に、これらのマスク値の倍数を加えても、
値としては同じということになります。

なお、32bitの要素を8個使って(32*8=256bit)表現するものも使います。