楕円曲線論はじめの一歩 (11)

今回のおはなし

みなさんこんにちは。

VIPPOOL でエンジニアをやっています、星月です。

前回までで、楕円曲線上にある 1 つか 2 つの有理点から、
異なる有理点を見つける、という作業についてみてきました。

今回は、その作業についてもう少し詳しく考えてみましょう。

「新たな点を見つける」という演算

与えられた楕円曲線と、2 つの有理点から、異なる有理点を導き出す操作。

りんごが 1 個（点 P）と、別のりんごが 1 個（点 Q）から、りんごが 2 個ある状態（点 S）を導き出すのと
まったく同じ構図であることに、気づいたでしょうか？

そう、P と Q から S を求める。これもまた、足し算と同じ「演算」と呼べるのです。

点と点を足し算する演算、つまり「群」であるわけです。

群であることを確かめてみましょう。

演算が閉じている

線を引いて交点を求めるので、演算については閉じていることがわかります。
もちろん、無限遠点を含めれば、の話ですが。

結合法則

これを証明するのは少々大変なので省略しますが、
結合法則も実はちゃんと満たします。

単位元は無限遠点

無限遠点と楕円曲線上の点との足し算は、元の点のままになります。

逆元は x 軸に対して対称な点

前回お話した通り、( x, y ) と ( x, -y ) を足すと無限遠点になります。

つまり、点 P ( x, y ) と点 -P ( x, -y ) の足し算は単位元になるわけで、
( x, y ) と ( x, -y ) は逆元の関係にあることがわかります。

可換群である

2 つの点を通る直線を引く、という操作から始まるので、
どちらがどちらでも結果は変わらないことはお分かりと思います。

つまり、この群は可換群といえます。

まとめ

いかがでしたでしょうか。
楕円曲線上の有理点について調べると、
実は可換群であったことがわかりました。

今回はここまで。
ご質問、ご意見等ありましたらお気軽にリプライください。

楕円曲線論はじめの一歩 (10)

今回のおはなし

みなさんこんにちは。

VIPPOOL でエンジニアをやっています、星月です。

前回は、楕円曲線と直線が 2 点で交わる場合について見てみました。
実はもう 1 パターン、2 点でしか交わらないケースがあるので、
今回はそちらについて見てみましょう。

垂直線になる場合

f:id:y-hoshizuki:20181225193558p:plain

これはつまり、( x, y ) と ( x, -y ) が与えられた場合ですね。
この場合は完全な垂直線を引くことになり、2 点でしか交わりません。

そこで、「無限遠点」という概念を持ってきます。

f:id:y-hoshizuki:20181225193614p:plain

グラフの上の方（下の方でもいいですが）には、「全ての垂直線と交わる点がある」と考えます。

少し突飛な考え方ですね。

地球儀の、北極点を想像してみてください。
北極点は、地球上の全ての経度線と交わっていますね。
そんな感じです。

二次元のグラフで見ていると少し滅茶苦茶に見えますが、
実は射影平面という考え方を導入して三次元で見ると実在する点なのです。

射影平面

ここで、楕円曲線の定義を思い出してみましょう。

y^2=x^3+ax+b

ここで、今は有理点、つまり x と y が有理数である点について考えているので、
有理数は 2 つの整数を使って \frac{X}{Z} と表すことができるため、

\frac{Y}{Z}^2=\frac{X}{Z}^3+a\frac{X}{Z}+b

と書くことが出来ます。大文字で書いた X, Y, Z は全て整数です。

両辺に Z^3 をかけてやると、

Y^2Z=X^3+aXZ^2+bZ^3

となります。どの項も、X, Y, Z をあわせると 3 次の項になっていることがお分かりでしょうか？
a と b は楕円曲線を定義するパラメータで、定数なので次数にはカウントしません。

このように、全ての項の次数が同じ方程式のことを、同次式と呼びます。

変数が 3 つに増えたので、三次元のグラフを想像してみましょう。

f:id:y-hoshizuki:20181225193627p:plain

このように、3 次元の空間でみると、Z=1 のところでスライスした断面図が、
今まで見てきた楕円曲線のグラフであることは、数式からわかると思います。

次元が 1 つあがっているので、楕円曲線上の点は、この空間内での線（実際には「整数」に限定してるので点線）
になり、楕円曲線自体は面（整数に限定してるのでメッシュ状の面）に対応していることになります。

2 つの点を結ぶ直線も面に対応しているので、楕円曲線の面と重なっている曲線が、交点を表すことになります。

では無限遠点はどこに対応するのでしょうか？

f:id:y-hoshizuki:20181225193642p:plain

それはここ。Z=0 の平面です。

グラフ上でどの垂直線をとっても、この三次元空間で見ると Z=0 の面と交差していることにします。

というわけで、二次元では描けない点が実は存在している、ということで
理解しておいていただければと思います。

ちなみに、無限遠点は \mathbb{O} と表記することが多いようです。

まとめ

今回は、楕円曲線と直線が 3 点で交わらないケースの最後の 1 パターンについて見てみました。
射影平面という概念を導入することで、無限遠点というものを手に入れました。

今回はここまで。
ご質問、ご意見等ありましたらお気軽にリプライください。

楕円曲線論はじめの一歩 (9)

今回のおはなし

みなさんこんにちは。

VIPPOOL でエンジニアをやっています、星月です。

前回、「楕円曲線に交わるように直線を引くと、その直線は必ず 3 箇所で交わります」と書きましたが、
実際には例外があります。

今回はその例外について見ていきましょう。

楕円曲線と接する場合

f:id:y-hoshizuki:20181225193413p:plain

楕円曲線に直線を重ねると、この図のように接線となる場合があります。
その場合は、2 点でしか交わりません。

このような場合は、3 点で交わっている状態から連続的に変化させていき、その極限を考えます。

f:id:y-hoshizuki:20181225193426p:plain

P-P'-Q の直線は 3 点で交わっています。
これを少しずつ、Q の位置を変えずに上にずらしていきます。

すると、P と P' はどんどん近づいていって、あるとき P'' の 1 点に集約されます。

つまり、接線となっている点は、その点で 2 回、交わってる状態と「連続」しているわけです。
要するに、接線の部分で 2 回交わっているとカウントするわけですね。

中学校で二次方程式の解を求める時に、「重解は 2 回交わっているものとみなす」と習いました。
あれと同じです。

数式で考えるともう少し明白です。

前回、2 点 P = ( x1, y1 ) と Q = ( x2, y2 ) から有理点 S を求める式をお見せしました。

x_3=(\frac{y_2-y_1}{x_2-x_1})^2-x_1-x_2
y_3=\frac{y_2-y_1}{x_2-x_1}(x_1-x_3)-y_1

ここで、\lim_{x_2 \to x_1} を考えます。
x2 が変化すると y2 もあわせて変化していくことに注意して極限を求めると、

x_3=(\frac{3x_1^2+a}{2y_1})^2-2x_1
y_3=\frac{3x_1^2+a}{2y_1}(x_1-x_3)-y_1

が得られます。今回も詳細な計算は省略します。

式の形はだいぶ違いますが、傾きを表している

\frac{y_2-y_1}{x_2-x_1}

が、

\frac{3x_1^2+a}{2y_1}

に変わっているだけです。

直線を連続的に移動させて点 P と点 P' が極限まで近づいて点 P'' になる。
これを数式で考えるとこうなる、というお話です。

接する場合を考えると何ができるか

さて、以上の考え方を逆にすれば、
「楕円曲線上に有理点が 1 個があれば、そこに接線を引くことで別の有理点が見つかる」
ということになります。

P と P' から S を発見できるのであれば、P'' と P'' からも S を発見できるというわけです。

前回は有理点が 2 個から別の点を見つけましたが、実は 1 個でもあれば見つけられる、
というお話です。

まとめ

今回は、楕円曲線と直線が 3 点で交わらないケースについて見てみました。
実はもう 1 パターンあるのですが、それについては次回、触れることにしましょう。

今回はここまで。
ご質問、ご意見等ありましたらお気軽にリプライください。

楕円曲線論はじめの一歩 (8)

今回のおはなし

みなさんこんにちは。

VIPPOOL でエンジニアをやっています、星月です。

前回まで、代数論の基礎を簡単になぞりました。
そして今回からみなさんお待ちかね、楕円曲線の話をはじめようと思います。

そもそも楕円曲線とは

楕円曲線って何でしょう？

楕円曲線とは、y^2=x^3+ax+b こんな形をした方程式のことです。

a, b は係数で、x と y が変数です。
この方程式の解をグラフにするとこんな感じになります。

f:id:y-hoshizuki:20181225193049p:plain

f:id:y-hoshizuki:20181225193102p:plain

え、どのあたりが楕円かって？...名前のことは気にしない方がいいです。
いろいろな歴史的事情でこう呼ばれているだけで、これが楕円曲線なんです。

詳しく知りたい方は、楕円積分について調べるといいですが、
あまりオススメはしません...

天下り的で申し訳ないですが、こればかりは、「こういうもの」として
覚えていただければと思います。

楕円曲線上の有理点

さて、問題です。

ある楕円曲線が与えられたとき、その楕円曲線に含まれる有理点、
つまり x, y 座標それぞれが有理数となる点はどれだけあるでしょうか？

まったく存在しない？それとも有限個？もしくは無限に存在する？

...実はこの問題は未解決問題の 1 つで、未だに回答は出ていません。
残念。

楕円曲線上の有理点を探す問題

未解決の問題について考えても仕方ないので、
とりあえず、さらに条件を加えます。

ある楕円曲線と、「その楕円曲線上の有理点が 2 つ与えられたとき」、
他の有理点を探すことはできるでしょうか？

f:id:y-hoshizuki:20181225193119p:plain

実は、楕円曲線に交わるように直線を引くと、その直線は必ず 3 箇所で交わります。
実際には例外があって 2 箇所になる場合もありますが、とりあえず後回しにします。

この交点を左から順に P, Q, R としましょう。
P と Q が有理点であれば、R も有理点になることは計算すればわかります。

これだけだと、3 つ目を見つけて終了してしまいますので、さらにもう 1 つみつけましょう。

f:id:y-hoshizuki:20181225193205p:plain

R を通る垂直線との交点、つまり、R の y 座標を反転させた点 S も有理点となります。
( x, y ) が有理点なら、 ( x, -y ) も有理点、という話です。

さて、これで 4 つ目が出てきました。ここで、直線 SP や直線 SQ を引くと、
さらにたくさん有理点が見つかりそうですね。

点 S を導き出せるのは非常に重要そうです。

さて、ここで、つまり有理点は無限に存在するんだ！と思ったあなた、残念早とちり。
これを繰り返したときに、既知の点以外である保証がないので、
無限に存在するとは限りません。つまり、どこかでループする可能性があるのです。

ともあれ、2 つの有理点から、別の有理点を見つける方法があることはわかっていただけたと思います。

実際に計算してみる

有理点 P の座標 ( x1, y1 ) と、有理点 Q の座標 ( x2, y2 ) から、新たな有理点 S の座標 ( x3, y3 )
を求めてみましょう。

詳しい計算については他のサイトを参照してもらうことにしてここでは答えだけ。

x_3=(\frac{y_2-y_1}{x_2-x_1})^2-x_1-x_2
y_3=\frac{y_2-y_1}{x_2-x_1}(x_1-x_3)-y_1

と、なります。x1, x2, y1, y2 すべて有理数ならば、x3, y3 も有理数になることがおわかりでしょうか？

有理点 2 つから、新たな有理点が得られることが、数式からも見て取れます。

まとめ

今回からようやく楕円曲線の話に入りました。
話題の焦点は「楕円曲線上で、x と y がともに有理数となる点」つまり「有理点」です。
これを突き詰めていくと面白いことがたくさんあります。

今回はここまで。
ご質問、ご意見等ありましたらお気軽にリプライください。

楕円曲線論はじめの一歩 (7)

今回のおはなし

みなさんこんにちは。

VIPPOOL でエンジニアをやっています、星月です。

前回は「他にどんなものが『体』となるか？」から「有限体」について語りました。
今回はもう 1 つ、「体」となるものを紹介しようと思います。

数直線

みなさん「数直線」って覚えていますか？

f:id:y-hoshizuki:20181225192636p:plain

直線上の点を実数に対応させて図にするアレです。

例えば、3 はここです。

f:id:y-hoshizuki:20181225192649p:plain

これを使うと、数値が視覚的に見れて便利、という優れものです。

数直線上に存在しない点

さて、ここでとある方程式を持ってきます。

x^2+1=0

この左辺には、最小多項式、原始多項式という名前がついていますが、
今は覚えなくても大丈夫です。

この方程式の解となる値はどこでしょう？

二次方程式の判別式を覚えている方はすぐにわかると思いますが、
この方程式には実数の解は「存在しません」。

そのため、数直線上の点には対応しません。

でももし仮にそんな値が存在するとしたら？と考えると、いろいろ面白いことがわかります。
それが、「拡大体」という概念への入り口となります。

とりあえず方程式の解が存在するとして、数直線の図に、無理やり点を作りましょう。
数直線上は全部実数に対応しているので、
その外に、対応する点をおきます。0 の真上が都合がいいので、そこにおきます。

f:id:y-hoshizuki:20181225192659p:plain

そんな適当においていいの？と思われそうですが、
重要なのは 0～1 を結ぶ直線と、0～解 を結ぶ直線とが
「0 で直交しているところ」がポイントです。

これにより、ユークリッド幾何学の概念を取り込むことができるから便利なのですが、
今はそこに詳しく触れる必要は特にないので、忘れてしまっても大丈夫です。

呼び方がないと不便なので、「虚数単位」「i」と呼びます。
電気回路を扱う人は、電流 i と見分けをつけるためにあえて j と呼んでいるようですが、
ここは数学の人たちの流儀に合わせて i を使っていきます。

数直線から複素平面へ

さて、今、実数と対応付けられた数直線１本と、虚数単位の点があります。

新しく加わった虚数単位 i と、いろいろな実数 x, y を使って
x+yi で表すことのできる値を「複素数」と呼びますが、
その複素数全体のそれぞれに対応する点はどこでしょう？

f:id:y-hoshizuki:20181225192713p:plain

この図の水色で表した「平面」全体が複素数全体のそれぞれに対応付けられる点となります。
これが複素平面、別名、ガウス平面です。

逆に見れば、この平面内のどの点も、虚数単位 i と実数 x, y を使って
x+yi で表すことができる複素数と対応付けられています。

f:id:y-hoshizuki:20181225192732p:plain

例えば、3+2i はここの点と対応づけられます。

存在しない値を追加して線を面にする

数直線から複素平面を作ったように、元々実数として含まれていなかったはずの点を
追加することで面を作る。ということができます。

実数は元々「体」ですが、こうやって作った x+yi の集合、複素数も、「体」となります。

f:id:y-hoshizuki:20181225192745p:plain

この新しく作った体を「拡大体」と呼び、今回のように、実数に x^2+1=0 の解を追加して
作った拡大体を特別に「複素数体」と呼んでいます。

複素数の足し算と複素平面

複素数は実は「体」の用件を満たす、ということは足し算ができます。
(3+2i)+(2+2i)=5+4i

これを複素平面で見てみましょう。

f:id:y-hoshizuki:20181225192758p:plain

このように、0 の点（原点）からの矢印をつなげていくことで、
複素数の足し算ができます。

小学校で数直線を習ったとき、数直線での足し算、やりましたよね？
それと同じことができるという話です。

まとめ

解の存在しない方程式を用意して、その解が仮に存在することとして追加することで、
１次元だった数直線を平面に拡大する、というやり方です。

既知の体から、拡大体を作る方法についてお話しました。
そしてその一例が、複素数体となります。

今回はここまで。
ご質問、ご意見等ありましたらお気軽にリプライください。

楕円曲線論はじめの一歩 (6)

今回のおはなし

みなさんこんにちは。

VIPPOOL でエンジニアをやっています、星月です。

前回は掛け算（割り算）を抽象化した概念、「体」について説明しました。
そして、「実数」は「体」の条件を満たしてることを確認しました。
今回は、他にどんなものが「体」と呼べるのか、みていこうと思います。

自然数は？

自然数とは、1 2 3 4... のことですね。流派によっては 0 も含みます。
自然数は足し算について、逆元（マイナス元）が存在しないので、
体の条件を満たしていません。

なら整数は？

それでは自然数にマイナスも含めた整数ではどうでしょう？

確かに、足し算は可換群となっています。
しかし、掛け算に対して、逆元が存在しないので、体の条件を満たしていません。

例えば、3 の掛け算に対する逆元は \frac{1}{3} で整数ではありません。

有限巡回群に掛け算を導入する

有限巡回群 \mathbb{Z}/7\mathbb{Z} の足し算はこう定義していました。

(x + y) \bmod 7

これと同じように掛け算も定義してみます。

(x \times y) \bmod 7

実はこうすると、体の条件を満たすようになります。

確認してみましょう。

まず、足し算が群であることは確認しました。

足し算は可換でしょうか？実は足し算を定義する式を見れば一目瞭然で、
(x + y) \bmod 7 = (y + x) \bmod 7
なので、左右を入れ替えても結果は同じことがわかります。
つまり、足し算に対しては可換群であります。

次に、掛け算について、0 以外が可換群であるか確認してみましょう。

掛け算の定義で mod 7 しているので、掛け算の結果は必ず 0 ～ 6 の間に含まれます。
つまり、掛け算に対して“閉じて”います。

結合法則を確認するのは少々手間なので細かいところは省きますが、ざっくりと、
(((x \times y) \bmod 7) \times z) \bmod 7 = (x \times ( (y \times z) \bmod 7)) \bmod 7
が成り立つので、結合法則は成り立つといえます。

掛け算に対する単位元は 1 ですね。

逆元ですが、以下のようになっています。

元 逆元 元×逆元 mod 7
1 1 1 1
2 4 8 1
3 5 15 1
4 2 8 1
5 3 15 1
6 6 36 1

全ての元に対して逆元が存在していますね。

掛け算に対して可換かどうか。
(x \times y) \bmod 7 = (y \times x) \bmod 7
左右を入れ替えても同じ結果になることがわかると思います。

0 の掛け算についても、結合法則を満たすし、可換なのは明白だと思います。

最後に分配法則。これも細かいとこをまで見るときりがないので、ざっくりと
(x \times ( (y + z) \bmod 7) = ( ( (x \times y) \bmod 7) + ( (x \times z) \bmod 7)) \bmod 7
が成り立つので、分配法則も成り立ちます。

以上より、\mathbb{Z}/7\mathbb{Z} は、掛け算を
(x \times y) \bmod 7
と定義することで、「体」と呼べることが確認できました。

実はこれは別の名前がついていまして、有限体、もしくはガロア体と呼ばれています。
\mathbb{F}_7 もしくは GF(7) と書いたりもします。

7 以外の数字でも有限体になるのでしょうか？

答えは No。例えば mod 12 の有限巡回群に同じ掛け算を定義しても、
元 6 に対する逆元は存在しないため、「体」の条件を満たしません。

実は、mod の後ろ側、7 にあたる部分が“素数”であれば「体」の条件を満たして「有限体」となる。
ということがわかっています。そのため、素数を使って作った有限体のことを
総称して、素数 prime の頭文字をとって \mathbb{F}_p とか GF(p) と書きます。

暗号の世界ではよく「素数」を使いますが、それは「有限体」を作るために必要なんです。

まとめ

今回は、体の条件を満たすものについて触れました。

メインディッシュの「有限体」は、暗号の世界では非常に重要な概念ですので、
よーく覚えておいてくださいね。

今回はここまで。
ご質問、ご意見等ありましたらお気軽にリプライください。

楕円曲線論はじめの一歩 (5)

今回のおはなし

みなさんこんにちは。

VIPPOOL でエンジニアをやっています、星月です。

前回まで、ずっと足し算の話をしてきました。
じゃあ、掛け算と割り算はどうなんでしょう？というのが今回のテーマです。

「掛け算（割り算）」と呼んでもいい条件

掛け算ついても、過去の偉い人たちが散々検討を重ねた結果、
「これを満たせば『掛け算』と呼んで差し支えないだろう」
という条件が決まっています。

「足し算」が存在する

掛け算というのは、それ単体で存在するものではなく、
足し算がある上に、さらに追加の演算として存在するものである。

というわけです。つまり、足し算ができる上で、さらに追加で別の演算ができるときに、
その追加の演算を「掛け算」と呼ぶわけです。

足し算は可換群の性質を持つ

「可換」とは、「左と右を入れ替えても結果が変わらない」という性質のことです。

1 + 2 = 2 + 1

つまり、足し算が群であるだけでなく、
追加で「左と右を入れ替えても同じ結果になる」という性質を備えている必要があります。

掛け算は 0 以外に対して可換群の性質を持つ

ここまでは、要するに「掛け算が存在するためには『足し算』が要る。それは可換群である。」という話でした。

掛け算の本質はここからです。

足し算の可換群の元から 0 を除くと、掛け算に対しても可換群の性質を持ちます。

つまり、こういうことです。

f:id:y-hoshizuki:20181225192008p:plain

「群」とは足し算を抽象化したものである。と説明してきましたが、
実は掛け算も、本質的な性質としては、似たようなものとして説明できてしまうわけです。
これ、結構面白くないですか？

足し算と異なるのは、0 を含まないという点と、つながっている順番（構造）が
異なるというところだけです。

つまり、足し算ができて、足し算とは構造の違う演算がもう一種類定義されたとき、
それを掛け算と呼んでいるわけです。

0 の掛け算は結合法則が成り立って可換である

結合法則が成り立つ。つまり、

(a * b) * c = a * (b * c)

このどこに 0 が入っても等号が成立します。また、可換である。つまり

0 * a = a * 0 = 0

となります。

「分配法則」が成り立つ

これは小学校で習いましたね。

3 \times (1+2) = 3 \times 1 + 3 \times 2

ということです。

具体例で見てみましょう

抽象的に説明してもピンと来ないと思うので、
具体的に、「実数」に対して考えてみましょう。

まず、実数には和と積、２種類の演算ができます。

次に、和については、可換群の要素を満たしています。

  1. 実数と実数の和は実数　→　演算について閉じている
  2. 和の順序を入れ替えても結果は同じ　→　結合法則を満たす
  3. 0 をいくら足しても結果は同じ　→　単位元（零元）は 0
  4. マイナスをつけた数との和は 0　→　逆元（マイナス元）が存在する
  5. 和の左右を入れ替えても結果は同じ　→　可換である

なお、掛け算の「単位元」「逆元」と混同しないように、
足し算の群の方は「零元」「マイナス元」と呼んだりします。

さらに、積についても、0 を除けば可換群の性質を満たします。

  1. 実数と実数の積は実数　→　演算について閉じている
  2. 積の順序を入れ替えても結果は同じ　→　結合法則を満たす
  3. 1 をいくらかけても結果は同じ　→　単位元は 1
  4. 逆数をかけると 1 になる　→　逆元が存在する
  5. 積の左右を入れ替えても結果は同じ　→　可換である

0 の掛け算に関しては、結合法則を満たすし、可換でありますね。

あとは、小学校で習ったとおり、分配法則も満たします。

以上から、実数は全ての条件を満たしていることがわかります。

つまり、これらの条件は、実数に対する和と積から、
極限まで具体性をそぎ落とした、「和と積についての本質的な性質」といえるわけです。

この、「和と積についての本質的な性質」を満たすもののことを「体」と呼びます。

まとめ

掛け算とは、足し算ができる上で、さらに別の演算が定義されている場合に、
それが特定の条件を満たしている場合の呼び名である、というお話でした。

そしてそれは、実数のように、普通に四則演算に使っているものから、
具体性を極限までそぎ落とした、「四則演算の本質」であるということでした。

今回はここまで。
ご質問、ご意見等ありましたらお気軽にリプライください。