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

secp256k1における逆数つまり1/aの計算方法を解説します。 法素数qに対して、が1/aとなります。 なぜなら 最後の等号は、フェルマーの小定理を使っています。 やることはaをq-2回ベキ乗することです。 pythonでq-2を2進表現してみましょう。 >>> q = 2 ** 25…

平方剰余 http://nakano.math.gakushuin.ac.jp/~shin/html-files/Algebra_Introduction/2011/11.pdf について簡単に説明しておきます。 整数aと整数pを与えた時に の式を満たす解xは存在する場合と、存在しない場合があります。 解が存在する時、a は p を法…

secp256k1における平方剰余計算を考えてみます。 secp256k1の法素数 はこの形をみてわかる通り、なので、 この記事mod p での平方剰余を計算する(p mod 4 = 3の場合) - Pebble Coding で示したように、解は(存在する場合は) と書けます。 コンピュータで計算…

の素体上の有理点の数を調べます。 楕円曲線Eの有理点の数を#Eと書きます。 素数pを3で割って2余る場合は、有理点の数は無限遠点を含み、#E= p + 1 であることが知られています。 の場合の、有理点の数をpythonで調べた結果がこちらです。 p, p mod 3, #E 2,…

素体は体であり、元は{0, 1, ..., p-1}のp個あります。 素体という時、pは素数です。 体なので、加法と乗法について閉じているわけですが、乗法演算の部分のみを取り出した群のことを、 素体の乗法群と呼びと書きます。 この乗法群には加法の単位元0は含まれ…

群論における写像の定義メモ。 準同型写像、同型写像、自己同型写像。 写像というのはプログラムで考えると、引数を一つ入力として持ち、戻り値を一つ返す関数だとイメージすることができますが、 要するに関数f(x)のことです。 準同型写像 関数f(x)が f(x)f…