ECDSAの署名＋αから公開鍵を算出したい (7)

今日、会社に行ったので、日本語のMastering Bitcoinを読んでいた。
そうすると、気になる記述が。
「0x02は偶数で、0x03は奇数」と。

もちろん、2は偶数で3は奇数なのだが、そうではなく、Y座標が偶数の場合は0x02を、奇数の場合は0x03を、ということだ。
えー、楕円曲線のグラフと関係ないやん！

http://chimera.labs.oreilly.com/books/1234000001802/ch04.html#pubkey_compression

When calculating the elliptic curve in binary arithmetic on the finite field of prime order p, the y coordinate is either even or odd, which corresponds to the positive/negative sign as explained earlier.

わざわざ「in binary arithmetic on the finite field of prime order p」と書いてあるので、グラフ空間とは違うんだよ、といいたいのだろう。

---

で、このよくわからない空間は何だろうか？
調べても理解できないような気がするのだが、やっておかねばなるまい。

Mastering Bitcoinの日本語PDFでは「素数位数pの有限体上で二進数演算を用いて」(p.81)と書かれていたが、もちろん意味が分からない。

prime order p : 素数位数p
on the finite field : 有限体上
in binary arithmetic : 2進数演算を用いて

なのだろうが、分解したところでわからないものはわからない。

素数がprimeで、位数がorderらしい。
困ったときのwikipediaなのだけど、数学関係のwikipediaって、書いてあることが難しいよね...
湯桶読みかどうかすらわからんかったのだが、変換するときは「いすう」でよかった。

https://mathtrain.jp/isuu

う、うーん・・・。
よく出てくる「mod p」が現れたので安心しそうになったが、わからん。。。
こっちを先に見ましょう、というリンク先の方がよいか。

https://mathtrain.jp/primitive

これなら、例も載っているのでわかる(気になれる)。
n乗する数(r)と、剰余を求める法(p)の3つが登場人物で、rⁿのnをインクリメントしながらpの剰余を求めていき、剰余が1になるときのnが「法pに対するrの位数はn」という書き方をするようだ。

何の役に立つのかわからんが、重要らしい。

「法」というのがなんかわかりづらかったのだが、moduloのことらしい。
A mod n = Bだと、「法nに対する」みたいな感じらしい。

http://www.maitou.gr.jp/rsa/rsa09.php

言葉の使い方としては、こっちを読むとわかった気がする。
「10を法とする世界」みたいな、数字の世界観＝世界を表す法、のような感じ方でよさそうだ。
10を法とする場合、その世界には0～9の数字しかないので、9の次は0になってしまうのだ。
マリオブラザーズで、画面の右端を突き抜けると左端に出てくるのと同じだ(古い。。。)。

pを法としているので、この世界は0～p-1の範囲ですべてを表すことになる。
そういう世界になるように、mod pするのだ。

そして、たぶんpはprimeのpで、素数なのだろう。
mod pして、その結果が1になるということは、たとえばpが10なら、11とか21とか、そういう数字だ。
(X - 1) / p = k(kは整数)になり、X = rⁿのはずだから、(rⁿ - 1) / p = k。
例では、p=7, r=2, n=3だから、(2³ - 1) / 7 = (8 - 1) / 7 = 7/7 = 1。

原始根というものも関係するようだから、見ておこう。
さっきの結果から、pとnだけ使うようだ。
今度は、n¹～n^p-1を求めていく。

3¹ ---> 3 mod 7 = 3
3² ---> 9 mod 7 = 2
3³ ---> 27 mod 7 = 6
3⁴ --->  81 mod 7 = 4
3⁵ ---> 243 mod 7 = 5
3⁶ ---> 729 mod 7 = 1

このように、1～p-1が重複せずに現れることを「一巡する」と呼ぶようだ。

ここで思ったのは「さっきのr=2はどこに出てくるの？？」だ。
rは原始根ということになると思ったのだが、「3は7に対する原始根」と書かれている。
でも、法7に対する2の位数は3、ともある。

うぅ。。。

Y軸の正負が偶数/奇数に置き換えられるのは、このmod pすると重複しない値が出てくるということと関係していそうな気がする。
が、違うような気もする。

もっと心に余裕ができたら調べることにして、今回は「正負と偶数/奇数は対応してるんだよ」にとどめておこう。